Vídeňané útočí - Wieners attack - Wikipedia

The Wienerův útok, pojmenovaný podle kryptologa Michaela J. Wienera, je typem kryptografický útok proti RSA. Útok využívá pokračující zlomek metoda vystavení soukromého klíče d když d je malý.

Souvislosti s RSA

Fiktivní postavy Alice a Bob jsou lidé, kteří chtějí bezpečně komunikovat. Přesněji řečeno, Alice chce Bobovi poslat zprávu, kterou může číst pouze Bob. Nejprve Bob vybere dva připraví p a q. Poté vypočítá RSA modul N = pq. Tento modul RSA je zveřejněn společně s šifrování exponent E. N a E tvoří pár veřejných klíčů (e, N). Zveřejněním těchto informací může kdokoli zašifrovat zprávy Bobovi. The dešifrování exponent d splňuje ${ displaystyle ed = 1 { bmod { lambda}} (N)}$ , kde ${ displaystyle lambda (N)}$ označuje Funkce Carmichael, i když někdy ${ displaystyle varphi (N)}$ , Eulerova funkce phi, je použito (poznámka: toto je pořadí multiplikativní skupina ${ displaystyle mathbb {Z} _ {N} ^ {*}}$ , což nemusí být nutně cyklická skupina). Šifrovací exponent E a ${ displaystyle lambda (N)}$ také musí být relativně prime takže existuje modulární inverzní. The faktorizace z N a soukromý klíč d jsou drženy v tajnosti, takže jen Bob může dešifrovat zpráva. Pár soukromých klíčů označujeme jako (d, N). Šifrování zprávy M darováno ${ displaystyle C equiv M ^ {e} { bmod {N}}}$ a dešifrování šifrovacího textu ${ displaystyle C}$ darováno ${ displaystyle C ^ {d} equiv (M ^ {e}) ^ {d} equiv M ^ {(ed)} equiv M { bmod {N}}}$ (použitím Fermatova malá věta ).

Za použití Euklidovský algoritmus, lze efektivně obnovit tajný klíč d pokud někdo ví faktorizace z N. Tím, že máte tajný klíč d, lze efektivně zohlednit modul N.^[1]

Malý soukromý klíč

V RSA kryptosystém, Bob by mohl mít tendenci používat malou hodnotu d, spíše než velké náhodné číslo pro vylepšení RSA dešifrování výkon. Wienerův útok však ukazuje, že zvolit malou hodnotu pro d bude mít za následek nezabezpečený systém, ve kterém může útočník obnovit všechny tajné informace, tj. rozbít RSA Systém. Tento zlom je založen na Wienerově teorému, který platí pro malé hodnoty d. Wiener dokázal, že útočník může efektivně najít d když ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}}$ .^[2]

Wienerův článek také představil některá protiopatření proti jeho útoku, která umožňují rychlé dešifrování. Dvě techniky jsou popsány následovně.

Volba velkého veřejného klíče: Vyměnit ${ displaystyle e}$ podle ${ displaystyle e '}$ , kde ${ displaystyle e '= e + k cdot lambda (N)}$ pro některé velké z ${ displaystyle k}$ . Když ${ displaystyle e '}$ je dostatečně velký, tj. ${ displaystyle e '> N ^ { frac {3} {2}}}$ , pak nelze použít Wienerův útok bez ohledu na to, jak malý ${ displaystyle d}$ je.

Za použití Čínská věta o zbytku: Předpokládejme, že jeden si vybere d takové, že oba ${ displaystyle d_ {p} = d { bmod {(}} p-1)}$ a ${ displaystyle d_ {q} = d { bmod {(}} q-1)}$ jsou malé, ale ${ displaystyle d}$ samo o sobě není, pak půst dešifrování z ${ displaystyle C}$ lze provést následujícím způsobem:

