Coppersmiths útok - Coppersmiths attack - Wikipedia

Coppersmithův útok popisuje třídu kryptografické útoky na kryptosystém veřejného klíče RSA založeno na Coppermithova metoda. Mezi konkrétní aplikace metody Coppersmith pro útok na RSA patří případy, kdy je veřejný exponent E je malá nebo pokud je k dispozici částečná znalost tajného klíče.

Základy RSA

Veřejný klíč v systému RSA je n-tice celá čísla ${ displaystyle (N, e)}$, kde N je produktem dvou prvočísel p a q. Tajný klíč je dán celým číslem d uspokojující ${ displaystyle ed equiv 1 { pmod {(p-1) (q-1)}}}$; ekvivalentně může být tajný klíč dán ${ displaystyle d_ {p} equiv d { pmod {p-1}}}$ a ${ displaystyle d_ {q} equiv d { pmod {q-1}}}$ pokud Čínská věta o zbytku se používá ke zlepšení rychlosti dešifrování, viz CRT-RSA. Šifrování a zpráva M vyrábí šifrový text ${ displaystyle C equiv M ^ {e} { pmod {N}}}$ které lze dešifrovat pomocí ${ displaystyle d}$ výpočtem ${ displaystyle C ^ {d} equiv M { pmod {N}}}$.

Nízký veřejný exponent

S cílem snížit šifrování nebo podpis -ověření je užitečné použít malou veřejnost exponent (${ displaystyle e}$). V praxi běžná volba pro ${ displaystyle e}$ jsou 3, 17 a 65537 ${ displaystyle (2 ^ {16} +1)}$. Tyto hodnoty pro E jsou Fermat připraví, někdy označované jako ${ displaystyle F_ {0}, F_ {2}}$ a ${ displaystyle F_ {4}}$ resp ${ displaystyle (F_ {x} = 2 ^ {2 ^ {x}} + 1)}$. Jsou vybráni, protože dělají modulární umocňování provoz rychlejší. Také, když jsem si vybral takové ${ displaystyle e}$, je jednodušší vyzkoušet, zda ${ displaystyle gcd (e, p-1) = 1}$ a ${ displaystyle gcd (e, q-1) = 1}$ při generování a testování prvočísel v kroku 1 generace klíčů. Hodnoty ${ displaystyle p}$ nebo ${ displaystyle q}$ že tento test nevyhoví, může být odmítnut tam a poté. (Ještě lepší: pokud E je prvočíslo a větší než 2 než test ${ displaystyle p , { bmod {,}} e neq 1}$ může nahradit nákladnější test ${ displaystyle gcd (p-1, e) = 1}$.)

Pokud je veřejný exponent malý a prostý text ${ displaystyle m}$ je velmi krátká, pak může být snadné invertovat funkci RSA, což umožňuje určité útoky.Vycpávková schémata zajistit, aby zprávy měly plnou délku, ale navíc si zvolily veřejného exponenta ${ displaystyle e = 2 ^ {16} +1}$ je doporučeno. Když se použije tato hodnota, vyžaduje ověření podpisu 17 násobení, na rozdíl od asi 25 při náhodném výběru ${ displaystyle e}$ používá se podobné velikosti. Na rozdíl od nízkého soukromého exponenta (viz Wienerův útok ), útoky, které platí, když jsou malé ${ displaystyle e}$ používá se zdaleka ne celkem přestávka který by získal tajný klíč dNejvýkonnější útoky na málo veřejného exponenta RSA jsou založeny na následující větě, která je způsobena Don Coppersmith.

Coppermithova metoda

Věta 1 (Coppersmith)^[1]

