El ataque del herrero

El ataque de Coppersmith describe una clase de ataques criptográficos contra el criptosistema de clave pública RSA basados ​​en el método de Coppersmith . Algunas aplicaciones particulares del método de Coppersmith para atacar RSA incluyen casos en los que el exponente público e es pequeño o cuando se dispone de información parcial sobre un factor primo de la clave secreta.

La clave pública en el sistema RSA es una tupla de números enteros.${\displaystyle (N,e)}$donde N es el producto de dos números primos p y q . La clave secreta viene dada por un número entero d que satisface${\displaystyle ed\equiv 1{\pmod {(p-1)(q-1)}}}$; equivalentemente, la clave secreta puede ser dada por${\displaystyle d_{p}\equiv d{\pmod {p-1}}}$y${\displaystyle d_{q}\equiv d{\pmod {q-1}}}$Si se utiliza el teorema chino del resto para mejorar la velocidad de descifrado, consulte CRT-RSA . El cifrado de un mensaje M produce el texto cifrado.${\displaystyle C\equiv M^{e}{\pmod {N}}}$, que se puede descifrar usando${\displaystyle d}$mediante computación${\displaystyle C^{d}\equiv M{\pmod {N}}}$.

Para reducir el tiempo de cifrado o verificación de firma, es útil utilizar un exponente público pequeño (${\displaystyle e}$). ^{[ 1 ]} En la práctica, las opciones comunes para${\displaystyle e}$son 3, 17 y 65537${\displaystyle (2^{16}+1)}$. Estos valores para e son primos de Fermat , a veces denominados${\displaystyle F_{0},F_{2}}$y${\displaystyle F_{4}}$respectivamente${\displaystyle (F_{x}=2^{2^{x}}+1)}$Se eligen porque hacen que la operación de exponenciación modular sea más rápida. Además, habiendo elegido tales${\displaystyle e}$, es más sencillo comprobar si${\displaystyle \gcd(e,p-1)=1}$y${\displaystyle \gcd(e,q-1)=1}$mientras se generan y prueban los números primos en el paso  1 de la generación de claves . Valores de${\displaystyle p}$o${\displaystyle q}$que no superen esta prueba pueden ser rechazados en ese mismo momento. (Mejor aún: si e es primo y mayor que 2, entonces la prueba${\displaystyle p{\bmod {e}}\neq 1}$puede reemplazar la prueba más costosa${\displaystyle \gcd(p-1,e)=1}$.)

Si el exponente público es pequeño y el texto plano${\displaystyle m}$es muy corto, entonces la función RSA puede ser fácil de invertir, lo que hace posibles ciertos ataques. Los esquemas de relleno aseguran que los mensajes tengan longitudes completas, pero además elegir el exponente público${\displaystyle e=2^{16}+1}$Se recomienda. Cuando se utiliza este valor, la verificación de firma requiere 17 multiplicaciones, en comparación con aproximadamente 25 cuando se utiliza un valor aleatorio.${\displaystyle e}$de tamaño similar se utiliza. A diferencia del exponente privado bajo (ver el ataque de Wiener ), los ataques que se aplican cuando un pequeño${\displaystyle e}$Los métodos utilizados están lejos de ser una ruptura total , que permitiría recuperar la clave secreta d . Los ataques más poderosos contra RSA de exponente público bajo se basan en el siguiente teorema, que se debe a Don Coppersmith .

Se presenta la forma más simple del ataque de Håstad para facilitar la comprensión. ^{[ 2 ]} El caso general utiliza el método del herrero de cobre.

