Qué tan malo es 3 como exponente público de RSA

Question

Estoy creando una aplicación en la que tengo que usar RSA para encriptar algunas cosas usando una clave pública. Quiero que esta encriptación sea realmente rápida. Inicialmente, probé una clave de 2048 bits con F4 (= 65537) como exponente, pero no es lo suficientemente rápido. Así que ahora estoy teniendo en cuenta las siguientes 2 opciones:

1. 2048 módulo de bits, e = 3
2. 1024 módulo de bits, e = 65537

Tanto satisfacer mis requerimientos de desempeño, pero que uno proporciona una mejor ¿seguridad? También debería tener en cuenta que utilizo el esquema de relleno PKCS # 1.

Answer 1

Si usa relleno aleatorio como OAEP en PKCS n. ° 1, la mayoría (¿todas?) De las debilidades conocidas al usar exponentes bajos ya no son relevantes.

¿Has probado con e = 17? No hay ninguna regla que indique que debe elegir 3 o 65537.

Answer 2

Si el exponente es baja y el valor de m * e < módulo, que sólo puede tomar la raíz eth del texto cifrado para descifrar.

Esto es de mis notas sobre criptografía de hace dos años. Pero, en respuesta a su pregunta, parecería que la opción 2 es mejor.

Alguien que esté más dispuesto a hacer matemáticas podría darle una mejor explicación de por qué.

Answer 3

En su libro 'Practical Cryptography', Bruce Schneier y Niels Ferguson sugieren utilizar un exponente público de 3 para las firmas y 5 para el cifrado. Debe verificar los otros criterios que recomiendan para evitar catástrofes. La sección 13.4 cubre esto (p229ff), y discute el requisito no muy complejo dado que n = pq (donde pyq son primos aleatorios), ni (p-1) ni (q-1) puede ser un múltiplo de 3 o 5 .Pero aun así, revisa el libro para ver los detalles.

(Creo que hay una new edition del libro que saldrá en 2010.)

Answer 4

Siempre que se utiliza un buen esquema de relleno, entonces no hay razón conocida por e = 3 deben tener un peor de seguridad que cualquier otro exponente público. Usar un exponente corto tiene problemas si tampoco usa un buen esquema de relleno, pero el problema radica más en el esquema de relleno que en el exponente.

La "primera impresión" de muchos investigadores es que e = 3 no es mejor que cualquier otro exponente público, y e = 3 podría llegar a ser un poco más débil en cualquier momento posterior, aunque los puntos nada en tales una debilidad en este momento.

La longitud de la clave tiene un impacto práctico mucho mayor en la seguridad. Recientemente se ha descifrado una clave RSA de 768 bits (¡esto no fue fácil! Cuatro años de trabajo con computadoras grandes y cerebros más grandes). Una clave de 1024 bits se considera adecuada para el corto plazo, pero los usos a largo plazo (por ejemplo, los datos cifrados tienen un alto valor y aún deben ser confidenciales en el año 2030) exigirían algo más grande, p. 2048 bits. Ver this site para obtener mucha información sobre cómo se puede estimar la fuerza criptográfica y ha sido estimada por varios investigadores y organizaciones.

Si busca cifrado asimétrico muy rápido, es posible que desee investigar Rabin-Williams encryption scheme, que es más rápido que RSA, al tiempo que proporciona al menos el mismo nivel de seguridad para la misma longitud de salida (pero no es fácil de usar un estándar detallado para ese esquema, contrariamente a RSA con PKCS # 1, por lo que está un poco solo aquí).

Answer 5

Si bien actualmente no se conoce ningún ataque en caso de que se use un relleno correcto, los exponentes pequeños tienen más probabilidades de generar exploits en caso de errores de implementación. Y los errores de implementación lamentablemente siguen siendo una amenaza. P.ej. this es una vulnerabilidad que fue bastante "popular". (Nota, esto es para firmas. Solo quiero mostrar que incluso el software comercial puede tener errores graves.)

Si tiene que tomar atajos, debe tener en cuenta las implicaciones potenciales de sus acciones. Es decir. elegir un pequeño módulo o un pequeño exponente ambos tienen sus propios inconvenientes.

Si elige un módulo pequeño (1024 bit), no puede asumir que sus datos pueden mantenerse confidenciales durante décadas.

Si elige un exponente pequeño, es posible que sea más susceptible a errores de implementación.

En el primer caso, sabes muy bien cuando tus secretos están en peligro, ya que es bastante fácil seguir el progreso en el factoring. (Esto supone por supuesto que las agencias que no publican, por ejemplo, NSA, no son su enemigo). En el segundo caso (errores de implementación), no sabe cuándo cometió un error. Puede estar seguro usando e = 3 o podría haber cometido un gran error. Es decir. en un caso, tiene una forma bastante buena de estimar su riesgo y, en el otro caso, no.

Por lo tanto, yo recomendaría no utilizar e = 3 en absoluto. Utilizaría más margen de seguridad frente a las amenazas que son difíciles de predecir, que aquellas amenazas que se publicitan ampliamente.

Answer 6

su información, ver esto por un poco de historia: http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-forgery-explained-with-nate-lawson-part-iv.html

Answer 7

Para citar 1997 papel "pequeñas soluciones a ecuaciones polinómicas y baja exponente RSA vulnerabilidades" de Don Coppersmith:

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 utiliza esquema de relleno RSA-OAEP, el esquema de relleno PKCS # 1 (que está utilizando op) es vulnerable si se utiliza exponente público 3.