Verificación de la primalidad de los números para su uso en RSA [cerrado]

RSA tiene garantizado el uso de números primos. De hecho, si los números no fueran números primos, las operaciones de la clave RSA simplemente no funcionarán (con una probabilidad abrumadoramente alta). Sin embargo, la utilidad de línea de comandos OpenSSL tiene la capacidad de verificar la primalidad de un número mediante la prueba de primalidad de Miller-Rabin, el algoritmo de prueba estándar para verificar números primos para su uso en criptografía:

OpenSSL> prime
No prime specified
options are
-hex           hex
-checks <n>    number of checks
-generate      generate prime
-bits <n>      number of bits
-safe          safe prime
error in prime
OpenSSL> prime -generate -bits 256
315016830147073940139675761214468273143
OpenSSL> prime 315016830147073940139675761214468273143
ECFE08DCA281B26A5EDDE8DF7D2A33F7 is prime
OpenSSL> prime 10000000000000
9184E72A000 is not prime

Creo que el número predeterminado de cheques es 64, pero puede aumentar esto para mejorar la precisión usando la opción -checks . Cada verificación ejecuta una ronda de prueba de Miller-Rabin que individualmente tiene un 75% de probabilidad de detectar que un número compuesto es de hecho compuesto. Específicamente, la posibilidad de no identificar un número compuesto como tal es 4 ^{- n} , donde n es el número de rondas utilizadas. Con el valor predeterminado de 64 rondas, esto es 4 ^-64 o 2 ^-128 . Para poner eso en perspectiva, si coloca un número compuesto en 64 rondas de pruebas de primalidad de MR, la posibilidad de que se etiquete falsamente como primo es equivalente a la posibilidad de adivinar correctamente una clave de cifrado de 128 bits en el primer intento.

He explicado más sobre las pruebas de primalidad en OpenSSL en otra respuesta .