Attacco di Wiener ad RSA (tesi di laurea triennale in matematica)

Universit degli Studi di Trento

Facolt di Scienze Matematiche Fisiche e Naturali

Dipartimento di Matematica

Attacco di Wiener ad RSA

Elisa Signori

Relatore: Prof. Massimiliano Sala

Controrelatore: Prof. Andrea Caranti

Anno accademico 2012/2013

Universit degli Studi di Trento

Facolt di Scienze Matematiche Fisiche e Naturali

Dipartimento di Matematica

Attacco di Wiener ad RSA

Tesi di:

Elisa Signori

Relatore:

Prof. Massimiliano Sala

Controrelatore:

Prof. Andrea Caranti

Anno accademico 2012/2013

A Linda, che mi ha dato la carica per portare a termine

questo percorso, e a tutta la mia grande famiglia...

Ringraziamenti

Desidero ringraziare il prof. Sala, relatore di questa tesi, e Marco Calderini che

mi hanno costantemente guidata e supportata durante la stesura della stessa.

Ringrazio Simone e Linda per essermi stati pazientemente accanto durante questo

percorso ed Emanuela, Paolo e Lorenzo per l'incrollabile sostegno dimostratomi in

tutti questi anni.

Ringrazio inne gli innumerevoli amici che mi hanno tirato su il morale nei mo-

menti di sconforto e tutti i compagni di studi che, in vari modi, mi hanno saputo

aiutare.

Indice

Acknowledgment 1

Introduzione 1

1 Introduzione alla crittograa e preliminari 1

1.1 Cifrari a chiave pubblica e a chiave privata . . . . . . . . . . . . . . . 1

1.2 Numeri primi e funzione di Eulero . . . . . . . . . . . . . . . . . . . . 3

1.3 Teorema cinese dei resti . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Fattorizzazione in numeri primi . . . . . . . . . . . . . . . . . . . . . 9

2 Algoritmo RSA, requisiti di sicurezza e principali attacchi 11

2.1 Algoritmo RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Firma autenticata nell'RSA . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Requisiti generali per la sicurezza . . . . . . . . . . . . . . . . . . . . 17

2.4 Attacchi elementari dovuti a errata scelta del modulo . . . . . . . . . 19

2.5 Attacchi con esponente pubblico piccolo . . . . . . . . . . . . . . . . 19

2.5.1 Attacco di Hstad sulla trasmissione . . . . . . . . . . . . . . 20

2.5.2 Attacco di Franklin-Reiter sui messaggi correlati . . . . . . . . 22

2.5.3 Attacco di Coppersmith . . . . . . . . . . . . . . . . . . . . . 22

2.6 Attacchi all'esposizione parziale della chiave . . . . . . . . . . . . . . 23

2.6.1 Esposizione parziale della chiave con esponenti piccoli . . . . . 23

2.6.2 Esposizione parziale della chiave con esponenti medi . . . . . . 24

2.7 Attacchi con esponente privato piccolo . . . . . . . . . . . . . . . . . 24

3 Frazioni continue 25

4 Attacco di Wiener a RSA 29

4.1 Attacco di Wiener . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Algoritmo dell'attacco di Wiener passo per passo . . . . . . . . . . . 35

4.3 Esempio numerico di attacco di Wiener . . . . . . . . . . . . . . . . . 37

4.4 Come contrastare l'attacco di Wiener . . . . . . . . . . . . . . . . . . 39

4.4.1 Scelta di e grande . . . . . . . . . . . . . . . . . . . . . . . . . 39

i

4.4.2 Utilizzo del teorema cinese dei resti . . . . . . . . . . . . . . . 39

4.5 Miglioramenti dell'attacco di Wiener . . . . . . . . . . . . . . . . . . 40

Bibliograa 42

ii

Introduzione

Il crittosistema RSA [RSA78], che deve il nome ai suoi inventori Rivest, Shamir e

Adleman, fa parte dei crittosistemi cos detti a chiave pubblica, dove ad ogni utente

coinvolto nella comunicazione viene associata una coppia di chiavi, una pubblica ed

una privata.

Tale algoritmo stato ed ancora largamente utilizzato per proteggere dati digitali

e per garantirne l'autenticit (ad esempio pagamenti con carte di credito on-line, posta

elettronica certicata, ecc.). Nel corso degli anni, sono stati ideati vari attacchi ad

RSA ([Bon99]); tuttavia, il crittosistema non mai stato veramente compromesso a

livello pratico.

Per cifrare con il crittosistema RSA, il mittente utilizza due interi, l'esponente di

cifratura e e il modulo n (la coppia di valori (n, e) costituisce la chiave pubblica del

destinatario). Per decifrare, il destinatario sfrutta invece la cosiddetta chiave privata

composta dalla coppia di interi (n, d), dove n il modulo del sistema e d l'esponente

privato di decifratura (noto soltanto al destinatario). Tali parametri sono scelti in

modo tale che n sia il prodotto di due numeri primi segreti, p e q, e i valori e e d

soddisno la seguente equivalenza in modulo

e d 1 (mod (p 1)(q 1)).1

La sicurezza di RSA si basa sulla dicolt di fattorizzare numeri interi grandi in

fattori primi. Per rompere il sistema, necessario fattorizzare n (ovvero calcolare i

primi p e q); si pu dimostrare che tale problema equivalente a ricavare l'esponente

privato d. Per questo motivo scegliere opportunamente i vari parametri di fonda-

mentale importanza per la sicurezza del sistema.

In questo elaborato verr descritto in dettaglio RSA e verranno illustrati alcu-

ni attacchi ad esso; in particolare, si focalizzer l'attenzione sull'attacco di Wiener,

il quale permette di determinare l'esponente privato d, se scelto sotto una certa soglia.

In sintesi, vengono ora riportati gli argomenti presentati in questa tesi.

1

Si noti che, anch d esista, ci si deve assicurare che e e (p 1)(q 1) siano coprimi.

iii

Il Capitolo 1 tratter generalmente i sistemi crittograci a chiave pubblica e a

chiave privata. Esso conterr inoltre alcuni importanti teoremi e dezioni prelimina-

ri; servir anzitutto denire la relazione di congruenza e la funzione di Eulero (n).

Verr poi enunciato il teorema cinese dei resti e si tratter brevemente il problema

della fattorizzazione in numeri primi, su cui si basa la sicurezza di RSA.

Nel Capitolo 2 si passer a descrivere dettagliatamente l'algoritmo di RSA, siste-

ma crittograco a chiave pubblica; dopo averne illustrato un esempio, si vedr come

si pu facilmente ottenere una rma digitale per garantire l'autenticit del mittente

di un messaggio. Seguir una sezione dedicata all'elencazione di alcuni requisiti di

sicurezza; tali norme sono dettate dal NIST, ovvero il National Institute of Standards

and Technology. Verr poi fatta una breve panoramica su alcuni tra i principali

attacchi noti al sistema RSA.

Per poter descrivere in particolare l'attacco di Wiener, servir la teoria delle fra-

zioni continue, sulla quale si concentra tutto il Capitolo 3. Verranno dati quindi la

denizione di frazione continua nita semplice, la denizione di convergente m-esima

dello sviluppo in frazione continua e alcuni teoremi e proposizioni fondamentali per

la comprensione dei contenuti seguenti.

Inne, il Capitolo 4 si focalizzer sull'attacco di Wiener ad RSA. Si enuncer e si

dimostrer quindi il teorema di Wiener e si descriver dettagliatamente l'algoritmo

