Atacul Wiener

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 februarie 2019; verificările necesită 8 modificări .

Atacul Wiener , numit după criptologul Michael J. Wiener, este un tip de atac criptografic împotriva algoritmului RSA . Atacul folosește metoda fracțiunii continue pentru a sparge sistemul cu un mic exponent închis . $d$

Pe scurt despre RSA

Înainte de a începe o descriere a modului în care funcționează atacul lui Wiener, merită să introduceți câteva concepte care sunt folosite în RSA [1] . Consultați articolul principal RSA pentru mai multe detalii .

Pentru a cripta mesajele conform schemei RSA , se folosește o cheie publică - o pereche de numere , pentru decriptare - o cheie privată . Numerele se numesc exponenti deschisi si respectiv inchisi, numarul se numeste modul. Modulus , unde și sunt două numere prime . Legătura dintre exponentul închis, deschis și modul este dată ca , unde este funcția Euler . $(e,N)$ $(d,N)$ $e,d$ $N$ $N=pq$ $p$ $q$ $ed=1{\bmod {\varphi }}(N)$ $\varphi (N)=(p-1)(q-1)$

Dacă cheia publică poate fi recuperată într-un timp scurt , atunci cheia este vulnerabilă: după ce au primit informații despre cheia privată , atacatorii au posibilitatea de a decripta mesajul. $(e,N)$ $d$ $(d,N)$

Istoria algoritmului

Criptosistemul RSA a fost inventat de Ronald Rivest , Adi Shamir și Leonard Adleman și publicat pentru prima dată în 1977 [1] . De la publicarea articolului, criptosistemul RSA a fost investigat pentru vulnerabilități de mulți cercetători. [2] Majoritatea acestor atacuri folosesc implementări potențial periculoase ale algoritmului și folosesc condiții explicite pentru unele defecțiuni ale algoritmului: modul comun, cheie publică mică, cheie privată mică [3] . Astfel, un algoritm de atac criptografic împotriva algoritmului RSA cu o cheie privată mică a fost propus de criptologul Michael J. Wiener într-un articol publicat pentru prima dată în 1990. [4] Teorema lui Wiener afirmă că dacă cheia este mică, atunci cheia privată poate fi găsită în timp liniar .

Cheie privată mică

În criptosistemul RSA , Bob poate folosi o valoare mai mică decât un număr mare aleatoriu pentru a îmbunătăți performanța de decriptare RSA . Totuși, atacul lui Wiener arată că alegerea unei valori mici pentru for va avea ca rezultat o criptare nesigură în care un atacator poate recupera toate informațiile secrete, adică să spargă sistemul RSA . Acest hack se bazează pe teorema lui Wiener, care este valabilă pentru valori mici ale . Wiener a dovedit că un atacator poate găsi eficient când . $d$ $d$ $d$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Wiener a introdus și câteva contramăsuri împotriva atacului său. Cele două metode sunt descrise mai jos: [5]

1. Alegerea unei chei publice mari :

Înlocuiți cu , unde pentru unele mari . Când este suficient de mare, adică , atunci atacul lui Wiener este inaplicabil, indiferent cât de mic .

e

e'

e'=e+k\cdot \varphi (N)

k

e'

e'>N^{\frac {3}{2)}

d

2. Folosind teorema chineză a restului :

Alegeți astfel încât și , și sunt mici, dar nu în sine, atunci decriptarea rapidă a mesajelor poate fi efectuată după cum urmează:

d

d_{p}=d{\bmod {(}}p-1)

d_{q}=d{\bmod {(}}q-1)

d

C

În primul rând, calculează $M_{p}=C^{d_{p}}{\bmod {p}}$ $M_{q}=C^{d_{q}}{\bmod {q}}$
Folosind teorema chineză a restului pentru a calcula o valoare unică care satisface și . Rezultatul satisface cum este necesar. Ideea este că atacul lui Wiener nu este aplicabil aici, deoarece valoarea poate fi mare. $M\in \mathbb {Z_{N}}$ $M=M_{p}{\bmod {p)}$ $M=M_{q}{\bmod {q}}$ $M$ $M=C^{d}{\bmod {N}}$ $d{\bmod {\varphi }}(N)$

Cum funcționează atacul Wiener

Pentru că

ed=1{\pmod {\operatorname {lcm} (p-1,q-1)))))

atunci există un număr întreg astfel încât: $K$

ed=K\times \operatorname {lcm} (p-1,q-1)+1

Merită determinat și înlocuit în ecuația anterioară : $G=\gcd(p-1,q-1)$

ed={\frac {K}{G}}(p-1)(q-1)+1

Dacă notăm și , atunci înlocuirea în ecuația anterioară va da: $k={\frac {K}{\gcd(K,G))}$ $g={\frac {G}{\gcd(K,G))}$

ed={\frac {k}{g}}(p-1)(q-1)+1

Împărțind ambele părți ale ecuației la , rezultă că: $dpq$

