Wiener-hyökkäys

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. helmikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .

Wiener-hyökkäys , joka on nimetty kryptologi Michael J. Wienerin mukaan, on eräänlainen kryptografinen hyökkäys RSA-algoritmia vastaan . Hyökkäys käyttää jatkuvan murto -osan menetelmää järjestelmän katkaisemiseen pienellä suljetulla eksponentilla . $d$

Lyhyesti RSA:sta

Ennen kuin aloitat kuvauksen Wienerin hyökkäyksen toiminnasta, kannattaa esitellä joitakin RSA :ssa käytettyjä käsitteitä [1] . Katso lisätietoja RSA :n pääartikkelista .

Viestien salaamiseen RSA -kaavan mukaisesti käytetään julkista avainta - numeroparia , salauksen purkamiseen - yksityistä avainta . Lukuja kutsutaan avoimiksi ja suljetuiksi eksponenteiksi, lukua kutsutaan moduuliksi. Modulus , jossa ja ovat kaksi alkulukua . Suljetun, avoimen eksponentin ja moduulin välinen yhteys annetaan muodossa , jossa on Euler-funktio . ${\näyttötyyli (e,N)}$ ${\näyttötyyli (d,N)}$ ${\näyttötyyli e,d}$ $N$ $N = pq$ $s$ $q$ $ed=1{\bmod {\varphi }}(N)$ $\varphi (N)=(p-1)(q-1)$

Jos julkinen avain voidaan palauttaa lyhyessä ajassa , avain on haavoittuvainen: saatuaan tiedon yksityisestä avaimesta hyökkääjät voivat purkaa viestin salauksen. ${\näyttötyyli (e,N)}$ $d$ ${\näyttötyyli (d,N)}$

Algoritmin historia

RSA-salausjärjestelmän keksivät Ronald Rivest , Adi Shamir ja Leonard Adleman , ja se julkaistiin ensimmäisen kerran vuonna 1977 [1] . Artikkelin julkaisun jälkeen monet tutkijat ovat tutkineet RSA-salausjärjestelmän haavoittuvuuksia. [2] Useimmat näistä hyökkäyksistä käyttävät algoritmin mahdollisesti vaarallisia toteutuksia ja käyttävät eksplisiittisiä ehtoja jollekin algoritmin puutteelle: yhteinen moduuli, pieni julkinen avain, pieni yksityinen avain [3] . Siten kryptografinen hyökkäysalgoritmi RSA-algoritmia vastaan pienellä yksityisellä avaimella ehdotti kryptologi Michael J. Wiener artikkelissa, joka julkaistiin ensimmäisen kerran vuonna 1990. [4] Wienerin lause sanoo, että jos avain on pieni, niin yksityinen avain löytyy lineaarisessa ajassa .

Pieni yksityinen avain

RSA - salausjärjestelmässä Bob voi käyttää pienempää arvoa suuren satunnaisluvun sijaan parantaakseen RSA -salauksen purkamista . Wienerin hyökkäys kuitenkin osoittaa, että pienen arvon valitseminen for:lle johtaa epävarmaan salaukseen, jossa hyökkääjä voi palauttaa kaikki salaiset tiedot, eli rikkoa RSA -järjestelmän . Tämä hakkerointi perustuu Wienerin lauseeseen, joka pätee pienille arvoille . Wiener osoitti, että hyökkääjä voi löytää tehokkaasti milloin . $d$ $d$ $d$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Wiener esitteli myös vastatoimia hyökkäystään vastaan. Nämä kaksi menetelmää kuvataan alla: [5]

1. Suuren julkisen avaimen valitseminen :

Korvaa , jossa joillekin suurille . Kun se on riittävän suuri , niin Wienerin hyökkäystä ei voida soveltaa vaikka kuinka pieni tahansa .

e

e'

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

k

e'

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

d

2. Kiinan jäännöslauseen avulla :

Valitse niin, että ja , ja ovat pieniä, mutta ei itseään, niin nopea viestin salauksen purku voidaan suorittaa seuraavasti:

d

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

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

d

C

Ensin se laskee $M_{p}=C^{d_{p}}{\bmod {p}}$ $M_{q}=C^{d_{q}}{\bmod {q}}$
Laskemalla kiinalaisen jäännöslauseen avulla yksilöllinen arvo , joka täyttää ja . Tulos tyydyttää tarpeen mukaan. Asia on siinä, että Wienerin hyökkäys ei sovellu tähän, koska arvo voi olla suuri. $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)$

