Wienerův útok

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 15. února 2019; kontroly vyžadují 8 úprav .

Wienerův útok , pojmenovaný po kryptologovi Michaelu J. Wienerovi, je typem kryptografického útoku proti algoritmu RSA . Útok používá metodu pokračujícího zlomku k rozbití systému malým uzavřeným exponentem . $d$

Krátce o RSA

Před zahájením popisu toho, jak Wienerův útok funguje, stojí za to představit některé koncepty, které se používají v RSA [1] . Další podrobnosti naleznete v hlavním článku RSA .

Pro šifrování zpráv podle schématu RSA se používá veřejný klíč - dvojice čísel , pro dešifrování - soukromý klíč . Čísla se nazývají otevřené a uzavřené exponenty, číslo se nazývá modul. Modul , kde a jsou dvě prvočísla . Souvislost mezi uzavřeným, otevřeným exponentem a modulem je dána jako , kde je Eulerova funkce . $(e,N)$ $(d,N)$ $e,d$ $N$ $N=pq$ $p$ $q$ $ed=1{\bmod {\varphi }}(N)$ $\varphi (N)=(p-1)(q-1)$

Pokud lze veřejný klíč obnovit v krátké době , pak je klíč zranitelný: po obdržení informace o soukromém klíči mají útočníci příležitost zprávu dešifrovat. $(e,N)$ $d$ $(d,N)$

Historie algoritmu

Kryptosystém RSA vynalezli Ronald Rivest , Adi Shamir a Leonard Adleman a poprvé byl publikován v roce 1977 [1] . Od zveřejnění článku byl kryptosystém RSA zkoumán kvůli zranitelnosti mnoha výzkumníků. [2] Většina těchto útoků využívá potenciálně nebezpečné implementace algoritmu a používá explicitní podmínky pro nějakou chybu v algoritmu: společný modul, malý veřejný klíč, malý soukromý klíč [3] . Kryptolog Michael J. Wiener tedy v článku poprvé publikovaném v roce 1990 navrhl kryptografický algoritmus útoku proti algoritmu RSA s malým soukromým klíčem. [4] Wienerův teorém říká, že pokud je klíč malý, lze soukromý klíč nalézt v lineárním čase .

Malý soukromý klíč

V kryptosystému RSA může Bob ke zlepšení výkonu dešifrování RSA použít spíše menší hodnotu než velké náhodné číslo . Wienerův útok však ukazuje, že volba malé hodnoty pro způsobí nezabezpečené šifrování, ve kterém může útočník obnovit všechny tajné informace, tj. prolomit systém RSA . Tento hack je založen na Wienerově teorému, který platí pro malé hodnoty . Wiener dokázal, že útočník dokáže efektivně najít , kdy . $d$ $d$ $d$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Wiener také zavedl některá protiopatření proti jeho útoku. Tyto dva způsoby jsou popsány níže: [5]

1. Výběr velkého veřejného klíče :

Nahradit za , kde pro některé velké . Když je Wienerův útok dostatečně velký, to znamená , že je nepoužitelný, bez ohledu na to, jak je malý .

E

e'

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

k

e'

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

d

2. Pomocí čínské věty o zbytku :

Vyberte tak, aby a , a byly malé, ale ne samy o sobě, pak lze rychlé dešifrování zpráv provést následovně:

d

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

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

d

C

Nejprve se počítá $M_{p}=C^{d_{p}}{\bmod {p}}$ $M_{q}=C^{d_{q}}{\bmod {q}}$
Použití čínské věty o zbytku k výpočtu jedinečné hodnoty , která splňuje a . Výsledek vyhovuje podle potřeby. Jde o to, že Wienerův útok zde není použitelný, protože hodnota může být velká. $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)$

Jak funguje Wienerův útok

Protože

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

pak existuje celé číslo takové, že: $K$

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

Stojí za to určit a dosadit v předchozí rovnici : $G=\gcd(p-1,q-1)$

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

Pokud označíme a , pak substituce do předchozí rovnice dostane: $k={\frac {K}{\gcd(K,G)))$ $g={\frac {G}{\gcd(K,G)))$

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

Vydělením obou stran rovnice číslem se ukáže, že: $dpq$

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

, kde .

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

V důsledku toho je o něco méně než a první zlomek se skládá výhradně z veřejných informací . Stále je však zapotřebí metoda pro testování takového předpokladu. Zatímco poslední rovnici lze zapsat jako: ${\frac {e}{pq))$ ${\frac {k}{dg))$ $ed>pq$

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

Pomocí jednoduchých algebraických operací a identit lze stanovit přesnost takového předpokladu. [6]

Wienerova věta

Nechte , kde . Nechte _ $N=pq$ $q<p<2q$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

Mít kde , cracker může zotavit . [7] $\left\langle N,e\right\rangle$ $ed=1{\bmod {\varphi }}(N)$ $d$

Důkaz Wienerovy věty

Důkaz je založen na aproximacích pomocí spojitých zlomků . [osm]

Od , pak existuje pro které . Tudíž: $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) } }}

Jedná se tedy o přiblížení . I když cracker nezná , může jej použít k aproximaci. Opravdu, protože: ${\frac {k}{d))$ ${\frac {e}{\varphi (N)))$ $\varphi (N)$ $N$

$\varphi (N)=Np-q+1$ a , máme: a $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))$

Použitím namísto , dostaneme: $N$ $\varphi (N)$

\left\vert {\frac {e}{N}}-{\frac {k}{d}}\right\vert =\left\vert {\frac {ed-kn}{Nd}}\ vpravo\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}}}}}

Nyní znamená . Protože , znamená , a nakonec se ukáže: $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

kde

k<d

