:: RSA ::
Torna alla pagina di Crittografia
Che cos'è
RSA è un cifrario asimmetrico, che basa la propria sicurezza sulla difficoltà della fattorizzazione di un numero n.
Generazione dei parametri
Si devono scegliere p e q, due numeri primi.
n = pq
φ(n) = (p-1)(q-1)
Scelgo un numero e con queste proprietà:
* e < φ(n)
* e coprimo con φ(n)
Scelgo un numero d tale che ed = 1 mod φ(n)
Chiave privata: n, d
Chiave pubblica: n, e
Crittografia: per crittografare un messaggio M, avendo a disposizione la chiave pubblica dell'utente, devo fare
C = Me mod n
Decrittografia: per decrittografare C, faccio:
M = Cd mod n
Dimostrazione
Il teorema di Eulero dice che aφ(n) = 1 mod n.
Un corollario dice che aφ(n)+1 = a mod n.
Adesso vediamo un po' i miei numeri e e d. Come ho scritto sopra, devo avere ed = 1 mod φ(n). Questo vuol dire che ed sono nella forma kφ(n) + 1.
Perché? Se ci pensate, il motivo è semplice: se ed è congruo a 1 in modulo φ(n), vuol dire che posso scrivere il numero ed come un multiplo di φ(n), il che sarebbe congruo a 0, a cui aggiungo 1. Ecco perché ed = kφ(n) + 1.
Il teorema di Eulero visto sopra (deriva dal teorema di Fermat) mi dice che aφ(n)+1 = a mod n. Prendiamo ora C = Me mod n. Come dicevo sopra, per decrittografare, faccio M = Cd mod n.
Sviluppiamo i conti:
M = Cd mod n = (Me)d mod n = Med mod n
Siccome sappiamo che ed = kφ(n) + 1, allora
Med mod n = Mkφ(n) + 1 = M
per via del teorema di Eulero visto sopra!
Sicurezza
Dobbiamo distinguere due tipi di sicurezza: una relativa alla chiave, l'altra relativa alla cifratura stessa
Sicurezza della chiave
Avere la chiave sicura vuol dire: se ho la chiave pubblica di un tizio, ovvero {e, n}, so ricavare la chiave privata, ovvero {d, n}?
La risposta è: sì, se sono in grado di fattorizzare n, ovvero trovare quei numeri p e q che so essere i fattori di n. Infatti, n = pq. Se so p e q, so anche dire quanto vale φ(n), che in questo caso è (p-1)(q-1). Se so quanto vale φ(n), so anche calcolare l'inverso di un numero in quel modulo, ovvero, so calcolare d a partire da e: se ed = 1 mod φ(n), vuol dire che e e d sono inversi moltiplicativi in modulo φ(n). L'inverso di un numero è quell'altro numero che, moltiplicato per il primo, mi dà il neutro dell'operazione. Il neutro della moltiplicazione è 1, quindi e e d sono inversi in modulo φ(n): e = d-1 mod φ(n).
Il problema, dentro qui, è che dato un numero n abbastanza grande, trovarne i fattori diventa una cosa molto ma molto lunga: siamo nell'ordine degli anni-macchina! Ovviamente, la potenza dei computer cresce di anno in anno, e ogni tanto si scoprono algoritmi un po' più efficienti per fattorizzare un numero, però, se devo crackare la chiave privata di un tizio, e ci metto 1 anno a scoprirla, che me ne faccio?
Sicurezza della cifratura
Qui la domanda è: se ho C, so ricavare M senza sapere la chiave?
La risposta è: BO! Nel senso che non si sa se ciò sia equivalente a fattorizzare n. Comunque non c'è ancora arrivato nessuno.
Ma ci sono anche altri attacchi, che ora vedremo.
Chosen Ciphertext Attack
Sono nello scenario chosen ciphertext, il che vuol dire che l'attaccante può farsi decifrare un testo a sua scelta.
Orbene: se M è il messaggio, l'attaccante si fa cifrare il messaggio C * xe, ed è in grado di ottenere la decifratura di M.
Infatti, decifrando C * xe avrei:
M = (C * xe^)'^d = Med*xed = M * x mod n
Quindi, avendo in mano Mx mod n, divido per x (ovvero moltiplico per x-1, e lo so fare perché conosco x e n) e ottengo M a partire dalla sua cifratura.
Common Modulus Attack
Se ci sono due persone, la cui chiave contiene lo STESSO n, e ad entrambe viene inviato lo STESSO messaggio M, allora un attaccante è in grado di risalire ad M senza avere la chiave, ma avendo solo i due messaggi cifrati C1 e C2.
Quello che ha in mano è:
C1 = Me1 mod n
C2 = Me2 mod n
dove C1 e C2 sono i cifrati mandati al primo e al secondo personaggio, rispettivamente, e e1 ed e2 sono la loro chiave pubblica: {e1, n}, {e2, n}. Abbiamo infatti detto qui sopra che siamo nel caso in cui due persone abbiano la stessa n.
Quindi, tramite l'algoritmo di Euclide esteso (è esteso l'algoritmo, non Euclide!) l'attaccante è in grado di calcolare due numeri r ed s che abbiano la seguente proprietà:
e1*r + e2*s = 1 mod n
Euclide esteso calcola ciò in un botto solo.
Con in mano questi valori, si fa poi:
C1r * C2s= (Me1)r * (Me2)s = Me1r + e2s'^ mod n = M'^1 = M mod n
Infatti, abbiamo detto sopra che e1*r + e2*s = 1 mod n.
Low Exponent Attack
Questo è invece il caso in cui diverse chiavi pubbliche hanno lo stesso valore e, e hanno le rispettive n prime tra di loro. Occorre poi che lo stesso messaggio M venga inviato ai vari utenti.
Utilizzando il teorema cinese del resto è possibile risolvere questo sistema:
x = C1 mod n1
x = C2 mod n2
x = C3 mod n3
x = M3 mod n1n2n3 => poi calcolo M = x1/3
Non sto qui a dimostrare perché funziona, perché dovrei conoscere il teorema cinese del resto, ma si dà il caso che non lo conosca:)
Informazioni parziali
La domanda è: guardando C, sono in grado di dire qualcosa su di M?
Ci sono due cose che sarebbe interessante sapere: se M è più lungo o più corto della metà di n (ricordo che comunque M < n), oppure se è pari o no.
Ebbene, è stato dimostrato che calcolare queste due cose, ovvero rispondere con un SI o con un NO alle domande qui sopra, è equivalente a invertire RSA, cioè fattorizzare n, quindi computazionalmente impossibile.
Attacchi ad implementazioni
Sono due attacchi particolari, che riguardano le implementazioni di RSA in hardware.
Il primo attacco è detto timing attack: se un attaccante è in grado di osservare quanto tempo ci mette un calcolatore di velocità nota a produrre i risultati quando calcola i vari valori di RSA, è in grado di risalire alla chiave privata.
Lo stesso avviene per il power attach: se l'attaccante è in grado di monitorare il consumo di corrente di un processore che calcola RSA (ricordando che per calcoli complessi l'uso di corrente sale), allora può risalire alla chiave privata.
Per proteggersi da ciò basta introdurre dei calcoli casuali qua e là per sbarellare le osservazioni.
Ottimizzazioni
Il calcolo xy mod z è molto ma molto oneroso, perché sia x che y sono numeroni. È il calcolo che si fa sia in crittografia che in decrittografia:
C = Me mod n
M = Cd mod n
Per velocizzare un po' le cose, ricordiamo la rappresentazione binaria di y:
y = y0*20 + y121 y222 + ... + yn2n
Infatti, ogni bit di un numero binario rappresenta una potenza di 2. Spero non ci siano dubbi riguardo a questo per gli studenti di informatica:D
Saltando a pié pari le dimostrazioni (le metto solo a richiesta, se no divento matto con apici e pedici) si può osservare che
xy = x elevato a y0*20 + y121 y222 + ... + yn2n
L'ottimizzazione left-to-right riconduce tutto ciò alla forma:
(xy0(xy1(xyn)2)2)2
L'ottimizzazione right-to-left invece riconduce il tutto alla forma:
(x)y0(x2)y1(x4)y2(x8)y3
A che serve tutto ciò? Se dovessi fare il calcolo xy mod z nel metodo intuitivo, farei x*x mod z un numero y di volte. Se y è un numero gigantesco, il tempo che ci metto è gigantesco, perché faccio un numero spropositato di operazioni.
Invece, col metodo left-to-right, se guardate bene vedete che il numero di operazioni che devo fare è lo stesso numero dei bit che compongono y. Quindi, se y è un numero di 512 bit, allora eseguo 512 operazioni, e non 2512! Con right-to-left il numero di operazioni che eseguo è polinomiale nella lunghezza in bit di y.
Ora, prendiamo un y di questa forma binaria: y = 1000000001.
Vuol dire che
y0 = 1
y1 = 0
y2 = 0
...
y9 = 1
Questo vuol dire che, quando vado ad utilizzare il metodo left-to-right o right-to-left, non solo faccio meno operazioni, ma posso vedere subito che diverse esponenti sono facili da calcolare, perché il relativo yn è 0! È un bel vantaggio!
Firma digitale
RSA può essere usato anche per la firma digitale.
Notiamo innanzitutto che c'è una sorta di "reversibilità" nell'algoritmo. Se, infatti, C = Me mod n, e per decrittare faccio M = Cd mod n, è anche vero che posso fare tranquillamente F = Md mod n, e decritto con M = Fe mod n.
Quello che accade è che uso la chiave privata per crittare M, e generare il valore di firma F. Il destinatario riceve F, e tramite la chiave pubblica è in grado di verificare che la firma corrisponda al messaggio.
Una delle condizioni è che M < n. Nel caso di messaggi lunghi, capita più che spesso che M > n, e non posso firmare direttamente.
L'alternativa 1 è quella di dividere il messaggio in tanti mi e crittarli singolarmente. Ma se il messaggio è lungo, gli mi diventano tanti, e già la crittografia RSA è lenta, e non si finisce più.
Quello che si fa in concreto è allora firmare con RSA l'hash del messaggio.
Calcolo di potenze con modulo
Premessa: magari è cosa nota, ma io non sapevo nulla di quello che tra poco vi rivelerò. Spero quindi di fare cosa gradita e che possa essere utile a qualcuno.
Può capitare di dover calcolare potenze del tipo 2053 mod 77, ed io durante l'esame non ricordandomi nulla di matematica del discreto ho tentato di risolvere il tutto con la calcolatrice, ovviamente con pessimi risultati.
Studiando (pazzesco!) a casa ho poi scoperto di questa proprietà dell'aritmetica modulare:
(a x b) mod n = ((a mod n) x (b mod n)) mod n
Come usarla nel nostro caso? Semplicemente immaginando 2053 come il prodotto di 2010 x 2010 x 2010 x 2010 x 2010 x 203. Così facendo possiamo facilmente calcolare che 2010 mod 77 = 1, 203 mod 77 = 69 e riportarci alla forma:
(1 x 1 x 1 x 1 x 1 x 69) mod 77 = 69 mod 77 = 69.
Infatti come mi conferma Maple 20^53 mod 77 = 69; ovviamente si possono scegliere le potenze che più ci aggradano (purchè in questo caso la loro somma faccia 53), semplificando ulteriormente i calcoli.
Torna alla pagina di Crittografia
