Come funziona il cifrario RSA

In questo articolo parleremo finalmente di come funziona il cifrario RSA.

C’erano una volta tre crittografi statunitensi. I loro nomi erano: Ronald Rivest, Adi Shamir e Leonard Adleman. Un bel giorno del 1977, Rivest, Shamir e Adleman decisero di pubblicare un articolo in cui spiegavano come comunicare a distanza e in modo cifrato (che è come dire “in un modo incomprensibile ad un eventuale hacker capace di intercettare la comunicazione”). E fu così che nacque l’RSA.

Alcune cose da conoscere prima di poter parlare dell’ RSA:

• Come calcolare il massimo comune divisore con il metodo di Euclide
• Come calcolare una “potenza (mod N)”
• Cosa è la “phi di Eulero”
• Cosa è “l’inverso (mod N)” di un numero
• L’ Algoritmo Euclideo Esteso

Per rendere il tutto più chiaro, abbiamo suddiviso l’articolo in cinque parti. Godetevi lo spettacolo!

Episodio I. Bob genera le due chiavi (pubblica e privata) dell’ RSA

• Bob sceglie due numeri primi P e Q.
• Bob calcola N = P x Q.
• Bob calcola la “phi” di Eulero di (P x Q). Il risultato è Phi(N) = (P – 1)(Q – 1) = N – P – Q + 1.
• Bob sceglie un numero E compreso tra 1 e Phi(N) e coprimo con Phi(N).
• Bob calcola “l’inverso (mod Phi(N))” di E usando l’Algoritmo Euclideo Esteso. Il risultato è un numero D compreso tra 1 e Phi(N).
• I numeri N ed E sono la chiave pubblica di Bob.
• I numeri P, Q e D sono la chiave privata di Bob.

Facciamo ora un esempio relativo all’Episodio I:

• Supponiamo che i due numeri primi scelti da Bob siano P = 23 e Q = 73.
• Bob calcola N = 23 x 73 = 1679. (Una nota: a volte il numero N è chiamato “modulo dell’RSA”)
• Bob calcola la “phi” di Eulero di 1679. Il risultato è Phi(1679) = 22 x 72 = 1584.
• Bob sceglie un numero E compreso tra 1 e 1584 e coprimo con 1584. Supponiamo che sia E = 5 il numero scelto da Bob. (Una nota: il numero E è chiamato spesso “esponente pubblico”).
• Bob calcola “l’inverso (mod 1584)” di 5 usando l’Algoritmo Euclideo Esteso. Il risultato è D = 317. (Una nota: il numero D è chiamato spesso “esponente privato”).
• I numeri N = 1679 ed E = 5 sono la chiave pubblica di Bob.
• I numeri P = 23, Q = 73 e D = 317 sono la chiave privata di Bob.

Episodio II. La chiave pubblica di Bob viene pubblicata su Internet

• Bob salva la chiave pubblica e quella privata su una pennetta USB.
• Bob si reca di persona presso una Certification Authority, ovvero un’azienda che è autorizzata per legge a pubblicare le chiavi pubbliche dell’ RSA su Internet.
• La Certification Authority controlla che Bob abbia generato correttamente le due chiavi (pubblica e privata).
• La Certification Authority controlla che le chiavi generate da Bob siano sicure, ovvero che sia difficilissimo risalire alla chiave privata conoscendo soltanto la chiave pubblica. In altre parole, la Certification Authority si mette nei panni di un eventuale hacker e prova a calcolare P, Q e D conoscendo soltanto N ed E.
• Se le chiavi di Bob superano i test di correttezza e di sicurezza (vedi i due punti precedenti), allora Bob riceve dalla Certification Authority un certificato (chiamato X.509) contenente tutti i dettagli relativi alla sua chiave privata.
• La Certification Authority pubblica il certificato di Bob su Internet.

Episodio III. Alice invia un messaggio cifrato a Bob

• Alice cerca su Internet il certificato con la chiave pubblica di Bob. In altre parole, Alice cerca i due numeri N ed E che Bob ha generato nell’Episodio I.
• Alice sceglie il messaggio da inviare a Bob. Il messaggio è un numero M compreso tra 1 e (N – 1).
• Alice calcola C = M^E (mod N).
• Alice invia il numero C a Bob.

Facciamo un esempio relativo all’Episodio III:

• Alice cerca su Internet il certificato X.509 con la chiave pubblica di Bob. Scopre così che N = 1679 ed E = 5.
• Alice sceglie un messaggio M compreso tra 1 e 1678. Supponiamo il messaggio di Alice sia M = 144.
• Alice calcola 144⁵ (mod 1679). Il risultato è C = 1428.
• Alice invia il numero 1428 a Bob.

Episodio IV. Bob decifra il messaggio di Alice

• Bob calcola C^D (mod N). Il risultato che ottiene Bob è uguale al messaggio M di Alice!

Facciamo un esempio relativo all’Episodio IV:

• Il messaggio cifrato che Bob ha ricevuto da Alice è C = 1428.
• (Ricordiamo che l’esponente privato di Bob è D = 317). Bob calcola 1428³¹⁷ (mod 1679). Il risultato è 144, ovvero il messaggio M di Alice!

Episodio V: un hacker di nome Oscar intercetta il messaggio cifrato e prova a decifrarlo.

• Per decifrare il messaggio cifrato (cioè C), Oscar deve calcolare C^D (mod N).
• Per calcolare C^D (mod N), Oscar deve scoprire quanto vale l’ esponente privato D.
• Per scoprire il valore di D, Oscar deve calcolare Phi(N) (questo perché D è “l’inverso (mod N)” dell’ esponente pubblico E).
• Per calcolare facilmente Phi(N), Oscar deve trovare due numeri primi P e Q tali che N = P x Q. Detto in altre parole, Oscar deve fattorizzare N.
• Siccome fattorizzare N è un problema difficile da risolvere (anche per un computer!), Oscar non è in grado di calcolare i due numeri P e Q che moltiplicati tra loro danno come risultato N. La segretezza della comunicazione tra Alice e Bob è salva!

Il nostro articolo sull’ RSA termina qui. Ovviamente non esitate a scrivere nei commenti se avete dubbi o domande. Buona crittografia! xD