Wiener támadás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. február 15-én felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A Michael J. Wiener kriptológusról elnevezett Wiener-támadás egyfajta kriptográfiai támadás az RSA algoritmus ellen . A támadás a folyamatos tört módszert használja a rendszer törésére egy kis zárt kitevővel . $d$

Röviden az RSA-ról

Mielőtt elkezdené a Wiener-támadás működésének leírását, érdemes bevezetni néhány RSA -ban használt fogalmat [1] . További részletek az RSA fő cikkében találhatók .

Az üzenetek RSA séma szerinti titkosításához nyilvános kulcsot használnak - egy számpárt , a visszafejtéshez - egy privát kulcsot . A számokat nyitott és zárt kitevőknek, a számokat modulusnak nevezzük. Modulus , ahol és két prímszám . A zárt, nyitott kitevő és a modulus közötti kapcsolatot a következőképpen adjuk meg , ahol az Euler-függvény . ${\megjelenítési stílus (e,N)}$ ${\megjelenítési stílus (d,N)}$ $e,d$ $N$ $N=pq$ $p$ $q$ $ed=1{\bmod {\varphi }}(N)$ $\varphi (N)=(p-1)(q-1)$

Ha a nyilvános kulcsot rövid időn belül vissza lehet állítani , akkor a kulcs sebezhető: miután információt kaptak a titkos kulcsról , a támadóknak lehetőségük van visszafejteni az üzenetet. ${\megjelenítési stílus (e,N)}$ $d$ ${\megjelenítési stílus (d,N)}$

Az algoritmus története

Az RSA kriptorendszert Ronald Rivest , Adi Shamir és Leonard Adleman találta fel, és először 1977-ben publikálták [1] . A cikk megjelenése óta számos kutató vizsgálta az RSA kriptorendszer sebezhetőségét. [2] A legtöbb ilyen támadás az algoritmus potenciálisan veszélyes megvalósításait használja, és kifejezett feltételeket használ az algoritmus néhány hibájára: közös modulus, kis nyilvános kulcs, kis privát kulcs [3] . Így egy kriptográfiai támadási algoritmust az RSA algoritmus ellen kis privát kulccsal javasolt Michael J. Wiener kriptológus egy 1990-ben megjelent cikkében. [4] Wiener tétele kimondja, hogy ha a kulcs kicsi, akkor a privát kulcs lineáris időben megtalálható .

Kis privát kulcs

Az RSA titkosítási rendszerben Bob kisebb értéket használhat nagy véletlenszám helyett az RSA visszafejtési teljesítményének javítására . Wiener támadása azonban azt mutatja, hogy a for számára kis érték kiválasztása bizonytalan titkosítást eredményez, amelyben a támadó vissza tudja állítani az összes titkos információt, azaz feltörheti az RSA rendszert . Ez a feltörés Wiener-tételen alapul, amely kis értékekre érvényes . Wiener bebizonyította, hogy a támadó hatékonyan meg tudja találni , amikor . $d$ $d$ $d$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Wiener néhány ellenintézkedést is bevezetett támadása ellen. A két módszert az alábbiakban ismertetjük: [5]

1. Nagy nyilvános kulcs kiválasztása :

Cserélje ki a , ahol néhány nagy . Ha elég nagy, azaz , akkor Wiener támadása nem alkalmazható, bármilyen kicsi is legyen .

e

e'

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

k

e'

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

d

2. A kínai maradéktételt használva :

Válassza ki , hogy a és , és kicsik legyenek, de nem önmaga, akkor a gyors üzenet visszafejtése a következőképpen hajtható végre:

d

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

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

d

C

Először is kiszámítja $M_{p}=C^{d_{p}}{\bmod {p}}$ $M_{q}=C^{d_{q}}{\bmod {q}}$
A kínai maradéktétel segítségével kiszámítunk egy egyedi értéket , amely kielégíti és . Az eredmény igény szerint kielégíti . A lényeg, hogy Wiener támadása itt nem alkalmazható, mert az érték nagy lehet. $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)$

