Ataque de calderero

El ataque Coppersmith describe una clase de ataques criptográficos a la clave pública del criptosistema RSA basados en el método Coppersmith . La peculiaridad de usar este método para ataques RSA incluye casos en los que el exponente público es pequeño o cuando la clave privada es parcialmente conocida.

Conceptos básicos de RSA

La clave pública del criptosistema RSA es un par de números naturales , donde es el producto de dos números primos y , y el número es un exponente público. Un número entero ( , donde es la función de Euler de ) coprima con valor . Por lo general , los números primos se toman como calidad y contienen una pequeña cantidad de bits individuales en notación binaria, por ejemplo, los números primos de Fermat 17, 257 o 65537. $\left\langle N,e\right\rangle$ $norte$ $pags$ $q$ $mi$ $mi$ ${\ estilo de visualización 1 <e <\ phi (N)}$ ${\ estilo de visualización \ phi (N) = (p-1) (q-1)}$ $norte$ ${\ estilo de visualización \ phi (N)}$ $mi$

La clave secreta se determina a través del exponente privado . El número es multiplicativamente inverso al número módulo , es decir, el número satisface la relación: $d$ $d$ $mi$ ${\ estilo de visualización \ phi (N)}$

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

El par se publica como una clave pública RSA ( ing . RSA public key ), y el par desempeña el papel de una clave privada RSA ( ing . RSA private key ) y se mantiene en secreto. $\left\langle N,e\right\rangle$ $\left\langle N,d\right\rangle$

Teorema del calderero

Redacción [1]

Sea y un polinomio normalizado de grado . Deje , . Entonces, dado el par, el atacante efectivamente encontrará que todos los enteros son satisfactorios . El tiempo de ejecución está determinado por la ejecución del algoritmo LLL en una red de dimensión , donde . [2] $N\en \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))$ ${\ estilo de visualización O (\ omega)}$ ${\displaystyle \omega =\min \left\{{\tfrac {1}{\varepsilon)),\log _{2}{N}\right\))$

Prueba

$\Caja$ Sea un número natural , que definiremos más adelante. definamos $m>1$

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

Usamos los polinomios para y como base de nuestra red . Por ejemplo, cuando y obtenemos una matriz reticular dividida por filas: $L$ $g_{i,k}(xX)$ ${\ estilo de visualización i = 0,..., d-1}$ ${\ estilo de visualización k = 0,..., m-1}$ $re=3$ $metro=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{bmatriz}}$ ,

donde "—" denota elementos fuera de la diagonal distintos de cero cuyo valor no afecta al determinante . El tamaño de esta red es , y su determinante se calcula de la siguiente manera: ${\ estilo de visualización \ omega = md}$

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

Requerimos eso . esto implica ${\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)))$

que se puede simplificar a

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

donde y para todos . Si tomamos , entonces obtenemos a, por lo tanto, y . En particular, si queremos resolver para un , es suficiente tomar , donde . [3] $\varepsilon ={\tfrac {d-1}{d(\omega -1)))$ ${\displaystyle {\tfrac {1}{2{\sqrt {2))))\leqslant \gamma _{\omega }<{\tfrac {1}{\sqrt {2))))$ $\omega$ ${\ estilo de visualización m \ flecha derecha \ infinito}$ ${\displaystyle\omega\rightarrow\infty}$ ${\ estilo de visualización \ varepsilon \ flecha derecha 0}$ $X<M^{{\tfrac {1}{d}}-\varepsilon _{0}}$ $\varepsilon_{0}$ ${\ estilo de visualización m = O (k/d)}$ ${\displaystyle k=\min \left\{{\tfrac {1}{\varepsilon)),\log _{2}{N}\right\))$ $\cuadrado negro$

Ataque de Hasted

Redacción

