RSA è il principale algoritmo crittografico su cui si fonda la crittografia asimmetrica e la maggior parte delle applicazioni moderne che includono la sicurezza informatica, soprattutto le applicazioni Web o più in generale le applicazioni di rete.

Principi di base

L’algoritmo RSA fu inventato nel 1977 da tre ingegneri del MIT, Ronald Rivest, Adi Shamir e Leonard Adleman – l’acronimo RSA deriva appunto dalle iniziali degli autori. Su RSA si basa la crittografia asimmetrica o a crittografia a chiave pubblica, che abbiamo introdotto in questo post. 

Spiegare come funziona l’algoritmo in maniera semplice non è affatto banale, in quanto si basa su principi matematici abbastanza complessi. Se volessimo fare un riassunto della matematica di base, potremmo partire dal seguente principio: dato un numero n, è molto difficile trovare i due numeri primi p e q che sono fattori di n. In base a tale principio, si può rendere pubblico il numero n senza timore che, a partire da n, si riescano a fattorizzare p e q, da cui dipende la chiave privata. Nella crittografia asimmetrica, infatti, esiste una chiava pubblica ed una chiave privata, che devono essere utilizzate in coppia per cifrare e decifrare il messaggio segreto. 

Algoritmo RSA

I passi dell’algoritmo crittografico RSA possono essere riassunti come segue:

1. Si scelgono p e q numeri primi grandi a piacere

2. Si calcola n=pq e z=(p−1)(q−1)

3. Si sceglie e<n|MCD(e,z)=1

4. Si trova d tale che edmodz=1 da cui segue che d=(km+1)/e

5. Si trovano la chiave pubblica K⁺ e la chiave privata K⁻:
   K⁺:coppia (e,n)
   
   K⁻:coppia (d,n)

6. Si cifra il messaggio ottenendo il messaggio cifrato c (operazione di encryption) con c=m^emodn

7. Si decifra il messaggio ottenendo il messaggio originale m (operazione di decryption) con m=c^dmodn.

Ad esempio, prova a fare questo esercizio. Dati p=7, q=13 ed e=11, scegliendo un k=9, quale sarà d? Si avrà che d=59. In questo modo abbiamo così calcolato la coppia di chiavi pubblica e privata.