Atacul unui fierar

Atacul Coppersmith descrie o clasă de atacuri criptografice asupra cheii publice a criptosistemului RSA bazate pe metoda Coppersmith . Particularitatea utilizării acestei metode pentru atacurile RSA include cazuri când exponentul public este mic sau când cheia privată este parțial cunoscută.

Bazele RSA

Cheia publică a criptosistemului RSA este o pereche de numere naturale , unde este produsul a două numere prime și , iar numărul este un exponent public. Un număr întreg ( , unde este funcția Euler a ) coprim cu valoare . De obicei numerele prime sunt luate ca calitate , conținând un număr mic de biți unici în notație binară, de exemplu, numere prime Fermat 17, 257 sau 65537. $\left\langle N,e\right\rangle$ $N$ $p$ $q$ $e$ $e$ $1<e<\phi (N)$ $\phi (N)=(p-1)(q-1)$ $N$ $\phi (N)$ $e$

Cheia secretă este determinată prin exponentul privat . Numărul este invers multiplicativ cu numărul modulo , adică numărul satisface relația: $d$ $d$ $e$ $\phi (N)$

$d\cdot e\equiv 1{\bmod {\phi }}(N)$ .

Perechea este publicată ca o cheie publică RSA ( eng . RSA public key ), iar perechea joacă rolul unei chei private RSA ( eng . RSA private key ) și este ținută secretă. $\left\langle N,e\right\rangle$ $\stanga\langle N,d\dreapta\rangle$

Teorema lui Coppersmith

Formulare [1]

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 . [2] $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$

Atacul lui Hasted

Formulare

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 [4]

$\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$

Atacul lui Coppersmith

Formulare

Să presupunem o cheie publică RSA , unde lungimea este -biți. Să luăm multe . Lăsați mesajul să nu aibă mai mult de biți. Să definim și , unde și sunt numere întregi distincte , și și .Dacă adversarul primește ambele cifruri de la (dar nu primește sau ), atunci el poate recupera efectiv mesajul . $\left\langle N,e\right\rangle$ $N$ $n$ $m=\lfloor n/e^{2}\rfloor$ $M\in \mathbb {Z} _{N}$ $nm$ $M_{1}=2^{m}M+r_{1}$ $M_{2}=2^{m}M+r_{2)$ $r_{1}$ $r_{2}$ $0\leqslant r_{1}$ $r_{2}\leqslant 2^{m)$ $\left\langle N,e\right\rangle$ ${\displaystyle C_{1},C_{2))$ $M_{1},M_{2}$ $r_{1}$ $r_{2}$ $M$

Dovada [2]

$\Cutie$ Să definim și . Știm că atunci când , aceste polinoame au o rădăcină comună. Cu alte cuvinte, aceasta este rădăcina „rezultatului” . grad cel mai adesea . Mai mult, . Prin urmare, este o rădăcină modulo mică , iar adversarul o poate găsi eficient folosind teorema lui Coppersmith . Odată cunoscut, atacul Franklin-Reiter poate fi folosit pentru a acoperi , prin urmare, și . $g_{1}(x,y)=x^{e}-C_{1)$ $g_{1}(x,y)=(x+y)^{e}-C_{2}$ $y=r_{2}-r_{1)$ $M_{1}$ $\Delta =r_{2}-r_{1)$ $h(y)=\mathrm {res} _{x}(g_{1},g_{2})\in \mathbb {Z} _{N}[y]$ $h$ $e^{2}$ $|\Delta |<2^{m}<N^{1/e^{2)}$ $\Delta$ $h$ $N$ $\Delta$ $M_{2}$ $M$ $\blacksquare$

Note

↑ Don Coppersmith. Găsirea unei rădăcini mici a unei ecuații modulare univariate . (nedefinit) (link indisponibil)
↑ 12 Dan Boneh . Douăzeci de ani de atacuri asupra criptosistemei RSA . Preluat la 1 decembrie 2016. Arhivat din original la 26 martie 2016. (nedefinit)
↑ Glenn Durfee. CRIPTANALIZA RSA FOLOSIND METODE ALGEBRICE ȘI LATICĂ (iunie 2002). Consultat la 1 decembrie 2016. Arhivat din original pe 4 martie 2016. (nedefinit)
↑ Ushakov Konstantin. Hackerea sistemului RSA . Data accesului: 6 decembrie 2016. Arhivat din original la 1 decembrie 2016. (nedefinit)