Teorema lui Coppersmith

Teorema lui Coppersmith ( metoda lui Coppersmith) este o teoremă care vă permite să găsiți efectiv toate zerourile polinoamelor normalizate modulo o anumită valoare. [unu]

Teorema este folosită în principal pentru atacuri asupra criptosistemului RSA . Această metodă este eficientă dacă exponentul de codificare este suficient de mic sau când o parte a cheii secrete este cunoscută . Teorema este, de asemenea, legată de algoritmul LLL .

Descriere

Introducere

Teorema propune un algoritm pentru găsirea eficientă a rădăcinilor unui polinom normalizat modulo , care sunt mai mici decât . Dacă este mic, atunci algoritmul va rula mai repede. Avantajul teoremei este capacitatea de a găsi rădăcini mici ale unui polinom modulo . Dacă modulul este un număr prim, atunci nu are rost să folosim teorema lui Coppersmith . Va fi mult mai eficient să folosiți alte moduri de a găsi rădăcinile unui polinom. [unu] $f$ $N$ $X=N^{1/d)$ $X$ $N$

Exponent mic de codare

Pentru a reduce timpul de criptare sau de verificare a semnăturii, este de dorit să folosiți un mic (exponent de codificare). Cea mai mică valoare posibilă este , dar se recomandă utilizarea (pentru a proteja împotriva unor atacuri). Când se utilizează valoarea , sunt necesare 17 înmulțiri pentru a verifica semnătura ( , unde este ordinea grupului multiplicativ , poate aproximativ 1000). Atacurile concentrate pe utilizarea de mici nu sunt întotdeauna eficiente. ${\textstyle e}$ $3$ $e=2^{16}+1=65537$ $2^{{16}}+1$ $\forall e\leqslant \phi (N)$ $\phi (N)$ $\mathbb {Z} _{N}$ ${\textstyle e}$

Cele mai puternice atacuri asupra exponentului mic de codare se bazează pe teorema lui Coppersmith , care are multe aplicații, dintre care una este atacul Hasted. [2]

Atacul lui Hasted

Să presupunem că un expeditor trimite același mesaj în formă criptată unui anumit număr de persoane , fiecare dintre aceștia folosind același mic exponent de codare , să zicem , și perechi diferite și . Expeditorul criptează mesajul folosind pe rând cheia publică a fiecărui utilizator și îl trimite destinatarului corespunzător. Apoi, dacă adversarul ascultă canalul de transmisie și colectează textele cifrate transmise , atunci el va putea recupera mesajul . $M$ $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$

Dovada

$\Cutie$ Să presupunem că inamicul a interceptat și , unde . Presupunem că sunt relativ primi , altfel cel mai mare divizor comun , altul decât unitatea, însemna găsirea unui divizor al unuia dintre . Aplicând teorema chineză a restului la și obținem , astfel încât , care are valoarea . Cu toate acestea, știind asta , obținem . Prin urmare , adică adversarul poate decripta mesajul luând rădăcina cubă a . ${\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$

Pentru a recupera un mesaj cu orice valoare a exponentului de codificare deschis , este necesar ca adversarul să intercepteze textele cifrate . $M$ ${\textstyle e}$ $k\geqslant e$ $\blacksquare$

Formulare

Fie și un polinom normalizat de grad . Să , . Apoi, având în vedere perechea, atacatorul va găsi efectiv toate numerele întregi satisfăcătoare . Timpul de execuție este determinat de execuția algoritmului LLL pe o rețea de dimensiune , unde . [unu] $N\in \mathbb {Z}$ $f(x)\in \mathbb {Z[x]} -$ $d$ $X=N^{{\tfrac {1}{d}}-\varepsilon }$ $\varepsilon \geqslant 0$ $\stanga\langle N,f\dreapta\rangle$ $\left\vert x_{0}\right\vert <\left\vert X\right\vert$ $f(x_{0})\equiv 0{\bmod {N)}$ $O(\omega )$ $\omega =\min \left\{{\tfrac {1}{\varepsilon }),\log _{2}{N}\right\)$

Dovada

$\Cutie$ Fie un număr natural , pe care îl vom defini mai târziu. Să definim $m>1$

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

Folosim polinoamele pentru și ca bază pentru rețeaua noastră . De exemplu, când și obținem o matrice latice acoperită de rânduri: $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}}$ ,

unde „—” denotă elemente nenule în afara diagonalei a căror valoare nu afectează determinantul . Mărimea acestei rețele este , iar determinantul său se calculează după cum urmează: $\omega =md$

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

Noi cerem asta . asta implică $\det(L)<2^{-\omega (\omega -1)/4}\omega ^{-\omega /2)$

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

care poate fi simplificat la

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

unde si pentru toti . Dacă luăm , atunci obținem a, prin urmare, și . În special, dacă vrem să rezolvăm pentru un arbitrar , este suficient să luăm , unde . [3] $\varepsilon ={\tfrac {d-1}{d(\omega -1)})$ ${\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}}$ $\varepsilon_{0}$ $m=O(k/d)$ $k=\min \left\{{\tfrac {1}{\varepsilon }),\log _{2}{N}\right\)$ $\blacksquare$

Vezi și

Atacul unui fierar

Note

↑ 1 2 3 Dan Boneh. Douăzeci de ani de atacuri asupra criptosistemei RSA . Consultat la 25 noiembrie 2016. Arhivat din original la 26 martie 2016. (nedefinit)
↑ Ushakov Konstantin. Hackerea sistemului RSA . Data accesului: 25 noiembrie 2016. Arhivat din original la 1 decembrie 2016. (nedefinit)
↑ Glenn Durfee. CRIPTANALIZA RSA FOLOSIND METODE ALGEBRICE ȘI LATICĂ (iunie 2002). Data accesului: 30 noiembrie 2016. Arhivat din original pe 4 martie 2016. (nedefinit)