Cifrario RSA: il metodo
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
1, m
2....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=me mod n.
- Esempio: per trasmettere il numero 7, Biagio calcola c = me mod N = 73 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.
Riassumendo
Riassumiamo nella seguente tabella i numeri necessari al cifrario RSA
| Utente | Parte pubblica | Parte segreta
|
|---|
| Aldo | N | e | p, q [N = p*q] | b = Φ(N) | d
|
| Esempio | 55 | 3 | 5, 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.
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)
