IL CODICE RSA

Il codice RSA permette di cifrare un messaggio attraverso un procedimento che richiede l'utilizzo dei numeri primi

• Si determini la prima chiave n, prodotto di p e q, due numeri primi molto elevati, tali che la fattorizzazione di n sia difficile o perlomeno n risulti una funzione unidirezionale rispetto al tempo d'uso del codice. N viene infatti resa pubblica.

Esempio: n=pq=5*7=35

• Si calcoli dunque il valore della funzione di Eulero in n: b=f(n)=(p-1)*(q-1) il cui valore rimane segreto; si scelga ancora un intero d tale che d e f(n) siano primi tra loro, infine il suo inverso h, ovvero il più piccolo x per cui (dx-1)/f(n) é un intero, il numero h é la seconda chiave, e viene reso pubblico, mentre d resta segreto.

Esempio:

• Per trasmettere il messaggio lo si traduce inizialmente in un vettore di numeri (in precedenza ci si è accordati riguardo alla modalità di 'traduzione'). Stabilita dunque la sequenza numerica m₁, m₂.m_r si trasmettono gli m uno alla volta.
  Il crittogramma corrispondente a m è allora c=m ^h mod n.

Esempio:

• La chiave di decifrazione è costituita dall'intero b, segreto, nella formula m=c^b mod n.

Esempio: m=c^b mod n=17²⁴mod 35=3

In sintesi:per cifrare un messaggio dunque il trasmettitore deve prendere le diverse cifre pubbliche del ricevente e costruire un messaggio cifrato, quest'ultimo a sua volta utilizza la parte segreta del suo codice per decifrarlo.

Il codice RSA viene considerato sicuro perchè, essendo la formula di decifrazione basata su f(n) calcolabile solo se a conoscenza di p e q, non esiste un algoritmo efficiente per scomporre n in p e q, perlomeno in tempi accettabili.

Potrebbe sorgere il dubbio che esista un modo di calcolare f(n) senza passare per p e q: questa ipotesi in effetti è verificabile ma ha lo stesso grado di complessità di fattorizzare n.