RSA estandares para la generacion de primos

[daryo]

leyendo un articulo de kriptopolis sobre el rsa, encontre que ademas del tamaño de los numeros primos hay otros parametros para evitar que sean dificiles de hayar

Para que la codificación RSA sea segura, los primos "p" y "q" elegidos deben cumplir ciertas condiciones. De lo contrario, puede romperse fácilmente el sistema, independientemente de lo grandes que sean "p" y "q". Ahora mismo sólo recuerdo dos de esas condiciones. Una es que "p" y "q" deben ser de tamaños en bits parecidos, pero deben tener una diferencia lo suficientemente grande como para impedir su descomposición prima con el método de factorización de Fermat. Otra creo recordar que "p-1" y "q-1" deben estar compuestos por primos grandes (no cuenta el 2, por supuesto), que si no se cumple, puede romperse el código también.

queria saber si alguien conoce sobre esto y pueda ampliar la info

http://www.kriptopolis.com/entender-rsa

[kub0x]

Buenas daryo,

es grato saber que te interesas por la criptografía asimétrica. Trataré de ser lo más conciso posible. Eso sí, hecho de menos la notación matemática de latex, será duro describirlo.

RSA basa su seguridad en la elección de dos primos ambos del mismo tamaño, actualmente, 2048 bit o superior, ya que se ha demostrado que 1024 bits no son suficientes.

Los primos antes de su elección son sometidos a un test de primalidad basado en la probabilidad, este test es el de Miller-Rabin, y nos asegura que la probabilidad de que un entero positivo sea pseudoprimo (falso primo) sea ínfima. El par de primos debe de tener una diferencia signicativa  -> Δ>2^((k/2)−100).

Ahora se compone la clave pública mediante el producto de ambos primos, por lo tanto la clave pública corresponde a un número semiprimo.

N = p.q y su tamaño en bits será el doble de cualquiera de los primos.

Ahora, calculamos el totient de N, siendo el totient los enteros menores o iguales que N coprimos con N. Con esto quiero decir que el totient devuelve la cantidad de enteros positivos que no comparten ningún factor con N, es decir, aquellos números que no han sido formados por 'p' o por 'q'. Piensa, todos los números primos menores que N son coprimos con N directamente, y luego, también serán coprimos los productos de esos primos entre sí, excluyendo los productos que incluyen a 'p' y 'q'.

phi(N) = N - p - q + 1 // A 'N' le quitas los múltiplos de 'p' y de 'q' excluyendo el múltiplo p.q (por eso sumo +1).
phi(N) = (p-1)(q-1) // Es la ecuación de arriba abreviada

Una vez que tenemos el totient, calculamos la clave privada mediante la multiplicativa inversa de modulo N. Esta clave se utilizará para cifrar o firmar texto plano.

e.d = 1 (mod phi(N)) // Siendo e = 2^16 + 1 = 65537 pues debe ser coprimo con N sino seria trivial atacarlo.

Para entender esta operación debes primero entender bien como funcionan los grupos multiplicativos de enteros módulo N, dónde a cada clase de congruencia o entero le corresponde otra clase que satisface la propiedad multiplicativa.

Ten en cuenta que los grupos multiplicativos de enteros mod N son la base de Diffie-Hellman, DSA, El-Gamal y del cifrado/descifrado/firmado en RSA. Aquí puedes aprender más -> https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n también recomiendo Khan Academy o mismamente YouTube para aprender más. Si te interesa, te adelanto, te lo pasarás en grande.

Ahora que está formado el esquema completo, comentaré los posibles vectores de ataque en RSA:

- Para enviar un mensaje cifrado en RSA componemos el ciphertext mediante s = m ^ e (mod N). Si m^e es menor que N entonces s=m^e y m=pow(m^e, 1/e) y habrás obtenido el mensaje, pues m^e < N y m equivale a la raíz e-ésima.

- Se han dado varios fallos de implementación (OpenSSL entre ellos) dónde varías claves públicas compartían factores primos entre sí, por lo que se ideó un proyecto para almacenar claves públicas y mediante el greatest common divisor obtener los factores primos compartidos. Obviamente con un sólo factor obtienes el otro.

- En el campo de los grupos multiplicativos mod N RSA a diferencia de Diffie-Hellman no utiliza un divisor primo por lo que reduce su espacio de congruencias, así como la base también es distinta dependiendo del mensaje a firmar, por lo que podrían existir más de una clave privada 'd' menor que la actual, ya que el totient de N tiene varios factores primos. Si se quiere implementar de forma segura un algoritmo de firma o cifrado basado en este tipo de esquema se deben de utilizar raíces primitivas.

- En TLS (dejemos atrás a SSL) se descubrió una vulnerabilidad llamada FREAK que permitía degradar el tamaño en bits de la clave pública, por lo que reducía el problema de factorización puediendo así completar el Handshake TLS.

-En los certificados actuales se incluyen firmas digitales preferiblemente SHA-256 ya que SHA-1 se ha concretado inseguro. Dichas firmas van firmadas con la clave privada de la CA que emitió el certificado. Cuando visitas una web vía HTTPS te presentan el certificado y tu descifras la firma digital con la clave pública de la CA que emitió el certificado recibido. Si el descifrado equivale al SHA-256 del certificado presentado entonces fue emitido por la CA que debe de ser de confianza y además el certificado no fue modificado. Aquí mediante colisionamiento se demostró en MD5 que se podía falsificar una firma en un certificado modificado. En SHA-1 se han hecho papers teorizándolo, que yo sepa hasta el momento.

Si te quedó alguna cuestión no dudes en comentarla.

Saludos.

[daryo]

muchas gracias kub0x si tengo dudas vendre de nuevo a molestar

[engel lex]

No se si te ayude, pero aquí dejo esto
http://foro.elhacker.net/scripting/algortimo_rsa_en_phyton-t427548.0.html;msg1987982#msg1987982