Angreb af kobbersmed

Coppersmith - angrebet beskriver en klasse af kryptografiske angreb på den offentlige nøgle til RSA -kryptosystemet baseret på Coppersmith-metoden . Det særlige ved at bruge denne metode til RSA- angreb omfatter tilfælde, hvor den offentlige eksponent er lille, eller når den private nøgle er delvist kendt.

Grundlæggende om RSA

Den offentlige nøgle til RSA -kryptosystemet er et par naturlige tal , hvor er produktet af to primtal og , og tallet er en offentlig eksponent. Et heltal ( , hvor er Euler-funktionen af ) primer med værdi . Normalt tages primtal som kvalitet , der indeholder et lille antal enkelte bit i binær notation, for eksempel Fermat-primtal 17, 257 eller 65537. $\left\langle N,e\right\rangle$ $N$ $s$ $q$ $e$ $e$ $1<e<\phi (N)$ $\phi (N)=(p-1)(q-1)$ $N$ $\phi (N)$ $e$

Den hemmelige nøgle bestemmes gennem den private eksponent . Tallet er multiplikativt omvendt til tallet modulo , det vil sige, at tallet opfylder relationen: $d$ $d$ $e$ $\phi (N)$

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

Parret udgives som en RSA offentlig nøgle ( eng . RSA public key ), og parret spiller rollen som en RSA privat nøgle ( eng . RSA privat nøgle ) og holdes hemmeligt. $\left\langle N,e\right\rangle$ $\left\langle N,d\right\rangle$

Coppersmith's theorem

Ordlyd [1]

Lad og være et normaliseret polynomium af grad . Lad ,. _ Så, givet parret, vil angriberen effektivt finde alle heltal tilfredsstillende . Udførelsestiden bestemmes af udførelsen af LLL-algoritmen på et gitter af dimension , hvor . [2] $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 \venstre\{{\tfrac {1}{\varepsilon )),\log _{2}{N}\right\))$

Bevis

$\Boks$ Lad være et naturligt tal , som vi vil definere senere. Lad os definere $m>1$

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

Vi bruger polynomierne til og som grundlag for vores gitter . For eksempel, hvornår og vi får en gittermatrix spændt ud af rækker: $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}}$ ,

hvor "—" angiver ikke-nul off-diagonale elementer, hvis værdi ikke påvirker determinanten . Størrelsen af dette gitter er , og dets determinant beregnes som følger: $\omega =md$

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

Det kræver vi . dette indebærer ${\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)))$

som kan forenkles til

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

hvor og for alle . Hvis vi tager , så får vi en, derfor og . Især, hvis vi ønsker at løse for en vilkårlig , er det tilstrækkeligt at tage , hvor . [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}}$ $\varepsilon_{0}$ $m=O(k/d)$ ${\displaystyle k=\min \left\{{\tfrac {1}{\varepsilon )),\log _{2}{N}\right\))$ $\blacksquare$

Attack of Hasted

Ordlyd

Antag, at en afsender sender den samme besked i krypteret form til et vist antal personer , som hver især bruger den samme lille kodningseksponent , f.eks . og forskellige par , og . Afsenderen krypterer beskeden ved hjælp af hver brugers offentlige nøgle på skift og sender den til den relevante modtager. Så, hvis modstanderen lytter til transmissionskanalen og indsamler de transmitterede chiffertekster , vil han være i stand til at gendanne beskeden . $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$

Bevis [4]

$\Boks$ Antag, at fjenden opsnappede og , hvor . Vi antager, at de er relativt prime , ellers betød den største fælles divisor bortset fra enhed at finde en divisor af en af . Anvender den kinesiske restsætning til og vi får , sådan at , som har værdien . Men når vi ved det , får vi . Derfor , det vil sige, at modstanderen kan dekryptere beskeden ved at tage terningeroden af . ${\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$

For at gendanne en besked med en hvilken som helst værdi af den åbne kodningseksponent , er det nødvendigt for modstanderen at opsnappe chifferteksterne . $M$ ${\textstyle e}$ $k\geqslant e$ $\blacksquare$

Angreb af Coppersmith

Ordlyd

Antag en RSA offentlig nøgle , hvor længden er -bits. Lad os tage en masse . Lad beskeden ikke være mere end en smule lang. Lad os definere og , hvor og er forskellige heltal , og og . Hvis modstanderen modtager begge cifre fra (men ikke modtager eller ), så kan han effektivt gendanne beskeden . $\left\langle N,e\right\rangle$ $N$ $n$ $m=\lgulv n/e^{2}\rgulv$ $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}$ ${\displaystyle 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$

Bevis [2]

$\Boks$ Lad os definere og . Vi ved, at når , disse polynomier har en fælles rod. Dette er med andre ord roden til "det resulterende" . grad oftest . Desuden . Derfor er det en lille modulrod , og modstanderen kan finde den effektivt ved at bruge Coppersmiths sætning . Når først det er kendt, kan Franklin-Reiter-angrebet bruges til at dække , og . ${\displaystyle g_{1}(x,y)=x^{e}-C_{1))$ $g_{1}(x,y)=(x+y)^{e}-C_{2}$ ${\displaystyle y=r_{2}-r_{1))$ $M_{1}$ ${\displaystyle \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$

Noter

↑ Don Coppersmith. At finde en lille rod til en univariat modulær ligning . (ubestemt) (utilgængeligt link)
↑ 12 Dan Boneh . Tyve års angreb på RSA-kryptosystemet . Hentet 1. december 2016. Arkiveret fra originalen 26. marts 2016. (ubestemt)
↑ Glenn Durfee. KRYPTANALYSE AF RSA VED HJÆLP AF ALGEBRAISK OG LATTICE METODER (juni 2002). Hentet 1. december 2016. Arkiveret fra originalen 4. marts 2016. (ubestemt)
↑ Ushakov Konstantin. Hacking af RSA-systemet . Dato for adgang: 6. december 2016. Arkiveret fra originalen 1. december 2016. (ubestemt)