Prende il nome dai tre matematici che l'hanno proposta: Ridler, Shamir, Adleman
Si consideri un orologio con 12 ore sul quadrante. Le addizioni su questo orologio si compiono spostando la lancetta a partire dalle ore 0 e facendole compiere i passi corrispondenti ai numeri da sommare. Ad esempio la somma 4+9 si ottiene portando prima la lancetta sul 4 e poi, da qui, facendole toccare le successive 9 ore, la lancetta si ferma sul numero 1, cioè:
(9+4) modulo 12 = 1.
Si consideri un orologio con un numero primo p di ore sul quadrante. Se si sceglie un qualsiasi numero su questo quadrante e lo si eleva alla potenza p la lancetta ritorna nuovamente sullo stesso numero. Ad esempio su un orologio con 5 ore, svolgendo la potenza di 2 elevato a 5 si ottiene ancora 2.
Potenze di 2 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 210 |
| 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | |
Su un orologio di 5 ore | 2 | 4 | 3 | 1 | 2 | 4 | 3 | 1 | 2 | 4 |
Si calcolino le potenze di 3 su un orologio con 13 ore sul quadrante. La lancetta posizionata sul 3, rappresenta 31. Si trovano le seguenti potenze:
| 31 mod 13 = 3 | 32 mod 13 = 9 | 33 mod 13 = 1 | 34 mod 13 = 3 | 35 mod 13 = 9 | 36 mod 13 = 1 | 37 mod 13 = 3 | 38 mod 13 = 9 | 39 mod 13 = 1 | 310 mod 13 = 3 | 311 mod 13 = 9 | 312 mod 13 = 1 | 313 mod 13 = 3 |
La lancetta ritorna sul 3 dopo che il 3 è stato moltiplicato per sé stesso 13 volte.
Cioè:
xp (modulo p) = x
Si costruisca il seguente schema con Excel:
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | |
| 1 | Numero Ore | 13 | ||||||||||||
| 2 | base | 3 | ||||||||||||
| 3 | esponente | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
| 4 | potenza | =POTENZA($B2;B3) | ||||||||||||
| 5 | Lancetta | =RESTO(B4;$B1) |
Copiare le formule dell'intervallo B4:B5 nell'intervallo C4:N5
Modificando il numero di ore sul quadrante, nella cella B1, e la posizione iniziale della lancetta, nella cella B2, si può verificare la validità della regola trovata da Gauss: la lancetta ritorna nella posizione iniziale quando si esegue la potenza di grado uguale al numero di ore sul quadrante dell'orologio.
Si consideri un orologio con un numero qualsiasi N di ore sul quadrante. N si può esprimere come il prodotto di due numeri primi p e q, cioè N = p x q. Su questo orologio l'andamento ripetitivo, osservato sull'orologio con un numero primo di ore, si ritrova dopo (p-1)x(q-1) passaggi.
L'idea di criptare il numero di una carta di credito è basato su questo meccanismo: il cliente che vuole fare un acquisto tramite Internet riceve un numero (molto grande) dall'azienda che deve eseguire la transazione. Questo numero è scelto prendendo due numeri primi molto grandi (se ognuno è di 60 cifre il numero potrebbe anche essere di 120 cifre).
Il numero N è pubblico ma i due numeri primi p e q sono segreti. L'azienda comunica al cliente anche un secondo numero (pubblico): E. Il cliente inserisce il numero C della propria carta di credito ma, il programma, sulla rete invia il numero ottenuto dall'operazione CE (modulo N).
Un programma che intercetta questo risultato deve risalire a C. Le difficoltà sono almeno due: nell'operazione di moltiplicazione il numero di cifre del risultato aumenta ad ogni moltiplicazione (al massimo raddoppia) e quindi si verificano degli overflow (nel calcolatore ad orologio ciò non succede); inoltre bisogna trovare un numero C che moltiplicato E volte per sè stesso, su un calcolatore con N cifre, restituisce sè stesso. Questa operazione non è impossibile ma richiede un tempo enorme per giungere a termine. Anche provare ad elencare tutti i possibili valori di N è un'operazione molto lunga.
Per ritrovare il numero di partenza l'azienda che riceve il numero cifrato deve elevarlo ad un numero D (segreto).
L'uso della chiave pubblica per criptare è molto semplice. Si supponga che Alice deve comunicare con Bob. Questi non devono scambiarsi la chiave segreta condivisa (come nel caso dei sistemi a chiave simmetrica), Bob (il destinatario dei messaggi di Alice) possiede due chiavi - la chiave pubblica che ognuno (compreso l'intruso) può conoscere e una chiave privata che conosce solo Bob. Allo scopo di comunicare con Bob, Alice deve procurarsi prima la chiave pubblica di Bob. Alice, con questa chiave e mediante un algoritmo di criptografia pubblico (cioè tutti possono conoscerlo), cripta i suoi messaggi destinati a Bob. Bob riceve i messaggi criptati di Alice e, mediante la sua chiave privata e un algoritmo pubblico, decripta i messaggi di Alice. In questo modo Alice può mandare un messaggio segreto a Bob senza scambiarsi la chiave privata.
Dato un qualsiasi messaggio m, risulta che dB(eB(m)) = m, cioè codificando il messaggio m con la chiave pubblica di Bob (eB) e poi decodificando il testo così cifrato con la chiave privata (dB), si ottiene nuovamente il messaggio m. Anche scambiando l'ordine delle chiavi si ottiene lo stesso risultato, cioè: eB(dB(m)) = dB(eB(m)) = m.
La criptografia a chiave pubblica si basa su questa semplice osservazione. Un primo problema è che un intruso, sebbene intercetti i messaggi criptati di Alice senza capirne il contenuto, conosce la chiave pubblica di Bob e l'algoritmo di criptografia usato da Alice. Trudy può allora predisporre un attacco scegliendo il testo in chiaro, cioè applica l'algoritmo di criptografia di Alice e la chiave pubblica di Bob per criptare un messaggio di sua scelta. L'efficacia dell'algoritmo a chiave pubblica si basa sulla scelta delle chiavi: deve essere impossibile o almeno estremamente difficile in pratica, determinare la chiave privata di Bob o decifrare i messaggi di Alice verso Bob. Un secondo problema è che, siccome la chiave di criptografia di Bob è pubblica, chiunque può inviare un messaggio cifrato a Bob spacciandosi per Alice. Nel caso di una singola chiave segreta, il fatto che il mittente conosce la chiave segreta, implicitamente conferma al ricevitore l'identità del mittente. Nella criptografia a chiave pubblica questa certezza viene a mancare perchè chiunque può mandare un messaggio a Bob, usando la sua chiave pubblica. Sarà necessario ricorrere ad un Certificato per collegare un'entità (come Bob) ad una specifica chiave pubblica.
L'algoritmo RSA (le iniziali dei tre matematici che l'hanno creato: Ron Rivest, Adi Shamir, Leonard Adleman) è il principale algoritmo di criptografia a chiave pubblica. Si supponga che Bob voglia ricevere messaggi criptati. L'algoritmo RSA richiede due componenti:
scelta della chiave pubblica e della chiave privata;
algoritmo per criptare e decriptare.
Per costruire le chiavi Bob deve:
scegliere due numeri primi molto grandi, p e q. Quanto più grandi sono i valori tanto più difficile sarà violare la codifica, ma di conseguenza si allungheranno i tempi per la codifica e la decodifica. I laboratori RSA suggeriscono di usare valori tali che il prodotto p·q sia dell'ordine di 768 bit per usi personali e 1024 bit per usi industriali.
Calcolare n = p·q e z = (p-1)·(q-1).
Scegliere un numero e, minore di n, che non abbia fattori in comune con z, a parte 1. (In questo caso, e e z sono detti primi tra loro). Viene usata la lettera 'e' perchè il suo valore serve per criptare (encrypt).
Trovare un numero d, tale che e·d - 1 sia divisibile per z. Viene usata la lettera 'd' perchè il suo valore serve per decriptare (decrypt). Detto in altri termini, dato il valore e, si sceglie d in modo che il resto della divisione di e·d con z sia 1. (cioè e·d mod z =1).
La chiave pubblica di Bob è la coppia di numeri (n, e); la sua chiave privata è la coppia di numeri (n, d).
Le operazioni di codifica di Alice e quelle di decodifica di Bob avvengono come segue:
Il messaggio che Alice deve inviare a Bob, rappresentato da una configurazione di bit, corrisponde ad un numero m, tale che m < n. Per codificare, Alice calcola la potenza me, e poi calcola il resto della divisione tra me e n. Si ottiene così il valore criptato c, del messaggio in chiaro m che Alice spedisce, cioè:
c = me mod n
Per decriptare il messaggio cifrato c, bob calcola
m = cd mod n
che richiede l'uso della chiave segreta (n,d).
L'operazione di elevazione a potenza richiesta da RSA è piuttosto lenta, perchè richiede che la CPU esegua molte operazioni, prima di determinare il risultato. La criptografia a chiave simmetrica DES è molto più veloce. Di conseguenza, se Alice deve inviare un grosso volume di dati criptati a Bob, Alice sceglie la chiave segreta per codificare i dati e la comunica a Bob. Questa chiave è riferita come "chiave di sessione" ed è indicata con KS. Alice cripta la chiave segreta, che ha scelto, usando la chiave pubblica di Bob, cioè calcola c = (KS)e mod n. Bob riceve la chiave di sessione c criptata con l'algoritmo RSA e la decripta per ottenere la chiave i sessione KS. A questo punto Bob conosce la chiave di sessione che Alice userà per trasferire dati criptati.
La criptografia RSA sembra una magia. Come succede che il processo di decodifica di un messaggio criptato restituisce il messaggio originario? Nell'aritmetica dell'orologio, o aritmetica modulare, le operazioni di addizione, di moltiplicazione e di elevazione a potenza forniscono risultati in un intervallo pari al numero n di ore sul quadrante.
Cioè il risultato di ogni operazione è il resto della divisione per n.
Nella codifica RSA, un messaggio, rappresentato da un numero intero m, viene dato come esponente al valore della chiave pubblica, usando l'aritmetica modulo n per criptare. Per decriptare il testo cifrato c viene eseguita l'elevazione di d alla potenza c, usando ancora l'aritmetica modulo n.
Il risultato dell'operazione di criptografia seguito dall'operazione di decriptografia è (me)d. Si ha:
(me)d mod n = me·d mod n
Gauss osservò alcune proprietà dei numeri primi nell'aritmetica modulare. In particolare, se p e q sono primi, ed n = p·q, allora x·y mod n è equivalente a x(y mod (p-1)(q-1)) mod n. Applicando questa proprietà si ha:
(me)d mod n = m(ed mod (p-1)(q-1)) mod n
Ma ricordando che e e d sono stati scelti in modo che e·d - 1 sia esattamente divisibile per (p-1)·(q-1), o equivalentemente che e·d diviso per (p-1)·(q-1) dia resto 1, ovvero e·d mod (p-1)·(q-1) = 1. questo porta a:
(me)d mod n = m1 mod n = m
cioè:
(me)d mod n = m.Anche invertendo l'ordine delle potenze si ottiene ancora il messaggio originario.
(me)d mod n = m = (md)e mod n
La sicurezza di RSA si basa sul fatto che non esiste un metodo per trovare i fattori primi (p e q) di un numero, in questo caso n. Se qualcuno conoscesse p e q, allora dalla chiave pubblica e, potrebbe risalire alla chiave segreta d. La sicurezza non è garantita perchè non è stato mai dimostrato che è impossibile trovare i fattori primi di un numero in un modo diverso dal procedimento per tentativi.
scegliere due numeri p e q molto grandi; ad esempio p = 61 e q = 53;
Calcolare n = p·q = 3233. Questo valore determina il numero di bit che si possono codificare. Cioè il testo viene suddiviso in gruppi di k bit, tali che 2k < n. Con i valori dell'esempio, risulta k = 11 bit.
Calcolare z = (p-1)·(q-1) = 3120 e scomporlo in fattori: 3120 = 24·5·3·13.
Scegliere un numero e < z che non abbia fattori in comune con z.
e = 17 (e è l'iniziale di encrypt, cioè e è la chiave pubblica per criptare il messaggio da spedire sulla rete).
Trovare un numero intero d, tale che:
(e·d) mod z = 1 (d è l'iniziale di decrypt, cioè d è la chiave privata per decriptare il messaggio ricevuto).
Per la ricerca di d si può procedere nel seguente modo:
e·d = Q·z + R, dove Q è il quoziente ed R è il resto della divisione tra e·d e z. Quindi
Imponendo R=1 e assegnando, in successione, valori crescenti a Q fino a quando si ottiene un numero intero, si trova il valore da assegnare a d, in questo esempio risulta d=2753.
Il valore di e serve per criptare i gruppi di bit del messaggio, il valore di d serve per decriptare il testo cifrato.
La chiave pubblica è usata per criptare il testo. Se M è il messaggio, composto da k bit, il corrispondente testo cifrato è: y = M17 modulo 3233. La chiave privata è usata per decriptare il messaggio: y2753 modulo 3233 = x
La potenza di un numero si può esprimere come potenze di potenze. Ad esempio
23153 = (231·23152) =
= 231·(23126)2 =
= 231·((23113)2)2 =
= 231·(231·(2316)2)2)2 =
= 231·(231·((2313)2)2))2)2 =
= 231·({231·[(231·2312)2]2}2)2
Omettendo la dimostrazione, si perviene ad una regola pratica per calcolare la potenza di un numero.
Si esprima l'esponente in base 2, cioè: 53 = 110101.
L'algoritmo per calcolare la potenza di un numero è
Partendo dalla cifra binaria di sinistra, e iniziando assegnando alla potenza P il valore 1, quando si incontra
1: si eleva P al quadrato e si moltiplica per la base
0: si eleva P al quadrato.
La potenza P=23153 viene calcolata secondo i seguenti passi:
P = 1
si incontra b5 = 1 si calcola: P = P2 x base = 12x231 → P
si incontra b4 = 1 si calcola P = P2 x base = 2312x231 = 2313 → P
si incontra b3 = 0 si calcola P = P2 = 2316 → P
si incontra b2 = 1 si calcola P = P2 x base = 23112 x 231 = 23113 → P
si incontra b1 = 0 si calcola P = P2 = 23126 → P
si incontra b0 = 1 si calcola P = P2 x base = 23152x231 = 23153 → P
Le operazioni Modulo hanno le seguenti proprietà: (ved. Stefano Leonesi - Numeri e Crittografia su google libri.)
Il resto di un quadrato è uguale al quadrato dei resti: X2 mod N = (X mod N)2. Esempio:
132 mod 11 = 169 mod 11 = 4
(13 mod 11)2 = 22 = 4
Il resto di una somma è uguale alla somma dei resti: (X+Y) mod N = (X mod N) + (Y mod N)
Il resto di un prodotto è uguale al prodotto dei resti: (X·Y) mod N = (X mod N)·(Y mod N)
Si codifichi 231 con la chiave pubblica 3233:
Messaggio cifrato: 23117 (modulo 3233) = 2576 Messaggio decriptato: 25762753 (modulo 3233) = 231.
Sia 231 il messaggio da trasmettere. In un foglio di calcolo predisporre lo schema seguente:
Nell'intervallo B2:B6 e nell'intervallo H3:H14 si esprimono in binario i due numeri che costituiscono le chiavi. Al solo scopo di verifica, nelle corrispondenti celle di sinistra si inseriscono i pesi delle cifre binarie.
Nella cella B1 scrivere il messaggio da criptare: 231
| A | B | C | D | E | F | G | H | I | J | |
| 1 | pesi | 231 | elevato a 17 modulo | 3233 | ||||||
| 2 | 16 | 1 | =B1 | =C6 | elevato a | 2753 | modulo | 3233 | ||
| 3 | 8 | 0 | =RESTO(C2*C2;D1) | 2048 | 1 | =RESTO(F2;J2) | ||||
| 4 | 4 | 0 | =RESTO(C3*C3;D1) | 1024 | 0 | =SE(H4=1;RESTO(I3*I3*F$2;J$2);RESTO(I3*I3;J$2)) | ||||
| 5 | 2 | 0 | =RESTO(C4*C4;D1) | 512 | 1 | =SE(H5=1;RESTO(I4*I4*F$2;J$2);RESTO(I4*I4;J$2)) | ||||
| 6 | 1 | 1 | =RESTO(C5*C5*B1;D1) | Messaggio criptato | 256 | 0 | =SE(H6=1;RESTO(I5*I5*F$2;J$2);RESTO(I5*I5;J$2)) | |||
| 7 | 128 | 1 | =SE(H7=1;RESTO(I6*I6*F$2;J$2);RESTO(I6*I6;J$2)) | |||||||
| 8 | 64 | 1 | =SE(H8=1;RESTO(I7*I7*F$2;J$2);RESTO(I7*I7;J$2)) | |||||||
| 9 | 32 | 0 | =SE(H9=1;RESTO(I8*I8*F$2;J$2);RESTO(I8*I8;J$2)) | |||||||
| 10 | 16 | 0 | =SE(H10=1;RESTO(I9*I9*F$2;J$2);RESTO(I9*I9;J$2)) | |||||||
| 11 | 8 | 0 | =SE(H11=1;RESTO(I10*I10*F$2;J$2);RESTO(I10*I10;J$2)) | |||||||
| 12 | 4 | 0 | =SE(H12=1;RESTO(I11*I11*F$2;J$2);RESTO(I11*I11;J$2)) | |||||||
| 13 | 2 | 0 | =SE(H13=1;RESTO(I12*I12*F$2;J$2);RESTO(I12*I12;J$2)) | |||||||
| 14 | 1 | 1 | =SE(H14=1;RESTO(I13*I13*F$2;J$2);RESTO(I13*I13;J$2)) | |||||||
| 15 |
Nella cella I14 si trova il messaggio decriptato.
La formula per il calcolo della potenza inizia in corrispondenza del bit più significativo della chiave, assegnando al risultato il valore del messaggio da criptare o decriptare. Per ogni bit successivo, se è 1 si calcola il quadrato della cella soprastante, il risultato si moltiplica per la base e quindi se ne prende il resto della divisione per N. Se è 0, invece, si calcola il quadrato della cella soprastante, e quindi se ne prende il resto della divisione per N.