Hogyan működik a Wiener-támadás

Mert a

ed=1{\pmod {\operátornév {lcm} (p-1,q-1)))))

akkor van egy egész szám : $K$

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

Érdemes az előző egyenletben meghatározni és behelyettesíteni : $G=\gcd(p-1,q-1)$

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

Ha és jelöljük , akkor az előző egyenletbe való behelyettesítés a következőt kapja: $k={\frac {K}{\gcd(K,G)))$ $g={\frac {G}{\gcd(K,G)))$

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

Ha az egyenlet mindkét oldalát elosztjuk -vel , akkor kiderül, hogy: $dpq$

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

, hol .

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

Ennek eredményeként valamivel kevesebb, mint , és az első töredék teljes egészében nyilvános információkból áll . Azonban még mindig szükség van egy módszerre egy ilyen feltételezés tesztelésére. Míg az utolsó egyenlet a következőképpen írható fel: ${\frac {e}{pq))$ ${\frac {k}{dg))$ $ed>pq$

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

Egyszerű algebrai műveletek és azonosságok segítségével megállapítható egy ilyen feltevés pontossága . [6]

Wiener-tétel

Hadd , hol . Hadd . $N=pq$ $q<p<2q$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Ha van hol , a cracker meggyógyulhat . [7] $\left\langle N,e\right\rangle$ $ed=1{\bmod {\varphi }}(N)$ $d$

Wiener-tétel bizonyítása

A bizonyítás folyamatos törteket használó közelítéseken alapul . [nyolc]

Mivel , akkor létezik , amelyre . Következésképpen: $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) } }}

Tehát ez egy közelítés . Annak ellenére, hogy a cracker nem tudja , használhatja a közelítéshez. Sőt, mert: ${\frac {k}{d))$ ${\frac {e}{\varphi (N)))$ $\varphi (N)$ $N$

$\varphi (N)=Np-q+1$ és , van: és $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))$

A helyett használva a következőket kapjuk: $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}}}}}

Ez azt jelenti . Mivel a , azt jelenti , és a végén kiderül: $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

ahol

k<d

Amióta és ezért: $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 }{4}}}}

Mivel , akkor és ez alapján azt jelenti: $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}}}}

Az (1) és (2) bekezdésből arra következtethetünk, hogy:

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

A tétel jelentése az, hogy ha a fenti feltétel teljesül, akkor megjelenik a konvergensek között a szám folytonos törtrészére . ${\frac {k}{d))$ ${\frac {e}{N))$

Ezért az algoritmus végül megtalálja az ilyeneket [9] . ${\frac {k}{d))$

Az algoritmus leírása

Nyilvános RSA kulcsot veszünk figyelembe , amellyel meg kell határozni a privát kitevőt . Ha ez ismert , akkor ez a következő [10] algoritmus szerint tehető meg : ${\megjelenítési stílus (e,N)}$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

1. Bontsa ki a törtet egy folyamatos törtté .

{\frac {e}{N))

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

2. Egy folytatólagos törthez keresse meg az összes lehetséges konvergens halmazát .

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

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

3. Fedezze fel a megfelelő frakciót :

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

3.1. Határozza meg a lehetséges értéket számítással .

\varphi (N)

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

3.2. Az egyenlet megoldása után kapjunk egy gyökérpárt .

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

(p_{n},q_{n})

4. Ha az egyenlőség igaz egy gyökpárra , akkor a zárt kitevő megtalálható .

(p_{n},q_{n})

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

{\displaystyle d=d_{n))

Ha a feltétel nem teljesül, vagy nem sikerült gyökérpárt találni , akkor meg kell vizsgálni a következő megfelelő frakciót , visszatérve a 3. lépéshez.

(p_{n},q_{n})

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

Példa az algoritmus működésére

Ez a két példa [10] egyértelműen bemutatja a privát kitevő megtalálását, ha ismert az RSA nyilvános kulcsa . $d$ ${\megjelenítési stílus (e,N)}$

RSA nyilvános kulcs esetén : $(e,N)=(1073780833.1220275921)$

