RSA  E CODICI SEGRETI

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 urgente a Harry, per salvarlo: Lucius Malfoy vuole, infatti, raggiungere Harry per farlo diventare una statua di marmo!

Dividiamo l'intero procedimento in 3 parti.

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 PHI(primo p) = p-1 e che PHI(primo p ∙ primo q) = PHI(p) ∙ PHI(q)]:  

  esempio: PHI(55) = PHI(5) ∙ PHI(11) = (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.

1. scrive il suo messaggio in chiaro;

 esempio: messaggio in chiaro = SCAPPA

2. applica il codice di Cesare con chiave +3;

          esempio: messaggio pre-cifrato con il cifrario di Cesare = VFDSSD

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

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

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

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

5. 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  

6. 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  

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

1. la chiave privata è I = 27, come visto nella 1a PARTE. Ora, 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  

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

      esempio: la stringa ottenuta è 22 6 4 19 19 4 

3. Harry applica il cifrario di Cesare e... SCAPPA!

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.