¿Qué método se usa para verificar la primalidad del número en la criptografía RSA?

Answer 1

Por lo general, se realizan múltiples pruebas aleatorias de Miller-Rabin. El código es lo suficientemente simple como para no haber visto problemas de malas implementaciones, y las posibilidades de que los compuestos pasen incluso una prueba en tamaños RSA son extremadamente pequeñas.

Los problemas típicos no son una falla de múltiples pruebas de MR que pasan un compuesto, sino problemas estructurales donde los números de alguna manera ni siquiera obtuvieron una prueba básica.

FIPS 186–4 tiene mucha información sobre este tema para RSA, DSA y ECDSA. Incluye recomendaciones para la cantidad de pruebas de MR, así como la recomendación de incluir una prueba de Lucas. Hay implementaciones de pseudocódigo de la mayoría de las funciones necesarias para las implementaciones. También muestran un algoritmo recomendado de Shawe-Taylor.

Existen algunos otros métodos, como los generadores principales probados. Esto incluye el método de Maurer (existen varias implementaciones en diferentes idiomas) y Shawe-Taylor. Estos crean primos probados al azar utilizando pruebas básicas (teorema de Pocklington o BLS75 3 o 5). Sin embargo, no conozco muchos programas que los utilicen (en código abierto sospecho que la mayoría de la gente nunca ha oído hablar de ellos).

Soy consciente de un módulo que realiza pruebas de primalidad opcionales utilizando ECPP en el primo aleatorio, pero es muy poco común. Creo que usar BPSW (una prueba de Miller-Rabin de base 2 más una prueba fuerte de Lucas) más pruebas de Miller-Rabin adicionales opcionales será lo suficientemente rápido y bueno. Llegamos a 36 años sin encontrar un solo contraejemplo BPSW incluso con búsquedas específicas.