Attacco di Wiener a RSA

(1)

Alma Mater Studiorum

_{· Universit`}

a di

Bologna

FACOLT `A DI SCIENZE Corso di Laurea in Matematica

ATTACCO DI WIENER

AD RSA

MEDIANTE FRAZIONI

CONTINUE

Tesi di Laurea in Algoritmi della Teoria dei Numeri e

Crittografia

Relatore:

Prof. ALIFFI DAVIDE

DIOMEDI STEFANO

Presentata da:

III Sessione

(2)

(3)

Indice

Introduzione II

1 RSA 3

1.1 Sicurezza di RSA . . . 6

1.2 Attacchi base ad RSA . . . 7

2 Frazioni Continue 9 2.1 Algoritmo Euclideo . . . 9

2.2 Frazioni continue semplici finite e numeri razionali . . . 10

2.3 Frazioni continue semplici infinite e numeri irrazionali . . . 13

2.4 L’approssimazione di razionali mediante i convergenti . . . 14

3 Attacco di Wiener 19 3.1 Scopo dell’attacco . . . 19

3.2 Quando si puo realizzare . . . 20

3.3 Come funziona . . . 20

3.3.1 Teorema di Wiener e Convergenti . . . 20

3.3.2 Algoritmo per il calcolo di Frazioni Continue . . . 21

3.3.3 Algoritmo applicato a RSA e Criteri di Esattezza . . . 25

3.3.4 Come contrastare l’attacco . . . 27

3.3.5 Esempio di attacco di Wiener a RSA . . . 28

Bibliografia 35

(4)

Introduzione

La crittografia `e una disciplina che studia la trasformazione dell’informa-zione con lo scopo di renderla sicura da destinatari o usi non voluti.

L’operazione che trasforma un messaggio in chiaro, cioè leggibile da chiun-que, in un messaggio incomprensibile è chiamata cifratura, mentre il proces-so che riconverte il messaggio cifrato in un messaggio comprensibile è detto decifrazione. Entrambe queste operazioni, scritte sotto forma di algoritmo, avranno in input una o piu chiavi segrete.

Lo schema generale `e questo:

due utenti A e B vogliono scambiarsi un messaggio segreto m, su un canale insicuro, senza che questo venga intercettato da un terzo utente che chiame-remo E.

Fino a pochi anni fa l’unico metodo crittografico conosciuto era quello della crittografia simmetrica, nella quale viene usata solo una chiave sia per cifrare che per decifrare, una per ogni coppia di utenti. Il problema per`o sta nel condividere la chiave segreta tra gli utenti senza che questa venga intercettata da E, quindi c’`e bisogno di un canale sicuro.

(5)

2 INDICE

Lo schema generale `e il seguente:

Nel 1976 Diffie e Hellman proposero un nuovo crittosistema, detto crittosistema asimmetrico o a chiave pubblica, che negli anni , dopo perfezionamenti ad opera di Rivest, Shamir e Adleman, nel 1977 divenne il crittosistema RSA, che si basa sulla difficoltà di fattorizzazione degli interi in fattori primi. La differenza fondamentale con i crittosistemi simmetrici è che qui ogni utente ha 2 chiavi differenti, una per cifrare pubblica e una per decifrare che viene tenuta segreta. Questo è un grosso passo avanti in quanto ad esempio viene risolto il problema della distribuzione delle chiavi : con la crittografia simmetrica era necessario scambiare l’ unica chiave segreta attraverso un canale sicuro, mentre con quella asimmetrica non bisogna più preoccuparsi di scambiare la chiave su un canale segreto in quanto l’unica informazione da scambiare è quella pubblica già accessibile a tutti.

(6)

Capitolo 1

RSA

Lo schema generale di RSA `e il seguente:

l’utente A vuole mandare un messaggio m a B senza che E lo intercetti.

B sceglie due primi p e q grandi e distinti e li moltiplica per formare il numero:

nB = pq.

che viene detto modulo del nostro sistema RSA, e viene trovato

ϕ(nB) = (p − 1)(q − 1) dove ϕ `e la funzione di Eulero. Poi B sceglie il suo

esponente di cifratura eB (esponente pubblico) in modo che questo sia primo

con ϕ(nB), e eB < ϕ(nB). Infine viene calcolato l’esponente di decifrazione

dB (esponente privato) tale che il suo prodotto con eB sia congruo ad 1

mo-dulo ϕ(nB), ovvero eBdB ≡ 1 (mod(ϕ(nB))).

La chiave pubblica di B sar`a il modulo e l’esponente di cifratura ovvero la coppia (eB, nB) mentre la sua chiave privata sar`a l’esponente di

decifrazio-ne dB. Nel caso in cui B voglia mandare un messaggio ad A, quest’ultimo

sceglierà a sua volta due primi e seguirà lo stesso procedimento di B gene-rando però le sue due chiavi (eA, nA) e dA.

(7)

4 1. RSA

Quindi lo schema diventa:

Ora vediamo le fasi di Cifratura e Decifrazione nel caso in cui A voglia mandare il messaggio m (che per semplicit`a consideriamo come un numero) - Cifratura Preso il messaggio in chiaro m, A calcola utilizzando

l’espo-nente pubblico di B:

C = memod n e manda C a B.

- Decifrazione Una volta ricevuto il messaggio cifrato C, attravero il suo esponente privato, B calcola:

Cdmod n = m e decifra il messaggio criptato.

La decifrazione funziona in quanto:

d · e ≡ 1 mod ϕ(n) ⇒ d · e = 1 + kϕ(n) da cui:

Cd= (me)d = m1+kϕ(n)_{= m · m}k(ϕ(n))_{= m · (m}ϕ(n))k con mϕ(n) _{≡ 1 mod n da cui:}

Cd= m mod n. Esempio 1.0.1.

Generazione Chiavi

• B sceglie due primi p e q:

(8)

5

• B calcola n = p · q e ϕ(n) = (p − 1)(q − 1):

n = 47 × 71 = 3337, ϕ(n) = 46 × 70 = 3220 • B sceglie e tale che MCD(e, ϕ(n)) = 1:

e = 79 • B calcola d = e−1_{mod ϕ(n):}

d = 79−1_{mod 3220 = 1019}

• La chiave pubblica `e la coppia (e, n):

(e, n) = (79, 3337) • La chiave privata `e d:

d = 1019 Cifratura

