Para generar un par de claves RSA de 2048 bits, debe generar dos números primos grandes con una longitud de 1024 bits. Que yo sepa, OpenSSL elige un número aleatorio de 1024 bits y comienza a buscar un número primo a su alrededor. ¿Cómo puede OpenSSL verificar si el número es primo o no tan rápido?
Probar la primalidad es mucho más fácil que realizar la factorización de enteros.
Hay varias formas de probar la primalidad, como el determinista Tamiz de Eratóstenes y el probabilístico Pruebas de primalidad de miller- Rabin . OpenSSL utiliza varias pruebas para verificar la primalidad. Primero, someten el número a los controles deterministas, intentando la división del candidato con una cantidad de números primos pequeños, luego una serie de pruebas de primalidad de Miller-Rabin. La gran mayoría de los números primos candidatos se descartan con la primera prueba de primalidad. Todos los candidatos que los aprueben están sujetos a nuevas rondas de pruebas, cada una de las cuales aumenta la certeza de que es una prioridad.
Cuando se usan las pruebas de Miller-Rabin, un número compuesto tiene un 75% de probabilidad de ser detectado como tal en cada ronda, por lo que después de solo 64 rondas de pruebas, la probabilidad de que un número compuesto no se detecte es de 2 < sup> -128 . En otras palabras, la prueba tiene una posibilidad de 4 -n de un falso negativo, donde n es el número de rondas de pruebas. También hay varias formas mucho más lentas de comprobar si un número es primo con certeza completa , como Prueba de primalidad Agrawal – Kayal-Saxena , pero para fines criptográficos, ser realmente, muy seguro es suficiente, por lo que no suelen ser utilizados.
Por defecto, OpenSSL tiende a ser paranoico extra y realiza otras pruebas, específicamente para un safe prime . Entonces, cuando se encuentra un número primo, p , también verifica si (p - 1) / 2 es primo. Esto es importante para aplicaciones específicas de números primos, como Diffie-Hellman, donde los números primos seguros evitan ciertos ataques.
Esto es posible a una alta velocidad porque verificar que un número entero es un número primo con un margen de error extremadamente bajo es significativamente más fácil que factorizarlo, y porque los números primos no son tan poco comunes (es fácil para encontrar un gran número de primos incrementando un número y probando la primalidad). La prueba de primalidad de Miller-Rabin es muy eficiente. La prueba demuestra la composición si x n - 1 ≢ 1 (mod n) (la Prueba de Fermat ), y comprobando si x (n - 1) / 2 e (mod n) es una no cuadrada raíz cuadrada de 1 mod n donde n es el entero que se está probando y x es un testigo aleatorio que satisface el intervalo < em> 1 < x < n .
La implementación de pseudocódigo de la prueba tomada de Wikipedia es:
Input: n > 3, an odd integer to be tested for primality;
k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2r·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
pick random integer a in the range [2, n − 2]
x ← ad mod n
if x = 1 or x = n − 1 then
continue WitnessLoop
repeat r - 1 times:
x ← x2 mod n
if x = 1 then
return composite
if x = n − 1 then
continue WitnessLoop
return composite
return probably prime
Consulte esta respuesta de Crypto.SE sobre la generación de claves RSA y FIPS 186-4 estándar, sección 5.1.
Lea otras preguntas en las etiquetas cryptography rsa openssl