{\frac {e}{pq}}={\frac {k}{dg}}(1-\delta )

, unde .

\delta ={\frac {p+q-1-{\frac {g}{k}}}{pq}}

Ca rezultat, puțin mai puțin decât , iar prima fracțiune constă în întregime din informații publice . Cu toate acestea, este încă necesară o metodă de testare a unei astfel de ipoteze. În timp ce ultima ecuație poate fi scrisă astfel: ${\frac {e}{pq)}$ ${\frac {k}{dg)}$ $ed>pq$

edg=k(p-1)(q-1)+g

Folosind operații și identități algebrice simple , se poate stabili acuratețea unei astfel de presupuneri. [6]

Teorema lui Wiener

Să , unde . Lasă . $N=pq$ $q<p<2q$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Având unde , un cracker se poate recupera . [7] $\left\langle N,e\right\rangle$ $ed=1{\bmod {\varphi }}(N)$ $d$

Dovada teoremei lui Wiener

Dovada se bazează pe aproximări folosind fracții continue . [opt]

Din moment ce , atunci există pentru care . Prin urmare: $ed=1{\bmod {\varphi }}(N)$ ${\mathit {k)}$ $ed-k\varphi (N)=1$

\left\vert {\frac {e}{\varphi (N))} - {\frac {k}{d}}\right\vert = {\frac {1}{d\varphi (N) } }}

Deci, aceasta este o aproximare . Chiar dacă biscuitul nu știe , îl poate folosi pentru a o aproxima. Într-adevăr, pentru că: ${\frac {k}{d)}$ ${\frac {e}{\varphi (N))}$ $\varphi (N)$ $N$

$\varphi (N)=Np-q+1$ și , avem: și $p+q-1<3{\sqrt {N}}$ $\left\vert p+q-1\right\vert <3{\sqrt {N}}$ $\left\vert N+1-\varphi (N)-1\right\vert <3{\sqrt {N)}$

Folosind în loc de , obținem: $N$ $\varphi (N)$

\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kn}{Nd}}\ dreapta\vert =\stanga\vert {\frac {ed-k\varphi (N)-kN+k\varphi (N)}{Nd))\dreapta\vert

=\left\vert {\frac {1-k(N-\varphi (N))}{Nd)}\right\vert \leq \left\vert {\frac {3k{\sqrt {N} }}{Nd}}\right\vert ={\frac {3k{\sqrt {N}}}{{\sqrt {N}}{\sqrt {N}}d}}={\frac {3k}{ d{\sqrt {N}}}}}

Acum , înseamnă . Deoarece , înseamnă , și în cele din urmă rezultă: $k\varphi (N)=ed-1<ed$ $k\varphi (N)<ed$ $e<\varphi (N)$ $k\varphi (N)<ed<\varphi (N)d$

k\varphi (N)<\varphi (N)d

Unde

k<d

Din moment ce și prin urmare: $k<d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

(1)\left\vert {\frac {e}{N}} - {\frac {k}{d}}\right\vert <{\frac {1}{dN^{\frac {1} {patru}}}}

Din moment ce , atunci , și pe baza acesteia , înseamnă: $d<{\frac {1}{3}}N^{\frac {1}{4)),2d<3d$ $2d<3d<N^{\frac {1}{4}}$ $2d<N^{\frac {1}{4}}$

(2){\frac {1}{2d}}>{\frac {1}{N^{\frac {1}{4}}}}

Din (1) și (2), putem concluziona că:

{\displaystyle \left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert <{\frac {3k}{d{\sqrt {N}}}} <{\frac {1}{d\cdot 2d}}={\frac {1}{2d^{2))))

Semnificația teoremei este că, dacă condiția de mai sus este îndeplinită, atunci apare printre convergente pentru fracția continuă a numărului . ${\frac {k}{d)}$ ${\frac {e}{N)}$

Prin urmare, algoritmul va găsi în cele din urmă astfel de [9] . ${\frac {k}{d)}$

Descrierea algoritmului

Se consideră o cheie publică RSA , prin care este necesar să se determine exponentul privat . Dacă se știe că , atunci se poate face după următorul algoritm [10] : $(e,N)$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

1. Extindeți fracția într-o fracție continuă .

{\frac {e}{N)}

[a_{1},a_{2}...]

2. Pentru o fracție continuă , găsiți mulțimea tuturor convergentelor posibile .

[a_{1},a_{2}...]

{\frac {k_{n}}{d_{n}}}

3. Explorați fracția potrivită :

{\frac {k_{n}}{d_{n}}}

3.1. Determinați valoarea posibilă calculând .

\varphi (N)

f_{n}={\frac {ed_{n}-1}{k_{n}})

3.2. După ce am rezolvat ecuația , obțineți o pereche de rădăcini .

x^{2}-((N-f_{n})+1)x+N=0

(p_{n},q_{n})

