Coppersmith útok

Útok Coppersmith popisuje třídu kryptografických útoků na veřejný klíč kryptosystému RSA založených na Coppersmithově metodě . Zvláštností použití této metody pro RSA útoky jsou případy, kdy je veřejný exponent malý nebo kdy je soukromý klíč částečně znám.

Základy RSA

Veřejný klíč kryptosystému RSA je dvojice přirozených čísel , kde je součin dvou prvočísel a , a číslo je veřejný exponent. Celé číslo ( , kde je Eulerova funkce ) je spojeno s hodnotou . Obvykle se prvočísla berou jako kvalita obsahující malý počet jednotlivých bitů v binárním zápisu, například Fermat prvočísla 17, 257 nebo 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$

Tajný klíč je určen prostřednictvím soukromého exponentu . Číslo je multiplikativně inverzní k číslu modulo , to znamená, že číslo splňuje vztah: $d$ $d$ $E$ $\phi (N)$

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

Pár je publikován jako veřejný klíč RSA ( angl . RSA public key ) a pár hraje roli soukromého klíče RSA ( eng . RSA private key ) a je držen v tajnosti. $\left\langle N,e\right\rangle$ $\left\langle N,d\right\rangle$

Coppersmithův teorém

Formulace [1]

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

Attack of Hasted

Formulace

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

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

Attack of Coppersmith

Formulace

Předpokládejme veřejný klíč RSA , kde délka je -bitů. Vezměme si hodně . Nechť zpráva není delší než bitů. Definujme a , kde a jsou odlišná celá čísla a a Pokud protivník obdrží obě šifry od (ale nepřijme nebo ), pak může efektivně obnovit zprávu . $\left\langle N,e\right\rangle$ $N$ $n$ $m=\lpodlaží n/e^{2}\rpodlaží$ $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$

Důkaz [2]

$\Box$ Pojďme definovat a . Víme, že když , tyto polynomy mají společný kořen. Jinými slovy, toto je kořen „výsledku“ . stupně nejčastěji . Navíc, . Proto je to malý modulo kořen a protivník jej může efektivně najít pomocí Coppersmithovy věty . Jakmile je znám, útok Franklin-Reiter může být použit ke krytí , tedy a . ${\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$

Poznámky

↑ Don Coppersmith. Nalezení malého kořene jednorozměrné modulární rovnice . (neurčitý) (nedostupný odkaz)
↑ 12 Dan Boneh . Dvacet let útoků na kryptosystém RSA . Získáno 1. prosince 2016. Archivováno z originálu dne 26. března 2016. (neurčitý)
↑ Glenn Durfee. KRYPTANALÝZA RSA POMOCÍ ALGEBRAICKÉ A MŘÍŽKOVÉ METODY (červen 2002). Staženo 1. prosince 2016. Archivováno z originálu 4. března 2016. (neurčitý)
↑ Ušakov Konstantin. Hackování systému RSA . Datum přístupu: 6. prosince 2016. Archivováno z originálu 1. prosince 2016. (neurčitý)