di attacco. Verranno illustrati inoltre dei metodi per contrastarlo, ideati da Wiener

stesso, e verranno fornite alcune note storiche su ulteriori miglioramenti scoperti di

recente.

iv

Introduzione alla crittograa e preliminari

Questo capitolo inizia con una breve introduzione alla crittograa, alla quale segue

una descrizione sintetica dei sistemi crittograci a chiave pubblica e a chiave privata.

Per comprendere il funzionamento dell'algoritmo del sistema RSA, necessario de-

nire la funzione di Eulero (n), dove n un intero positivo, e enunciare il teorema

cinese dei resti. Si tratta poi brevemente il problema della fattorizzazione in numeri

primi.

1.1 Cifrari a chiave pubblica e a chiave privata

La crittograa la scienza che si occupa di proteggere le informazioni che vengo-

no scambiate durante la comunicazione tra due utenti su un canale potenzialmente

insicuro; l'obiettivo che essa si pregge quindi di impedire a una terza persona di

comprendere i messaggi inviati tra mittente e destinatario del sistema.

Lo sviluppo della crittograa andato di pari passo con quello della crittanalisi, che

si occupa dello studio degli attacchi ai cifrari, e dell'informatica, che studia invece l'e-

laborazione di dati e la loro rappresentazione mediante apparecchiature elettroniche;

questo perch crittogra e crittanalisti necessitano di elaboratori molto sosticati per

poter condurre le loro indagini sulla cifratura e decifratura dei messaggi.

Con l'avvento di internet le applicazioni della crittograa hanno assunto importanza

sempre maggiore, essendoci sempre pi bisogno di sicurezza, specialmente nelle tran-

sazioni in rete e non (si pensi a bancomat e carte di credito in generale).

Fino a non molti anni fa si utilizzavano sistemi crittograci a chiave simmetrica;

in questi casi Alice e Bob, che vogliono scambiarsi informazioni, utilizzano una sola

chiave privata per cifrare e decifrare i messaggi. Questa chiave ovviamente deve essere

nota solo a loro perch possano comunicare senza che Eva (l'intruso) la intercetti e

possa decifrare i messaggi; il problema che lo scambio della chiave deve avvenire in

modo sicuro, quindi si richiede necessariamente che il canale lo sia.

Per eliminare il pericolo di cui abbiamo parlato, negli anni Settanta nasce la critto-

graa a chiave pubblica (o asimmetrica) che andremo qui di seguito a descrivere.

1

Capitolo 1. Introduzione alla crittograa e preliminari

Figura 1.1: chiave pubblica

Alice e Bob scelgono entrambi una chiave pubblica con la quale poter cifrare messaggi

a loro diretti, mentre mantengono segreta la chiave associata per decifrarli; cio, Alice

cifra con la chiave pubblica di Bob che l'unico in grado di decifrare il messaggio,

utilizzando la chiave privata nota solo a lui (vedi gura 1.1). Con i sistemi crittogra-

ci asimmetrici ogni utente possiede due chiavi, una pubblica (nota a tutti coloro con

cui si vuole comunicare) e una privata (nota soltanto all'utente che deve decifrare i

messaggi). Si risolve cos il problema dello scambio delle chiavi, cruciale nei sistemi

a chiave privata.

2

1.2. Numeri primi e funzione di Eulero

La crittograa a chiave pubblica permette anche di garantire l'identit di chi invia

un messaggio (rma digitale); infatti il mittente pu rmare un messaggio con la

sua chiave privata (che solo lui possiede) e chiunque potr vericare l'autenticit

di tale rma grazie alla chiave pubblica, che nota a tutti. Questa innovazione

molto importante se si considerano tutte le operazioni che compiamo ogni giorno (ad

esempio la PEC

1

) in cui ci necessario.

Il pi conosciuto cifrario a chiave pubblica RSA, ideato da Ronal Rivest, Adi Shamir

e Leonard Adleman nel 1976, che sfrutta alcune propriet fondamentali dei numeri

primi ([RSA78]). La sua sicurezza si basa sulla dicolt di fattorizzare un numero

intero; in particolare, nell'RSA la chiave pubblica costituita da un numero intero n

ottenuto moltiplicando tra loro due numeri primi molto grandi, che restano segreti.

1.2 Numeri primi e funzione di Eulero

Denizione 1. Un numero intero maggiore di 1 si dice primo se divisibile senza resto

soltanto per 1 e per se stesso.

Ci sono vari modi per testare la primalit di un intero n. Il pi semplice provare

a dividerlo per tutti i primi no a

n (non ha senso andare avanti perch, se n non

primo, avr sicuramente un fattore primo minore o uguale a

n); tuttavia questo

metodo non praticabile perch molto laborioso per primi grandi e quindi necessita

di tempi eccessivamente lunghi. Ci sono metodi pi sosticati per determinare che un

numero primo, ma spesso pi facile vedere che un numero non primo. Questo

perch i numeri primi sono numeri speciali, che godono di particolari propriet: se

una di esse non soddisfatta per un certo numero, possiamo dire con certezza che

esso non primo.

Denizione 2 (Congruenza). Sia n Z; allora a e b si dicono congruenti modulo nse n divide a b ovvero se esiste un numero intero c tale che a = b+ cn. In simboli:a b (mod n).Si pu facilmente dimostrare che la congruenza modulo n (con n > 0) una

relazione di equivalenza; in particolare, essa d luogo a n classi di equivalenza

[0] , [1] , [n 1]

che corrispondono a tutti i possibili resti della divisione per n.

Si denota con Zn l'anello quoziente modulo la relazione di equivalenza; in particolare,

1

Sta per posta elettronica certicata.

3


si dimostra che Zn un campo se e solo se n primo.

Denizione 3 (Funzione di Eulero). Sia n un numero intero positivo; allora (n) il

numero degli interi non negativi minori di n che sono coprimi con n. Equivalente-

mente, (n) l'ordine del gruppo degli elementi invertibili dell'anello Zn (ogni classeresto ha un unico rappresentante non negativo minore di n).

Proposizione 1. La funzione moltiplicativa, cio

(m n) = (m) (n)

se (m,n) = 1.

Dimostrazione. Per il Teorema (3) cinese dei resti, che verr enunciato in seguito, si

ha l'isomorsmo seguente

Zmn Zm Znu + mnZ 7 (u + mZ, u + nZ). (1.1)

Grazie a esso possiamo dire che il numero (mn) di elementi invertibili del primo

anello uguaglia quello del secondo, che (m)(n) per una generale propriet del

prodotto diretto di anelli.

Osservazione 1. Se p primo, (n) = p 1, perch tutti gli interi positiviminori di p sono coprimi con p.

Se n potenza di un primo p, cio n = p, per un opportuno vale

(n) = p p1 = p1 (p 1).

Questo perch il numero di interi positivi coprimi con p dato dalla dierenza

tra il numero degli interi positivi minori di p e il numero dei multipli positivi

di p minori o uguali a p.

Il caso che interessa a noi, relativo all'RSA n = p q dove p e q sono due numeriprimi grandi e distinti (anch ci sia una certa sicurezza p e q dovrebbero avere circa

100 cifre decimali). Dalle propriet della funzione di Eulero abbiamo che

(n) = (p) (q) = (p 1) (q 1).

4

1.2. Numeri primi e funzione di Eulero

Teorema 1 (di Eulero-Fermat). Siano a, n interi positivi con (a, n) = 1; allora

a(n) 1 (mod n).