Supongamos que un remitente envía el mismo mensaje.${\displaystyle M}$en forma encriptada a varias personas${\displaystyle P_{1};P_{2};\dots ;P_{k}}$, cada uno utilizando el mismo pequeño exponente público${\displaystyle e}$, decir${\displaystyle e=3}$y diferentes módulos${\displaystyle \left\langle N_{i},e\right\rangle }$Un argumento simple muestra que tan pronto como${\displaystyle k\geq 3}$Los textos cifrados son conocidos, el mensaje${\displaystyle M}$ya no es seguro: Supongamos que Eva intercepta${\displaystyle C_{1},C_{2}}$, y${\displaystyle C_{3}}$, dónde${\displaystyle C_{i}\equiv M^{3}{\pmod {N_{i}}}}$Podemos suponer${\displaystyle \gcd(N_{i},N_{j})=1}$a pesar de${\displaystyle i,j}$(de lo contrario, es posible calcular un factor de uno de los números)${\displaystyle N_{i}}$mediante computación${\displaystyle \gcd(N_{i},N_{j})}$.) Mediante el teorema chino del resto , puede calcular${\displaystyle C\in \mathbb {Z} _{N_{1}N_{2}N_{3}}^{*}}$de tal manera que${\displaystyle C\equiv C_{i}{\pmod {N_{i}}}}$. Entonces${\displaystyle C\equiv M^{3}{\pmod {N_{1}N_{2}N_{3}}}}$; sin embargo, dado que${\displaystyle M<N_{i}}$a pesar de${\displaystyle i}$, tenemos${\displaystyle M^{3}<N_{1}N_{2}N_{3}}$. De este modo${\displaystyle C=M^{3}}$se mantiene sobre los enteros, y Eve puede calcular la raíz cúbica de${\displaystyle C}$para obtener${\displaystyle M}$.

Para valores mayores de${\displaystyle e}$, se necesitan más textos cifrados, en particular,${\displaystyle e}$Los textos cifrados son suficientes.

Franklin y Reiter identificaron un ataque contra RSA cuando se cifran varios mensajes relacionados: si dos mensajes difieren solo por una diferencia fija conocida entre los dos mensajes y están cifrados con RSA bajo el mismo módulo RSA${\displaystyle N}$, entonces es posible recuperar ambos. El ataque fue descrito originalmente con exponente público${\displaystyle e=3}$, pero funciona de manera más general (con un costo creciente a medida que aumenta)${\displaystyle e}$crece).

Dejar${\displaystyle \left\langle N;e_{i}\right\rangle }$sea ​​la clave pública de Alice. Supongamos que${\displaystyle M_{1};M_{2}\in \mathbb {Z} _{N}}$son dos mensajes distintos que satisfacen${\displaystyle M_{1}\equiv f(M_{2}){\pmod {N}}}$para algún polinomio conocido públicamente${\displaystyle f\in \mathbb {Z} _{N}[x]}$. Para enviar${\displaystyle M_{1}}$y${\displaystyle M_{2}}$Para Alice, Bob puede, ingenuamente, cifrar los mensajes y transmitir los textos cifrados resultantes.${\displaystyle C_{1};C_{2}}$Eve puede recuperarse fácilmente${\displaystyle M_{1};M_{2}}$, dado${\displaystyle C_{1};C_{2}}$, utilizando el siguiente teorema: Sea${\displaystyle g_{1}(x)=f(x)^{e}-C_{1}\in \mathbb {Z} _{N}[x]}$y${\displaystyle g_{2}(x)=x^{e}-C_{2}\in \mathbb {Z} _{N}[x]}$. Entonces${\displaystyle (x-M_{2})}$es un factor de ambos${\displaystyle g_{1}(x)}$y${\displaystyle g_{2}(x)}$En la mayoría de los casos, calcular el máximo común divisor del polinomio revela el mensaje directamente:

${\displaystyle \gcd(g_{1}(x),g_{2}(x))=x-M_{2}{\pmod {N}}}$

Una vez${\displaystyle M_{2}}$se encuentra,${\displaystyle M_{1}}$se recupera mediante computación${\displaystyle f(M_{2}){\pmod {N}}}$.

Al igual que los ataques de Håstad y Franklin-Reiter, este ataque explota una debilidad de RSA con exponente público.${\displaystyle e=3}$Coppersmith demostró que si el relleno aleatorio sugerido por Håstad se utiliza incorrectamente, el cifrado RSA no es seguro.

Supongamos que Bob envía un mensaje.${\displaystyle M}$a Alice usando un pequeño relleno aleatorio antes de cifrarlo . Una atacante, Eve, intercepta el texto cifrado e impide que llegue a su destino. Bob decide reenviarlo.${\displaystyle M}$a Alice porque Alice no respondió a su mensaje. Él rellena aleatoriamente${\displaystyle M}$Eve vuelve a intentarlo y transmite el texto cifrado resultante. Ahora tiene dos textos cifrados que corresponden a dos cifrados del mismo mensaje utilizando dos claves aleatorias diferentes.

Aunque Eve no sabe qué bloc de notas aleatorio se está utilizando, aún puede recuperar el mensaje.${\displaystyle M}$mediante el uso del siguiente teorema, si el relleno aleatorio es demasiado corto.

• ataque de ROCA