Kuinka Wiener-hyökkäys toimii

Koska

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

sitten on sellainen kokonaisluku : $K$

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

Kannattaa määrittää ja korvata edellisessä yhtälössä : $G=\gcd(p-1,q-1)$

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

Jos merkitsemme ja , korvaus edelliseen yhtälöön antaa: $k={\frac {K}{\gcd(K,G)))$ $g={\frac {G}{\gcd(K,G)))$

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

Jakamalla yhtälön molemmat puolet luvulla , käy ilmi, että: $dpq$

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

, missä .

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

Tämän seurauksena hieman vähemmän kuin , ja ensimmäinen murto-osa koostuu kokonaan julkisesta tiedosta . Menetelmää tällaisen oletuksen testaamiseksi tarvitaan kuitenkin edelleen. Kun taas viimeinen yhtälö voidaan kirjoittaa seuraavasti: ${\frac {e}{pq))$ ${\frac {k}{dg))$ $ed>pq$

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

Käyttämällä yksinkertaisia algebrallisia operaatioita ja identiteettejä voidaan määrittää tällaisen oletuksen tarkkuus . [6]

Wienerin lause

Anna , missä . Anna . $N = pq$ $q<p<2q$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Ottaa missä , krakkausyksikkö voi toipua . [7] $\left\langle N,e\right\rangle$ $ed=1{\bmod {\varphi }}(N)$ $d$

Todistus Wienerin lauseesta

Todistus perustuu likiarvoihin käyttämällä jatkuvia murtolukuja . [kahdeksan]

Koska , sitten on olemassa jolle . Näin ollen: $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) } }}

Tämä on siis likiarvo . Vaikka krakkausyksikkö ei tiedä , hän voi käyttää sitä arvioimaan sitä. Todellakin, koska: ${\frac {k}{d))$ ${\frac {e}{\varphi (N)))$ $\varphi (N)$ $N$

$\varphi (N)=Np-q+1$ ja , meillä on: ja $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))$

Käyttämällä sen sijaan , saamme: $N$ $\varphi (N)$

\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kn}{Nd}}\ right\vert =\left\vert {\frac {ed-k\varphi (N)-kN+k\varphi (N)}{Nd))\right\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}}}}}

Nyt tarkoittaa . Koska , tarkoittaa , ja lopulta käy ilmi: $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

missä

k<d

Siitä lähtien ja siksi: $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 }{neljä}}}}

Koska , silloin ja tämän perusteella tarkoittaa: $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}}}}

(1) ja (2) perusteella voimme päätellä, että:

{\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))))

Lauseen tarkoitus on, että jos yllä oleva ehto täyttyy, niin esiintyy luvun jatkuvan murto-osan konvergenttien joukossa . ${\frac {k}{d))$ ${\frac {e}{N))$

Siksi algoritmi löytää lopulta sellaisen [9] . ${\frac {k}{d))$

Algoritmin kuvaus

Tarkastellaan julkista RSA - avainta , jolla on tarpeen määrittää yksityinen eksponentti . Jos se tiedetään , niin se voidaan tehdä seuraavan algoritmin [10] mukaan : ${\näyttötyyli (e,N)}$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

1. Laajenna murto-osa jatkuvaksi jakeeksi .

{\frac {e}{N))

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

2. Etsi jatkuvalle murtoluvulle kaikkien mahdollisten konvergenttien joukko .

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

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

3. Tutki sopivaa fraktiota :

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

3.1. Määritä mahdollinen arvo laskemalla .

\varphi (N)

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

3.2. Kun olet ratkaissut yhtälön , hanki juurpari .

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

(p_{n},q_{n})

4. Jos yhtälö on tosi juurparille , niin suljettu eksponentti löytyy .

(p_{n},q_{n})

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

{\näyttötyyli d=d_{n))

Jos ehto ei täyty tai juurparia ei voitu löytää , on tarpeen tutkia seuraava sopiva murto palaamalla vaiheeseen 3.

(p_{n},q_{n})

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

Esimerkki algoritmin toiminnasta

Nämä kaksi esimerkkiä [10] osoittavat selvästi yksityisen eksponentin löytämisen, jos RSA :n julkinen avain tunnetaan . $d$ ${\näyttötyyli (e,N)}$

Julkiselle RSA - avaimelle : $(e,N)=(1073780833.1220275921)$