táblázat: a zárt kitevő megtalálása 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	-	-	-	-
egy	1/1	1073780832	-	-	-
2	7/8	1227178094	-	-	-
3	22/25	1220205492	30763	39667	1220275921

Kiderül, hogy . Ebben a példában láthatja, hogy a kicsiség feltétele teljesül . $d=25$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\kb. 62.30074...$

RSA nyilvános kulcs esetén : $(e,N)=(1779399043.2796304957)$

táblázat: a zárt kitevő megtalálása 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	-	-	-	-
egy	1/1	1779399042	-	-	-
2	1/2	3558798085	-	-	-
3	2/3	2669098564	-	-	-
négy	5/8	2847038468	-	-	-
5	7/11	2796198496	47129	59333	2796304957

Kiderül, hogy . Ebben a példában azt is észreveheti, hogy a kicsinységi feltétel teljesül . $d=11$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\kb. 76,65224...$

Az algoritmus összetettsége

Az algoritmus bonyolultságát a konvergensek száma határozza meg a szám folytonos törtrészéhez , ami a nagyságrendű érték . Azaz a szám lineáris időben [11] visszaáll a kulcshosszból . ${\frac {e}{N))$ $O(log(n))$ $d$

Linkek

↑ 12 Rivest , 1978 .
↑ Boneh, 1999 , Bevezetés, p. egy.
↑ Coppersmith, 1996 .
↑ Wiener, 1990 .
↑ Wiener, 1990 , Combatting the Continued Fraction Attack on RSA., p. 557.
↑ Render, 2007 .
↑ Boneh, 1999 .
↑ Khaled, 2006 .
↑ Herman, 2012 , Az RSA rendszer sebezhetőségéről. Kis titkos kulcs., pp. 283-284.
↑ 2016. Kedmi 12 .
↑ Herman, 2012 , Az RSA rendszer sebezhetőségéről. Kis titkos kulcs., p. 284: "E törtek száma O(ln(n)) nagyságrendű érték, vagyis a d szám lineáris időben áll vissza."

Irodalom

Rivest R., Shamir A., Adleman L. Módszer digitális aláírások és nyilvános kulcsú kriptorendszerek megszerzésére // Az ACM kommunikációja. - 1978. - P. 120-126 .
Wiener M. Rövid RSA titkos exponensek kriptanalízise // IEEE Transactions on Information Theory. - 1990. - P. 553-558 .
Coppersmith D., Franklin M., Patarin J., Reiter M. Low-Exponent RSA with Related Messages // A kriptográfiai technikák elmélete és alkalmazása című 15. éves nemzetközi konferencia előadásai. - 1996. - P. 1-9 .
Boneh D. Húsz éves támadások az RSA kriptorendszer ellen // Az Amerikai Matematikai Társaság (AMS) közleményei. – 1999.
Dujella A. Folytatódott törtek és RSA kis titkos kitevővel // CoRR . - 2004. - P. 1-11 .
Khaled S. Mathematical Attacks on RSA Cryptosystem (angol) // Journal of Computer Science. - 2006. - P. 665-671 .
E. Wiener támadása a rövid titkos kitevők ellen // IEEE Proceedings. — 2007. (elérhetetlen link)
Sarkar S., Maitra S. Újralátogatva Wiener támadását – Új gyenge kulcsok az RSA-ban // Indian Statistical Institute. – 2008.
Justin J., Siddhart R., Sushant P., Shriket P. Az RSA tanulmányozása és a Wiener támadása elleni javasolt változat // International Journal of Computer Applications. - 2010. - P. 15-20 .
Kedmi S. Python A Wiener's Attack megvalósítása . — 2016.
Stinson D. Kriptográfia elmélete és gyakorlata . — 2e. - A CRC Press Company, 2002. - ISBN 1-58488-206-9 .
Herman O.N., Neszterenko Yu.V. Számelméleti módszerek a kriptográfiában . - 1. - ACADEMA, 2012. - ISBN 978-5-7695-6786-5 . (Orosz)