Coppersmithova věta

Coppersmithův teorém ( Coppersmithova metoda) je teorém, který vám umožní efektivně najít všechny nuly normalizovaných polynomů modulo určité hodnoty. [jeden]

Věta se používá především pro útoky na kryptosystém RSA . Tato metoda je účinná, pokud je exponent kódování dostatečně malý nebo pokud je známa část tajného klíče . Tato věta také souvisí s algoritmem LLL .

Popis

Úvod

Věta navrhuje algoritmus pro efektivní nalezení kořenů normalizovaného polynomu modulo , které jsou menší než . Pokud je malý, algoritmus poběží rychleji. Výhodou věty je schopnost najít malé kořeny polynomu modulo . Pokud je modul prvočíslo, pak nemá smysl používat Coppersmithovu větu . Mnohem efektivnější bude použít jiné způsoby, jak najít kořeny polynomu. [jeden] $F$ $N$ ${\displaystyle X=N^{1/d))$ $X$ $N$

Malý exponent kódování

Pro zkrácení doby šifrování nebo ověřování podpisu je žádoucí použít malý (exponent kódování). Nejmenší možná hodnota je , ale doporučuje se používat (pro ochranu před některými útoky). Při použití hodnoty , je k ověření podpisu potřeba 17 násobení ( , kde je pořadí multiplikativní skupiny , možná asi 1000). Útoky zaměřené na použití malých nejsou vždy účinné. ${\textstyle e}$ $3$ $e=2^{16}+1=65537$ $2^{{16}}+1$ $\forall e\leqslant \phi (N)$ $\phi (N)$ $\mathbb {Z} _{N}$ ${\textstyle e}$

Nejsilnější útoky na malý exponent kódování jsou založeny na Coppersmithově teorému , který má mnoho aplikací, z nichž jednou je útok Hasted. [2]

Attack of Hasted

Předpokládejme, že jeden odesílatel pošle stejnou zprávu v zašifrované podobě určitému počtu lidí , z nichž každý používá stejný malý exponent kódování , řekněme , a různé páry a . Odesílatel zašifruje zprávu pomocí veřejného klíče každého uživatele a odešle ji příslušnému příjemci. Poté, pokud protivník naslouchá přenosovému kanálu a shromažďuje přenášené šifrové texty , bude schopen obnovit zprávu . $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$

Důkaz

$\Box$ Předpokládejme, že nepřítel byl zachycen a kde . Předpokládáme, že jsou relativně prvočísla , jinak největší společný dělitel jiný než jednota znamenal nalezení dělitele jednoho z . Aplikováním čínské věty o zbytku na a dostaneme takové, že , který má hodnotu . Když to však víme , dostáváme . To znamená , že protivník může dešifrovat zprávu tím , že vezme krychli z . ${\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$

Pro obnovení zprávy s libovolnou hodnotou exponentu otevřeného kódování je nutné, aby protivník zachytil šifrové texty . $M$ ${\textstyle e}$ $k\geqslant e$ $\blacksquare$

Formulace

Dovolit a být normalizovaný polynom stupně . Nechte ,. _ Útočník pak s daným párem efektivně najde všechna celá čísla vyhovující . Doba provádění je určena provedením algoritmu LLL na mřížce dimenzí , kde . [jeden] $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\))$

Důkaz

$\Box$ Nechť je přirozené číslo , které budeme definovat později. Pojďme definovat $m>1$

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

Polynomy používáme pro a jako základ naší mřížky . Například když a dostaneme mřížkovou matici rozloženou po řádcích: $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}}$ ,

kde "—" označuje nenulové mimodiagonální prvky, jejichž hodnota neovlivňuje determinant . Velikost této mřížky je a její determinant se vypočítá takto: $\omega =md$

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

To vyžadujeme . z toho vyplývá ${\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)))$

které lze zjednodušit

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

kde a pro všechny . Pokud vezmeme , pak dostaneme a, tedy a . Konkrétně, pokud chceme řešit pro libovolný , postačí vzít , kde . [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$

Viz také

Coppersmith útok

Poznámky

↑ 1 2 3 Dan Boneh. Dvacet let útoků na kryptosystém RSA . Získáno 25. listopadu 2016. Archivováno z originálu dne 26. března 2016. (neurčitý)
↑ Ušakov Konstantin. Hackování systému RSA . Datum přístupu: 25. listopadu 2016. Archivováno z originálu 1. prosince 2016. (neurčitý)
↑ Glenn Durfee. KRYPTANALÝZA RSA POMOCÍ ALGEBRAICKÉ A MŘÍŽKOVÉ METODY (červen 2002). Datum přístupu: 30. listopadu 2016. Archivováno z originálu 4. března 2016. (neurčitý)