Taulukko: suljetun eksponentin löytäminen 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	-	-	-	-
yksi	1/1	1073780832	-	-	-
2	7/8	1227178094	-	-	-
3	22/25	1220205492	30763	39667	1220275921

Siitä käy ilmi . Tässä esimerkissä voit nähdä, että pienuusehto täyttyy . $d=25$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\noin 62.30074...$

Julkiselle RSA - avaimelle : $(e,N)=(1779399043.2796304957)$

Taulukko: suljetun eksponentin löytäminen 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	-	-	-	-
yksi	1/1	1779399042	-	-	-
2	1/2	3558798085	-	-	-
3	2/3	2669098564	-	-	-
neljä	5/8	2847038468	-	-	-
5	7/11	2796198496	47129	59333	2796304957

Siitä käy ilmi . Tässä esimerkissä voit myös huomata, että pienuusehto täyttyy . $d=11$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\noin 76.65224...$

Algoritmin monimutkaisuus

Algoritmin monimutkaisuus määräytyy luvun jatkuvan murto-osan konvergenttien lukumäärän mukaan, joka on suuruusluokkaa oleva arvo . Eli numero palautetaan lineaarisessa ajassa [11] avaimen pituudesta . ${\frac {e}{N))$ $O(log(n))$ $d$

Linkit

↑ 12 Rivest , 1978 .
↑ Boneh, 1999 , Johdanto, s. yksi.
↑ Coppersmith, 1996 .
↑ Wiener, 1990 .
↑ Wiener, 1990 , Combatting the Continued Fraction Attack on RSA., s. 557.
↑ Renderöinti, 2007 .
↑ Boneh, 1999 .
↑ Khaled, 2006 .
↑ Herman, 2012 , RSA-järjestelmän haavoittuvuudesta. Pieni salainen avain, ss. 283-284.
↑ 12 Kedmi , 2016 .
↑ Herman, 2012 , RSA-järjestelmän haavoittuvuudesta. Pieni salainen avain., s. 284: "Näiden murto-osien lukumäärä on O(ln(n)) suuruusluokkaa oleva arvo, eli luku d palautetaan lineaarisessa ajassa."

Kirjallisuus

Rivest R., Shamir A., Adleman L. Menetelmä digitaalisten allekirjoitusten ja julkisen avaimen salausjärjestelmien hankkimiseksi // ACM:n viestintä. - 1978. - S. 120-126 .
Wiener M. Lyhyiden RSA-salaisten eksponentien kryptaanalyysi // IEEE Transactions on Information Theory. - 1990. - S. 553-558 .
Coppersmith D., Franklin M., Patarin J., Reiter M. Low-Exponent RSA with Related Messages // Proceedings of the 15. vuosittainen kansainvälinen konferenssi teoriasta ja kryptografisten tekniikoiden soveltamisesta. - 1996. - s. 1-9 .
Boneh D. Kaksikymmentä vuotta hyökkäyksiä RSA:n salausjärjestelmää vastaan // Notices of the American Mathematical Society (AMS). – 1999.
Dujella A. Jatketut murtoluvut ja RSA pienellä salaisen eksponentin kanssa // CoRR . - 2004. - s. 1-11 .
Khaled S. Matemaattiset hyökkäykset RSA:n salausjärjestelmään (englanniksi) // Journal of Computer Science. - 2006. - S. 665-671 .
Renderöi E. Wienerin hyökkäys lyhyitä salaisia eksponenteja vastaan // IEEE Proceedings. — 2007. (linkki ei käytettävissä)
Sarkar S., Maitra S. Wienerin hyökkäys - uudet heikot avaimet RSA:ssa // Indian Statistical Institute. – 2008.
Justin J., Siddhart R., Sushant P., Shriket P. Tutkimus RSA:sta ja ehdotetusta vaihtoehdosta Wienerin hyökkäystä vastaan // International Journal of Computer Applications. - 2010. - s. 15-20 .
Kedmi S. Python Wienerin hyökkäyksen toteutus . – 2016.
Stinson D. Kryptografian teoria ja käytäntö . – 2e. - A CRC Press Company, 2002. - ISBN 1-58488-206-9 .
Herman O.N., Nesterenko Yu.V. Numeroteoreettiset menetelmät kryptografiassa . - 1. - ACADEMA, 2012. - ISBN 978-5-7695-6786-5 . (Venäjän kieli)