Número primo aleatorio

En criptografía , se entiende por número primo aleatorio un número primo que contiene un número determinado de bits en notación binaria , sobre cuyo algoritmo de generación se imponen ciertas restricciones. La generación de números primos aleatorios es una parte integral de los procedimientos de obtención de claves en muchos algoritmos criptográficos, incluidos RSA y ElGamal .

Debido al hecho de que probar la simplicidad de números grandes requiere costos de tiempo significativos, el requisito de la simplicidad del número resultante a menudo se debilita a una fuerte seudosimplicidad por varias razones aleatorias diferentes. Los algoritmos de prueba de seudosimplicidad fuertes existentes son órdenes de magnitud más rápidos que los algoritmos de prueba de primalidad más conocidos. Al mismo tiempo, los números que superan con éxito la prueba de pseudosimplicidad fuerte en varias bases aleatorias son primos con una alta probabilidad, y esta probabilidad crece con el número de bases sobre las que se realiza la prueba.

Requisitos para el algoritmo y su implementación

Los requisitos de los algoritmos para generar números primos aleatorios se reducen a los dos siguientes:

• La distribución de los números primos resultantes debe ser casi uniforme en el conjunto de todos los números primos de k bits. Hay varias formas de garantizar que se cumpla este requisito.
• El proceso de generar un número primo aleatorio particular no se puede reproducir, incluso conociendo los detalles del algoritmo y su implementación. Por lo general, este requisito se cumple mediante el uso de un PRNG seguro inicializado con alguna clave obtenida del exterior (es decir, que no forma parte del algoritmo ni de su implementación). La clave puede ser, por ejemplo, el valor de la función hash criptográfica de la frase secreta solicitada al usuario.

Algoritmos típicos para generar números primos aleatorios

En todas partes a continuación se supone que se utiliza un PRNG criptográficamente fuerte inicializado con una clave secreta (los detalles dependen del PRNG utilizado y de cómo se obtiene y presenta la clave).

Pruebas de simplicidad

Puede verificar la primacía (probable) de un número p que contiene k bits como este:

1. Asegúrese de que p no sea divisible por pequeños números primos 3, 5, 7, 11, etc. hasta un pequeño límite (por ejemplo, 256). Tal verificación le permite cortar de manera efectiva una gran cantidad de números obviamente compuestos antes de verificarlos con algoritmos que consumen más tiempo. Entonces, comprobar que p es divisible por los números primos 2, 3, 5 y 7 filtra todos los números pares y el 54 % de los números impares, comprobar que p es divisible por todos los números primos hasta 100 filtra el 76 % de los números impares , y comprobando que p es divisible por todos los números primos hasta 256 elimina el 80% de los números impares.
2. Ejecute la prueba de Miller-Rabin con al menos k rondas .

Si el número p falla al menos una verificación, no es primo. De lo contrario, con alta probabilidad (dependiendo del número de rondas) el número p es primo.

Construcción directa

1. Genere bits aleatorios y compóngalos en un número p de k bits con el bit más significativo igual a 1.
2. Aumenta p en 1 y comprueba si es primo. Repita este paso hasta encontrar un número primo.

El segundo paso puede acelerarse si consideramos solo números impares o números comparables a 1 y 5 módulo 6, etc.

( n - 1)-métodos

Los métodos de construcción de primos ( n -1) usan el conocimiento de los divisores primos de n -1 para probar si n es primo usando la prueba de primalidad de Lucas . [una]

Un representante típico de esta clase de métodos se describe en el libro "Introducción a la criptografía" editado por V. V. Yashchenko. [2]

Generación de números primos Sophie Germain

Los primos de Sophie Germain  son primos p tales que 2p + 1 también es primo.

Notas

1. ↑ Cheryomushkin A.V. Conferencias sobre algoritmos aritméticos en criptografía. - M. : MTSNMO , 2002. - 104 p. — ISBN 5-94057-060-7 .
2. ↑ Yu. V. Nesterenko. Capítulo 4.5. Cómo construir números primos grandes // Introducción a la criptografía / Ed. V. V. Yashchenko. - Pedro, 2001. - 288 p. - ISBN 5-318-00443-1 . Copia archivada (enlace no disponible) . Fecha de acceso: 18 de febrero de 2008. Archivado desde el original el 25 de febrero de 2008. (indefinido)