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

No hay 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 a p-1 para todos los primos p que dividen el módulo).

Si usa un pequeño exponente y no usa ningún relleno para el cifrado y encripta exactamente el mismo mensaje con varios públicos distintos claves, entonces su mensaje está en riesgo: si e = 3 , y usted cifra el mensaje m con las claves públicas n ₁ , n₂ y n₃ , entonces tienes c _i = m ³ mod n_i para i = 1 a 3 . Mediante el Teorema del Resto Chino , puede reconstruir m³ mod n₁n₂n₃ , que resulta ser m ³ (sin modulo) porque n₁n₂n₃ es un número 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 inadecuado (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 descritos 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 del exponente, se refiere más o menos directamente a esta ocurrencia. Eso es un poco de tradición antigua e incorrecta, que a veces se invierte en una prohibición contra los exponentes de big (ya que es un mito, el mito inverso también es un mito y no es más, y no menos, - fundamentado); Creo que esto es lo que observas aquí.

Sin embargo, se pueden encontrar algunas razones por las que 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 al tener un pequeño exponente privado ; se ha descrito un ataque de recuperación de clave cuando la longitud del exponente privado no es más del 29% de la longitud del exponente público. Cuando quiere forzar que el exponente privado sea corto (por ejemplo, para acelerar las operaciones de clave privada), más o menos tiene que usar un gran exponente público (tan grande como el módulo); exigir que el exponente público sea corto puede verse como una especie de contramedida indirecta.

• Algunas implementaciones de RSA ampliamente implementadas ahogan a los grandes exponentes públicos de RSA. P.ej. el código RSA en Windows (CryptoAPI, utilizado 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.

Sin embargo, "los riesgos pueden ser grandes" parece que 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").

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 inadecuado. Esos ataques se evitan mediante el uso adecuado del relleno. Cualquier biblioteca de cifrado que valga la pena tenerla sería mejor que estuviera usando el relleno adecuado (de lo contrario, tendrá problemas mucho peores).

Por lo tanto, no hay una buena razón para que una biblioteca criptográfica prohíba totalmente el uso de ese exponente.

Dicho esto, desde una perspectiva de rendimiento, cuanto más pequeño 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 de Rabin. Sin embargo, este esquema no es tan conocido y requiere un código ligeramente diferente, por lo que no se usa mucho).

Esos cinco números son Fermat primes .

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

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

Así que esto es más probable sobre la velocidad o la convención que sobre la seguridad. No es que haya nada malo en ser eficiente. Pero para estar seguro, solicite una referencia como otra respuesta sugerida.

También vea esta publicación .

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

Usted no debe estar satisfecho con la respuesta dada por los desarrolladores de la biblioteca que utiliza y pedir una referencia concreta. Con demasiada frecuencia, resulta que algunos papeles fueron mal entendidos. Por ejemplo, podría imaginar que un 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 la anterior. Este documento advierte que cuando la clave pública generada por GnuPG resulta ser un valor inusual como 65539, el atacante aprende un poco de información sobre la clave secreta. La conclusión es que el algoritmo de generación de claves de GnuPG podría mejorarse, pero no que 65539 sea una clave pública incorrecta.

No pude encontrar ninguna referencia de que otros valores para el exponente público sean vulnerables. Se recomienda utilizar un exponente público cercano a una potencia de 2 por razones de rendimiento, de acuerdo con el RSA. guía com para el algoritmo RSA

Según Wikipedia , NIST no permite un exponente público más pequeño que 65537, ya que los exponentes más pequeños son un problema si no están debidamente rellenados.

Para citar el documento de 1997 de Don Coppersmith "Pequeñas soluciones a ecuaciones polinómicas y vulnerabilidades de RSA de bajo exponente":

  

El cifrado RSA con exponente 3 es vulnerable si el oponente conoce dos tercios del mensaje.

Si bien esto puede no ser un problema si se usa el esquema de relleno RSA-OAEP, el esquema de relleno PKCS # 1 (que se proporciona como un esquema de relleno adecuado en las respuestas a continuación) es vulnerable si se usa el exponente público 3.