1. Nejprve spočítejte ${ displaystyle M_ {p} equiv C ^ {d_ {p}} { bmod {p}}}$ a ${ displaystyle M_ {q} equiv C ^ {d_ {q}} { bmod {q}}}$ .
2. Použijte Čínská věta o zbytku vypočítat jedinečnou hodnotu ${ displaystyle M in mathbb {Z_ {N}}}$ který uspokojuje ${ displaystyle M equiv M_ {p} { bmod {p}}}$ a ${ displaystyle M equiv M_ {q} { bmod {q}}}$ . Výsledek ${ displaystyle M}$ splňuje ${ displaystyle M equiv C ^ {d} { bmod {N}}}$ podle potřeby. Jde o to, že Wienerův útok zde neplatí, protože jeho hodnota je ${ displaystyle d { bmod { lambda}} (N)}$ může být velký.^[3]

Jak funguje Wienerův útok

Všimněte si, že

{ displaystyle lambda (N) = operatorname {lcm} (p-1, q-1) = { frac {(p-1) (q-1)} {G}} = { frac { varphi (N)} {G}}}

kde ${ displaystyle G = gcd (p-1, q-1)}$

Od té doby

{ displaystyle ed equiv 1 { pmod { lambda (N)}}}

,

existuje celé číslo K. takhle

{ displaystyle ed = K krát lambda (N) +1}

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

Definování ${ displaystyle k = { frac {K} { gcd (K, G)}}}$ a ${ displaystyle g = { frac {G} { gcd (K, G)}}}$ a dosazením do výše uvedeného získáte:

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

.

Děleno ${ displaystyle dpq}$ :

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

, kde

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

.

Tak, ${ displaystyle { frac {e} {pq}}}$ je o něco menší než ${ displaystyle { frac {k} {dg}}}$ a první je složen výhradně z veřejnosti informace. Stále je však nutná metoda kontroly a odhadu. Za předpokladu, že ${ displaystyle ed> pq}$ (rozumný předpoklad, pokud ${ displaystyle G}$ je velká) poslední výše uvedená rovnice může být zapsána jako:

{ displaystyle edg = k (p-1) (q-1) + g}

Pomocí jednoduchých algebraický manipulace a identity, lze zkontrolovat odhad přesnost.^[1]

Wienerova věta

Nechat ${ displaystyle N = pq}$ s ${ displaystyle q$ . Nechat ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}}$ .
Dáno ${ displaystyle left langle N, e right rangle}$ s ${ displaystyle ed equiv 1 ( mathrm {mod} lambda (N))}$ se může útočník efektivně zotavit ${ displaystyle d}$ .^[2]

Příklad

Předpokládejme, že jsou veřejné klíče ${ displaystyle left langle N, e right rangle = left langle 90581,17993 right rangle}$
Útok určí ${ displaystyle d}$ .
Použitím Wienerovy věty a pokračující zlomky přiblížit ${ displaystyle d}$ Nejprve se pokusíme najít pokračující zlomky expanze ${ displaystyle { frac {e} {N}}}$ . Všimněte si, že tento algoritmus najde zlomky v jejich nejnižších termínech. Víme to

{ displaystyle { frac {e} {N}} = { frac {17993} {90581}} = { cfrac {1} {5 + { cfrac {1} {29+ dots + { cfrac { 1} {3}}}}}} = doleva [0,5,29,4,1,3,2,4,3 doprava]}

Podle pokračující zlomky expanze ${ displaystyle { frac {e} {N}}}$ , všechny konvergenty ${ displaystyle { frac {k} {d}}}$ jsou:

{ displaystyle { frac {k} {d}} = 0, { frac {1} {5}}, { frac {29} {146}}, { frac {117} {589}}, { frac {146} {735}}, { frac {555} {2794}}, { frac {1256} {6323}}, { frac {5579} {28086}}, { frac {17993} { 90581}}}

Můžeme ověřit, že první konvergentní neprodukuje faktorizaci ${ displaystyle N}$ . Konvergentní ${ displaystyle { frac {1} {5}}}$ výnosy

{ displaystyle varphi (N) = { frac {ed-1} {k}} = { frac {17993 krát 5-1} {1}} = 89964}

Teď, když vyřešíme rovnici

{ displaystyle x ^ {2} - left ( left (N- varphi (N) right) +1 right) x + N = 0}

{ displaystyle x ^ {2} - left ( left (90581-89964 right) +1 right) x + 90581 = 0}

{ displaystyle x ^ {2} -618x + 90581 = 0}

pak najdeme kořeny což jsou ${ displaystyle x = 379; 239}$ . Proto jsme našli faktorizaci

