Coppersmithin lause

Coppersmithin lause ( Coppersmithin menetelmä) on lause, jonka avulla voit tehokkaasti löytää normalisoitujen polynomien nollat tietyllä arvolla. [yksi]

Lausetta käytetään pääasiassa hyökkäyksiin RSA - salausjärjestelmää vastaan . Tämä menetelmä on tehokas, jos koodauseksponentti on tarpeeksi pieni tai kun osa salaisesta avaimesta tunnetaan . Lause liittyy myös LLL-algoritmiin .

Kuvaus

Johdanto

Lause ehdottaa algoritmia, jolla voidaan löytää tehokkaasti normalisoidun polynomimodulin juuret , jotka ovat pienempiä kuin . Jos se on pieni, algoritmi toimii nopeammin. Lauseen etuna on kyky löytää polynomin modulon pienet juuret . Jos moduuli on alkuluku, ei ole mitään järkeä käyttää Coppersmithin lausetta . On paljon tehokkaampaa käyttää muita tapoja löytää polynomin juuret. [yksi] $f$ $N$ ${\displaystyle X=N^{1/d))$ $X$ $N$

Pieni koodauseksponentti

Salauksen tai allekirjoituksen vahvistusajan lyhentämiseksi on suositeltavaa käyttää pientä (koodauseksponenttia). Pienin mahdollinen arvo on , mutta sitä suositellaan käytettäväksi (joitakin hyökkäyksiä vastaan). Arvoa käytettäessä tarvitaan 17 kertolaskua allekirjoituksen tarkistamiseksi ( , missä on kertovan ryhmän järjestys , ehkä noin 1000). Pienten käyttöön keskittyvät hyökkäykset eivät aina ole tehokkaita. ${\textstyle e}$ $3$ $e=2^{16}+1=65537$ $2^{{16}}+1$ $\forall e\leqslant \phi (N)$ ${\näyttötyyli \phi (N)}$ $\mathbb {Z} _{N}$ ${\textstyle e}$

Tehokkaimmat hyökkäykset pientä koodauseksponenttia vastaan perustuvat Coppersmithin lauseeseen , jolla on monia sovelluksia, joista yksi on Hasted-hyökkäys. [2]

Attack of Hasted

Oletetaan, että yksi lähettäjä lähettää saman viestin salatussa muodossa tietylle määrälle ihmisiä , joista jokainen käyttää samaa pientä koodauseksponenttia , esimerkiksi , ja eri pareja , ja . Lähettäjä salaa viestin vuorollaan kunkin käyttäjän julkisella avaimella ja lähettää sen sopivalle vastaanottajalle. Sitten, jos vastustaja kuuntelee lähetyskanavaa ja kerää lähetetyt salatekstit , hän pystyy palauttamaan viestin . $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$

Todiste

$\Laatikko$ Oletetaan, että vihollinen sieppasi ja missä . Oletetaan, että ne ovat suhteellisen alkulukuja , muuten suurin yhteinen jakaja muu kuin yksikkö tarkoitti löytää jakaja yhdelle . Soveltamalla kiinalaista jäännöslausetta , saadaan sellainen, että jolla on arvo . Kuitenkin tietäen sen , saamme . Siksi vastustaja voi purkaa viestin salauksen ottamalla kuutiojuuren . ${\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$

Jos haluat palauttaa viestin , jolla on mikä tahansa avoimen koodauseksponentin arvo, vastustajan on siepattava salatekstit . $M$ ${\textstyle e}$ $k\geqslant e$ $\musta neliö$

Sanamuoto

Olkoon ja normalisoitu astepolynomi . Anna , . Sitten, kun otetaan huomioon pari, hyökkääjä löytää tehokkaasti kaikki kokonaisluvut tyydyttävinä . Suoritusaika määräytyy LLL-algoritmin suorituksella dimensioimalla hilassa , jossa . [yksi] $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\))$

Todiste

$\Laatikko$ Olkoon luonnollinen luku , jonka määrittelemme myöhemmin. Määritellään $m>1$

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

Käytämme polynomeja hilallemme ja sen perustana . Esimerkiksi, milloin ja saamme rivien kattaman hilamatriisin : $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}}$ ,

jossa "—" tarkoittaa nollasta poikkeavia diagonaalisia elementtejä, joiden arvo ei vaikuta determinanttiin . Tämän hilan koko on , ja sen determinantti lasketaan seuraavasti: $\omega =md$

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

Vaadimme sitä . tämä tarkoittaa ${\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)))$

joka voidaan yksinkertaistaa

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

missä ja kaikille . Jos otamme , niin saamme siis, ja . Erityisesti, jos haluamme ratkaista mielivaltaisen , riittää , missä . [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\))$ $\musta neliö$

Katso myös

Kuparisepän hyökkäys

Muistiinpanot

↑ 1 2 3 Dan Boneh. 20 vuotta hyökkäyksiä RSA:n salausjärjestelmää vastaan . Haettu 25. marraskuuta 2016. Arkistoitu alkuperäisestä 26. maaliskuuta 2016. (määrätön)
↑ Ushakov Konstantin. RSA-järjestelmän hakkerointi . Käyttöpäivä: 25. marraskuuta 2016. Arkistoitu alkuperäisestä 1. joulukuuta 2016. (määrätön)
↑ Glenn Durfee. RSA:n KRYPTANALYYSI ALGEBRIA- JA HILAMENETELMIÄ KÄYTTÄMÄLLÄ (kesäkuu 2002). Käyttöpäivä: 30. marraskuuta 2016. Arkistoitu alkuperäisestä 4. maaliskuuta 2016. (määrätön)