Cifrari a chiave pubblica -> Il cifrario RSA
Cifrario RSA: il metodo
La funzione di Eulero - Cifrario RSA: demo - RSA è una permutazione

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

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): (m1, m2....mr).

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

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 = cd mod N; infatti si dimostra che cd mod N = m.

Riassumendo

Riassumiamo nella seguente tabella i numeri necessari al cifrario RSA

UtenteParte pubblicaParte segreta
AldoNep, q [N = p*q]b = Φ(N)d
Esempio5535, 11 [55 = 5*11]40 = Φ(55)27

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

Valido HTML 4.01!