4. Dacă egalitatea este adevărată pentru o pereche de rădăcini , atunci se găsește exponentul închis .

(p_{n},q_{n})

N=p_{n}\cdot q_{n)

d=d_{n)

Dacă condiția nu este îndeplinită sau nu a fost posibilă găsirea unei perechi de rădăcini , atunci este necesar să se investigheze următoarea fracție adecvată , revenind la pasul 3.

(p_{n},q_{n})

{\frac {k_{n+1}}{d_{n+1}}}

Un exemplu despre cum funcționează algoritmul

Aceste două exemple [10] demonstrează clar găsirea exponentului privat dacă cheia publică RSA este cunoscută . $d$ $(e,N)$

Pentru o cheie publică RSA : $(e,N)=(1073780833.1220275921)$

Tabel: găsirea exponentului închis d

e / N = [0, 1, 7, 3, 31, 5, 2, 12, 1, 28, 13, 2, 1, 2, 3]
n	k n / d n	phi n	p n	q n	p n q n
0	0/1	-	-	-	-
unu	1/1	1073780832	-	-	-
2	7/8	1227178094	-	-	-
3	22/25	1220205492	30763	39667	1220275921

Se dovedește că . În acest exemplu, puteți vedea că condiția de micime este îndeplinită . $d=25$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\aproximativ 62,30074...$

Pentru o cheie publică RSA : $(e,N)=(1779399043.2796304957)$

Tabel: găsirea exponentului închis d

e / N = [0, 1, 1, 1, 2, 1, 340, 2, 1, 1, 3, 2, 3, 1, 21, 188]
n	k n / d n	f n	p n	q n	p n q n
0	0/1	-	-	-	-
unu	1/1	1779399042	-	-	-
2	1/2	3558798085	-	-	-
3	2/3	2669098564	-	-	-
patru	5/8	2847038468	-	-	-
5	7/11	2796198496	47129	59333	2796304957

Se dovedește că . În acest exemplu, puteți observa, de asemenea, că condiția de micime este îndeplinită . $d=11$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\aproximativ 76,65224...$

Complexitatea algoritmului

Complexitatea algoritmului este determinată de numărul de convergente pentru fracția continuă a numărului , care este o valoare de ordinul . Adică, numărul este restaurat în timp liniar [11] din lungimea cheii . ${\frac {e}{N)}$ $O(log(n))$ $d$

Link -uri

↑ 12 Rivest , 1978 .
↑ Boneh, 1999 , Introducere, p. unu.
↑ Calămar, 1996 .
↑ Wiener, 1990 .
↑ Wiener, 1990 , Combating the Continued Fraction Attack on RSA., p. 557.
↑ Render, 2007 .
↑ Boneh, 1999 .
↑ Khaled, 2006 .
↑ Herman, 2012 , Despre vulnerabilitatea sistemului RSA. Mică cheie secretă., pp. 283-284.
↑ 12 Kedmi , 2016 .
↑ Herman, 2012 , Despre vulnerabilitatea sistemului RSA. Mică cheie secretă., p. 284: „Numărul acestor fracții este o valoare de ordinul lui O(ln(n)), adică numărul d este restaurat în timp liniar”.

Literatură

Rivest R., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems // Comunicații ale ACM. - 1978. - P. 120-126 .
Wiener M. Cryptanalysis of short RSA secret exponents // IEEE Transactions on Information Theory. - 1990. - P. 553-558 .
Coppersmith D., Franklin M., Patarin J., Reiter M. Low-Exponent RSA with Related Messages // Proceedings of the 15th annual international Conference on Theory and application of cryptographic techniques. - 1996. - P. 1-9 .
Boneh D. Twenty Years of attacks on the RSA Cryptosystem // Notices of the American Mathematical Society (AMS). — 1999.
Dujella A. Continuare fracții și RSA cu exponent secret mic // CoRR . - 2004. - P. 1-11 .
Khaled S. Atacurile matematice asupra Cryptosystem RSA (engleză) // Journal of Computer Science. - 2006. - P. 665-671 .
Redați Atacul lui E. Wiener asupra exponenților secreti scurti // Proceedings IEEE. — 2007. (link inaccesibil)
Sarkar S., Maitra S. Revizuirea atacului lui Wiener - Noi chei slabe în RSA // Institutul Indian de Statistică. — 2008.
Justin J., Siddhart R., Sushant P., Shriket P. Studiul RSA și varianta propusă împotriva atacului lui Wiener // International Journal of Computer Applications. - 2010. - P. 15-20 .
Kedmi S. Python Implementarea atacului lui Wiener . — 2016.
Stinson D. Teoria și practica criptografiei . — 2e. - A CRC Press Company, 2002. - ISBN 1-58488-206-9 .
Herman O.N., Nesterenko Yu.V. Metode teoretice ale numerelor în criptografie . - 1. - ACADEMA, 2012. - ISBN 978-5-7695-6786-5 . (Rusă)