• Un utente A vuole mandare a B il messaggio m = 688 (per sempli-cit`a consideriamo un numero) usando la chiave pubblica di B kB =

(79, 3337)

• A calcola C = me_{mod n:}

C = 68879mod 3337 = 1570 Decifrazione

• B riceve il messaggio cifrato C = 1570 • B si ricava m con la formula m = Cdmod n:

(9)

6 1. RSA

1.1 Sicurezza di RSA

La sicurezza di RSA si basa fondamentalmente su un problema intratta-bile, ovvero quello della fattorizzazione di n, da cui segue la conoscenza di ϕ(n). Infatti E conosce la chiave pubblica, quindi sia l’esponente pubblico che il modulo, e se fosse in grado di fattorizzare quest’ultimo, troverebbe i due primi p e q con cui ricaverebbe ϕ(n) = (p − 1)(q − 1) e troverebbe l’esponente segreto risolvendo:

d e + y ϕ(n) = 1

Mostriamo ora che l’unico modo per decifrare un messaggio `e conoscere l’e-sponente segreto d:

Proposizione 1.1.1.

Conoscere ϕ(n) `e equivalente a conoscere p e q

Dimostrazione. Poich`e p e q sono primi allora posso calcolare:

ϕ(n) = (p − 1)(q − 1) ⇒ ϕ(n) = pq − (p + q) + 1 = n − (p + q) + 1 ne viene che p e q sono le radici del polinomio x2_{− (p + q)x + pq.}

Definizione 1.1.

Dato il modulo n, si dice che r `e un esponente universale se:

ar _{≡ 1 mod n ∀a ∈ Z : MCD(a, n) = 1}

Osservazione 1.

Se n è un primo allora n − 1 è un esponente universale per il teorema di Fermat, inoltre in generale per il teorema di Eulero ϕ(n) è sempre un espo-nente universale e un espoespo-nente universale è sempre pari

Proposizione 1.1.2.

Esiste un algoritmo propbabilistico che, dato un esponente universale del modulo n = p · q permette di trovare p e q.

Proposizione 1.1.3.

La conoscenza di d permette la fattorizzazione di n

Dimostrazione. Basta scrivere ed = 1 + kϕ(n) da cui ed − 1 sar`a espo-nente universale, quindi utilizzando l’algoritmo per gli esponenti universali, fattorizzo n.

(10)

1.2 Attacchi base ad RSA 7

1.2 Attacchi base ad RSA

Ci sono due strategie generali per attaccare l’algoritmo RSA:

• trovare un algoritmo che, dato un messaggio cifrato C e la chiave pub-blica (e, n), restituisce il messaggio decifrato m senza per`o recuperare la chiave privata d, ma nessuno ha mai trovato un algoritmo efficiente. • ricavare la chiave privata da quella pubblica.

Come abbiamo visto nella sezione riguardante la sicurezza, ci sono 3 alternative equivalenti per ricavare la chiave privata da quella pubblica:

1. fattorizzare n 2. Calcolare ϕ(n)

3. ricavare il valore d dalla chiave pubblica

rese però inutili dal problema, intrattabile, della fattorizzazione di n. In alcuni casi particolari però è facile forzare il sistema, a causa di una scelta errata dei parametri. Questo succede ad esempio:

• se m ed e sono cos`ı piccoli che me _{< n; allora risulta facile trovare la}

radice e-esima di C poich`e C = me _{e poi con un algoritmo di}

appros-simazione numerica si pu`o trovare m

• se p − q < n1/4 _{ci sono algoritmi veloci per trovare p e q.}

• se p − 1 e q − 1 hanno solo fattori piccoli, n si fattorizza velocemente con l’algoritmo di Pollard p − 1

• se, come `e stato trovato da Wiener, (lo vedremo in maniera piu appro-fondita nel capitolo dedicato), q < p < 2q e d < 1

3n

1 4.

(11)

(12)

Capitolo 2

Frazioni Continue

In questo capitolo ci occuperemo di spiegare cosa è una frazione continua e di esporre le sue proprietà fondamentali sfruttate dall’attacco dell’ esponente segreto piccolo. Ci soffermeremo più sulla parte delle frazioni continue per i razionali che per gli irrazionali, perchè questi ultimi non sono utilizzati dalla crittografia.

2.1 Algoritmo Euclideo

L’algoritmo di Euclide `e un algoritmo ricorsivo risalente al 300 a.C. che permette, dati due numeri interi (a, b) di calcolare il loro massimo comun divisore d (M CD(a, b) = d) senza richiedere la fattorizzazione in fattori pri-mi di a e di b che, per numeri troppo grandi, risulta essere praticamente impossibile.

Vediamo come funziona:

siano a, b ∈ Z, a > b : a, b ≥ 2 per semplicit`a.

Vale che M CD(a, b) = M CD(b, r1) con r1 resto della divisione di a per b.

Applichiamo la divisione con resto iterativamente fino ad ottenere un resto nullo: PASSO 1 : a = b∗q1+r1      se r1 = 0 ⇒ MCD(a, b) = b se r1 6= 0

PASSO 2 (cio`e si riapplica il procedimento con a = b e b = r1)

PASSO 2 : b = r1∗ q2+ r2

