Coppersmith's attack

Coppersmith útok popisuje třídu útoků na veřejného klíče kryptografického RSA na základě teorému Coppersmith tyto (viz níže). Veřejný klíč v systému RSA je n-tice celých čísel $(N, e)$ , kde N je součin dvou prvočísel p a q .Tajný klíč je dána tím, celé číslo d uspokojující $ed \ equiv 1 \ bmod \ (p-1) (q-1)$ , ekvivalentně, může tajný klíč bude dána $d_p \ equiv d \ bmod (p-1)$ a $d_q \ equiv d \ bmod (q-1)$ v případě, že čínská věta o zbytku se používá ke zlepšení rychlosti dekódování, viz CRT-rsa . Šifrování azprávy M produkuje ciphertext $C \ equiv M ^ e \ bmod N$ , které mohou být dešifrovat pomocí $d$ výpočtem $C ^ d \ equiv M \ bmod N$ .

Coppersmith věta má mnoho aplikací v útoku RSA zvláště pokud veřejný exponent e je malý, nebo pokud částečná znalost tajného klíče je k dispozici.

[ editovat ]Nízká veřejný exponent útok

Za účelem snížení šifrování nebo podpis - ověření doby, je vhodné použít malý veřejnou exponent ( $E$ ). V praxi, společné možnosti pro $E$ jsou 3, 17 a 65537 $(2 ^ {16} 1)$ . ^[ 1 ] Tyto hodnoty pro e jsou Fermatova prvočísla , někdy označované jako $F_0, f_2$ a $F_4$ , resp $(F_x = 2 ^ {2 ^ x} 1)$ . Jsou vybrány, protože oni dělají modulární umocňování operace rychleji. Také, co si vyberete jako $E$ , že je jednodušší ověřit, zda $\ Gcd (e, p-1) = 1$ a $\ Gcd (e, q-1) = 1$ při generování a testování prvočísel v kroku 1generování klíčů . Hodnoty $p$ nebo $q$ že selhání tento test může být zamítnuta tam a pak. (Ještě lepší: pokud e je prvočíslo a větší než 2, pak zkouška $p \, \ bmod \, e \ NE1$ může nahradit dražší testu $\ Gcd (p-1, e) = 1$ .
Pokud veřejný exponent je malý a holý $m$ je velmi krátký, pak RSA funkce mohou být snadno invertovat což některé útoky možné. polstrování systémyzajistí, že zprávy mají plné délky, ale navíc volbě veřejného exponentu $e = 2 ^ {16} + 1$ se doporučuje. Pokud se používá tato hodnota, ověřování podpisu vyžaduje 17 násobení, jak protichůdný k zhruba 1000, kdy náhodný $E$ se používá stejné velikosti. rozdíl nízké soukromý exponent (viz Wienerova útoku ), útoky, které se použijí v případě malé $E$ použití jsou daleko od celkového přestávky , které by navrácení tajný klíč d. . Nejsilnější útoky na nízkou míru veřejného exponentu RSA jsou založeny na následující věta, která je vzhledem k Don Coppersmith .

[ editovat ]Věta 1 (Coppersmith) ^[ 2 ]

Nechť N je celé číslo a $f \ in {\ mathbb Z} [x]$ je monic polynom stupně $d$ nad celými čísly. Nastavit $X = N ^ {\ frac {1} {d} - \ epsilon}$ pro $\ Frac {1} {d}> \ epsilon> 0$ . Pak, stejně $\ Left \ langle N, f \ right \ rangle$ může útočník, Eve, efektivně najít celá čísla $x_0 <X$ uspokojující $f (x_0) = 0 \, \ bmod \, N$ . Doba chodu dominuje čas potřebný ke spuštěníLLL algoritmus na mřížce o rozměru O $(W)$ s $w = {\ rm min} (\ frac {1} {\ epsilon}, \ log_2N)$ .

Tato věta uvádí existenci algoritmu , který může efektivně najít všechny kořenyna $F$ modulo $N$ , které jsou menší než $X = N ^ {\ frac {1} {d}}$ . Jak $X$ se zmenší, bude algoritmu runtime snížit. Tato věta je síla je schopnost najít všechny malé kořeny polynomů modulo složené $N$ .

[ upravit překlad ]Håstad tyto Broadcast útoku

Nejjednodušší forma útoku Håstad je je předložen usnadňují pochopení.Obecný případ využívá Coppersmith větu.

[ editovat ]Jak to funguje? ^[ 3 ]

Předpokládejme, že jednoho odesílatele odešle stejnou zprávu $M$ v zašifrované podobě na počtu lidí $P_1; P_2, \ dots, P_k$ , z nichž každý se stejným malý veřejný exponent $E$ , říkají $e = 3$ , a různé moduly $\ Left \ langle N_i, e_i \ right \ rangle$ . Jednoduchý argument ukáže, že jakmile $k \ ge 3$ ciphertexts jsou známy, zpráva $M$ je již bezpečný: Předpokládejme Eve zachytí $C_1, c_2$ , a $C_3$ , kde $C_i \ equiv M ^ 3 \, \ bmod \, N_i$ . Můžeme se domnívat, $\ Gcd (N_i, N_j) = 1$ pro všechny $i, j$ (jinak, je možné vypočítat faktor jednoho z $N_i$ "s tím, že počítá $\ Gcd (N_i, N_j)$ .) Do čínské věty o zbytcích , může si spočítat $C \ in \ mathbb (Z) ^ * _ {N_1N_2N_3}$ tak, že $C \ equiv C_i \, \ bmod \, N_i$ . Pak $C \ equiv M ^ 3 \, \ bmod \, N_1 N_2 N_3$ , nicméně, protože $M <N_i$ pro všechny $já$ ", máme $M ^ 3 <N_1N_2N_3$ . Tak $C = M ^ 3$ má přes celá čísla, a Eva mohou vypočítat třetí odmocninu z $C$ získat $M$ .

Pro větší hodnoty $E$ více ciphertexts jsou zapotřebí, a to zejména, $E$ ciphertexts jsou dostatečné.

[ editovat ]Zevšeobecňování

Håstad také ukázal, že použití lineární - padding , aby $M$ před šifrování nechrání proti tomuto útoku. Předpokládejme, že útočník dozví, že $C_i = f_i (M) ^ {e}$ pro $1 \ leq i \ leq k$ a některé lineární funkce $f_i$ , tj., Bob použije podložku na zprávy $M$ před šifrováním tak, aby příjemci obdrží mírně odlišné zprávy. Například, pokud $M$ je $m$ bitů dlouhé, může Bob šifrování $M_i = i2 ^ m + M$ a poslat to do i -tého příjemce.

Pokud dostatečně velká skupina lidí se účastní, může útočník obnovit holý $M_i$ ze všech ciphertext s podobnými metodami. Ve více obecnosti, Håstad prokázáno, že systém jednorozměrných rovnic modulo nesoudělná kompozitů, například použitím jakékoli pevné polynomiální $g_1 (M) = 0$ mod $N_i$ , by mohla být vyřešena, pokud dostatečně mnoho rovnic jsou k dispozici. Tentoútok naznačuje, že randomizované výplň by měl být použit ve šifrování RSA .

[ editovat ]Věta 2 (Håstad)

Předpokládejme, že $N_1, \ dots, N_k$ jsou nesoudělná celá čísla a nastavení $N_ {\ rm min} = {\ rm min} _i \ {N_i \}$ . Nechť $g_i (x) = \ in \ mathbb {Z} / N_i \ left [x \ right]$ je k. polynomymaximálního stupně $q$ . Předpokládejme, že existuje jedinečná $M <N_ {\ rm min}$ uspokojující $g_i (M) = 0$ (mod $N_i$ ) pro všechny $i \ in \ left \ {1, \ dots, k \ right \}$ . Dále předpokládám $k> q$ . K dispozici je efektivníalgoritmus , který vzhledem k tomu, $\ Left \ langle N_i, g_i \ left (x \ right) \ right \ rangle$ pro všechny $já$ , počítá $M$ .

Důkaz :
Vzhledem k tomu, $N_i$ jsou nesoudělná čínská věta o zbytcích by mohly být použity pro výpočet koeficientů $T_i$ uspokojující $T_i \ equiv 1 \ bmod N_i (je _1)$ a $T_i \ equiv 0 \ bmod \ N_j$ pro všechny $i \ ne j$ . Nastavení $g (x) = \ sum i \ cdot t_i \ cdot g_i (x)$ víme, že $g (M) \ equiv 0 \ bmod \ \ prod N_i$ .Vzhledem k tomu, $T_i$ jsou nenulová jsme, že $g \ left (x \ right)$ je také nenulová. Stupeň $g \ left (x \ right)$ je nejvíce $q$ . Podle Věty Coppersmith je, můžeme spočítat všechnyceločíselné kořeny $x_0$ splňují $g (x_0) \ equiv 0 \ bmod \ prod N_i$ a $\ Left | x_0 \ right | <\ left (\ prod N_i \ right) ^ {\ frac {1} {q}}$ . Nicméně, my víme, že $M <N_ {\ rm min} <(\ prod N_1) ^ {\ frac {1} {k}} <(\ prod N_1) ^ {\ frac {1} {q}}$ , takže $M$ je mezi kořeny nalezených věty Coppersmith je.

Tato věta může být použita k problému vysílání RSA následujícím způsobem: Předpokládejme i -tý holý je naplněn polynomu $f_i \ left (x \ right)$ , tak, že $N_i = \ left (f_i \ left (x \ right) \ right) ^ {} e_i-C_i \ bmod \ N_i$ . Pak polynomy $g_i = \ left (f_i \ left (x \ right) \ right) ^ {} e_i-C_i \ bmod N_i$ splňují tento vztah. Útok uspěje jednou $k> {\ rm max} _i (e_i \ cdot \ deg f_i)$ . Původní výsledek používal na Håstad metodu namísto plného Coppersmith metodu. Jeho výsledek byl vyžadován $k = O (q ^ {2})$ zprávy, kde $q = {\ rm max} _i (e_i. \ deg f_i)$ . ^[ 3 ]

[ upravit překlad ]Franklin-Reiter Související zprávy útoku

Franklin-Reiter poznal nový útok proti RSA s veřejným exponentem $e = 3$ .Jestliže dvě zprávy se liší pouze známým pevnou rozdílu mezi oběma zpráv a jsou RSA šifrované za stejných RSA modulu $N$ , pak je možné získat oba.

[ editovat ]Jak to funguje?

Nechť $\ Left \ langle N; e_i \ right \ rangle$ je Alicin veřejný klíč. Předpokládejme, že $M_1, m_2 \ in \ mathbb {Z} _N$ jsou dvě odlišné zprávy splňující $M_1 \ equiv f (m_2) \, \ bmod \, N$ nějakou veřejně známou polynomu $f \ in \ mathbb {Z} _N [x]$ . Chcete-li odeslat $M_1$ a $M_2$ Alici, může Bob naivně šifrování na zprávy a předá výsledné ciphertexts $C_1; c_2$ . Eve si můžete snadno obnovit $M_1; m_2$ , stejně $C_1; c_2$ , pomocí následující větu:

[ editovat ]Věta 3 (Franklin-Reiter)

Nastavit $e = 3$ a nechat $\ Left \ langle N, e \ right \ rangle$ se RSA veřejný klíč. Nechte $M_1 \ ne m_2 \ in \ mathbb {Z} ^ * _N$ uspokojit $M_1 \ equiv f (m_2) \, \ bmod \, N$ nějakou lineární polynom $f = ax + b \ in \ mathbb {Z} _N [x]$ s $b \ ne 0$ . Pak, stejně $\ Left \ langle N, e, c_1, c_2, f \ right \ rangle$ může útočník, Eve, obnovit $M_1, m_2$ v časovémkvadratický v $\ Log_2 N$ .

Pro libovolné $E$ (spíše než omezení na $e = 3$ ) potřebný čas je kvadratický v $E$ a $\ Log_2 N$ ).

Důkaz :
Vzhledem k tomu, $C_1 = m_1 ^ e \, \ bmod \, N$ víme, že $M_2$ je kořen z polynomu $g_1 (x) = f (x) ^ e - c_1 \ in \ mathbb {Z} _N [x]$ . Podobně, $M_2$ je kořen $g_2 (x) = x ^ e-c_2 \ in \ mathbb {Z} _N [x]$ . Lineární součinitel $x-m_2$ rozděluje obě polynomů . Proto, Eva vypočítává největší společný dělitel (gcd) o $g_1$ a $g_2$ , v případě, že gcd dopadá být lineární, $M_2$ se nachází. Gcd může být počítán v kvadratické času $E$ a $\ Log_2 N$ pomocí Euclidean algoritmus .

[ upravit překlad ]Coppersmith tyto Short Pad útoku

Stejně jako Håstad je a Franklin Reiter útoku, tento útok využívá slabost RSA s veřejným exponentem $e = 3$ . Coppersmith ukázal, že pokud randomizované padding navrhl Håstad se používá nesprávně pak RSA šifrování není bezpečné.

[ editovat ]Jak to funguje?

Předpokládejme, že Bob pošle zprávu $M$ Alici pomocí malého náhodného polstrování před zašifrováním to. Útočník, Eve, zachytí šifrový text a zabraňuje jeho dosažení svého cíle. Bob se rozhodne odeslat $M$ Alici, protože Alice nereagoval na jeho poselství. On náhodně podložky $M$ znovu a přenáší výsledný šifrovaný. Eva má nyní dva ciphertexts odpovídající dvěma šifrování stejné zprávy pomocí dvou různých náhodných vycpávky.

I když Eva neví, náhodné podložku používán, pořád může obnovit zprávu $M$ pomocí následující větu, pokud náhodná výplň je příliš krátký.

[ editovat ]Věta 4 (Coppersmith)

Nechť $\ Left \ langle N, e \ right \ rangle$ je veřejný RSA klíč kde $N$ je $n$ -bitů. Nastavit $m = \ lfloor \ frac {n} {e ^ 2} \ rfloor$ .Nechť $M \ in \ mathbb {Z} ^ * _N$ je zpráva délky u většiny $nm$ bitů. Definovat $M_1 = 2 ^ m M + R_1$ a $M_2 = 2 ^ m M + R_2$ , kde $R_1$ a $R_2$ je odlišnécelá čísla s $0 \ le R_1, R_2 <2 ^ m$ . Pokud Marvin je dána $\ Left \ langle N, e \ right \ rangle$ a šifrování $C_1, c_2$ s $M_1, m_2$ (ale není uveden $R_1$ , nebo $R_2$ , může efektivně obnovit $M$ .

Důkaz ^[ 2 ]
Definovat $g_1 (x, y) = x ^ e - c_1$ a $g_2 (x, y) = x ^ e - c_2$ . Víme, že když $y = R_2 - R_1$ tyto polynomy mají $x = m_1$ jako společný kořen.Jinými slovy, $\ Vartriangle = R_2 - R_1$ je kořen výslednice $h (y) = {\ rm res} _x (g_1, g_2) \ in \ mathbb {Z} _N [y]$ . Kromě toho, $\ Left | \ vartriangle \ right | <2 ^ m <N ^ {\ frac {1} {e ^ 2}}$ .Proto, $\ Vartriangle$ je malý kořen $hod$ modulo $N$ , a Marvin může efektivně najít pomocí Věty 1 (Coppersmith) . Jakmile $\ Vartriangle$ je známo, Franklin-Reiter útok může být použita k obnovení $M_2$ a následně $M$ .