Supongamos que un remitente envía el mismo mensaje en forma encriptada a un cierto número de personas , cada una de las cuales usa el mismo pequeño exponente de codificación , digamos , y diferentes pares , y . El remitente cifra el mensaje utilizando la clave pública de cada usuario y lo envía al destinatario correspondiente. Entonces, si el adversario escucha el canal de transmisión y recopila los textos cifrados transmitidos , entonces podrá recuperar el mensaje . $METRO$ ${\displaystyle P_{1};P_{2};...;P_{k))$ ${\ estilo de texto e}$ ${\ estilo de visualización e = 3}$ $\left\langle N_{i},e\right\rangle$ $M<N_{i},\forall i$ $k\geqslant 3$ $METRO$

Prueba [4]

$\Caja$ Supongamos que el enemigo interceptó y , dónde . Suponemos que son primos relativos , de lo contrario el máximo común divisor distinto de la unidad significaba encontrar un divisor de uno de . Aplicando el teorema chino del resto a y obtenemos , tal que , que tiene el valor . Sin embargo, sabiendo que , obtenemos . Por lo tanto , es decir, el adversario puede descifrar el mensaje tomando la raíz cúbica de . ${\ estilo de visualización C_ {1}, C_ {2}}$ $C_{3}$ $C_{i}=M^{3}{\bmod {N}}_{i}$ ${\ estilo de visualización N_{1},N_{2},N_{3))$ $norte$ ${\ estilo de visualización C_ {1}, C_ {2}}$ $C_{3}$ $C\en \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$ $M^{3}<N_{1}N_{2}N_{3}$ $C=M^{3}$ $METRO$ $C$

Para recuperar un mensaje con cualquier valor del exponente de codificación abierta , es necesario que el adversario intercepte los textos cifrados . $METRO$ ${\ estilo de texto e}$ $k\geqslant e$ $\cuadrado negro$

Ataque de Coppersmith

Redacción

Suponga una clave pública RSA , donde la longitud es -bits. Tomemos mucho . Deje que el mensaje no sea más que bits de largo. Definamos and , donde y son enteros distintos , y y .Si el adversario recibe ambos cifrados de (pero no recibe o ), entonces puede recuperar el mensaje de manera efectiva . $\left\langle N,e\right\rangle$ $norte$ $norte$ $m=\lpiso n/e^{2}\rpiso$ $M\en \mathbb {Z} _{N}$ $Nuevo Méjico$ $M_{1}=2^{m}M+r_{1}$ ${\displaystyle 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$ ${\ estilo de visualización C_ {1}, C_ {2}}$ ${\ estilo de visualización M_ {1}, M_ {2}}$ $r_{1}$ $r_{2}$ $METRO$

Prueba [2]

$\Caja$ Definamos y . Sabemos que cuando , estos polinomios tienen una raíz común. En otras palabras, esta es la raíz del "resultante" . grado con mayor frecuencia . Además, . Por lo tanto, es una raíz de módulo pequeño , y el adversario puede encontrarla eficientemente usando el teorema de Coppersmith . Una vez conocido, el ataque de Franklin-Reiter puede usarse para cubrir , por lo tanto, y . ${\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$ ${\ estilo de visualización e ^ {2}}$ $|\Delta |<2^{m}<N^{1/e^{2))$ $\Delta$ $h$ $norte$ $\Delta$ $M_{2}$ $METRO$ $\cuadrado negro$

Notas

↑ Don Calderero. Hallar una pequeña raíz de una ecuación modular univariada . (indefinido) (enlace no disponible)
↑ 12 Dan Boneh . Veinte años de ataques al criptosistema RSA . Consultado el 1 de diciembre de 2016. Archivado desde el original el 26 de marzo de 2016. (indefinido)
↑ Glenn Durfee. CRIPTANÁLISIS DE RSA UTILIZANDO MÉTODOS ALGEBRAICOS Y ENREDADOS (Junio 2002). Consultado el 1 de diciembre de 2016. Archivado desde el original el 4 de marzo de 2016. (indefinido)
↑ Ushakov Konstantin. Hackear el sistema RSA . Fecha de acceso: 6 de diciembre de 2016. Archivado desde el original el 1 de diciembre de 2016. (indefinido)