Coppersmith-tétel

A Coppersmith -tétel ( Coppersmith - módszer) egy olyan tétel, amely lehetővé teszi, hogy hatékonyan megtalálja a normalizált polinomok összes nulláját egy bizonyos érték függvényében. [egy]

A tételt főleg az RSA kriptorendszer elleni támadásokra használják . Ez a módszer akkor hatékony, ha a kódolási kitevő elég kicsi, vagy ha a titkos kulcs egy része ismert . A tétel az LLL algoritmushoz is kapcsolódik .

Leírás

Bevezetés

A tétel egy algoritmust javasol egy normalizált polinom modulo gyökeinek hatékony megtalálására , amelyek kisebbek, mint . Ha kicsi, akkor az algoritmus gyorsabban fog futni. A tétel előnye, hogy képes megtalálni egy polinom modulo kis gyökét . Ha a modulus egy prímszám, akkor nincs értelme a Coppersmith -tételt használni . Sokkal hatékonyabb lesz más módszereket használni a polinomok gyökereinek megtalálására. [egy] $f$ $N$ ${\displaystyle X=N^{1/d))$ $x$ $N$

Kis kódolási kitevő

A titkosítási vagy aláírás-ellenőrzési idő csökkentése érdekében kívánatos kis (kódoló kitevő) használata. A lehető legkisebb érték a , de használata javasolt (egyes támadások elleni védelem érdekében). Az érték használatakor 17 szorzás szükséges az aláírás ellenőrzéséhez ( , ahol a szorzócsoport sorrendje , talán körülbelül 1000). A kicsi használatára összpontosító támadások nem mindig hatékonyak. ${\textstyle e}$ $3$ $e=2^{16}+1=65537$ $2^{{16}}+1$ $\forall e\leqslant \phi (N)$ $\phi (N)$ $\mathbb {Z} _{N}$ ${\textstyle e}$

A kis kódoló kitevő elleni legerősebb támadások Coppersmith tételén alapulnak , amelynek számos alkalmazása van, ezek közül az egyik a Hasted támadás. [2]

Attack of Hasted

Tegyük fel, hogy egy feladó ugyanazt az üzenetet titkosított formában küldi el bizonyos számú embernek , akik mindegyike ugyanazt a kis kódolási kitevőt használja , mondjuk , és különböző párokat , és . A feladó titkosítja az üzenetet az egyes felhasználók nyilvános kulcsával, és elküldi a megfelelő címzettnek. Ezután, ha az ellenfél hallgatja az átviteli csatornát, és összegyűjti a továbbított titkosított szövegeket , akkor képes lesz visszaállítani az üzenetet . $M$ ${\displaystyle P_{1};P_{2};...;P_{k))$ ${\textstyle e}$ $e=3$ $\left\langle N_{i},e\right\rangle$ $M<N_{i},\forall i$ $k\geqslant 3$ $M$

Bizonyítás

$\Doboz$ Tegyük fel, hogy az ellenség elfogta , és ahol . Feltételezzük, hogy ezek viszonylag prímszámúak , különben az egységen kívüli legnagyobb közös osztó az egyik osztójának megtalálását jelentette . Ha a kínai maradéktételt alkalmazzuk a -ra , és azt kapjuk , hogy , amelynek értéke van . Ennek ismeretében azonban megkapjuk . Ez azt jelenti , hogy az ellenfél visszafejtheti az üzenetet a kockagyökért . ${\displaystyle C_{1},C_{2))$ $C_{3}$ $C_{i}=M^{3}{\bmod {N}}_{i}$ ${\displaystyle N_{1},N_{2},N_{3))$ $n$ ${\displaystyle C_{1},C_{2))$ $C_{3}$ $C\in \mathbb {Z} _{N_{1},N_{2},N_{3))$ $C_{i}\equiv C{\bmod {N}}_{i}$ $C=M^{3}{\bmod {N}}_{1}N_{2}N_{3}$ $M<N_{i},\forall i$ ${\displaystyle M^{3}<N_{1}N_{2}N_{3))$ $C=M^{3}$ $M$ $C$

A nyílt kódolású kitevő tetszőleges értékével rendelkező üzenet helyreállításához szükséges, hogy az ellenfél elfogja a rejtjelezett szövegeket . $M$ ${\textstyle e}$ $k\geqslant e$ $\fekete négyzet$