(

se r2 = 0 ⇒ MCD(b, r1) = r1

se r2 6= 0 PASSO 3

(13)

10 2. Frazioni Continue

[. . . ]

PASSO i-esimo ; ri−2 = ri−1∗qi+ri

(

se ri = 0 ⇒ MCD(ri−2, ri−1) = ri−1

se ri 6= 0 PASSO i+1

L’ultimo resto non nullo sar`a l’ M CD(a, b) Esempio 2.1.1.

Calcoliamo l’MCD dei numeri 345786 e 7432: 345786 = 7432 ∗ 46 + 3914 7432 = 3914 ∗ 1 + 3518 3914 = 3518 ∗ 1 + 396 3518 = 396 ∗ 8 + 350 396 = 350 ∗ 1 + 46 350 = 46 ∗ 7 + 28 46 = 28 ∗ 1 + 18 28 = 18 ∗ 1 + 10 18 = 10 ∗ 1 + 8 10 = 8 ∗ 1 + 2 8 = 2 ∗ 4 + 0 ⇒ MCD(345786,7432)=2

2.2 Frazioni continue semplici finite e numeri

razionali

Un’applicazione molto significativa dell’ algoritmo euclideo `e quella delle frazioni continue, che sono un modo alternativo di rappresentare i numeri reali. Infatti, se vogliamo ad esempio trovare la frazione continua del numero

68

15, applichiamo l’algoritmo con a=68 e b=15 ottenendo:

68 = 15 ∗ 4 + 8 (2.1)

15 = 8 ∗ 1 + 7 (2.2)

8 = 7 ∗ 1 + 1 (2.3)

(14)

2.2 Frazioni continue semplici finite e numeri razionali 11

ora dividendo primo e secondo membro di (2.1) per 15. Otteniamo 68

15 = 4 + 8

15 (2.5)

Se notiamo che il numero razionale `e compreso tra 4 e 5 in quanto 8 15 < 1

e in piu scriviamo 8

15 come inverso di un numero maggiore di 1, la formula

(2.5) diventa 68 15 = 4 + 1 15 8 (2.6) Notiamo ora che dividendo la (2.2) per 8 otteniamo la frazione al denomina-tore di 1 che abbiamo nella (2.6)

15

8 = 1 +

7

8 (2.7)

e la riscriviamo nella forma

15 8 = 1 + 1 8 7 (2.8) Infine, applicando un analogo ragionamento alla (2.3) troviamo

8

7 = 1 + 1

7 (2.9)

Abbiamo cos`ı ottenuto la frazione continua di 68₁₅: 68 15 = 4 + 1 1 + ₁₊11 7 (2.10)

Abbiamo visto un esempio di frazione continua. Ora formalizziamo il tutto e iniziamo dando la seguente definizione:

Definizione 2.1 (Frazione Continua).

Si dice frazione continua finita una frazione della forma:

a1+ 1 a2+ 1 a3+ 1 a4+... 1 an−1+_an1 (2.11)

con a1, a2, ..., an numeri reali, tutti positivi, ad eccezione al pi`u di a1.

I numeri a2, ..., an si chiamano denominatori parziali o quozienti parziali della

frazione. Una frazione continua finita si dice semplice se tutti i suoi quozienti parziali sono interi.

(15)

Proposizione 2.2.1.

Una qualunque frazione continua semplice finita `e uguale ad un numero ra-zionale. Viceversa, un qualunque numero razionale si pu`o scrivere come frazione continua semplice finita.

Dimostrazione. La prima parte `e ovvia. Sia ora a_b il numero razionale, b > 0.Applichiamo l’algoritmo di euclide per trovare il M CD(a, b)

a = b ∗ a1+ r1 0 < r1 < b

b = r1∗ a2+ r2 0 < r2 < r1

r1 = r2 ∗ a3+ r3 0 < r3 < r2

... ...

ri = ri+1∗ ai+2+ ri+2 0 < ri+2 < ri+1

... ...

r_n−3 = r_n−2_{∗ a}_n−1+ r_n−1 0 < r_n−1 < r_n−2 rn−2 = rn−1∗ an+ rn 0 < rn < rn−1

rn−1 = rn∗ an+1+ 0

Dato che i resti sono tutti positivi, anche i quozienti ai, ad eccezione

eventual-mente del primo, saranno positivi. Riscriviamo le equazioni dell’algoritmo euclideo dividendo la prima per b, la seconda per r1, la terza per r2,e cos`ı via

fino all’ ultima per rn. Avremo

a b = a1+ r1 b = a1+ 1 b r1 b r1 = a2+ r2 r1 = a2+ 1 r1 r2 r1 r2 = a3+ r3 r2 = a3+ 1 r2 r3 r2 r3 = a4+ r4 r3 = a4+ 1 r3 r4 ... rn−1 rn = an+1

i primi membri delle precedenti uguaglianze sono dei numeri razionali, che abbiamo scritto come somma di un intero e di una frazione con numeratore 1.

(16)

2.3 Frazioni continue semplici infinite e numeri irrazionali 13

Con eliminazioni successive si ottiene a b = a1+ 1 b r1 = a1+ 1 a2+ r11 r2

da cui si arriva all’ espressione a b = a1+ 1 a2+ 1 a3+ 1 a4+... 1 an−1+_an1 (2.12)

Abbiamo cos`ı rappresentato il numero razionale a

b come frazione continua

finita semplice. Osservazione 2.

La scrittura (2.12) non `e molto comoda dal punto di vista della notazione, quindi si preferisce indicare la stessa frazione nel modo seguente:

[a1; a2, a3, . . . , an−1, an]

ossia come successione finita dei suoi quozienti parziali. Ad esempio la frazione dell’ esempio precedente si scrive

68

15 = [4; 1, 1, 7]

Si osservi che l’intero a1 sar`a zero se e solo se la frazione `e positiva e minore di

1. Inoltre osserviamo che a1 `e il valore intero approssimante per difetto a/b,

cio`e a1 = [a/b], a2 il valore approssimante per difetto di b/r1, cio`e a2 = [b/r1],

in generale

ai =

r_i−2 ri−1

2.3 Frazioni continue semplici e numeri

irra-zionali

Abbiamo visto che ogni numero razionale ha la sua rispettiva frazione continua; questo vale anche per gli irrazionali. Questi avranno la particolarità di avere frazioni continue infinite, e poichè non possiamo usare con questi l’algoritmo di Euclide per ricavare la frazione, si utilizzerà il seguente metodo. Facciamo prima un esempio: cerchiamo la frazione continua di√2. Dato che esso è compreso tra 1 e 2 (uno è la sua parte intera) potrò scrivere:

√

2 = 1 + 1 x

(17)

per qualche numero reale x > 1. Precisamente si ricava x =√2 + 1 da cui: x =√2 + 1 = 1 + 1 x + 1 = 2 + 1 x da questa si deducono le seguenti altre:

1 x = 1 2 + 1 x = 1 2 + 1 2+1 x = · · · = _{2 +} 1 1 2+ 1 2+... 1 2+ 1 2+ 1 x

al tendere di n a infinito si ottiene: √ 2 = 1 + 1 2 + ₂₊ 11 2+ 1 2+ 1 2+...

Questo intuitivamente `e il modo di scrivere√2 come Frazione Continua. In generale, sia f un irrazionale, si ha che i convergenti qi della frazione

continua di f di ottengono cosi:

q0 = ⌊f⌋ , r0 = f − q0, e (2.13) qi = 1 ri−1 , ri = 1 ri−1 − qi , per i = 1, 2, . . . , m (2.14)

2.4 L’approssimazione di razionali mediante

i convergenti

Definiamo ora i convergenti di una frazione continua: Definizione 2.2 (Convergente di una frazione continua).

Sia [a1; a2, a3, . . . , an]una frazione continua semplice finita. La frazione

conti-nua che si ottiene troncando la frazione conticonti-nua al k-esimo quoziente parziale si chiama k-esimo convergente e si denota nel modo seguente:

Ck= [a1; a2, a3, . . . , ak], per ogni 1 ≤ k ≤ n

Si noti che Ck+1 si ottiene da Ck sostituendo ak con ak+_a1

k+1

Osservazione 3.

Ogni Ck = [a1; a2, a3, . . . , ak] `e un numero razionale quindi usiamo la

nota-zione Ck = p_qk

(18)

2.4 L’approssimazione di razionali mediante i convergenti 15

per il calcolo del numeratore pke del denominatore qk a partire dai quozienti

parziali. Chiaramente se C1 = [a1] = p_q₁1, allora p1 = a1 e q1 = 1. Inoltre, se:

C2 = [a1; a2] = a1+ 1 a2 = a1a2+ 1 a2 = p2 q2

allora p2 = a1a2+ 1 e q2 = a2. Allo stesso modo , se:

C3 = [a1; a2, a3] = a1+_a₂₊1 1 a3 = a3(a2a1+ 1) + a1 a3a2+ 1 , allora p3 = a3(a2a1+ 1) + a1 = a3p2 + a1e q3 = a3a2+ 1 = a3q2 + q1. Da

ci`o si pu`o ottenere una formula ricorsiva per il calcolo del numeratore e del denominatore di un convergente:

pk = akpk−1+ pk−2, qk = akqk−1+ qk−2 (2.15)

Da queste si ottiene, con semplici calcoli,

pkqk−1− qkpk−1= −(pk−1qk−2− qk−1pk−2)

Dato che

p2q1− q2p1 = (a1a2+ 1) · 1 − a2a1 = 1,

ne segue:

pkqk−1− qkpk−1 = (−1)k (2.16)

Da qui segue in particolare che, per ogni k = 1, . . . , n, i numeri pk e qk sono

primi tra loro. Dividendo l’ultima relazione per qkqk−1 otteniamo

pk qk − pk−1 qk−1 = (−1) k qkqk−1 , ovvero: Ck− Ck−1= (−1) k qkqk−1 (2.17) valida per ogni k ≥ 1. In modo del tutto analogo si verifica la relazione

Ck− Ck−2 = (−1) k_a

k

qkqk−2

(19)

Esempio 2.4.1.

Calcolare tutti i convergenti di 68/15. Dall’ esempio possiamo scrivere di-rettamente lo sviluppo della frazione come 68₁₅ = [4; 1, 1, 7]. Utilizzando le formule ricorsive (2.15) si ottengono i vari convergenti:

C1 = 4 1 C2 = a1a2+ 1 a2 = 5 1 C3 = a3(a2a1+ 1) + a1 a3a2+ 1 = 9 2

Una approssimazione abbastanza buona di 68/15 sar`a 9/2.

Osserviamo che i convergenti Ck di una frazione semplice continua finita

hanno carattere oscillante. Infatti vale il seguente lemma Lemma 2.4.2.

Sia a/b = [a1; a2, a3, . . . , an] una frazione continua semplice. Allora i

conver-genti verificano le seguenti propriet`a: • C1 < C3 < C5 < . . . ,

• C2 > C4 > C6 > . . . ,

• C2j > C2j−1, per ogni j ≥ 1.

Di qui si deduce che:

C1 < C3 < C5 < · · · ≤

a

b ≤ · · · < C6 < C4 < C2, (2.19) ossia i convergenti approssimano la frazione continua ma in modo oscillante, cio`e quelli con indice dispari l’approssimano per difetto, e formano una suc-cessione crescente, quelli con indice pari per eccesso e formano una successio-ne decrescente, ed ogni convergente di indice pari `e maggiore del convergente precedente.

Dimostrazione. Dalla formula (2.16) dividendo per qk−1qk otteniamo

pk qk − pk−1 qk−1 = (−1) k−1 qk−1qk Ora se k = 1 si ha p1 q1 = po qo + 1 q0q1 > po qo ⇒ p1 q1 > po qo se k = 2 si ha p2 q2 = p1 q1 − 1 q1q2 < p1 q1 con 1 q1q2 < 1 q0q1 ⇒ p2 q2 > po qo e p2 q2 > p1 q1

(20)

2.4 L’approssimazione di razionali mediante i convergenti 17

Vediamo ora il principale risultato che permette l’attacco di Wiener al sistema RSA.

Teorema 2.4.3 (Teorema di Legendre).

Sia α un razionale e sia α = [a1; a2, . . . , an] il suo sviluppo in frazione

continua semplice e ne siano Cn = pn/qn i convergenti. Se p,q sono interi

con q > 0, e se n `e un intero positivo tale che

|qα − p| < |qnα − pn|, (2.20) allora q > qn+1. Inoltre, se α − p q < |α − Cn| (2.21) allora q > qn. In altri termini, ogni convergente Cn = pn/qn approssima il

valore α meglio di qualunque frazione il cui denominatore non superi qn.

Notiamo che tale risultato `e valido anche per α irrazionale.

Dimostrazione. Supponiamo valga la (2.20) e supponiamo per assurdo che sia q < qn+1. Consideriamo il sistema

(

pnx + pn+1y = p

qnx + qn+1y = q

Usando la (2.16), si trova

y = (−1)n(pqn− qpn), x = (−1)n(qpn+1− pqn+1).

Notiamo che x 6= 0, altrimenti si avrebbe q = qn+1y ≥ qn+1, contro l’ipotesi.

Allo stesso modo, y 6= 0 altrimenti avremmo p = pnx, q = qnx e allora

|qα − p| = |x||qnα − pn| ≥ |qnα − pn|

contro la (2.20).

Verifichiamo che x e y hanno segni opposti. Sia y < 0. Allora qnx = q −

qn+1y > 0 e pertanto x > 0 perch`e qn> 0. Sia y > 0. Poich`e qn+1y ≥ qn+1 >

q si ha qnx = q − qn+1y < 0, sicch`e x < 0. Dall’andamento oscillante dei

convergenti segue subito che qnα − pn e qn+1α − pn + 1 hanno segni opposti.

Pertanto x(qnα − pn) e y(qn+1α − pn + 1) hanno lo stesso segno. Poich`e

(21)

si ha

|qα − p| = |x||qnα − pn| + |y||qn+1α − pn+1| ≥ |qnα − pn|

contro la (2.20), Ci´o prova la prima parte del teorema.

Supponiamo ora valga la (2.21) e supponiamo per assurdo che sia q < qn.

Allora si ha: q α − p q < qn|α − Cn|

cio`e la (2.20). Ma allora deve essere q ≥ qn+1 e dunque avremo qn ≥ qn+1

che contraddice la (2.15) Teorema 2.4.4.

Sia α un razionale e sia α = [a1; a2, a3, . . . , an] il suo sviluppo in frazione

continua, e ne siano Cn = pn/qn i convergenti. Se p,q sono interi primi tra

loro, con q > 0 e tali che α − p q < 1 2q2,

allora p/q `e un convergente della frazione continua [a1; a2, a3, . . . , an].

Dimostrazione. Supponiamo che p/q non sia un convergente. Possiamo tro-vare due convergenti successivi Cn, Cn+1 tali che qn ≤ q ≤ qn+1. Per il

(22)

Capitolo 3

Attacco di Wiener

3.1 Scopo dell’attacco

Ci troviamo nella situazione descritta nel primo capitolo in cui A cerca di mandare un messaggio segreto m a B, utilizzando il sistema crittografico a chiave pubblica RSA, ed in cui E cerca di intercettare e decifrare il messaggio. Quindi avremo che B sceglie due primi p e q grandi e distinti e li moltiplica tra di loro ottenendo

n = pq

detto Modulo. Viene poi scelto l’esponente di cifratura e scelto in modo che: M CD(e, ϕ(n)) = 1

dove ϕ(n) `e la funzione di Eulero che ci da l’ordine del gruppo moltiplicativo degli elementi invertibili dell’anello Zn e se si conosce la fattorizzazione di

n, ovvero in questo caso p e q, si calcola facilmente con la formula ϕ(n) = (p − 1)(q − 1). Viene poi calcolato d l’esponente di decifrazione d in modo che

de ≡ 1 mod ϕ(n) ⇒ d ≡ e−1_modϕ(n)

( si pu`o calcolare con l’algoritmo esteso di Euclide); quindi per B si avranno le seguenti chiavi:

• CHIAVE PUBBLICA: (n, e) • CHIAVE PRIVATA: d

Ora, se A vuole mandare un messaggio m a B, calcola: C = memod n

(23)

20 3. Attacco di Wiener

e manda C a B, che potr`a decifrare il messaggio grazie alla sua chiave segreta d calcolando:

m ≡ Cdmod n ≡ mdemod n.

Lo scopo dell’avversario E sarà quello di ottenere la chiave segreta d di B a partire da ciò che conosce, cioè la chiave pubblica (n, e).

3.2 Quando si pu`

o realizzare

L’attacco di Wiener con esponente di cifratura basso, come ogni altro at-tacco crittografico, si basa su una debolezza del sistema, in questo caso sarà la lunghezza dell’esponente di decifrazione o cifratura. Quindi tale attacco sarà realizzabile se l’esponente sarà scelto abbastanza piccolo. Infatti in alcu-ni casi è preferibile usare un piccolo esponente di decifrazione in quanto viene cos`ı ridotto il tempo di decriptazione. Questo si ha perchè per un modulo di lunghezza fissata, il tempo di decifrazione o cifratura è proporzionale al numero di bit dell’esponente scelto.

Uno di questi casi, in cui scegliere un esponente corto porta un vantaggio, si verifica quando c’è una grosssa differenza di potenza di calcolo tra due ap-parecchi, ad esempio quando RSA viene usato nella comunicazione tra una carta di credito e un computer. In questo caso, sarebbe preferibile per il calcolatore della carta avere un esponente in grado di ridurre i processi com-putazionali richiesti. Un altro caso si ha quando c’è una esigenza di maggiore velocità di decriptazione da parte dell’utente B, che lo porterebbe a scegliere un esponente piu piccolo.

3.3 Come funziona

In breve questo attacco utilizza principalmente tre cose: il teorema di Wiener, il teorema di Legendre e l’algoritmo delle frazioni continue.

Studieremo l’attacco relativo all’esponente di decifrazione d.

3.3.1 Teorema di Wiener e Convergenti

L’Attacco di Wiener si basa sul seguente teorema che ci da una condizione fondamentale sulla lunghezza dell’esponente di decifrazione in relazione agli altri valori n, p, q, e ci dice se `e possibile o no usare tale attacco:

Teorema 3.3.1 (Teorema di Wiener).

(24)

3.3 Come funziona 21

primi tali che q < p < 2q. Siano 1 ≤ d, e < ϕ(n) tali che ed ≡ 1 (mod ϕ(n)). Allora se

d < 1 3n

1 4

allora è possibile calcolare d in maniera efficiente, cioè è possibile rompere il sistema RSA.

Dimostrazione.

Poich`e ed ≡ 1 (mod ϕ(n)), ne segue che ∃ un intero t tale che: ed − tϕ(n) = 1

Poich`e n = pq > q2_{, si ha che q <}√_{n, quindi:}

0 < n − ϕ(n) = p + q − 1 < 2q + q − 1 < 3q < 3√n ora vediamo che:

e n − t d = ed − tn dn = 1 + t(ϕ(n) − n) dn < 3t √ n dn = 3t d√n Poich`e t < d, si ha che 3t < 3d < n14, dunque:

e n − t d < 1 dn14 Infine se 3d < n14 si ha: e n − t d < 1 3d2 < 1 2d2

Quindi per il teorema di Legendre abbiamo che e

n `e un convergente della

frazione continua di _dt e quindi, con l’algoritmo delle frazioni continue che descriveremo fra poco, saremo in grado di ricavarci d.

3.3.2 Algoritmo per il calcolo di Frazioni Continue

Abbiamo visto nel Secondo Capitolo due modi per trovare la frazione continua di un numero, quello per i razionali con l’algoritmo di Euclide e quello per gli irrazionali. Useremo qui le notazioni del secondo metodo che pu`o comunque essere utilizzato per i razionali:

(25)

la frazione continua di un numero razionale positivo f è ottenuta sottraendo-gli la sua parte intera, invertendo il resto che si ottiene e sottraendo ancora la parte intera, finchè il resto non è zero, cioè:

q0 = ⌊f⌋ , r0 = f − q0, e (3.1) qi = 1 ri−1 , ri = 1 ri−1 − qi , per i = 1, 2, . . . , m (3.2) e avremo che f = [q0; q1, q2, . . . , qn] Esempio 3.3.2. f = 68₅ = [4, 1, 1, 7] infatti: q0 = 68 15 = 4 r0 = 68 15 − 4 = 8 15 q1 = 1 r0 = 15 8 = 1 r1 = 15 8 − 1 = 7 8 q2 = 1 r1 = 8 7 = 1 r1 = 8 7 − 1 = 1 7 q3 = 1 r2 = ⌊7⌋ = 7 r3 = 0 Osservazione 4 (Propriet`a).

Riscriviamo alcune propriet`a gi`a viste per i quozienti e i convergenti, ma con una nuova notazione:

• Si ha che ∀m qm ≥ 2

• Si ha che i convergenti approssimano la frazione continua in modo oscillante, quindi per ogni x vale che:

[q0; q1, . . . , qm] < [q0; q1, . . . , qm−1, qm+ x] se m `e pari

[q0; q1, . . . , qm] > [q0; q1, . . . , qm−1, qm+ x] se m `e dispari

Osservazione 5 (Metodo per calcolare f a partire dai quozienti).

Mostriamo ora come ricostruire f a partire dalla sua frazione continua. Se ni

e di, per i = 0, 1, . . . , m, sono i numeratori e i denominatori dei convergenti

i-esimi ne seguir`a: ni

di

(26)

e si avr`a che:

n0 = q0, d0 = 1, (3.3)

n1 = q0q1+ 1, d1 = q1, (3.4)

ni = qini−1+ ni−2, di = qidi−1+ di−2 per i = 1, 2, . . . , m (3.5)

in questo modo la frazione f = nm

dm pu`o essere ricostruita.

Osservazione 6.

Ricordiamo anche la relazione

nidi−1− ni−1di = −(−1)i per i = 1, 2, . . . , m (3.6)

Andiamo ora a descrivere l’algoritmo:

sia f′ _{un convergente e una buona approssimazione di f , si ha:}

f′ _{= f (1 − δ) per qualche δ ≥ 0} _(3.7)

Siano qi, ri e qi′, r′i i quozienti parziali (che per semplicit`a chiameremo

quo-zienti) e i resti rispettvamente di f e f′_{. Se δ `e abbastanza piccolo, allora}

posso trovare il numeratore e il denominatore di f usando questo algoritmo iterativo:

si ripetono i seguenti punti fino a trovare f : 1. Vengono generati i quozienti (q′

i) dell’ espansione in frazione continua

di f′

2. Usiamo la Costruzione a partire dalla frazione continua vista prima per costruire la frazione

[q′

0, q1′, . . . , qi−1′ , qi′+ 1] se i `e pari (3.8)

[q′

0, q1′, . . . , qi−1′ , qi′] se i `e dispari (3.9)

3. Si controlla se la frazione costruita `e proprio f . Osservazione 7.

La ragione per cui si aggiunge 1, se i quozienti sono in numero pari, `e che la stima di f che andiamo a cercare deve essere maggiore di f′_{, poich`e f ≥ f}′_;

