it-swarm-es.com

¿El exponente público de RSA debe estar solo en {3, 5, 17, 257 o 65537} debido a consideraciones de seguridad?

En mi proyecto estoy usando el valor de exponente público de 4451h. Pensé que era seguro y correcto hasta que comencé a usar una biblioteca comercial de cifrado RSA. Si uso este exponente con esta biblioteca, arroja una excepción.

Me puse en contacto con los desarrolladores de esta biblioteca y obtuve la siguiente respuesta: "Esta característica es para evitar algunos ataques a las claves RSA. La consecuencia es que el valor del exponente está limitado a {3, 5, 17, 257 o 65537}. La desactivación de esta comprobación es aún se está investigando, ya que los riesgos pueden ser grandes ".

Es la primera vez en mi vida que escucho que se utilizan valores distintos de {3, 5, 17, 257 o 65537} para romper el RSA. Solo sabía de usar 3 con relleno incorrecto siendo vulnerable.

¿Es eso realmente así? Seguramente, puedo usar otra biblioteca, pero después de tal respuesta me preocupé por la seguridad de mi solución.

70

No existe debilidad conocida para ningún exponente público corto o largo para RSA, siempre que el exponente público sea "correcto" (es decir, relativamente primo para p-1 para todos los primos p que divide el módulo).

If usa un pequeño exponente y no usa ningún relleno para el cifrado y usted cifra exactamente el mismo mensaje con varias claves públicas distintas, entonces su mensaje está en riesgo: si e = 3, y encripta el mensaje m con claves públicas n1, n2 y n3, entonces tienes cyo = m3 mod nyo para i = 1 a 3. Por el Teorema del resto chino , puedes reconstruir m3 mod n1norte2norte3, que resulta ser m3 (sin ningún módulo) porque n1norte2norte3 es un entero mayor. Una extracción de raíz cúbica (no modular) es suficiente para extraer m.

La debilidad, aquí, es no el pequeño exponente; más bien, es el uso de un relleno incorrecto (es decir, sin relleno) para el cifrado. El relleno es muy importante para la seguridad de RSA, ya sea encriptación o firma; Si no utiliza un relleno adecuado (como los que se describen en PKCS # 1 ), entonces tiene muchas debilidades, y la que se describe en el párrafo anterior no es la más grande, con diferencia. Sin embargo, cada vez que alguien se refiere a una debilidad relacionada con el tamaño de exponente, se refiere más o menos directamente a este hecho. Eso es un poco de historia antigua e incorrecta, que a veces se invierte en una prohibición contra exponentes ¡grande (ya que es un mito, el mito inverso también es un mito y ya no lo es - y no menos justificado); Creo que esto es lo que observas aquí.

Sin embargo, uno puede encontrar algunas razones por las cuales se debe evitar un gran exponente público:

  • Los pequeños exponentes públicos promueven la eficiencia (para operaciones de clave pública).

  • Hay problemas de seguridad acerca de tener un pequeño privado exponente; Se ha descrito un ataque de recuperación de clave cuando la longitud del exponente privado no supera el 29% de la longitud del exponente público. Cuando desee forzar que el exponente privado sea corto (por ejemplo, para acelerar las operaciones de clave privada), más o menos tendrá que usar un exponente público grande (tan grande como el módulo); exigir que el exponente público sea breve puede verse como una especie de contramedida indirecta.

  • Algunas implementaciones de RSA ampliamente implementadas se ahogan con grandes exponentes públicos de RSA. P.ej. el código RSA en Windows (CryptoAPI, usado por Internet Explorer para HTTPS) insiste en codificar el exponente público dentro de una sola palabra de 32 bits; no puede procesar una clave pública con un exponente público más grande.

Aún así, "los riesgos pueden ser grandes" parece la justificación genérica ("este es un problema de seguridad" es la forma habitual de decir "no lo implementamos pero no queremos admitir ningún tipo de pereza").

64
Thomas Pornin

Los desarrolladores son simplemente incorrectos. No hay nada malo con el exponente 0x4451 (decimal 17489); No crea ningún problema de seguridad.

Hace mucho tiempo, la gente solía pensar que los pequeños exponentes eran un problema, debido a un ataque que Thomas Pornin explicó al enviar el mismo mensaje a múltiples destinatarios. Pero hoy entendemos que los exponentes no tuvieron nada que ver con eso; El problema era el relleno incorrecto. Esos ataques se evitan mediante el uso adecuado de relleno. Cualquier biblioteca criptográfica que valga la pena debería estar usando un relleno adecuado (de lo contrario, tendrá problemas mucho peores).

Entonces, no hay una buena razón para que una biblioteca de cifrado prohíba rotundamente el uso de ese exponente.

Dicho esto, desde una perspectiva de rendimiento, cuanto menor sea el exponente, mejor será el rendimiento. La mejor opción es e = 3, porque proporciona el mejor rendimiento y no tiene problemas de seguridad conocidos. (En realidad, e = 2 es incluso un poco mejor. También se conoce como cifrado Rabin. Sin embargo, ese esquema no es tan conocido y requiere un código ligeramente diferente, por lo que no se usa ampliamente).

21
D.W.

Esos cinco números son primos de Fermat .

Ya que son de la forma 2 k  + 1, el cifrado es m e  = m · (( m 2)2... k veces...)2, que es más simple y más rápido que la exponenciación con un exponente de un tamaño similar en caso general .

Como son números primos, la prueba de que e es coprimo a ( p - 1) ( q - 1) es solo una prueba que e no lo divide.

Por lo tanto, es más probable que se trate de velocidad o convención que de seguridad. No es que haya nada malo en ser eficiente. Pero para estar seguro, solicite una referencia como otra respuesta sugerida.

Ver también esta publicación .

19
aaz

No conozco ninguna razón por la cual el exponente público de una clave RSA solo debe estar en el conjunto {3,5,17,257,65537}. Como mencionas, los exponentes pequeños como 3 o 5 son más riesgosos de usar, porque los efectos negativos de los errores de implementación (como el relleno incorrecto) pueden ser mayores. NIST solo permite exponentes públicos mayores de 2 ^ 16, pero no sé una razón para su decisión.

No debe estar satisfecho con la respuesta dada por los desarrolladores de la biblioteca que utiliza y solicitar una referencia concreta. Con demasiada frecuencia, resulta que algunos documentos fueron mal interpretados. Por ejemplo, podría imaginar que algún desarrollador lee la Sección 4 del documento "¿Podemos confiar en el software criptográfico? Defectos criptográficos en GNU Privacy Guard v1.2.3" de Phong Nguyen y llega a una conclusión incorrecta, como el anterior. Este documento observa que cuando la clave pública generada por GnuPG resulta ser un valor inusual como 65539, entonces el atacante aprende un poco de información sobre la clave secreta. La conclusión es que el algoritmo de generación de claves GnuPG podría mejorar, pero no es que 65539 sea una mala clave pública.

8
Accipitridae

No pude encontrar ninguna referencia de que otros valores para el exponente público son vulnerables. Es difícil usar un exponente público cercano a una potencia de 2 por razones de rendimiento, de acuerdo con guía de RSA.com para el algoritmo RSA

De acuerdo con Wikipedia , NIST no permite un exponente público menor que 65537, ya que los exponentes más pequeños son un problema si no se rellenan correctamente.

7
Andreas Arnold