Megfogalmazás

Legyen és egy fokú normalizált polinom . Hagyjuk , . Ezután a pár adott esetben a támadó minden egész számot kielégítőnek talál . A végrehajtási időt az LLL algoritmus végrehajtása határozza meg egy dimenziós rácson , ahol . [egy] $N\in \mathbb {Z}$ $f(x)\in \mathbb {Z[x]} -$ $d$ $X=N^{{\tfrac {1}{d}}-\varepsilon }$ $\varepsilon \geqslant 0$ $\left\langle N,f\right\rangle$ $\left\vert x_{0}\right\vert <\left\vert X\right\vert$ $f(x_{0})\equiv 0{\bmod {N))$ $O(\omega )$ ${\displaystyle \omega =\min \left\{{\tfrac {1}{\varepsilon )),\log _{2}{N}\right\))$

Bizonyítás

$\Doboz$ Legyen természetes szám , amelyet később definiálunk. Határozzuk meg $m>1$

${\displaystyle g_{i,k}(x)=x^{i}(f(x)/M)^{k))$

A polinomokat használjuk rácsunk alapjául . Például amikor és kapunk egy rácsmátrixot , amely sorokra feszül: $L$ $g_{i,k}(xX)$ $i=0,...,d-1$ $k=0,...,m-1$ $d=3$ $m=3$

${\begin{bmatrix}1\\&X\\&&X^{2}\\-&-&-&X^{3}M^{-1}\\&-&-&-&X^{4 }M^{-1}\\&&-&-&-&X^{5}M^{-1}\\-&-&-&-&-&-&X^{6}M^{-2} \\&-&-&-&-&-&-&X^{7}M^{-2}\\&&-&-&-&-&-&-&X^{8}M^{-2} \end{bmatrix}}$ ,

ahol a "-" nem nullától eltérő átlós elemeket jelöl, amelyek értéke nem befolyásolja a determinánst . Ennek a rácsnak a mérete , és a determinánsát a következőképpen számítjuk ki: $\omega =md$

${\displaystyle \det(L)=X^{\omega (\omega -1)/2}M^{-\omega (m-1)/2))$

Ezt megköveteljük . ez azt jelenti ${\displaystyle \det(L)<2^{-\omega (\omega -1)/4}\omega ^{-\omega /2))$

${\displaystyle X<M^{(m-1)/(\omega -1)}2^{-1/2}\omega ^{-1/(\omega -1)))$

amelyre leegyszerűsíthető

$X<\gamma _{\omega }\centerdot M^{{\tfrac {1}{d}}-\varepsilon }$ ,

hol és mindenért . Ha vesszük , akkor egy, tehát, és . Különösen, ha egy tetszőleges -t akarunk megoldani , akkor elegendő a , ahol . [3] $\varepsilon ={\tfrac {d-1}{d(\omega -1)))$ ${\displaystyle {\tfrac {1}{2{\sqrt {2))))\leqslant \gamma _{\omega }<{\tfrac {1}{\sqrt {2))))$ $\omega$ $m\rightarrow \infty$ $\omega \rightarrow \infty$ $\varepsilon \rightarrow 0$ $X<M^{{\tfrac {1}{d}}-\varepsilon _{0}}$ $\varepszilon_{0}$ $m=O(k/d)$ ${\displaystyle k=\min \left\{{\tfrac {1}{\varepsilon )),\log _{2}{N}\right\))$ $\fekete négyzet$

Lásd még

Rézműves támadás

Jegyzetek

↑ 1 2 3 Dan Boneh. Húsz éves támadások az RSA kriptorendszer ellen . Letöltve: 2016. november 25. Az eredetiből archiválva : 2016. március 26. (határozatlan)
↑ Ushakov Konstantin. Az RSA rendszer feltörése . Hozzáférés dátuma: 2016. november 25. Az eredetiből archiválva : 2016. december 1. (határozatlan)
↑ Glenn Durfee. AZ RSA KRIPTANAlízise ALGEBRAI ÉS RÁCSOS MÓDSZEREKKEL (2002. június). Hozzáférés dátuma: 2016. november 30. Az eredetiből archiválva : 2016. március 4. (határozatlan)