RSA

Con l'avvento dei computer, capaci di eseguire in tempi record calcoli lunghissimi, decifrando all'istante questo tipo di codici, si è dovuto inventare qualcosa di completamente nuovo.

Nel 1977 i 3 matematici Ronald Rivest, Adi Shamir e Leonard Adleman idearono l'algoritmo di cifratura RSA (acronimo dei loro cognomi) che utilizza proprio la difficoltà di fattorizzare in numeri primi. Si tratta di un sistema a chiave pubblica: tutti possono conoscere la chiave di cifratura ma non quella necessaria per la decifratura. Il fatto che le 2 chiavi siano distinte e che non sia possibile dedurre l'una dall'altra è il vero e proprio successo di questo sistema. 

Vediamo in dettaglio come funziona il sistema RSA.

Immaginiamo che Ron voglia mandare un messaggio a Harry. 

Dividiamo l'intero procedimento in 3 parti.

1a PARTE Prima che Ron prepari il suo messaggio, Harry deve aver comunicato la propria chiave pubblica al registro di Tripotter che raccoglie tutte le chiavi pubbliche ed essersi prodotto la propria chiave privata, in questo modo:

1.  Harry sceglie 2 numeri primi p e q, possibilmente molto grandi (maggiori di 300 cifre), e li moltiplica: il loro prodotto K1 = p ∙ q è la 1a parte della chiave pubblica, cioè la chiave che può essere resa nota (solo K1 viene reso nota, non p e non q);     esempio con numeri contenuti: p = 5; q = 11; K1 = 5 ∙ 11 = 55  →  K1 = 55 

2.  quindi Harry compie alcune operazioni su K1  per produrre sia la 2a parte della chiave pubblica sia la sua chiave privata:

   1. 1. 1. 1. 1. 1. 1. 1. cerca, grazie alla funzione di Eulero, il numero PHI di numeri naturali compresi fra 1 e K1, coprimi con K1 (si dimostra che, nel caso dei numeri primi p, PHI = p-1);

  esempio: PHI(55) = (5-1) ∙ (11-1) = 4 ∙ 10 = 40  → PHI(55) = 40

2. 1. 1. 1. 1. 1. 1. 1. 2. cerca il 1° naturale K2 che non abbia divisori in comune con PHI: K2 è la 2a chiave pubblica

 esempio: K2 = 3 perché MCD(2,40) = 2 ≠ 1, mentre MCD(3,40)=1

2. 1. 1. 1. 1. 1. 1. 1. 3. calcola l'inverso I di K2 modulo PHI: I  sarà la chiave privata;

  esempio: I = 27 perché 27 ∙ 3 = 81 ≡ 1 mod 40 

3.  Harry rende pubblica la sua chiave (K1 ; K2) = (55 ; 3) che verrà inserita nell'elenco pubblico di tutte le chiavi pubbliche di Tripotter, abbinate a chi le ha generate; terrà segretissima, invece, la sua chiave privata I = 27.

2a PARTE Ora Ron può agire:

4.  Ron prepara il suo messaggio:

   1. 1. 1. 1. 1. 1. 1. 1. scrive il suo messaggio in chiaro;

 esempio: messaggio in chiaro = SCAPPA

4. 1. 1. 1. 1. 1. 1. 1. 2. sostituisce a ogni lettera del suo messaggio in chiaro un numero (secondo una corrispondenza concordata, magari usando un cifrario a sostituzione fra quelli noti);

          esempio: messaggio pre-cifrato con il cifrario di Cesare (chiave = +3) = VFDSSD

 messaggio pre-cifrato, in numeri = 22 6 4 19 19 4

4. 1. 1. 1. 1. 1. 1. 1. 3. Ron cerca nell'elenco delle chiavi pubbliche quella di Harry (K1 e K2); 

          esempio: (K1 ; K2) = (55 ; 3)

4. 1. 1. 1. 1. 1. 1. 1. 4. applica una formula dell'aritmetica modulare che coinvolge K1 e K2 al 1° numero m1 del suo messaggio, ottenendo così il suo 1° numero cifrato; precisamente: c1 = m1 ^ K2 mod K1;   esempio: 1° numero da cifrare: c1 = 33 perché 22^3 = 10 648 ≡ 33 mod 55  

                        5. ripete il procedimento per ogni altro numero del messaggio, in successione.

esempio: 2° numero da cifrare: c2= 51  perché 6^3 = 216 ≡ 51 mod 55  

      3° = 6° numero da cifrare: c3 = c6 = 9  perché 4^3 = 64 ≡ 9 mod 55  

      4° = 5° numero da cifrare: c4 = c5 = 39  perché 19^3 = 6 859 ≡ 39 mod 55  

5. Ron può affidare finalmente al suo gufo Errol il messaggio da recapitare a Harry:

    esempio: messaggio cifrato finale = c1c2c3c4c5c6 = 33 51 9 39 39 9

3a PARTE Ora tocca a Harry! Tenterà di decifrare il messaggio che Errol gli ha recapitato:

6. Harry userà la chiave privata I per decifrare il messaggio ricevuto da Errol e risalire così al messaggio in chiaro di Ron, utilizzando la formula inversa: m1 = c1 ^ I mod K1. 

    esempio: 1° numero da decifrare: m1 = 22 perché 33^27  ≡ 22 mod 55  

      2° numero da cifrare: m2 = 6  perché 51^27 ≡ 6 mod 55  

      3° = 6° numero da cifrare: m3 = m6 = 4  perché 9^27 ≡ 4 mod 55

      4° = 5° numero da cifrare: m4 = m5 = 19  perché 39^19 ≡ 19 mod 55  

      Quindi Harry riapplica il cifrario di Cesare con chiave = -3 e traduce...

Soltanto Harry potrà decifrarlo, nemmeno lo stesso Ron sarebbe in grado di decifrare il messaggio che lui stesso ha cifrato, senza la chiave I! Questo perché calcolare PHI senza conoscere p e q è tanto difficile quanto fattorizzare K2 nei suoi 2 fattori primi. 

Questo algoritmo è ancora oggi considerato inviolabile: si stima che per fattorizzare un numero a 500 cifre siano necessari circa 1025  anni, quanto si stima essere la vita dell'Universo. Ha, però, lo svantaggio di richiedere una procedura di calcolo piuttosto lunga per la cifratura. Per questo, si utilizzano anche altri algoritmi, a supporti di questo.