Ecco i passi dell'algoritmo RSA.
Partiamo da Alice.
Sceglie due numeri primi p e q, grandi.
Calcola n = pq.
Calcola φ(n) = (p-1)(q-1).
Sceglie un numero e>2 primo rispetto a φ(n), piccolo.
Calcola d tale che ed ≡ 1 mod φ(n).
Pubblica (n,e), nasconde (p,q,d).
Bob vuole scrivere un messaggio m ad Alice (m è un numero, con l'attenzione che m<n)
Calcola c = me mod n.
Spedisce c.
Alice vuole leggere il messaggio crittato c. Per farlo, esegue il seguente calcolo:
cd mod n =
(me)d mod n =
med mod n = [per definizione di d: ed ≡ 1 mod φ(n)]
m1+kφ(n) mod n =
m·mkφ(n) mod n =
m·(mφ(n))k mod n = [per il Teorema di Eulero: mφ(n) ≡ 1 mod n]
m mod n =
m.
[Mnemonica per ricordarsi come funziona il tutto: e sta per encrypt, d per decrypt, c per cyphertext]
“Piano, piano, c'è troppa roba…”.
“Facciamo un esempio? Con dei numeri veri?”.
“Magari”.
“Ok, anche se non li prendiamo di 150 cifre. Usiamo numeri più piccoli, per capire il funzionamento”.
“Va benissimo”.
“Allora, Alice prima di tutto sceglie due numeri primi p e q, ne calcola il prodotto n e la funzione toziente. Ti propongo p = 127 e q = 131; fai tu i calcoli?”.
“Ok, allora: n = 127·131 = 16637; φ(n) = (p-1)(q-1) = 16380. Mi ricordo bene?”.
“Tutto bene, dato che n è il prodotto di due numeri primi, abbiamo che φ(pq) = φ(p)φ(q). E la funzione toziente di un primo p è uguale a p-1”.
“Adesso?”.
“Adesso Alice deve scegliere un numero e primo rispetto a 16380. Ti propongo e = 11”.
“Ora dici che devo calcolare d in modo tale che ed sia congruente a 1 modulo 16380. Ma non so mica come si fa”.
“Allora, per prima cosa si scrive che ed = 1 + 16380k. Questo è un altro modo per scrivere che ed è congruente a 1, giusto?”.
“Giusto, ricordo: è la divisione di ed per 16380: k è il quoziente e 1 il resto. Poi come andiamo avanti?”.
“Scriviamo l'espressione in questo modo, ricordandoci che e = 11: 11d-16380k = 1. Questa si chiama equazione diofantea: è una equazione di primo grado in due incognite, per le quali accettiamo solo valori interi”.
“Ok, ma come si risolve?”.
“Si usa l'algoritmo di Euclide per il Massimo Comun Divisore. È come se dovessimo calcolare MCD(16380,11)”.
“Ma sappiamo già che è 1”.
“Sì, è vero, ma utilizziamo i calcoli dell'algoritmo di Euclide per semplificare l'espressione. Comincia a fare la divisione tra 16380 e 11”.
“Boh, non ho ben capito, ma provo: 16380 diviso 11 mi dà quoziente 1489 e resto 1”.
“Bene, quindi 16380 = 1489·11+1, giusto?”.
“Giusto”.
“Sostituisci allora nell'equazione iniziale 16380 con 1489·11+1”.
“Mi viene 11d - (1489·11 + 1)k = 1”.
“Bene. Ora risolvi la parentesi e raccogli il fattore 11 che compare due volte”.
“Ecco: 11(d - 1489k) - k = 1”.
“Ecco fatto, questa è un'altra equazione diofantea più semplice della precedente, perché ha dei coefficienti più bassi e, soprattutto, perché uno dei due coefficienti è uguale a 1”.
“E cosa ci faccio?”.
“La risolvi: la soluzione più semplice si ha quando il coefficiente di 11 è uguale a 1, e k = 10. In questo modo ti viene 11-10 = 1”.
“Ah, credo di capire. Quindi d-1489k = 1, e k = 10”.
“Esatto. Vai avanti, sostituisci k = 10 nella prima delle due equazioni”.
“Mi viene d = 14890+1 = 14891”.
“Ecco trovato il tuo d. Se vuoi fare una verifica, ed = 11·14891 = 163801, che è congruente a 1 modulo 16380”.
“Ho capito”.
“Quindi Alice pubblica la chiave (n,e) = (16637,11), e tiene segreti p,q e d. Anzi, dato che di p e q non se ne fa più di niente, può anche cancellarli. L'importante è che tenga segreto d = 14891”.
“Perfetto. Ora Bob deve codificare il messaggio m, ma deve essere per forza un numero?”.
“Sì, ma non c'è problema, se deve spedire un testo si mette d'accordo con Alice sul tipo di codifica da usare per trasformare lettere in numeri, ed è a posto”.
“E se Eva intercetta questa conversazione?”.
“Nessun problema, Eva può ascoltare tutto. Gli unici dati che Eva non deve assolutamente conoscere sono p, q e d, ma non vengono mai trasmessi. Ti faccio presente che non è necessario tenere Eva all'oscuro del metodo crittografico usato. Questo è un principio fondamentale della crittografia: si chiama principio di Kerckhoffs”.
“Cosa dice, questo principio?”.
“Dice che un sistema crittografico deve essere sicuro indipendentemente dal fatto che il metodo usato sia pubblico. Shannon lo riformulò con le seguenti parole: The enemy knows the system”.
“Bello, meno cose si devono tener segrete, più sicuro è il sistema”.
“Esatto. Anzi, se l'algoritmo è pubblico è meglio: gli studiosi possono analizzarlo e scoprire eventuali falle. Ora prendiamo un messaggio m: ti propongo m = 12345”.
“Provo a codificarlo: dovrei calcolare c = me mod n = 1234511 mod 16637 = 6900”.
“Bene, questo è il messaggio crittato che viagga lungo il canale di comunicazione non sicuro da Bob verso Alice”.
“Con Eva che ascolta”.
“Esattamente. Ora vediamo come fa Alice a decrittare: prova”.
“Dunque, vediamo: Alice riceve c = 6900, e deve calcolare cd mod n = 690014891 mod 16637 = 12345. Ehi, funziona!”.
“Certo che funziona, abbiamo dimostrato tutto”.
“Ma Eva non può fare lo stesso? Come mai non riesce a decrittare?”.
“Lo vediamo la prossima volta. Esercizio per casa: prova a craccare il seguente messaggio crittato:”.
Chiave pubblica (n,e) = (9017,251),
Messaggio cifrato c = 6543.
Nessun commento:
Posta un commento