RSA è un cifrario a chiave pubblica che permette di cifrare un messaggio attraverso un procedimento che sfrutta le proprietà dei numeri primi. Supponiamo di avere come corrispondenti i soliti Aldo e Biagio.

Alla pagina Cifrario RSA: demo un demo PhP permette di provare il cifrario per numeri inferiori a 200 e per fini puramente dimostrativi; nella pratica si usano numeri molto più grandi (almeno 512 bit, che corrispondono a 170 cifre decimali!!)

Aldo genera le sue chiavi pubbliche e private

• Aldo genera due numeri primi distinti p e q e li moltiplica tra di loro ottenendo il numero N che viene reso pubblico, mentre p e q devono restare segreti.
  • Esempio:

    p = 5; q = 11 p.q = 5.11 = 55

    N = 55

• Aldo calcola b che è la funzione di Eulero di n: b = Φ(n) = (p-1)*(q-1). Il numero b deve restare segreto.
  • Esempio:

    Φ(55) = (5 - 1).(11 - 1) = 4.10 = 40

    b = 40

• Aldo calcola il primo intero e che sia primo con b (non abbia divisori in comune, ovvero MCD(e, b) = 1). Il numero e è la seconda chiave pubblica.
  • Esempio:

    e = 2 -> MCD(2, 40) = 2 NO e = 3 -> MCD(3, 40) = 1 SI

    e = 3

• Aldo calcola il numero d inverso di e nell'aritmetica finita di ordine b, che è il più piccolo x per cui sia e.d mod b = 1; il numero d é la chiave per decifrare e deve restare segreto. Si potrebbe usare il metodo basato sulla funzione di Eulero ma per numeri grandi la complessità sarebbe proibitiva; molto più efficiente un'estensione del classico algoritmo di Euclide per l'MCD; qui a titolo esemplificativo usiamo un semplice metodo a tentativi:
  • Esempio:
    

    d = 2 -> 2.3 mod 40 = 6 NO d = 3 -> 3.3 mod 40 = 9 NO d = 4 -> 4.3 mod 40 = 12 NO ... d = 26 -> 26.3 mod 40 = 78 mod 40 = 38 NO d = 27 -> 27.3 mod 40 = 81 mod 40 = 1 SI

    d = 27

Biagio invia un messaggio ad Aldo

Per trasmettere un messaggio ad Aldo, Biagio lo scompone inizialmente in una sequenza di numeri (in precedenza ci si è accordati riguardo alla modalità di "traduzione"; potrebbero essere p.es. i codici ASCII dei singoli caratteri ma così il cifrario degenererebbe in un banale cifrario monoalfabetico): (m₁, m₂....m_r).

Quindi Biagio legge le chiavi pubbliche di Aldo N e e e trasmette i numeri m uno alla volta cifrandoli con la formula c=m^e mod n.

• Esempio: per trasmettere il numero 7, Biagio calcola c = m^e mod N = 7³ mod 55 = 343 mod 55 = 13; il numero da trasmettere è quindi 13.

Aldo decifra il messaggio cifrato di Biagio

Aldo usa per questo la chiave di decifrazione d, segreta, che permette di recuperare m grazie alla formula m = c^d mod N; infatti si dimostra che c^d mod N = m.

• Esempio: m = c^d mod n = 13²⁷ mod 55 = 7 (provare per credere!)

Riassumendo

Riassumiamo nella seguente tabella i numeri necessari al cifrario RSA

In effetti RSA, dati gli N possibili messaggi (numeri) da 0 a N-1, effettua una permutazione degli stessi, come si può verificare nella pagina RSA è una permutazione.

RSA e il teorema cinese del resto

RSA richiede di eseguire calcoli modulari con modulo pq che è un numero molto grande (a 1024 o 2048 bit oggi); con numero così grandi i tempi possono essere molto lunghi; un metodo che viene spesso usato per ridurre il tempo di esecuzione fa uso del teorema cinese del resto.

Fonti bibliografiche e collegamenti

• P.Ferragina, F.Luccio Crittografia - Principi Algoritmi Applicazioni Bollati Boringhieri 2001 pag.121
• What is the RSA cryptosystem?: una spiegazione sintetica di RSA, dal sito ufficiale RSA Security
• RSA Algorithm: una spiegazione molto esauriente e dettagliata del metodo (in inglese)