|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.CrittoRSA History
Hide minor edits - Show changes to output
Changed lines 15-16 from:
# [[#g6|Esempio pratico]] to:
# [[#g6|Calcolo di potenze con modulo]] Changed line 177 from:
to:
!!Calcolo di potenze con modulo
Added lines 15-16:
# [[#g6|Esempio pratico]] Changed line 42 from:
to:
Changed line 57 from:
to:
Changed line 129 from:
to:
Changed line 164 from:
to:
Added lines 175-185:
[[#g6]]
!!Calcolo di potenze
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 20'^53^' 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 20'^53^' come il prodotto di 20'^10^' x 20'^10^' x 20'^10^' x 20'^10^' x 20'^10^' x 20'^3^'. Così facendo possiamo facilmente calcolare che 20'^10^' mod 77 = 1, 20'^3^' 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.
Changed line 172 from:
Quello che si fa in concreto è allora '''firmare con RSA l'hash del messaggio'''. to:
Quello che si fa in concreto è allora '''firmare con RSA l'[[hash -> Uni.CrittoHash]] del messaggio'''.
Added lines 6-17:
>>left bgcolor=#f5f9fc width=215px border='2px solid #cccccc' padding=5px<<
%center%'''Indice'''
# [[#g0|Che cos'è]]
# [[#g1|Generazione dei parametri]]
# [[#g2|Dimostrazione]]
# [[#g3|Sicurezza]]
# [[#g4|Ottimizzazioni]]
# [[#g5|Firma digitale]]
>><<
[[#g0]] Added line 21:
Added line 40:
Added line 55:
Changed lines 127-128 from:
to:
Added line 162:
Added lines 145-155:
!!Firma digitale
RSA può essere usato anche per la firma digitale.
Notiamo innanzitutto che c'è una sorta di "reversibilità" nell'algoritmo. Se, infatti, '''C = M'^e^' mod n''', e per decrittare faccio '''M = C'^d^' mod n''', è anche vero che posso fare tranquillamente '''F = M'^d^' mod n''', e decritto con '''M = F'^e^' 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 '''m'_i_'''' e crittarli singolarmente. Ma se il messaggio è lungo, gli '''m'_i_'''' 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'''.
Added lines 4-5:
[[Torna alla pagina di Crittografia -> Crittografia]] Changed lines 110-146 from:
Per proteggersi da ciò basta introdurre dei calcoli casuali qua e là per sbarellare le osservazioni. to:
Per proteggersi da ciò basta introdurre dei calcoli casuali qua e là per sbarellare le osservazioni.
!!!Ottimizzazioni
Il calcolo '''x'^y^' 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 = M'^e^' mod n
M = C'^d^' mod n
Per velocizzare un po' le cose, ricordiamo la rappresentazione binaria di '''y''':
y = y'_0_'*2'^0^' + y'_1_'2'^1^' y'_2_'2'^2^' + ... + y'_n_'2'^n^'
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
x'^y^' = x elevato a y'_0_'*2'^0^' + y'_1_'2'^1^' y'_2_'2'^2^' + ... + y'_n_'2'^n^'
L'ottimizzazione '''left-to-right''' riconduce tutto ciò alla forma:
(x'^y0^'(x'^y1^'(x'^yn^')'^2^')'^2^')'^2^'
L'ottimizzazione '''right-to-left''' invece riconduce il tutto alla forma:
(x)'^y0^'(x'^2^')'^y1^'(x'^4^')'^y2^'(x'^8^')'^y3^'
A che serve tutto ciò? Se dovessi fare il calcolo '''x'^y^' 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 2'^512^'! 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
y'_0_' = 1
y'_1_' = 0
y'_2_' = 0
...
y'_9_' = 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 y'_n_' è 0! È un bel vantaggio!
[[Torna alla pagina di Crittografia -> Crittografia]]
Changed lines 52-108 from:
La risposta è: sì, sotto certe particolari circostanze to:
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 * x'^e^'''', ed è in grado di ottenere la decifratura di M.
Infatti, decifrando '''C * x'^e^'''' avrei:
M = (C * x'^e^)'^d^' = M'^ed^'*x'^ed^' = 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 è:
C'_1_' = M'^e1^' mod n
C'_2_' = M'^e2^' mod n
dove C'_1_' e C'_2_' 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:
C'_1_''^r^' * C'_2_''^s^'= (M'^e1^')'^r^' * (M'^e2^')'^s^' = M'^e1r + 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 = C'_1_' mod n'_1_'
x = C'_2_' mod n'_2_'
x = C'_3_' mod n'_3_'
x = M'^3^' mod n'_1_'n'_2_'n'_3_' => poi calcolo M = x'^1/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.
Added lines 1-52:
(:title RSA :)
%titolo%''':: RSA ::'''
!!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''' = M'^e^' mod n
Decrittografia: per decrittografare C, faccio:
M = C'^d^' 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 = M'^e^' mod n'''. Come dicevo sopra, per decrittografare, faccio '''M = C'^d^' mod n'''.\\
Sviluppiamo i conti:
M = C'^d^' mod n = (M'^e^')'^d^' mod n = M'^ed^' mod n
Siccome sappiamo che '''ed = kφ(n) + 1''', allora
M'^ed^' mod n = M'^kφ(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 è: sì, sotto certe particolari circostanze
|
|