Dimostrazione. Se (a, n) = 1, l'intero a appartiene al gruppo degli elementi invertibili

dell'anello Zn (indicato come Zn). Poich tale gruppo ha ordine (n), segue le tesi.

Teorema 2 (piccolo teorema di Fermat). Sia p un primo; allora per ogni intero a vale

ap a (mod p).

Dimostrazione. Se p | a, la conclusione immediata; se invece p - a la tesi segue dalteorema di Eulero-Fermat. Tale risultato ancora pi evidente se la tesi si scrive

nella forma a (ap1 1) 0 (mod p).

Il piccolo teorema di Fermat ci illustra una delle propriet dei numeri primi, per

cui possiamo dire che, se un intero gode di questa propriet, c' un'alta probabilit

che esso sia primo. Tuttavia, bisogna fare attenzione ad alcuni numeri che deniamo

qui di seguito.

Denizione 4 (numero pseudoprimo). Un numero intero n si dice pseudoprimo rispet-

to alla base b se

bn1 1 (mod n).Notiamo che, se n primo, allora n pseudoprimo rispetto ad ogni base b, per il

piccolo teorema di Fermat.

I numeri pseudoprimi sono quindi numeri che pretenderebbero di essere primi passan-

do solo per il test bn1 1 (modn) per un certo b e ci ovviamente non sucienteper determinare la sua primalit. Tali numeri per fortuna si determinano facilmente;

possibile fare ci per la seguente Proposizione.

Proposizione 2. Sia n intero diverso da 1 e non primo; se n non pseudoprimo rispetto

a una certa base b allora non pseudoprimo rispetto ad almeno la met delle basi

possibili (che sono le (n) basi b con 0 < b < n e (b, n) = 1).

Dimostrazione. Sia B = {b (Zn) : bn1 = 1} l'insieme delle basi per cui n pseudoprimo, considerate modulo n. Osserviamo che B un sottogruppo proprio di

(Zn); infatti un sottogruppo in quanto, dati a, b B, cio an1 = bn1 = 1,segue che (ab)n1 = 1, quindi ab B e (a1)n1 = (an1)1 = 1, quindi a1 B.

5


Inoltre, per ipotesi, esiste almeno una base b per cui n non pseudoprimo e che quindi

non sta in B. Segue che

|B| = (n)|(Zn) : B| (n)

2

dove |(Zn) : B| indica la dimensione di B in Zn, cio il grado dell'estensione Zn diB (abbiamo dovuto provare che B sottogruppo di Zn).

Denizione 5. Sia n un intero dispari non primo e diverso da 1. Allora n si dice

numero di Carmichael se

bn1 1 (mod n)per ogni base b tale che (b, n) = 1.

Un numero di Carmichael quindi un numero non primo ma pseudoprimo rispet-

to a qualunque base. Anche i numeri di Carmichael si possono scoprire facilmente,

usando un semplice algoritmo basato sul fatto che, se un intero n primo, allora gli

unici interi b tali che b2 1 (mod n) sono 1.Esistono anche algoritmi pi ranati (in cui non ci addentriamo) per testare la pri-

malit di un intero, che non presentano casi eccezionali come i numeri di Carmichael.

1.3 Teorema cinese dei resti

Teorema 3 (Teorema cinese dei resti). Siano n1, n2, . . . , nm numeri interi positivi a

due a due coprimi e siano a1, a2, . . . , am altrettanti interi. Allora:

esiste un intero x che risolve il seguente sistema:x a1 (modn1)x a2 (modn2). . .

x am (modnm).(1.2)

Inoltre, detta x0 una soluzione particolare, essa rappresenta la soluzione generale

xk = x0 + (n1 n2 . . . nm) k, con k Z; due interi b e c che sono soluzione del sistema (1.2) sono congruenti tra loromodulo N = n1 n2 . . . nm, cio b c (modN); due interi v e z che siano congruenti tra loro modulo ni, per ogni i = 1 . . .m,lo sono anche modulo N .

6

1.3. Teorema cinese dei resti

Dimostrazione. Dimostrazione seguendo [Jac89] e [Sta07].

1. SiaN = n1n2. . .nm e sia, per ogni i = 1, . . . ,m, Ni = Nni =

j 6=i nj. Allora,per ogni indice i, non avendo ni alcun fattore primo con nj, (per ogni j 6= i),segue che ni non ha fattori primi in comune con Ni, ossia (Nj, ni) = 1. Quindi,

per ogni i = 1, . . . ,m, la congruenza lineare Nix bi (modni) ammette unasoluzione ci.

Sia ora c =m

i=1 Nici e sia ssato un indice i. Si osservi che, per ogni j 6= i,ni divide Nj e quindi anche Nici. Pertanto

c = Nici +j 6=i

Njcj Nici bi (modni).

L'ultima congruenza dovuta al fatto che ci verica il sistemaNix bi (modni).Sia ora k Z; allora, essendo N ni, per ogni i = 1, . . . ,m, si ha chexk x0 bi (modni), per ogni i = 1, . . . ,m, ossia xk soluzione del sistema(1.2).

Sia quindi x una soluzione del sistema (1.2). Allora x x0 (modni) per ogniindice i, quindi ni | (x x0). Poich gli ni sono a due a due coprimi, il loro pro-dotto (cio N) divide xx0; questo per il teorema fondamentale dell'aritmetica(4). Quindi esiste k Z tale che x x0 = kN , cio x = xk.

2. Siano b, c le soluzioni del sistemax a1 (modn1)x a2 (modn2). . .

x am (modnm).Allora b c soddisfa

b c 0 (modn1)b c 0 (modn2). . .

b c 0 (modnm)cio b c 0 (modni) per ogni i; ci signica che N | (b c), cio per ogniindice i b c multiplo del massimo comune divisore degli ni. Poich gli nisono a due a due coprimi, tale massimo comune divisore coincide proprio con il

loro prodotto.

7


3. Tale dimostrazione l'inversa del punto 2.

Il Teorema cinese dei resti (3) fondamentale nel funzionamento dell'algoritmo

del sistema RSA; esso permette infatti di eseguire calcoli modulari rispetto ad un

certo numero intero n e in particolare mostra come si possa calcolare x conoscendo

x (mod p) e x (mod q) (con p e q coprimi). La Formula di Garmer ([Sta07]) ci dice

operativamente come calcolare x.

Proposizione 3 (Formula di Garmer). Nelle ipotesi del teorema cinese dei resti, si ha

che la soluzione x al sistema (1.2) data da

x = (((a b)(q1 (mod p))) (mod p)) q + b.

Dimostrazione. Si verica inanzitutto che 0 x (n 1). Naturalmente x 0 et := (((a, b)(q1 (mod p))) (mod p)) un termine compreso tra 0 e p 1 perch calcolato modulo p.

Poich t (p1), tq (p1)q e x = tq + b (p1)q + (q1) = pq 1 = n 1si ha 0 x (n 1).Ora controlliamo che il risultato sia eettivamente corretto. Sia x (mod p) = a e

x (mod q) = b; allora

x (mod q) = (((a, b)(q1 (mod p))) (mod p)) q + b (mod q)= (K q + b) (mod q) per qualche K= b (mod q)

= b;

(1.3)

x (mod p) = (((a, b)(q1 (mod p))) (mod p)) q + b (mod p)= ((a b)q1 q + b) (mod p)= ((a b)(q1 q) + b) (mod p)= ((a b) + b) (mod p)= a (mod p)

= a.

