Nel precedente capitolo abbiamo affrontato l’implementazione della crittografia a chiave privata, nota anche come crittografia simmetrica. Oggi faremo un passo avanti esplorando uno dei concetti più affascinanti e cruciali della sicurezza informatica: la crittografia a chiave pubblica (o asimmetrica).

In questo articolo vedremo la teoria alla base di questo sistema e inizieremo a scrivere il codice in C per generare le nostre chiavi.

Simmetrica vs Asimmetrica: Qual è la differenza?

La crittografia simmetrica utilizza una sola chiave sia per cifrare che per decifrare il messaggio. La crittografia a chiave pubblica, invece, utilizza due chiavi distinte:

• La Chiave Pubblica: Può essere conosciuta da tutti. Chiunque voglia inviare un messaggio sicuro a un destinatario, utilizzerà la chiave pubblica di quest’ultimo per crittografarlo.
• La Chiave Privata: Deve rimanere segreta ed essere posseduta solo dal destinatario. È l’unica chiave in grado di decrittografare il messaggio cifrato con la chiave pubblica corrispondente.

La sicurezza di questo sistema risiede nell’asimmetria: pur conoscendo la chiave pubblica, è praticamente impossibile risalire al messaggio in chiaro o alla chiave privata per decrittografarlo.

Il ruolo dei Numeri Primi e l’algoritmo RSA

Lo schema di crittografia più diffuso e che implementeremo è l’RSA (dai nomi dei suoi inventori Rivest, Shamir e Adleman). L’intero funzionamento di questo algoritmo si basa sulle proprietà dei numeri primi.

La sicurezza del metodo si fonda sull’estrema difficoltà di fattorizzare numeri giganteschi. Se da un lato è facile moltiplicare due numeri primi tra loro, dall’altro, dato il risultato (chiamato modulo “n”), è difficilissimo risalire ai due fattori primi originali se questi sono sufficientemente grandi.

• Nel mondo reale, l’algoritmo RSA utilizza numeri primi enormi, composti da 100 a 600 cifre.
• Per il nostro scopo didattico e per poter seguire i passaggi matematici “a mano”, scriveremo il codice utilizzando numeri primi molto piccoli.

La Matematica dietro le Chiavi

Il processo per generare le chiavi si divide in diverse fasi:

1. Scelta dei numeri primi (P e Q): Nel nostro esempio in C, inizializzeremo il programma con P = 13 e Q = 17.
2. Calcolo del Modulo (N): Il modulo è semplicemente il prodotto di P e Q. Nel nostro caso, 13 * 17 = 221. Questo numero farà parte sia della chiave pubblica che di quella privata.
3. La Funzione Toziente di Eulero (fn): Serve per trovare il numero di interi positivi minori di N che sono coprimi con N (cioè che non hanno divisori in comune eccetto 1). Quando N è il prodotto di due numeri primi, la formula è semplice: fn = (P - 1) * (Q - 1). Con i nostri numeri, il risultato è 192.
4. Scelta dell’esponente di crittografia (E): Questo valore deve essere maggiore di 1, strettamente minore della funzione toziente (fn) e coprimo con essa. Sarà parte integrante della nostra chiave pubblica.+1
5. Calcolo dell’esponente di decrittografia (D): Questo valore matematico completerà la nostra chiave privata.

Implementazione in C

Nel video sul canale abbiamo iniziato a tradurre questa teoria in codice C. Tra le operazioni principali che abbiamo implementato ci sono:

• Una funzione factorize che riceve un numero e restituisce un array con l’elenco dei suoi fattori primi.
• Una funzione is_prime per verificare se un numero è divisibile solo per uno e per se stesso.
• Delle funzioni per calcolare tutti i candidati validi per gli esponenti E e D.

Scegliendo, ad esempio, 37 come candidato per “E” , andiamo a comporre la nostra chiave pubblica (37 e 221).

Prossimi passi

In questa prima parte abbiamo gettato le basi matematiche e scritto il codice necessario a generare in sicurezza la chiave pubblica e la chiave privata. La generazione delle chiavi è il motore invisibile della crittografia.

Nella seconda parte del tutorial, che vedremo nel prossimo video, prenderemo queste chiavi e le utilizzeremo finalmente per crittografare e decrittografare stringhe di testo reali.