Protože a proto: $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 }{čtyři}}}}

Protože , potom a na základě toho znamená: $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}}}}

Z (1) a (2) můžeme vyvodit, že:

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

Význam věty je, že pokud je splněna výše uvedená podmínka, objeví se mezi konvergenty pro pokračující zlomek čísla . ${\frac {k}{d))$ ${\frac {e}{N))$

Proto algoritmus nakonec takové najde [9] . ${\frac {k}{d))$

Popis algoritmu

Je uvažován veřejný RSA klíč , pomocí kterého je nutné určit privátní exponent . Pokud je známo, že , pak to lze provést podle následujícího algoritmu [10] : $(e,N)$ $d$ $d<{\frac {1}{3}}N^{\frac {1}{4}}$

1. Rozšiřte zlomek na pokračující zlomek .

{\frac {e}{N))

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

2. Pro pokračující zlomek najděte množinu všech možných konvergentů .

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

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

3. Prozkoumejte vhodnou frakci :

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

3.1. Určete možnou hodnotu výpočtem .

\varphi (N)

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

3.2. Po vyřešení rovnice získejte pár kořenů .

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

(p_{n},q_{n})

4. Je-li rovnost pravdivá pro pár kořenů , pak je uzavřený exponent nalezen .

(p_{n},q_{n})

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

{\displaystyle d=d_{n))

Pokud není podmínka splněna nebo nebylo možné najít pár kořenů , je nutné prozkoumat další vhodný zlomek a vrátit se ke kroku 3.

(p_{n},q_{n})

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

Příklad toho, jak algoritmus funguje

Tyto dva příklady [10] jasně demonstrují nalezení soukromého exponentu , pokud je znám veřejný klíč RSA . $d$ $(e,N)$

Pro veřejný klíč RSA : $(e,N)=(1073780833.1220275921)$

Tabulka: nalezení uzavřeného exponentu 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	-	-	-	-
jeden	1/1	1073780832	-	-	-
2	7/8	1227178094	-	-	-
3	22/25	1220205492	30763	39667	1220275921

Ukazuje se, že . V tomto příkladu můžete vidět, že podmínka malosti je splněna . $d=25$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\cca 62.30074...$

Pro veřejný klíč RSA : $(e,N)=(1779399043.2796304957)$

Tabulka: nalezení uzavřeného exponentu 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	-	-	-	-
jeden	1/1	1779399042	-	-	-
2	1/2	3558798085	-	-	-
3	2/3	2669098564	-	-	-
čtyři	5/8	2847038468	-	-	-
5	7/11	2796198496	47129	59333	2796304957

Ukazuje se, že . V tomto příkladu si také můžete všimnout, že podmínka malosti je splněna . $d=11$ $d<{\frac {1}{3}}N^{\frac {1}{4}}\cca 76,65224...$

Složitost algoritmu

Složitost algoritmu je určena počtem konvergentů pro pokračující zlomek čísla , což je hodnota řádu . To znamená, že číslo je obnoveno v lineárním čase [11] od délky klíče . ${\frac {e}{N))$ $O(log(n))$ $d$

Odkazy

↑ 12 Rivest , 1978 .
↑ Boneh, 1999 , Úvod, s. jeden.
↑ Coppersmith, 1996 .
↑ Wiener, 1990 .
↑ Wiener, 1990 , Boj proti pokračujícímu útoku frakcí na RSA., s. 557.
↑ Render, 2007 .
↑ Boneh, 1999 .
↑ Khaled, 2006 .
↑ Herman, 2012 , O zranitelnosti systému RSA. Malý tajný klíč., str. 283-284.
↑ 12. Kedmi , 2016 .
↑ Herman, 2012 , O zranitelnosti systému RSA. Malý tajný klíč., str. 284: "Počet těchto zlomků je hodnota v řádu O(ln(n)), to znamená, že číslo d je obnoveno v lineárním čase."

Literatura

Rivest R., Shamir A., Adleman L. Metoda získávání digitálních podpisů a kryptosystémů s veřejným klíčem // Komunikace ACM. - 1978. - S. 120-126 .
Wiener M. Kryptoanalýza krátkých tajných exponentů RSA // IEEE Transactions on Information Theory. - 1990. - S. 553-558 .
Coppersmith D., Franklin M., Patarin J., Reiter M. Low-Exponent RSA with Related Messages // Sborník z 15. výroční mezinárodní konference o teorii a aplikaci kryptografických technik. - 1996. - S. 1-9 .
Boneh D. Dvacet let útoků na kryptosystém RSA // Notices of the American Mathematical Society (AMS). — 1999.
Dujella A. Pokračující zlomky a RSA s malým tajným exponentem // CoRR . - 2004. - S. 1-11 .
Khaled S. Mathematical Attacks on RSA Cryptosystem (anglicky) // Journal of Computer Science. - 2006. - S. 665-671 .
Render E. Wiener's Attack on Short Secret Exponents // IEEE Proceedings. — 2007. (nedostupný odkaz)
Sarkar S., Maitra S. Revisiting Wiener's Attack - New Weak Keys in RSA // Indian Statistical Institute. — 2008.
Justin J., Siddhart R., Sushant P., Shriket P. Studie RSA a navrhovaná varianta proti Wienerově útoku // International Journal of Computer Applications. - 2010. - S. 15-20 .
Kedmi S. Python Implementace Wienerova útoku . — 2016.
Stinson D. Teorie a praxe kryptografie . — 2e. - A CRC Press Company, 2002. - ISBN 1-58488-206-9 .
Herman O.N., Nesterenko Yu.V. Metody teorie čísel v kryptografii . - 1. - ACADEMA, 2012. - ISBN 978-5-7695-6786-5 . (Ruština)