infatti per l’oscillazione dei convergenti si ha: [q′

(27)

Proposizione 3.3.3.

L’algoritmo delle frazioni continue ha successo se:

[q0; q1, . . . , qm−1, qm− 1] < f ≤ [q0; q1, . . . , qm−1, qm] se m `e pari

(3.10) [q0; q1, . . . , qm−1, qm+ 1] < f ≤ [q0; q1, . . . , qm−1, qm] se m `e dispari

(3.11) da cui equivalentemente basta che

δ < ₃ 1

2nmdm

(3.12) Dimostrazione.

Prima di tutto scriviamo δ come:

δ = 1 − f

′

f. (3.13)

Vediamo i casi m = 0, 1 ; m pari ≥ 2 e m dispari ≥ 3 Caso 1 m=0

Usando (3.10)(3.11) per sostituire f′ _{in (3.13) otteniamo:}

δ < 1 −[q0− 1] [q0] = 1 q0 = 1 n0d0 Caso 2 m=1

Come prima otteniamo:

δ < 1 − [q0; q1+ 1] [q0; q1]

= 1

(q0q1+ 1)(q1+ 1)

Sappiamo che qm ≥ 2 quindi in questo caso avremo che 3₂q1 ≥ q1 + 1

da cui:

δ < ₃ 1

2n1d1

Caso 3 m pari, m ≥ 2

Analogalmente agli altri casi otteniamo in questo caso: δ < 1 − [q0; q1, . . . , qm−1, qm− 1]

(28)

Usando (3.3) otteniamo due equivalenze: [q0; q1, . . . , qm−1, qm− 1] = (qm− 1)nm−1+ nm−2 (qm− 1)dm−1+ dm−2 [q0; q1, . . . , qm−1, qm] = qmnn−1+ nm−2 qmdm−1+ dm−2

che sostituite nella disuguaglianza danno:

δ < nm−1dm−2− nm−2dm−1

(qmnm−1+ nm−2)(qmdm−1+ dm−2− dm−1)

da cui usando le espressioni per nm e dm si ottiene:

δ < 1 nm(dm− dm−1) = 1 nmdm − 1 nmdm−1 < 1 nmdm Caso 4 m dispari, m ≥ 3

Come fatto per gli ultimi tre casi, otteniamo

δ < 1

nm(dm+ dm−1)

Poich`e dm = qmdm−1 + dm−2 e qm ≥ 2, abbiamo che dm + dm−1 ≤

(3/2)dm si ha

δ < ₃ 1

2nmdm

Osservazione 8 (Considerazioni sul tempo di esecuzione).

Se x = max(nm, dm), si pu`o dimostrare che il numero di quozienti dell’

espansione in frazione continua di f e O(log(x)). Per ogni quoziente, una approssimazione di f è generata e testata. Il tempo di calcolo per l’approssi-mazione di f è polinomiale in log(x). Se assumiamo che il test per la corret-tezza di f abbia la stessa velocità di calcolo, si avrà che questo algoritmo ha una velocità di calcolo polinomiale in log(x).

3.3.3 Algoritmo applicato a RSA e Criteri di Esattezza

Consideriamo la solita relazione tra l’esponente pubblico e e quello privato d tenendo conto che possiamo calcolare ϕ(n) = ϕ(pq) = mcm(p − 1, q − 1) da cui

(29)

da questa otteniamo che deve esistere un intero K tale che:

ed = K · mcm(p − 1, q − 1) + 1 (3.15)

ora se prendiamo G = M CD(p − 1, q − 1) e usiamo il fatto che mcm(p − 1, q − 1) = (p − 1)(q − 1)/G otteniamo:

ed = K

G(p − 1)(q − 1) + 1, (3.16)

ma `e possibile che K e G abbiano fattori comuni. Quindi definiamo k = K/M CD(K, G) e g = G/M CD(K, G) e avremo che k/g = K/G e M CD(k, g) = 1. Quindi si ha che:

ed = k

g(p − 1)(q − 1) + 1 (3.17)

e dividendo tutto per dpq otteniamo e pq = k dg(1 − δ), dove δ = p + q − 1 − gk pq (3.18)

Notare che abbiamo scritto le due frazioni come f′ _{= f (1 − δ), punto di}

partenza del nostro algoritmo e che la frazione _pqe `e formata interamente a partire da informazioni pubbliche e che `e una buona stima di k

dg.

Prima di utilizzare l’algoritmo delle frazioni continue, ricordiamo che questo algoritmo trova sempre delle frazioni ridotte ai minimi termini, quindi dal-l’equazione ed = K · mcm(p − 1, q − 1) + 1 vediamo che MCD(K, d) = 1. Poich`e k divide K, abbiamo che M CD(k, d) = 1. Anche M CD(k, g) = 1 per definizione. Quindi M CD(k, dg) = 1 e possiamo usare l’algoritmo delle frazioni continue per trovare k e dg purch`e δ sia abbastanza piccolo. Ora usando il fatto che δ < 3 1

2nmdm e che δ = p+q−1− g k pq otteniamo che: kdg < ₃ pq 2(p + q) (3.19) basta per dire che k e dg possono essere trovati. Notiamo che (−1 − g/k) non compare nell’aspressione per δ perch`e `e piccolo rispetto a (p + q). Vediamo ora come possiamo essere sicuri che i valori di k e dg siano giu-sti.

In modo da semplificare il test, assumeremo che ed > pq. Questa condizione non è una restrizione in quanto se fisso e o d, il valore atteso per l’altro sarà approssimativamente pq_G. A meno che G sia scelto molto grande, è molto

(30)

probabile che ed > pq. Dall’equazione (3.17), una conseguenza del fatto che ed > pq, `e che k > g. Riscrivendo la (3.17) come:

edg = k(p − 1)(q − 1) + g (3.20)

vediamo che dividendo edg per k otteniamo un quoziente di (p − 1)(q − 1) e un resto di g finchè k > g. Questo ci dà una stima per (p − 1)(q − 1)e per g. Se la stima di (p − 1)(q − 1) è zero, k e dg calcolati non sono quelli corretti. Questo caso va escluso. Ora, la stima per (p − 1)(q − 1) può essere usata per ottenere una stima di p+q₂ usando la seguente identità:

pq − (p − 1)(q − 1) + 1

2 =

p + q

2 . (3.21)

Se la stima di p+q₂ non `e un intero, allora le stime di k e dg sono sbagliate. Analogamente usando l’identit`a:

p + q 2 2 − pq = p − q₂ 2 (3.22) dalla stima di p+q₂ otteniamo una stima per p−q₂ 2

e se questa stima `e un quadrato perfetto, allora le stime di k e dg sono incorrette. Una volta trovati i valori esatti di k e dg possiamo scoprire l’esponente segreto d dividendo dg per g. Ricordiamo che g era il resto della divisione di edg per k. Volendo si possono anche ricavare facilmente p, q da p+q₂ ,p−q₂ .

Se non viene fatto nulla per prevenire questo attacco basato sulle frazioni continue, allora uno può aspettarsi che g sia piccolo e k < dg. Sotto questa condizione, possiamo vedere da (3.19) che un esponente segreto con circa un quarto dei bit rispetto al numero di bit del modulo, può essere trovato in tempo polinomiale. Questo attacco non può essere applicato nel caso in cui l’esponente ha un numero di bit pari al modulo. Questo perchè l’attacco si basa sulle informazioni che l’esponente pubblico ci da per poter fattoriz-zare il modulo e nel caso normale, l’esponente pubblico può essere scelto indipendentemente dal modulo.

3.3.4 Come contrastare l’attacco

Poichè è usuale scegliere un modulo di 1024 bit, ne segue che l’esponente deve essere almeno di 256 bit per evitare questo attacco. Ma questo, come abbiamo detto, non è un bene per i dispositivi con potenza di calcolo ridotta, dove la scelta di un piccolo esponente diminuiva il tempo di calcolo. Ma non tutto è perduto in quanto Wiener stesso ci da due metodi che permettono comunque una decriptazione veloce e la protezione dall’attacco :

(31)

Modo 1 Scelta di e grande: poich`e l’algoritmo calcola d se kdg < ₃ pq

2(p + q)

,

baster`a aumentare k o g per bloccarlo e ad esempio se io volessi au-mentare k basterebbe auau-mentare e poich`e abbiamo visto che

ed = k

g(p − 1)(q − 1) + 1 ⇒ k =

edg − 1 (p − 1)(q − 1)

e ci`o pu`o essere ottenuto aggiungendo ad e un multiplo di ϕ(n) e quindi lavorare con e′ _{= e + kϕ(n) con k intero.}

Modo 2 Teorema Cinese del Resto: qui utilizziamo il famoso Teorema Cinese dei Resti per velocizzare la decifrazione senza dover scegliere l’esponente d troppo piccolo. Supponiamo di aver scelto d tale che:

dp := d mod (p − 1)

dq := d mod (q − 1)

con dp e dq abbastanza piccolo, ad esempio di 128 bit, allora posso

andare a decriptare il messaggio criptato C calcolando prima: Mp ≡ Cdpmod p

Mq ≡ Cdqmod q

e usando poi il Teorema Cinese dei Resti per trovare l’unico valore M che risolve il sistema:

(

M ≡ Cdp_{mod p}

M ≡ Cdqmod q

Di positivo in questo metodo c’`e che d pu`o essere abbastanza grande anche se dp e dq non lo sono. Ma questi devono essere comunque non

troppo piccoli o sar`a possibile fattorizzare n.

3.3.5 Esempio di attacco di Wiener a RSA

Facciamo ora un esempio di questo attacco. Ho utilizzato un algoritmo e due funzioni implementati da me in Matlab (per facilitare i conti) che inserir`o

(32)

e spiegher`o passo per passo. L’utente B sceglie i numeri primi p = 2323259 e q = 3434351 ottenendo:

n = 2323259 · 3434351 = 7978886869909 ϕ(n) = 2323258 · 3434350 = 7978881112300

e sceglie come esponente pubblico e = 35943202454 e come esponente privato d = 313. Per prima cosa notiamo che le condizioni del teorema di Wiener sono rispettate infatti:

d < 1 3n

1

4 = 560.227

quindi `e possibile eseguire l’attacco. Abbiamo bisogno di due funzioni : uno per calcolare una frazione a partire dai suoi quozienti che ho chiama-to CalcoloF C, rappresentata nel seguente script:

function [ FC ,NUM,DEN ] = CalcoloFC( QUOZ ) NUM=[]; DEN=[]; L=length(QUOZ); if L==1 NUM(1)=QUOZ(1); DEN(1)=1; elseif L==2 NUM(1)=QUOZ(1); DEN(1)=1; NUM(2)=QUOZ(1)*QUOZ(2)+1; DEN(2)=QUOZ(2); else NUM(1)=QUOZ(1); DEN(1)=1; NUM(2)=QUOZ(1)*QUOZ(2)+1; DEN(2)=QUOZ(2); for i=3:1:L NUM(i)=QUOZ(i)*NUM(i-1)+NUM(i-2); DEN(i)=QUOZ(i)*DEN(i-1)+DEN(i-2); NUM(i) DEN(i) end end format rat

(33)

FC=sym(NUM(L))/sym(DEN(L)) end

in cui in input va inserito un vettore di quozienti ad esempio QU OZ = [q1, q2, q3] = [4, 56, 21]. L’algoritmo si basa sul processo iterativo (3.3) e

d`a in output la frazione relativa ai quozienti ed i numeratori e denominatori calcolati per trovarla. In questo caso la funzione d`a come risultato F C ovvero la frazione 4729₁₁₇₇ e DEN e N U M ovvero i vettori con i numeratori calcolati 4,225,4729 e i denominatori 1,56,1177.

L’altra funzione `e chiamata CalcoloQZ e calcola i quozienti a partire da una frazione, implementata nel seguente modo:

function [ q,dr,nr ] = CalcoloQZ( nf,df ) nr=[]; dr=[]; q(1)=floor(nf/df); dr(1)=df; nr(1)=nf-df*q(1); i=1; while nr(i)~=0 i=i+1; q(i)=floor(dr(i-1)/nr(i-1)); dr(i)=nr(i-1); nr(i)=dr(i-1)-q(i)*nr(i-1); end end

Questa funzione `e basata sulla formule (2.13),(2.14), prende in input il valore del numeratore nf e del denominatore della frazione df che ci interessa e d`a in output il vettore dei quozienti q, quello dei numeratori dei vari resti ottenuti nr e dei denominatori dr. Quindi mettendo in input la frazione 4729₁₁₇₇ otterremo i suoi quozienti 4, 56, 21 e i numeratori dei resti che sono 21, 1, 0 e i denominatori 1177, 21, 1.

Ora abbiamo bisogno dello script in cui è descritto l’attacco di Wiener che richiamerà più volte le funzioni descritte qui sopra:

disp(’ATTACCO DI WIENER’);

nf=input(’Inserire l ESPONENTE PUBBLICO: ’); df=input(’Inserire il MODULO: ’)

format rat

%f `e la mia frazione di partenza di cui voglio trovare i quozienti e resti,

%che usero per calcolare l’esponente privato f=nf/df;

(34)

%calcolo i quozienti e i resti della frazione nf/df [q,dr,nr ]=CalcoloQZ(nf,df);

disp(’i quozienti zono’) q

disp(’i numeratori dei resti sono’) nr

disp(’i numeratori dei resti sono’) dr

%calcolo NUM il vettore con tutti i numeratori e DEN quello con i %denominatori

[FC,NUM,DEN]=CalcoloFC(q); disp(’i numeratori sono’) NUM

disp(’i denominatori sono sono’) DEN

%ora scrivo tutte le frazioni ni/di in un vettore FCS FCS=[];

for i=1:1:length(NUM) FCS(i)=NUM(i)/DEN(i); end

disp(’tutte le frazioni n/d sono’) FCS

%PQ `e il vettore in cui inserir`o le stime di (p-1)(q-1)

PQ=[]

%troviamo i quozienti per stimare k/dg e li metto nel vettore QFC for i=1:1:length(FCS) QFC=q(:,[1:i]); if mod(i,2)~=0 QFC(i)=QFC(i)+1; end QFC

%qui calcolo una stima di k/dg cio`e KDG

[KDG,NUM,DEN]=CalcoloFC(QFC); KDG

V=length(DEN); K=NUM(V)

(35)

EDG=nf*DG PQ=fix(EDG/K)

%primo criterio di esattezza if PQ==0 continue end G=mod(EDG,K); PPQ=(df-PQ+1)/2 t=PPQ-floor(PPQ);

%secondo criterio di esattezza if t~=0

continue end

PMQ=(PPQ^2)-df;

m=sqrt(PMQ)-floor(sqrt(PMQ)); %terzo criterio di esattezza if m~=0 continue else d=DG/G break end end

Questo algoritmo chiede in input la chiave pubblica di B e va a calcolare la chiave privata di B d.

Andiamo a studiare l’algoritmo passo per passo e portiamo avanti il nostro esempio.

I numeri da inserire in input sono appunto la chiave pubblica e quindi e = 3594320245477 e n = 7978886869909 .

La prima cosa da fare `e calcolare i quozienti della frazione f = 3594320245477_{7978886869909} quindi usiamo la funzione CalcoloQZ(3594320245477, 7978886869909) e ot-teniamo i seguenti valori:

(36)

Quozienti Numeratori resti Denominatori resti

0 7978886869909 3594320245477 2 790246378955 3594320245477 4 433334729657 790246378955 1 356911649298 433334729657 1 76423080359 356911649298 4 51219327862 76423080359 1 25203752497 51219327862 2 811822868 25203752497 31 37243589 811822868 21 29707499 37243589 1 7536090 29707499 3 7099229 7536090 1 436861 7099229 16 109453 436861 3 108502 109453 1 951 108502 114 88 951 10 71 88 1 17 71 4 3 17 5 2 3 1 1 2 2 0 1

Ora attravero la funzione:

CalcoloF C([0, 2, 4, 1, 1, 4, 1, 2, 31, 21, 1, 3, 1, 16, 3, 1, 114, 10, 1, 4, 5, 1, 2])

otteniamo i vari denominatori die numeratori nidelle frazioni [0], [0, 2], [0, 2, 4] . . . .

Dopo di ci`o c’`e il ciclo f or, dove seguendo la costruzione (3.8) vengono cal-colate la varie stime di k/dg e poi usando le formule (3.21),(3.22) calcoliamo edg, g, (p+q)/2, ((p−q)/2)2 _{e verifichiamo attraverso 3 if i criteri di esattezza}

(37)

34 3. Attacco di Wiener ni/di k/dg edg g 0 1 3594320245477 0 1/2 1/2 7188640490954 0 4/9 5/11 39537522700247 2 5/11 5/11 39537522700247 2 9/20 14/31 111423927609787 9 41/91 41/91 327083142338407 38 50/111 91/202 726052689586354 39 141/313 141/313 1125022236834301 1 (p-1)(q-1) (p+q)/2 _{((p − q)/2)}2 _d 3594320245477 2192283312217 stop 7188640490954 395123189478 stop 7907504540049 35691164931 stop 7907504540049 35691164931 stop 7958851972127 10017448892 stop 7977637618009 624625951 stop 7978600984465 142942723 stop 7978881112300 2878805 308631358116 313

L’attacco ad RSA da quindi come risultato :

d = 313, p = 2323259, q = 3434351 k = 141 g = 1 infatti si ha che:

(38)

Bibliografia

[1] M. J. Wiener,Cryptanalysis of short RSA secret exponents (1990)

[2] A. Dujella,Continued Fractions and RSA whit small secret exponent, (2004)

[3] D. BonehTwenty years of attacks on the RSA cryptosystem (1999) [4] Baldoni, Ciliberto, Piacentini Cattaneo, Aritmetica, Crittografia e Codici

(2006). Springer-Verlag, Milano

[5] Douglas R. Stinson Cryptography theory and practice 3ed (2006)