(1.4)

8

1.4. Fattorizzazione in numeri primi

Osservazione 2. Dal teorema cinese dei resti sappiamo che la soluzione al sistema

(1.2) pu essere solo una, quindi la formula di Garmer risolve completamente il pro-

blema della risoluzione di tale sistema.

1.4 Fattorizzazione in numeri primi

La sicurezza dell'algoritmo RSA si basa sulla dicolt di fattorizzare numeri interi

molto grandi.

Denizione 6. Per fattorizzazione si intende la scomposizione di un numero intero

in un insieme di divisori non banali che, moltiplicati fra loro, diano il numero di

partenza.

Il teorema Fondamentale dell'Aritmetica assicura che la scomposizione in fattori

primi unica, a meno di cambi d'ordine tra i fattori.

Teorema 4 (Teorema fondamentale dell'aritmetica). Ogni numero intero a > 1 o

un numero primo o si scrive in modo unico come

a =ni=1

pi = p11 p22 . . . pnn

dove pi sono numeri primi e i interi positivi. A meno che non si inverta l'ordine dei

fattori, tale scomposizione unica.

Naturalmente, calcolare il prodotto di due o pi numeri interi primi p e q, anche

se molto grandi (composti di qualche centinaio di cifre) un'operazione pressoch

elementare e qualasiasi calcolatore attuale in grado di farlo in tempo breve. Tuttavia,

dato n = p q, dicile scomporlo nei suoi fattori elementari p e q. Nel corso dellastoria sono stati ideati molti metodi per rendere la fattorizzazione un problema sempre

pi veloce ed agevole; esso per rimane tuttora un problema complesso.

9

Algoritmo RSA, requisiti di sicurezza e principali

attacchi

In questo capitolo si va ad analizzare nel dettaglio il sistema crittograco a chiave

pubblica RSA. Viene inoltre descritto un esempio di rma autenticata e si elencano

le principali norme di sicurezza da seguire per non esporre il sistema ai pericoli pi

comuni. Inne, si presentano sinteticamente alcuni attacchi noti.

2.1 Algoritmo RSA

Nel 1978 Ronal Rivest, Adi Shamir e Leonard Adelman pubblicarono sulla rivista

Communication of ACM ([RSA78]) la descrizione del cifrario RSA (acronimo ottenu-

to dalle iniziali dei suoi inventori). Esso fu uno dei primi sistemi crittograci a chiave

pubblica (si veda la Sezione 1.1) ed operava a blocchi interpretando ogni messaggio

come un numero intero. Per alcuni anni RSA rimase soltanto una bella idea, ma

ben presto, per la sua semplicit e sicurezza, venne utilizzato (e lo anche oggi) in

molti settori, specialmente per la protezione di comunicazioni su piattaforme digitali.

L'algoritmo di codica e decodica sfruttato nel sistema RSA il seguente.

Alice, che vuole ricevere messaggi da Bob (o da qualsiasi utente), si costruisce

anzitutto una chiave pubblica. Sceglie quindi due numeri primi dispari distinti p e q

molto grandi (per avere una certa sicurezza, p e q devono avere circa 128 cifre, ovvero

circa 425 cifre binarie) e calcola n = p q; per quanto visto nella Proposizione 1

(n) = (p 1) (q 1).

Sceglie poi un intero e tale che (e, (n)) = 1.

Alice si quindi costruita la coppia (n, e), che rappresenta la sua chiave pubblica (di

cifratura); ogni utente potr utilizzarla per inviare un messaggio ad Alice.

Bob traduce il messaggio che vuole inviare ad Alice in una sequenza di numeri xi

X = (x1, x2, . . .)

11

Capitolo 2. Algoritmo RSA, requisiti di sicurezza e principali attacchi

con xi < n i. Si osservi che gli xi saranno quasi sicuramente primi con n, es-sendo che il rapporto

(n)ntende a 1 per n opportunamente grande. Bob deve ora

cifrare il messaggio in chiaro X = (x1, x2, . . .) per ottenere il messaggio cifrato

Y = (y1, y2, . . .) utilizzando la chiave pubblica e messa a disposizione da Alice e

lo fa nel modo seguente:

yi = xei (modn);

invia quindi Y ad Alice.

Per decifrare il messaggio Alice deve utilizzare la funzione inversa, che solo lei pu

calcolare perch l'unica a conoscere la fattorizzazione di n. Ricava quindi due numeri

d e t tali che

de + (n)t = 1

e procede nel modo seguente, presumendo per semplicit che gli xi siano primi con n:

xi = x1i = x

de+(n)ti = x

dei x(n)ti ydi (modn)

dato che yi = xei (modn) e x

(n)ti 1 (modn) per il teorema di Eulero-Fermat (1).Se xi non fosse primo con n, Alice compirebbe la stessa operazione applicando prima

il teorema cinese dei resti (3) su n = p q e poi il teorema di Eulero-Fermat (1).Per ottenere il messaggio in chiaro, ad Alice basta dunque calcolare la potenza d-

esima di yi e calcolarne il resto modulo n.

Riassumendo, i parametri utilizzati nell'algoritmo sono:

informazioni pubbliche informazioni private

n, e p, q, d

ALGORITMO ESEMPIO NUMERICO

Esempio 1. Alice sceglie due primi

grandi p e q e ne calcola il prodotto

n = p q

p = 31, q = 41 = n = 1271

Tabella 2.1: continua nella prossima pagina

12

2.1. Algoritmo RSA

Tabella 2.1: continua dalla pagina precedente


Alice calcola (n), cio trova il

numero degli interi minori di n e primi

con esso

(n) = 30 40 = 1200

Alice sceglie un numero e < (n) tale

che

(e, (n)) = 1

e = 13

la chiave pubblica (n, e) costruita (1200, 13)

Bob traduce il suo messaggio in una

sequenza di numeri xi minori di n

Supponiamo il messaggio sia

CIFRARIO: gli xi si otterranno ad

esempio dalla seguente relazione

xi = a + b 26, dove ogni letteracorrisponde a un numero compreso tra

0 e 25 cio

CI = x1 = 2 + 8 26 = 210FR = x2 = 5 + 17 26 = 447AR = x3 = 0 + 17 26 = 442IO = x4 = 8 + 14 26 = 372


13




Bob cifra il messaggio calcolando

yi = xei (modn)

Il messaggio cifrato risulta quindi:

y1 21013 (mod 1271) 818y2 44713 (mod 1271) 879y3 44213 (mod 1271) 729y4 37213 (mod 1271) 899

Alice calcola d e t con l'algoritmo di

Euclide esteso in modo che

d e + (n) t = 1

si ha quindi d = 277 e t = 3

Alice procede alla decodica del

messaggio: xi = ydi (modn)

x1 818277 (mod 1271) 210x2 879277 (mod 1271) 447x3 729277 (mod 1271) 442x4 899277 (mod 1271) 372

Alice applica la funzione inversa a

quella che ha applicato Bob per cifrare

e ottiene il messaggio in chiaro

210 = 2 + 8 26 = CI447 = 5 + 17 26 = FR442 = 0 + 17 26 = AR372 = 8 + 14 26 = IO

Tabella 2.1: Esempio numerico algoritmo RSA

14

2.2. Firma autenticata nell'RSA

2.2 Firma autenticata nell'RSA

Come stato anticipato nella Sezione (1.1), la crittograa a chiave pubblica per-

mette di rmare un messaggio; nel caso dell'algoritmo RSA, tale procedimento fun-

ziona nel modo seguente.

Sia 0 M < n un messaggio che Alice vuole inviare a Bob 1.Si possono dare varie denizioni di rma associata a un messaggio; la seguente ne

un semplice esempio.

Denizione 7 (Firma di un messaggio). Sia d esponente privato del sistema RSA con

modulo n; allora deniamo rma di un messaggio M la seguente:

sig(n,d)(M) = Md (modn).

Una rma denita in questo modo ha le seguenti caratteristiche.

Per Alice facile calcolare la rma del messaggio M da inviare a Bob; bastafare un elevamento a potenza modulo n.

La verica dell'autenticit della rma pu essere fatta da chiunque.

La rma dicile da falsicare per Eva; infatti tale operazione equivale arompere il crittosistema RSA.

Per vericare la rma si pu usare la seguente procedura:

ver(n,e)(M,F ) =

{VERO, seM = F e (modn)

FALSO, altrimenti.

Sia denito un sistema RSA con n = 47 71 = 3337, e = 79, d = 1019; conquesti parametri, (n) = 46 70 = 3220 ed eettivamente e d 1 (mod(n)).

1

Si pu eventualmente scomporre il messaggio in due parti, associate a due numeri minori di n;questa condizione necessaria poich non vogliamo che due messaggi distinti siano accoppiati alla

stessa rma.

15



Esempio 2. Alice vuole rmare un

messaggio; associa perci ad esso un

numero M , che sceglier compreso tra

0 e n, utilizzando un certo algoritmo

M = 1570

Alice utilizza il proprio esponente

privato d per calcolare la rma F

associata al messaggio M :

F = sig(n,d)(M) = Md (modn)

sig(3337,1019)(1570) =

15701019 (mod 3337) = 668

Bob riceve (M,F ), cio il messaggio

M con rma associata ad esso F

Bob riceve (1570, 668)

Bob deve vericare se eettivamente F

la rma del messaggio M calcolando

ver(n,e)(M,F ), cio Fe (modn); se tale

risultato pari a M la rma

garantita, altrimenti non lo

ver(3337,79)(1570, 668) = V ERO

perch 66879 1570 (mod 3337)

Tabella 2.2: Firma RSA

16

2.3. Requisiti generali per la sicurezza

2.3 Requisiti generali per la sicurezza

Nonostante la sua ecienza, il sistema RSA ha un costo computazionale piut-

tosto elevato perch, per garantire la sua integrit, si devono scegliere parametri

opportunamente grandi; ecco perch forte la tentazione di ridurre i tempi di codi-

ca/decodica, ad esempio abbassando alcuni parametri del sistema (come esponenti

pubblici o privati).

I requisiti generali per la sicurezza di RSA sono dati dal NIST, che sta per Na-

tional Institute of Standards and Technology. Elenchiamo di seguito alcune tra le pi

importanti norme che tale ente invita a rispettare (si veda [BCRS09]).

1. Le chiavi devono essere generate usando un metodo appropriato.

2. La chiave privata e i fattori primi p e q devono essere opportunamente protetti.

3. Ogni chiave pubblica e ogni utilizzo della chiave devono poter essere ricondotti

a un utente identicato.

4. La chiave pubblica deve essere protetta da modiche non autorizzate; a tale

riguardo, esiste un'Autorit Certicativa (CA), cio un ente abilitato a rila-

sciare un certicato digitale che segue standard internazionali e conforme alla

normativa vigente in materia.

5. Il destinatario della chiave pubblica deve essere certo dell'integrit dei dati ri-

cevuti e della corretta associazione tra chiave pubblica e possessore della coppia

di chiavi.

6. Una coppia di chiavi non pu essere usata per diversi scopi crittograci (come

rma digitale e processo di creazione di chiavi).

7. Il proprietario di una coppia di chiavi dev'essere sicuro che essa sia stata creata

con metodo appropriato e sicuro.

2

8. Il destinatario di una chiave pubblica dev'essere certo dell'identit del proprie-

tario della chiave e del fatto che esso eettivamente possieda tale chiave.

Oltre a questi vincoli sulla generazione delle chiavi (che impediscono di risalire

dalla chiave pubblica alla chiave privata), il NIST fornisce delle indicazioni per la

sicurezza nella cifratura e decifratura dei messaggi, cio per fare in modo che sia im-

possibile risalire dal messaggio cifrato al messaggio in chiaro. Questo processo di

2

Una coppia di chiavi nel sistema RSA consiste in una chiave pubblica (n, e) e in una chiaveprivata (p, q, d), dove n = p q, e primo con (n) e d tale che e d + (n) d 1 (modn).

17


dicile realizzazione per gli ardui problemi della fattorizzazione del modulo n e del

calcolo delle radici modulo n. 3

Il NIST propone quindi il rispetto di alcune norme per evitare la rottura dell'algorit-

mo RSA, che sono le seguenti:

n dev'essere prodotto di esattamente due primi distinti;

l'esponente pubblico e dev'essere scelto prima di generare i primi p e q e l'espo-nente privato d e deve essere un numero primo tale che

65.537 e 2256;

i primi p e q devono soddisfare le seguenti propriet:

1. devono essere generati indipendentemente e casualmente per diverse coppie

di chiavi;

2. (n), dove n = p q, dev'essere maggiore di e e relativamente primo conesso;

3. p e q devono essere scelti casualmente tra i primi che soddisfano

2(2(nbit/2)1) p, q (2nbit/2 1)

dove nbit corrisponde alla lunghezza in bit di n (solitamente 1024 che

corrisponde a 309 cifre decimali);

4. p q > 2(nbit/2)100;

l'esponente privato d, che dev'essere scelto dopo aver determinato e e dopo avergenerato i primi p e q

1. deve essere un intero positivo tale che

2nbit/2 < d(n);

2. ed 1 (mod(n)), quindi

d e1 (mod(n)).3

Si tende a basare la sicurezza di RSA sulla dicolt della fattorizzazione di n, essendo unaquestione molto pi discussa rispetto a quella del calcolo delle radici modulo n.

18

2.4. Attacchi elementari dovuti a errata scelta del modulo

Se d 2nbit/2, si devono rideterminare p, q ed e (e dev'essere scelto perprimo, prima di generare i nuovi p e q).

I principali attacchi ad RSA si basano sul mancato rispetto di almeno una di queste

norme.

2.4 Attacchi elementari dovuti a errata scelta del modulo

RSA stato analizzato n dalla sua creazione per la sua vulnerabilit ad attacchi

di vario tipo; nel corso delle ricerche si sono formulati degli algoritmi di rottura di

RSA molto eleganti, ma nessuno di essi si rivelato realmente minatorio per la sicu-

rezza del sistema. Questo perch il pericolo deriva da un uso errato dell'algoritmo, in

particolare da scelte infelici di alcuni parametri.

Un primo esempio di attacco al sistema RSA con chiave pubblica (n, e) quello che

sfrutta la fattorizzazione di n. Conoscere la fattorizzazione di n signica conoscere p

e q, quindi facile ricavare (n), da cui si ottiene l'esponente privato di decifrazione

d essendo d e1 (modn).Il modo pi intuitivo per decifrare il messaggio consiste nel calcolare, per ogni valore

di Zn, il valore crittato e ricercare quali parametri si trovano nel messaggio cifrato,ottenendo cos il messaggio in chiaro. Tuttavia questo procedimento risulta troppo

lungo, richiedendo un algoritmo di tempo esponenziale.

Un attacco interessante invece quello di Fermat, che consiste nella facile fatto-

rizzazione di n se (p q) < n1/2 e n 1 (mod 4). Con queste premesse, n sarfattorizzabile individuando due interi positivi x, y tali che

4n = x2 y2.

Fatto ci, p e q si ricaveranno ponendo p = 12(x+ y) e q = 1

2(x y); eettivamente

p e q saranno interi maggiori di 1 che moltiplicati tra loro danno n.

2.5 Attacchi con esponente pubblico piccolo

Per ridurre il tempo di cifratura o di verica della rma digitale, si pu esse-

re tentati di utilizzare un esponente pubblico e piccolo. Si noti che il pi picco-

lo valore di e possibile 3, ma in generale si raccomanda di assumere al minimo

e = 216 + 1 = 65.537, per evitare di incorrere in alcuni tipi di attacco. Se si prende

e = 216 +1, servono 17 moltiplicazioni per vericare la rma digitale; se invece si usa

un e casuale, comunque minore di (n), ne servono circa 1000. I valori di e vengono

19


solitamente scelti tra i primi di Fermat, cio primi del tipo 22x + 1 per il fatto che

rendono pi veloce l'elevamento a potenza modulo n e sono coprimi con p 1 e q 1.Quasi tutti gli attacchi che sfruttano il fatto che l'esponente pubblico e piccolo si

basano sul teorema di Coppersmith (vedi [Bon99]).

Teorema 5 (di Coppersmith). Sia n un intero e f Z[x] un polinomio monico digrado s; si consideri ssato X = n

1sper qualche 0. Allora, dati (n, f), possibile trovare tutti gli interi x0 tali che

|x0| < X e f(x0) 0 (modn).

Il teorema fornisce a Eva un eciente algoritmo per ricavare tutte le radici di f

modulo n minori di un ssato X = n1s. Al diminuire di X, si abbassa il tempo di

implementazione dell'algoritmo.

Un altro teorema ([BDF98], pag. 4, teorema 2.1), sempre dovuto a Coppersmith,

che generalizza il precedente e su cui si basano gli attacchi ad RSA con esponente

pubblico e piccolo, il seguente .

Teorema 6. Sia f(x, y) una funzione polinomiale, in due variabili sugli interi, di grado

massimo rispetto ad ogni variabile e si assumano i coecienti di f relativamente

primi fra loro. Siano X, Y limitazioni sulle soluzioni desiderate x0, y0; deniamo

f(x, y) := f(xX, yY ) e poniamo D come valore assoluto del massimo coeciente di

f . Se XY < D23, allora si possono determinare in tempo polinomiale tutte le coppie

di interi (x0, y0) con

f(x0, y0) = 0, |x0| < X e |y0| < Y.

Il seguente corollario mostra come si pu applicare il teorema di Coppersmith per

attaccare RSA.

Corollario 1. Sia n = p q modulo di un sistema RSA a nbit e siano dati r 2n4 ,p0 := p (mod r). Allora possibile fattorizzare n in un tempo polinomiale di n.

2.5.1 Attacco di Hstad sulla trasmissione

Alcuni attacchi che utilizzano il teorema di Coppersmith hanno lo scopo di recupe-

rare il messaggio in chiaro conoscendo il messaggio cifrato e le relazioni tra i messaggi

da cifrare (purch il messaggio sia cifrato utilizzando lo stesso esponente pubblico).

20

2.5. Attacchi con esponente pubblico piccolo

L'attacco di Hstad ad RSA ([Hs88]) rientra in questa categoria.

Si supponga che Bob voglia inviare un messaggio M a pi persone, ognuna delle

quali possiede una propria chiave pubblica (ni, ei) (sia M < ni per ogni i). Egli

cifra quindi il messaggio M usando ognuna delle chiavi pubbliche associate ai vari

destinatari e invia loro il messaggio. Eva intercetta tutti questi messaggi, che sa

essere in qualche relazione tra loro.

Assumiamo ei = 3 per ogni i; allora si pu dimostrare che Eva potr conoscere M se

i destinatari sono 3 o pi di 3. Infatti, i messaggi da decifrare sono:

C1 M3 (modn1)

C2 M3 (modn2)C3 M3 (modn3).

Sia inoltre (ni, nj) = 1 per ogni i 6= j, altrimenti gli ni sarebbero facilmentefattorizzabili.

Applicando il teorema cinese dei resti (3) a C1, C2, C3 possiamo ottenere C Zn1n2n3tale che

C M3 (modn1n2n3).Si noti che, essendoM < ni,M

3 < n1n2n3, quindi C = M3 sugli interi; Eva quindipu ottenere M calcolando le radici cubiche reali di C .

In generale, se tutti gli esponenti pubblici valgono e, Eva pu ottenere il messag-

gio in chiaro se il numero di destinatari maggiore o uguale ad e. Naturalmente,

l'attacco di Hstad applicabile per valori di e opportunamente piccoli.

Hstad descrive anche un attacco molto pi potente, basato sull'ipotesi che i mes-

saggi siano legati tra loro da una relazione polinomiale (come ad esempio Mi =

i2m + M); in tal caso, Bob ottiene per ogni destinatario un polinomio pubblico sso

fi ZNi . Il messaggio segreto sar quindi il cifrato dei vari fi(M), quindi Eva inter-cetta i Ci (fi(M))ei (modni) per ogni i. Si dimostra che Eva potr ottenere M seil numero di destinatari del messaggio almeno uguale al massimo prodotto dell'e-

sponente pubblico per il grado della funzione che lega tra di loro i vari messaggi. In

particolare, se Bob invia messaggi legati tra loro da una funzione lineare a k destinata-

ri, con esponenti pubblici uguali e, Eva pu risalire al messaggio segreto solo se k > e.

Si pu concludere quindi che per mantenere una certa sicurezza del sistema RSA

21


bisogna utilizzare esponenti di cifratura opportunamente elevati e continuamente di-

versi tra loro (cos come i moduli ni) oppure trasformare i messaggi tramite relazioni

polinomiali non stabili.

2.5.2 Attacco di Franklin-Reiter sui messaggi correlati

Franklin e Reiter danno il nome ad un attacco che si basa sull'uso di uno stes-

so modulo, di un esponente pubblico piccolo e di una funzione polinomiale che lega

tra loro i messaggi da inviare (si veda [CFPR96]). Con queste premesse possibile

recuperare il messaggio originale da quelli cifrati conoscendo la relazione che li lega,

purch siano creati usando la stessa chiave pubblica (n, e) (con e esponente pubbli-

co piccolo). Tale idea riassunta nel seguente lemma ([Bon99], pagina 209, Lemma 7).

Lemma 2.5.1. Sia e un esponente pubblico piccolo e (n, e) la chiave pubblica per RSA.

Siano M1,M2 Zn, M1 6= M2 messaggi da cifrare tali che M1 = f(M2) (modn),con f Zn[x] funzione polinomiale lineare f = ax + b (b 6= 0) 4; siano C1, C2 imessaggi M1,M2 cifrati. Allora, dati (n, e, C1, C2, f), Eva pu risalire al messaggio

in chiaro.

L'attacco di Franklin-Reiter costituisce la base per una classe pi ampia di attac-

chi ad RSA, sempre nelle ipotesi di modulo costante e esponente pubblico piccolo.

Per evitare questi tipi di attacchi, l'unica soluzione scegliere esponente pubblico ab-

bastanza grande, modicare n ad ogni cifratura ed eventualmente utilizzare relazioni

polinomiali non costanti per i vari messaggi.

2.5.3 Attacco di Coppersmith

Coppersmith raorza l'attacco di Franklin-Reiter (si veda [CFPR96]), riettendo

su come si possa facilmente camuare un messaggio. Un modo molto semplice per

rendere un messaggio pi dicile da decifrare aggiungere in coda al messaggio ori-

ginale alcuni bit casuali. Coppersmith ha vericato per che tale metodo pu portare

a dei pericoli per la sicurezza del sistema; infatti, se per caso Bob invia ad Alice

pi volte lo stesso messaggio (che viene intercettato da Eve), Eve ha a disposizione

pi messaggi cifrati che corrispondono allo stesso messaggio originale e pu, pur non

conoscendo i bit nali, leggere il messaggio in chiaro (si veda [Bon99]).

4

Questo attacco si pu estendere anche al caso in cui f una funzione polinomiale di un certogrado .

22

2.6. Attacchi all'esposizione parziale della chiave

Teorema 7. Sia (n, e) la chiave pubblica del sistema RSA, dove n lungo nbit; sia

inoltre m = ne2. Sia M Zn un messaggio lungo al massimo n m bit. Sia datol'algoritmo di cifratura seguente: M1 = 2

mM + r1, M2 = 2mM + r2, con r1 6= r2e 0 r1, r2 < 2m. Se Eva conosce la chiave pubblica (n, e) e la cifratura di M1,M2,cio C1, C2, pu ottenere facilmente il messaggio M pur non conoscendo r1, r2.

2.6 Attacchi all'esposizione parziale della chiave

Gli attacchi a esposizione parziale ([Bon99]) si basano sulla possibilit di risalire

all'esponente di decifratura d conoscendone soltanto una parte. Questo sistema

impiegato ad esempio negli attacchi di temporizzazione, che rompono sistemi RSA

studiando il tempo di esecuzione delle operazioni crittograche.

Sia n = p q il modulo del sistema RSA, composto da nbit; sia soddisfatta inoltre laseguente:

4 0, allora k > qn.2

Dimostrazione. Per assurdo, sia

hk6= pn

qnuna frazione che verica hk

< pnqncon h, k coprimi e 0 < k < qn. Allora, moltiplicando entrambi i membri per k e

tenendo conto dell'ipotesi k < qn abbiamo

|k h| < kqn|qn pn| < |qn pn| .

Ma questo in contraddizione con il lemma (3.0.1).

2

In altri termini, la migliore approssimazione razionale di un numero razionale che ha lacaratteristica di essere pi vicino a di qualsiasi altra approssimazione frazionaria con denominatorepi piccolo.

28

Attacco di Wiener a RSA

In questo capitolo si descrive nel dettaglio l'attacco di Wiener al sistema RSA.

Dopo averne illustrato con un esempio numerico il funzionamento, si accenna bre-

vemente a come sia possibile contrastare tale attacco e a come si sia recentemente

sviluppata la ricerca in questo settore.

4.1 Attacco di Wiener

L'attacco di Wiener ([Wie06]) fa parte della categoria di attacchi ad RSA basati

sulla scelta di un esponente privato piccolo; la tentazione ad abbassare gli esponenti

forte perch in questo modo si accelerano i processi di cifratura e di decifratura.

Tuttavia, ci sono alcuni pericoli che devono essere evitati.

Wiener mostr, gi nel 1990, che, scegliendo d < n1/4 (uscendo cio dai limiti det-

tati dal NIST), l'algoritmo RSA pu essere rotto. Wiener diede inoltre delle soluzioni

per evitare l'attacco da lui descritto; una di queste scegliere l'esponente pubblico e

sucientemente grande, in particolare e > n3/2.

Come si visto nella Sezione 3, le frazioni continue possono essere usate per

calcolare numeratore e denominatore di una frazione quando una buona stima di tale

frazione nota.

Sia f un numero razionale e q0, q1, . . . , qm la sua espansione in frazione continua.Allora essa si ottiene sottraendo la parte intera di f , invertendo ripetutamente il resto

e sottraendo ancora la parte intera, nch il resto non 0; cio:

q0 = bfc , r0 = f q0qi =

1

ri1

, ri =

1

ri1 qi(4.1)

per i = 1, 2, . . . ,m.

29

Capitolo 4. Attacco di Wiener a RSA

Osservazione 5. Per ogni m vale qm 2; infatti, se qm = 1 allora rm1 = 1,fatto impossibile.

Per ogni x > 0 si ha

q0, q1, . . . , qm < q0, q1, . . . , qm1, qm + x se m pariq0, q1, . . . , qm > q0, q1, . . . , qm1, qm + x se m dispari(4.2)

cio le approssimazioni razionali di un numero f che provengono dall'algoritmo

delle frazioni continue sono alternativamente pi grandi di f e pi piccole di f .

Infatti, q0, q1, . . . , qm1, qm = q0 +m1

j=0(1)jdjdj+1dove i di sono i denominatori

delle convergenti ai vari passi dell'algoritmo (q0, q1, . . . , qi = nidi , con (ni, di) =1).

Se f un numero reale e nmdm la convergente m-esima del suo sviluppo in frazione

continua, ricordiamo che valgono le seguenti relazioni (vedi Proposizione 5):

nidi1 ni1di = (1)i

per i = 1, 2, . . . ,m.

Sia ora f un'approssimazione di f cio tale che

f = f(1 )

per qualche 0; siano inoltre qi, ri e qi, ri i quozienti e i resti rispettivamente dif e di f .Se abbastanza piccolo, i numeratori e i denominatori di f possono essere ricavati

utilizzando il seguente algoritmo, da ripetersi nch non si ricava f .

1. Si generano i quozienti qi dell'espansione di f.

2. Utilizzando la relazione sui numeratori e i denominatori delle convergenti, si

costruisce la frazione q0, q

1, . . . , q

i1, q

i + 1

se i pari

q0, q1, . . . , q

i1, q

i

se i dispari.

3. Si controlla se la frazione costruita proprio f .

Osservazione 6. La ragione per cui si aggiunge 1, se i quozienti sono in numero pari,

che la supposizione di f deve essere maggiore di f , poich f f ; infatti, per la

30

4.1. Attacco di Wiener

(4.2), si ha q0, q

1, . . . , q

i1, q

i

< f =

q0, q

1, . . . , q

i1, q

i + r

i

.

Si noti che deve esistere un test che verichi la correttezza della supposizione di

f . L'algoritmo avr successo se

q0, q1, . . . qm1, qm 1 < f < q0, q1, . . . , qm1, qm se m pariq0, q1, . . . qm1, qm + 1 < f < q0, q1, . . . , qm1, qm se m dispari.(4.3)

Usando queste relazioni, si pu trovare che deve soddisfare la seguente:

1 f

f

(si veda [Wie06]).

Proposizione 6. Anch sia garantito il successo dell'algoritmo delle frazioni continue,

necessario che

pq; riscrivendo la (4.8) si ha

edg = k(p 1)(q 1) + g; (4.11)

quindi, si pu vedere che dividendo edg per k si ottiene quoziente (p 1)(q 1) eresto g, supponendo che k > g.

Ragionando in questo modo, si giunge a una supposizione di (p 1)(q 1) e g. Sela supposizione di (p 1)(q 1) 0, si hanno valori sbagliati per k e dg; questo casova escluso. La supposizione di (p 1)(q 1) serve a trovare una supposizione per(p+ q)

2usando la seguente identit:

pq (p 1)(q 1) + 12

=(p + q)

2. (4.12)

34

4.2. Algoritmo dell'attacco di Wiener passo per passo

Se la supposizione di

(p+ q)2non un intero, la supposizione di k e dg non pu essere

usata; la supposizione di

(p+ q)2pu essere usata per ottenere una supposizione di

(p q2

)2 usando l'identit seguente:(p + q

2

)2 pq =

(p q

2

)2. (4.13)

Se la supposizione di (p q2

)2 un quadrato perfetto allora le supposizioni di k e dg

sono corrette e in questo caso possibile ricavare d dividendo dg per g (si ricordi

che g era il resto della divisione di edgper k). Ora p e q possono essere determinati

partendo dalla conoscenza di

p+ q2e

p q2.

Se g piccolo e k < dg, da (4.10) si vede che esponenti privati d aventi numero di

cifre no a circa 1/4 i bit di n si possono reperire in tempo polinomiale.

Osservazione 7. Poich il numero di passi nello sviluppo in frazione continua dien al pi una costante moltiplicata per log n, e poich l'algoritmo della frazione

continua si ferma quando si ottiene

en, il procedimento che Eva deve compiere

per fattorizzare n termina rapidamente!

Generalmente, n di 1024 bit; quindi, per evitare questo attacco, d dev'esserealmeno di 256 bit. Sfortunatamente, 256 bit sono il limite operativo attuale

delle smart card.

4.2 Algoritmo dell'attacco di Wiener passo per passo

Partendo dalle ipotesi iniziali del Teorema 13, cio q < p < 2q e d < 13n

14, si

vuole scrivere cosa debba fare in pratica Eva per attaccare il sistema RSA utilizzando

la teoria fornita da Wiener (si veda [Ren04]).

In input si ha: e, pq.

In output si ha: d.

1. Sia i = 0, 1, 2, . . . ,m.

2. Si calcoli

qi =

epq

, se i = 0

1

ri1

, altrimenti.

(4.14)

35


3. Si calcoli

ri =

epq q0, se i = 0

1ri1 qi, altrimenti.(4.15)

4. Si calcoli

nidi

= q0, q1, . . . , qi:

ni =

q0, se i = 0

q0q1 + 1, se i = 1

qini1 + n

i2, altrimenti.

(4.16)

qi =

1, se i = 0

q1, se i = 1

qidi1 + d

i2, altrimenti.

(4.17)

5. Si trova una supposizione di

kdg:

q0, q1, . . . , qi + 1 , se i pari

q0, q1, . . . , qi , se i dispari.(4.18)

6. Si trova una supposizione di edg = e dg.

7. Si trova una supposizione di (p 1)(q 1) = edgk

.

8. Se (p 1)(q 1) = 0, si incrementa i e si riparte con l'algoritmo.

9. Si trova una supposizione di g = edg (mod k).

10. Si trova una supposizione di

p+ q2

= pq (p 1)(q 1)+12.

11. Se

p+ q2

= 0, si incrementa i e si riparte con l'algoritmo.

12. Si trova una supposizione di (p q2

)2 = (p+ q2

)2 pq.

13. Se (p q2

)2 non un quadrato perfetto, si incrementa i e si riparte con l'algoritmo.

14. Si calcola d = dgg.

36

4.3. Esempio numerico di attacco di Wiener

Si pu inoltre calcolare il valore di p e q sfruttando le seguenti relazioni:

p =p q

2+p + q

2

q = (p q

2 p + q

2

).(4.19)

4.3 Esempio numerico di attacco di Wiener

La seguente tabella illustra un esempio concreto di attacco di Wiener ad RSA.

Siano:

n = p q = 8927 e e = 2621.L'espansione in frazione continua sar eseguita su

en

= 26218927.

QUANTITA'

i=0 i=1 i=2

qi0 3 2

ri26218927

10642621

4931064

nidi

= q0, q1, . . . , qi01

13

27

supposizione per

kdG

11

13

310


37



QUANTITA' i=0 i=1 i=2

supposizione per edG2621 7863 26210

supposizione per (n)2621 7863 8736

supposizione per G0 0 2

supposizione per

p+q2

3153.5 532.5 96

supposizione per

pq2

289 = 172

d5

Tabella 4.1: Esempio numerico di attacco di Wiener

38

4.4. Come contrastare l'attacco di Wiener

4.4 Come contrastare l'attacco di Wiener

Come si anticipato, Wiener stesso sugger due metodi per non incorrere nel suo

attacco ([Wie06]).

4.4.1 Scelta di e grande

In questo primo caso, bisogna assicurarsi che e > n3/2; in tal caso, nella dimo-

strazione del Teorema di Wiener (13) non si pu pi essere sicuri che k sia piccolo e

quindi non si riesce a concludere l'attacco. Si consideri l'equazione ed = k(n) + 1

e si divida tutto per dn; si ottiene

e

n=

k(n) + 1

dn=

k(n p q + 1dn

=k

d

[1 k(p + q 1) 1

kn

] n3/2. Si noti per che un valore cos alto di e fa crescere notevolmente il tempo

di cifratura.

4.4.2 Utilizzo del teorema cinese dei resti

Questo metodo consiste nell'utilizzare il Teorema cinese dei resti (3) per velo-

cizzare la decifrazione senza scegliere d troppo piccolo. Supponiamo di utilizzare

nell'algoritmo RSA un esponente privato d tale che

dp := d (mod (p 1)),

dq := d (mod (q 1))siano piccoli (si possono intendere ad esempio di 128 bit ciascuno).

Allora si pu compiere una veloce decodica di un messaggio C calcolando dapprima

Mp Cdp (mod p),

Mq Cdq (mod q)

39


e usando il teorema cinese dei resti per ottenere l'unico valore M che verichi M Cd (modn). Il vantaggio i questo metodo consiste nel fatto che, anche se dp e dq

sono piccoli, d pu essere sucientemente grande (ad esempio dell'ordine di (n)).

L'utilizzo del Teorema cinese dei resti per la codica o la decodica richiede per che

non ci siano errori di calcolo, altrimenti RSA diventa vulnerabile; inoltre, dp e dq non

possono essere troppo piccoli, altrimenti sar possibile fattorizzare n.

4.5 Miglioramenti dell'attacco di Wiener

Sono stati dati, da Boneh e Durfee nel 2000, dei miglioramenti al limite dettato per

d daWiener; tali miglioramenti si basano sul teorema dovuto a Coppersmith su piccole

radici di polinomi a variabile unica. L'attacco di Boneh-Durfee consiste in un metodo

euristico con polinomi a due variabili; per l'implementazione dell'attacco coinvolta

la teoria sui reticoli, in particolare richiesto l'uso dell'algoritmo di riduzione delle

basi dei reticoli. Sulla base di tali teorie matematiche, Boneh e Durfee dimostrarono

che il sistema RSA insicuro per d < n121/2

< n0,292 ([BD06]).

Recentemente Hinek, Low e Teske hanno osservato che la dimostrazione di Boneh

e Durfee non totalmente corretta (si veda [HLT03]); si suppone di poter ottenere

d < n1/2, ma ad oggi questo un problema aperto. Al momento il miglior risultato

noto si deve a Verheul-van Tilborg e a Dujella ([Duj04]); il limite raggiunto d

Attacco di Wiener ad RSA (tesi di laurea triennale in matematica)

Documents

Transcript of Attacco di Wiener ad RSA (tesi di laurea triennale in matematica)