Nechat N být celé číslo a ${ displaystyle f in { mathbb {Z}} [x]}$ být monický polynom stupně ${ displaystyle d}$ přes celá čísla. Soubor ${ displaystyle X = N ^ {{ frac {1} {d}} - epsilon}}$ pro ${ displaystyle { frac {1} {d}}> epsilon> 0}$. Pak, vzhledem k tomu ${ displaystyle left langle N, f right rangle}$ Útočník, Eva, dokáže efektivně najít všechna celá čísla ${ displaystyle x_ {0}$ uspokojující ${ displaystyle f (x_ {0}) equiv 0 { pmod {N}}}$. The provozní doba dominuje čas potřebný ke spuštění Algoritmus LLL na mříž z dimenze Ó${ displaystyle (w)}$ s ${ displaystyle w = { rm {min}} left {{ frac {1} { epsilon}}, log _ {2} N right }}$.

Tato věta uvádí existenci algoritmus který dokáže efektivně najít vše kořeny z ${ displaystyle f}$ modulo ${ displaystyle N}$ které jsou menší než ${ displaystyle X = N ^ { frac {1} {d}}}$. Tak jako ${ displaystyle X}$ zmenší, runtime algoritmu se sníží. Silnou stránkou této věty je schopnost najít všechny malé kořeny polynomů modulo kompozit ${ displaystyle N}$.

Håstadův vysílací útok

Nejjednodušší forma útoku Håstad^[2] je uveden pro usnadnění porozumění. Obecný případ používá metodu Coppersmith.

Předpokládejme, že jeden odesílatel pošle stejnou zprávu ${ displaystyle M}$ v šifrované formě pro řadu lidí ${ displaystyle P_ {1}; P_ {2}; tečky; P_ {k}}$, z nichž každý používá stejný malý veřejný exponent ${ displaystyle e}$, řekněme ${ displaystyle e = 3}$a různé moduly ${ displaystyle left langle N_ {i}, e right rangle}$. Jednoduchý argument ukazuje, že jakmile ${ displaystyle k geq 3}$ šifrovací texty jsou známé, zpráva ${ displaystyle M}$ již není zabezpečený: Předpokládejme, že Eva zachytí ${ displaystyle C_ {1}, C_ {2}}$, a ${ displaystyle C_ {3}}$, kde ${ displaystyle C_ {i} equiv M ^ {3} { pmod {N_ {i}}}}$. Můžeme předpokládat ${ displaystyle gcd (N_ {i}, N_ {j}) = 1}$ pro všechny ${ displaystyle i, j}$ (jinak je možné vypočítat a faktor jednoho z ${ displaystyle N_ {i}}$Výpočetní technikou ${ displaystyle gcd (N_ {i}, N_ {j})}$.) Podle Čínská věta o zbytku, může počítat ${ displaystyle C in mathbb {Z} _ {N_ {1} N_ {2} N_ {3}} ^ {*}}$ takhle ${ displaystyle C equiv C_ {i} { pmod {N_ {i}}}}$. Pak ${ displaystyle C equiv M ^ {3} { pmod {N_ {1} N_ {2} N_ {3}}}}$ ; od té doby ${ displaystyle M$ pro všechny ${ displaystyle i}$', my máme ${ displaystyle M ^ {3}$. Tím pádem ${ displaystyle C = M ^ {3}}$ drží nad celými čísly a Eva může vypočítat třetí odmocnina z ${ displaystyle C}$ získat ${ displaystyle M}$.

Pro větší hodnoty ${ displaystyle e}$ je zapotřebí více šifrovacích textů, ${ displaystyle e}$ šifrovací texty jsou dostatečné.

Zobecnění

Håstad také ukázal, že použití a lineární -polstrování na ${ displaystyle M}$ před šifrováním nechrání před tímto útokem. Předpokládejme, že se to útočník dozví ${ displaystyle C_ {i} = f_ {i} (M) ^ {e}}$ pro ${ displaystyle 1 leq i leq k}$ a některé lineární funkce ${ displaystyle f_ {i}}$, tj. Bob použije a podložka do zpráva ${ displaystyle M}$ před šifrování tak, aby příjemci dostávali mírně odlišné zprávy. Například pokud ${ displaystyle M}$ je ${ displaystyle m}$ Bob dlouhý, možná zašifrovat ${ displaystyle M_ {i} = i2 ^ {m} + M}$ a pošlete to do ${ displaystyle i}$-tý příjemce.

Pokud je zapojena dostatečně velká skupina lidí, může útočník obnovit prostý text ${ displaystyle M_ {i}}$ ze všech šifrový text podobnými metodami. Obecněji Håstad dokázal, že systém univariate rovnice modulo relativně prime kompozity, jako je použití jakýchkoli pevných polynomiální ${ displaystyle g_ {i} (M) equiv 0 { pmod {N_ {i}}}}$, by mohl být vyřešen, pokud dostatečně mnoho rovnice jsou poskytovány. Tento Záchvat naznačuje, že randomizované polstrování by měl být použit v Šifrování RSA.

Věta 2 (Håstad)

Předpokládat ${ displaystyle N_ {1}, tečky, N_ {k}}$ jsou relativně prime celá čísla a nastavit ${ displaystyle N _ { rm {min}} = { rm {min}} _ {i} {N_ {i} }}$. Nechat ${ displaystyle g_ {i} (x) v mathbb {Z} / N_ {i} doleva [x doprava]}$ být ${ displaystyle k}$ polynomy maxima stupeň ${ displaystyle q}$. Předpokládejme, že existuje jedinečný ${ displaystyle M$ uspokojující ${ displaystyle g_ {i} (M) equiv 0 { pmod {N_ {i}}}}$ pro všechny ${ displaystyle i in left {1, dots, k right }}$. Dále předpokládejme ${ displaystyle k> q}$. Existuje efektivní algoritmus který, vzhledem k tomu ${ displaystyle left langle N_ {i}, g_ {i} left (x right) right rangle}$ pro všechny ${ displaystyle i}$, počítá ${ displaystyle M}$.

Důkaz

Protože ${ displaystyle N_ {i}}$ jsou relativně prime the Čínská věta o zbytku lze použít k výpočtu koeficienty ${ displaystyle T_ {i}}$ uspokojující ${ displaystyle T_ {i} equiv 1 { pmod {N_ {i}}}}$ a ${ displaystyle T_ {i} equiv 0 { pmod {N_ {j}}}}$ pro všechny ${ displaystyle i neq j}$. Nastavení ${ displaystyle g (x) = součet T_ {i} cdot g_ {i} (x)}$ víme, že ${ displaystyle g (M) equiv 0 { pmod { prod N_ {i}}}}$. Protože ${ displaystyle T_ {i}}$ jsou nonnula máme to ${ displaystyle g left (x right)}$ je také nenulová. Stupeň ${ displaystyle g left (x right)}$ je nanejvýš ${ displaystyle q}$. Podle Coppersmithovy věty můžeme spočítat vše celé číslo kořeny ${ displaystyle x_ {0}}$ uspokojující ${ displaystyle g (x_ {0}) equiv 0 { pmod { prod N_ {i}}}}$ a ${ displaystyle left | x_ {0} right | < left ( prod N_ {i} right) ^ { frac {1} {q}}}$. To však víme ${ displaystyle M$, tak ${ displaystyle M}$ je jedním z kořenů nalezených Coppersmithovou větou.

Tuto větu lze aplikovat na problém vysílání RSA následujícím způsobem: Předpokládejme ${ displaystyle i}$-tý prostý text je vyplněn polynomem ${ displaystyle f_ {i} vlevo (x vpravo)}$, aby ${ displaystyle g_ {i} = left (f_ {i} left (x right) right) ^ {e_ {i}} - C_ {i} { bmod {}} N_ {i}}$. Pak ${ displaystyle g_ {i} (M) equiv 0 { bmod {N}} _ {i}}$ je pravda a lze použít metodu Coppersmith. Útok jednou uspěje ${ displaystyle k> { rm {max}} _ {i} (e_ {i} cdot deg f_ {i})}$, kde ${ displaystyle k}$ je počet zpráv. Původní výsledek používal Håstadovu variantu místo plné metody Coppersmith. Ve výsledku to vyžadovalo ${ displaystyle k = O (q ^ {2})}$ zprávy, kde ${ displaystyle q = { rm {max}} _ {i} (e_ {i}. deg f_ {i})}$.^[2]

Franklin-Reiter útok související se zprávou

Franklin-Reiter identifikoval nový útok proti RSA s veřejností exponent ${ displaystyle e = 3}$. Pokud dva zprávy se liší pouze známým pevným rozdílem mezi těmito dvěma zprávami a jsou RSA šifrované pod stejným RSA modul ${ displaystyle N}$, pak je možné oba obnovit.

Nechat ${ displaystyle left langle N; e_ {i} right rangle}$ být veřejným klíčem Alice. Předpokládat ${ displaystyle M_ {1}; M_ {2} in mathbb {Z} _ {N}}$ jsou dva odlišné zprávy uspokojující ${ displaystyle M_ {1} equiv f (M_ {2}) { pmod {N}}}$ pro některé veřejně známé polynomiální ${ displaystyle f in mathbb {Z} _ {N} [x]}$. Poslat ${ displaystyle M_ {1}}$ a ${ displaystyle M_ {2}}$ Alice, Bob může naivně zašifrovat the zprávy a vysílat výsledný šifrovací texty ${ displaystyle C_ {1}; C_ {2}}$. Eva se může snadno vzpamatovat ${ displaystyle M_ {1}; M_ {2}}$ daný ${ displaystyle C_ {1}; C_ {2}}$pomocí následující věty:

Věta 3 (Franklin-Reiter)^[1]

Soubor ${ displaystyle e = 3}$ a nechte ${ displaystyle left langle N, e right rangle}$ být veřejným klíčem RSA. Nechat ${ displaystyle M_ {1} neq M_ {2} in mathbb {Z} _ {N} ^ {*}}$ uspokojit ${ displaystyle M_ {1} equiv f (M_ {2}) { pmod {N}}}$ pro některé lineární polynomiální ${ displaystyle f = sekera + b v mathbb {Z} _ {N} [x]}$ s ${ displaystyle b neq 0}$. Pak, vzhledem k tomu ${ displaystyle left langle N, e, C_ {1}, C_ {2}, f right rangle}$, útočník, Eva, se může vzchopit ${ displaystyle M_ {1}, M_ {2}}$ včas kvadratický v ${ displaystyle log _ {2} N}$.

Pro libovolný ${ displaystyle e}$ (spíše než se omezovat na ${ displaystyle e = 3}$) požadovaný čas je kvadratický v ${ displaystyle e}$ a ${ displaystyle log _ {2} N}$.

Důkaz

Od té doby ${ displaystyle C_ {1} equiv M_ {1} ^ {e} { pmod {N}}}$, víme, že ${ displaystyle M_ {2}}$ je vykořenit z polynomiální ${ displaystyle g_ {1} (x) = f (x) ^ {e} -C_ {1} in mathbb {Z} _ {N} [x]}$. Podobně, ${ displaystyle M_ {2}}$ je kořenem ${ displaystyle g_ {2} (x) = x ^ {e} -C_ {2} in mathbb {Z} _ {N} [x]}$. The lineární faktor ${ displaystyle x-M_ {2}}$ rozděluje obě polynomy Eva proto vypočítá největší společný dělitel (gcd) ze dne ${ displaystyle g_ {1}}$ a ${ displaystyle g_ {2}}$, pokud se gcd ukáže být lineární, ${ displaystyle M_ {2}}$ je nalezeno. The gcd lze vypočítat v kvadratickém čase v ${ displaystyle e}$ a ${ displaystyle log _ {2} N}$ za použití Euklidovský algoritmus.

Coppersmithův útok na krátkou podložku

Stejně jako útok Håstada a Franklin-Reitera využívá tento útok slabost RSA s veřejným exponentem ${ displaystyle e = 3}$. Coppersmith ukázal, že pokud se náhodně použije výplň navržená Håstadem nesprávně RSA šifrování není bezpečný.

Předpokládejme, že Bob pošle zprávu ${ displaystyle M}$ Alice pomocí malého náhodného polstrování šifrování to. Útočník, Eva, zachytí šifrový text a brání mu v dosažení cíle. Bob se rozhodne znovu poslat ${ displaystyle M}$ Alice, protože Alice na jeho zprávu neodpověděla. Náhodně polštářky ${ displaystyle M}$ znovu a vysílá výsledný šifrový text. Eve má nyní dva šifrovací texty odpovídající dvěma šifrováním stejné zprávy pomocí dvou různých náhodných bloků.

Přestože Eva nezná použitou náhodnou podložku, stále může zprávu obnovit ${ displaystyle M}$ pomocí následující věty, pokud je náhodná výplň příliš krátká.

Věta 4 (Coppersmith)

Nechat ${ displaystyle left langle N, e right rangle}$ být veřejností RSA klíč kde ${ displaystyle N}$ je ${ displaystyle n}$-bity dlouhé. Soubor ${ displaystyle m = lfloor { frac {n} {e ^ {2}}} rfloor}$. Nechat ${ displaystyle M in mathbb {Z} _ {N} ^ {*}}$ být nanejvýš dlouhá zpráva ${ displaystyle n-m}$ bity. Definovat ${ displaystyle M_ {1} = 2 ^ {m} M + r_ {1}}$ a ${ displaystyle M_ {2} = 2 ^ {m} M + r_ {2}}$, kde ${ displaystyle r_ {1}}$ a ${ displaystyle r_ {2}}$ jsou odlišný celá čísla s ${ displaystyle 0 leq r_ {1}, r_ {2} <2 ^ {m}}$. Pokud je dána Eva ${ displaystyle left langle N, e right rangle}$ a šifrování ${ displaystyle C_ {1}, C_ {2}}$ z ${ displaystyle M_ {1}, M_ {2}}$ (ale není uveden ${ displaystyle r_ {1}}$ nebo ${ displaystyle r_ {2}}$), může se efektivně zotavit ${ displaystyle M}$.

Důkaz^[1]

Definovat ${ displaystyle g_ {1} (x, y) = x ^ {e} -C_ {1}}$ a ${ displaystyle g_ {2} (x, y) = (x + y) ^ {e} -C_ {2}}$. Víme to kdy ${ displaystyle y = r_ {2} -r_ {1}}$, tyto polynomy mít ${ displaystyle x = M_ {1}}$ jako obyčejný kořen. Jinými slovy, ${ displaystyle vartriangle = r_ {2} -r_ {1}}$ je kořenem výsledný ${ displaystyle h (y) = { rm {res}} _ {x} (g_ {1}, g_ {2}) in mathbb {Z} _ {N} [y]}$. Dále ${ displaystyle left | vartriangle right | <2 ^ {m}$. Proto, ${ displaystyle vartriangle}$ je malý kořen ${ displaystyle h}$ modulo ${ displaystyle N}$a Eva jej může efektivně najít pomocí metody Coppersmith. Jednou ${ displaystyle vartriangle}$ je známo, že útok Franklin-Reiter lze použít k zotavení ${ displaystyle M_ {2}}$ a následně ${ displaystyle M}$.

Viz také

• Coppermithova metoda
• Útok ROCA

Reference