El ataque de Coppersmith describe una clase de ataques criptográficos en el criptosistema RSA de clave pública basado en el método Coppersmith . Las aplicaciones particulares del método Coppersmith para atacar RSA incluyen casos en los que el exponente público e es pequeño o cuando se dispone de un conocimiento parcial de la clave secreta.
Conceptos básicos de RSA
La clave pública en el sistema RSA es una tupla de números enteros , Donde N es el producto de dos números primos p y q . La clave secreta viene dada por un entero d que satisface; de manera equivalente, la clave secreta puede ser dada por y si se utiliza el teorema del resto chino para mejorar la velocidad de descifrado, consulte CRT-RSA . El cifrado de un mensaje M produce el texto cifrado que se puede descifrar usando por computación .
Ataque de bajo exponente público
Con el fin de reducir el cifrado o la firma - la verificación del tiempo, es útil el uso de una pequeña pública exponente (). En la práctica, las opciones comunes parason 3, 17 y 65537 . Estos valores para e son números primos de Fermat , a veces denominados y respectivamente . Se eligen porque hacen que la operación de exponenciación modular sea más rápida. Además, habiendo elegido tal, es más sencillo probar si y mientras genera y prueba los números primos en el paso 1 de la generación de claves . Valores de o que no superen esta prueba pueden ser rechazados allí mismo. (Aún mejor: si e es primo y mayor que 2, entonces la prueba puede reemplazar la prueba más cara .)
Si el exponente público es pequeño y el texto llano es muy corto, entonces la función RSA puede ser fácil de invertir, lo que hace posibles ciertos ataques. Los esquemas de relleno garantizan que los mensajes tengan una longitud completa, pero además eligen el exponente públicoes recomendado. Cuando se usa este valor, la verificación de firma requiere 17 multiplicaciones, en contraposición a alrededor de 25 cuando sese utiliza de tamaño similar. A diferencia del exponente privado bajo (ver Ataque de Wiener ), los ataques que se aplican cuando un pequeñose utiliza están lejos de una ruptura total que recuperaría la clave secreta d . Los ataques más poderosos sobre RSA de bajo exponente público se basan en el siguiente teorema que se debe a Don Coppersmith .
Método de calderero
- Teorema 1 (Calderero) [1]
- Sea N un número entero y ser un polinomio monico de grado sobre los enteros. Colocar por . Entonces, dado El atacante, Eve, puede encontrar eficientemente todos los números enteros. satisfactorio . El tiempo de ejecución está dominado por el tiempo que lleva ejecutar el algoritmo LLL en un entramado de dimensión O con .
Este teorema establece la existencia de un algoritmo que puede encontrar eficientemente todas las raíces de modulo que son mas pequeños que . Comose vuelve más pequeño, el tiempo de ejecución del algoritmo disminuirá. La fuerza de este teorema es la capacidad de encontrar todas las raíces pequeñas de polinomios módulo a compuesto.
El ataque de transmisión de Håstad
Se presenta la forma más simple del ataque de Håstad [2] para facilitar la comprensión. El caso general utiliza el método Calderero.
Suponga que un remitente envía el mismo mensaje en forma cifrada a varias personas , cada uno usando el mismo pequeño exponente público , decir , y diferentes módulos . Un simple argumento muestra que tan pronto como los textos cifrados son conocidos, el mensaje ya no es seguro: supongamos que Eva intercepta , y , dónde . Podemos asumir para todos (de lo contrario, es posible calcular un factor de uno de loses por computación .) Según el teorema del resto chino , puede calcular tal que . Luego ; sin embargo, desde para todos ', tenemos . Por lo tantotiene sobre los enteros, y Eva puede calcular la raíz cúbica de para obtener .
Para valores mayores de se necesitan más textos cifrados, en particular, los textos cifrados son suficientes.
Generalizaciones
Hastad también demostró que la aplicación de un lineal - el relleno deantes del cifrado no protege contra este ataque. Suponga que el atacante se entera de que por y alguna función lineal , es decir, Bob aplica una almohadilla al mensaje antes de cifrarlo para que los destinatarios reciban mensajes ligeramente diferentes. Por ejemplo, si es bits de largo, Bob podría cifrar y envía esto a la -ésimo destinatario.
Si está involucrado un grupo lo suficientemente grande de personas, el atacante puede recuperar el texto sin formato de todo el texto cifrado con métodos similares. En términos más generales, Håstad demostró que un sistema de ecuaciones univariadas módulo relativamente compuestos primos , como la aplicación de cualquier polinomio fijo , podría resolverse si se proporcionan suficientes ecuaciones . Este ataque sugiere que se debería utilizar un relleno aleatorio en el cifrado RSA .
- Teorema 2 (Håstad)
- Suponer son enteros primos relativamente y se establecen . Dejar ser polinomios de grado máximo . Supongamos que existe un único satisfactorio para todos . Además, suponga . Existe un algoritmo eficiente que, dado para todos , calcula .
- Prueba
Desde el son relativamente primos, el teorema chino del residuo podría usarse para calcular coeficientes satisfactorio y para todos . Configuración lo sabemos . Desde elson distintos de cero , tenemos esotambién es distinto de cero. El grado de es como máximo . Por el teorema de Coppersmith, podemos calcular todas las raíces enteras satisfactorio y . Sin embargo, sabemos que, entonces es una de las raíces encontradas por el teorema de Coppersmith.
Este teorema se puede aplicar al problema de la transmisión RSA de la siguiente manera: Suponga que-th texto plano se rellena con un polinomio , así que eso . Luegoes cierto y se puede utilizar el método de Coppersmith. El ataque tiene éxito una vez, dónde es el número de mensajes. El resultado original utilizó la variante de Håstad en lugar del método completo de calderería. Como resultado, requirió mensajes, donde . [2]
Franklin-Reiter identificó un nuevo ataque contra RSA con exponente público . Si dos mensajes difieren solo por una diferencia fija conocida entre los dos mensajes y están encriptados RSA bajo el mismo módulo RSA , entonces es posible recuperar ambos.
Dejar ser la clave pública de Alice. Suponerson dos mensajes distintos que satisfacenpara algún polinomio conocido públicamente . Mandar y a Alice, Bob puede cifrar ingenuamente los mensajes y transmitir los textos cifrados resultantes . Eva puede recuperarse fácilmente dado , utilizando el siguiente teorema:
- Teorema 3 (Franklin-Reiter) [1]
- Colocar y deja ser una clave pública RSA. Dejar satisfacer para algún polinomio lineal con . Entonces, dado , atacante, Eva, puede recuperarse en el tiempo cuadrático en .
Por un arbitrario (en lugar de restringir a ) el tiempo requerido es cuadrático en y .
- Prueba
Desde , lo sabemos es una raíz del polinomio . Similar, es una raíz de . El factor linealdivide ambos polinomios . Por lo tanto, Eva calcula el máximo común divisor (mcd) de y , si el mcd resulta ser lineal, es encontrado. El mcd se puede calcular en tiempo cuadrático en y utilizando el algoritmo euclidiano .
Ataque de plataforma corta de calderero
Como el ataque de Håstad y Franklin-Reiter, este ataque explota una debilidad de RSA con exponente público. Coppersmith demostró que si el relleno aleatorio sugerido por Håstad se usa incorrectamente, el cifrado RSA no es seguro.
Supongamos que Bob envía un mensaje a Alice usando un pequeño relleno aleatorio antes de encriptarlo . Una atacante, Eve, intercepta el texto cifrado y evita que llegue a su destino. Bob decide reenviara Alice porque Alice no respondió a su mensaje. Él rellena al azarde nuevo y transmite el texto cifrado resultante. Eve ahora tiene dos textos cifrados que corresponden a dos encriptaciones del mismo mensaje usando dos almohadillas aleatorias diferentes.
Aunque Eve no sabe qué teclado aleatorio se está usando, aún puede recuperar el mensaje. utilizando el siguiente teorema, si el relleno aleatorio es demasiado corto.
- Teorema 4 (Calderero)
- Dejar ser una clave RSA pública donde es -bits de largo. Colocar . Dejar ser un mensaje de extensión como máximo bits. Definir y , dónde y son enteros distintos con . Si a Eva se le da y las encriptaciones de (pero no se da o ), puede recuperarse de manera eficiente .
- Prueba [1]
Definir y . Sabemos que cuando, estos polinomios tienencomo una raíz común. En otras palabras,es una raíz de la resultante . Además,. Por eso, es una pequeña raíz de modulo , y Eve puede encontrarlo de manera eficiente utilizando el método Coppersmith. Una vez se conoce, el ataque de Franklin-Reiter se puede utilizar para recuperar y consecuentemente .
Ver también
- Ataque ROCA
Referencias
- ^ a b c D. Boneh, Veinte años de ataques al criptosistema RSA
- ^ a b Glenn Durfee, Criptoanálisis de RSA usando métodos algebraicos y de celosía