{ displaystyle N = 90581 = 379 krát 239 = p krát q}

.

Všimněte si, že pro modul ${ displaystyle N = 90581}$ , Wienerova věta bude fungovat, pokud

{ displaystyle d <{ frac {N ^ { frac {1} {4}}} {3}} přibližně 5,7828}

.

Důkaz Wienerovy věty

Důkaz je založen na aproximacích s použitím pokračujících zlomků.^[2]^[4]
Od té doby ${ displaystyle ed = 1 { bmod { lambda}} (N)}$ , existuje a ${ displaystyle { mathit {k}}}$ takhle ${ displaystyle ed-k lambda (N) = 1}$ . Proto

{ displaystyle left | { frac {e} { lambda (N)}} - { frac {k} {d}} right vert = { frac {1} {d lambda (N)} }}

.

Nechat ${ displaystyle G = gcd (p-1, q-1)}$ Všimněte si, že pokud ${ displaystyle varphi (N)}$ se používá místo ${ displaystyle lambda (N)}$ , pak lze důkaz nahradit ${ displaystyle G = 1}$ a ${ displaystyle varphi (N)}$ nahrazeno ${ displaystyle lambda (N)}$ .

Poté vynásobte ${ displaystyle { frac {1} {G}}}$ ,

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

Proto, ${ displaystyle { frac {k} {Gd}}}$ je aproximace ${ displaystyle { frac {e} { varphi (N)}}}$ . Ačkoli útočník neví ${ displaystyle varphi (N)}$ , může použít ${ displaystyle N}$ přiblížit to. Opravdu, protože

${ displaystyle varphi (N) = N-p-q + 1}$ a ${ displaystyle p + q-1 <3 { sqrt {N}}}$ , my máme:

{ displaystyle left vert p + q-1 right vert <3 { sqrt {N}}}

{ displaystyle left vert N- varphi (N) right vert <3 { sqrt {N}}}

Použitím ${ displaystyle N}$ namísto ${ displaystyle varphi (N)}$ získáváme:

{ displaystyle left vert { frac {e} {N}} - { frac {k} {Gd}} right vert = left vert { frac {edG-kN} {NGd}} vpravo vert}

{ displaystyle qquad = left vert { frac {edG-k varphi (N) -kN + k varphi (N)} {NGd}} right vert}

{ displaystyle = left vert { frac {1-k (N- varphi (N))} {NGd}} right vert}

{ displaystyle leq left vert { frac {3k { sqrt {N}}} {NGd}} right vert = { frac {3k { sqrt {N}}} {{ sqrt {N }} { sqrt {N}} Gd}} leq { frac {3k} {d { sqrt {N}}}}}

Nyní, ${ displaystyle k lambda (N) = ed-1$ , tak ${ displaystyle k lambda (N)$ . Od té doby ${ displaystyle e < lambda (N)}$ , tak ${ Displaystyle k lambda (N)$ , pak získáme:

{ displaystyle k lambda (N) < lambda (N) d}

{ displaystyle k

Od té doby ${ displaystyle k$ a ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}}$ Získáváme tedy:

(1)

{ displaystyle left vert { frac {e} {N}} - { frac {k} {Gd}} right vert leq { frac {1} {dN ^ { frac {1} { 4}}}}}

Od té doby ${ displaystyle d <{ frac {1} {3}} N ^ { frac {1} {4}}, 2d <3d,}$ pak ${ displaystyle 2d <3d$ , získáváme:

{ displaystyle 2d

, takže (2)

{ displaystyle { frac {1} {2d}}> { frac {1} {N ^ { frac {1} {4}}}}}

Z (1) a (2) to můžeme vyvodit

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

Li ${ displaystyle left vert x - { frac {a} {b}} pravý vert <{ frac {1} {2b ^ {2}}}}$ , pak ${ displaystyle { frac {a} {b}}}$ je konvergentní z ${ displaystyle x}$ , tím pádem ${ displaystyle { frac {k} {d}}}$ se objevuje mezi konvergenty ${ displaystyle { frac {e} {N}}}$ . Algoritmus tedy nakonec nakonec najde ${ displaystyle { frac {k} {Gd}}}$ .