cryptography - rabin - que significa primalidad
¿Cuántas iteraciones de Rabin-Miller debería usar para primos criptográficos seguros? (7)
Estoy generando un primer seguro de 2048 bits para una clave de tipo Diffie-Hellman, p, de manera que p y (p-1) / 2 son ambos primos.
¿Cuántas iteraciones de Rabin-Miller puedo usar tanto en p como en (p-1) / 2 y sigo confiando en una clave criptográficamente fuerte? En la investigación que he hecho, he escuchado de 6 a 64 iteraciones para números primos ordinarios de 1024 bits, por lo que estoy un poco confundido en este punto. Y una vez que está establecido, ¿cambia el número si está generando un primo seguro en lugar de uno común?
El tiempo de computación es escaso, por lo que esta es una pregunta práctica. Básicamente, me estoy preguntando cómo encontrar el menor número posible de pruebas que pueda realizar y al mismo tiempo mantener prácticamente la seguridad garantizada.
¿Importa? ¿Por qué no correr para 1000 iteraciones? Al buscar números primos, la primera vez que falla, deja de aplicar la prueba de Rabin-Miller, por lo que el tiempo que lleva encontrar un número primo no importa en realidad cuál sea el límite superior del número de iteraciones. Incluso podría ejecutar un algoritmo de comprobación de primalidad determinista después de esas 1000 iteraciones para estar completamente seguro.
Dicho esto, la probabilidad de que un número sea primo después de n iteraciones es 4 ^ -n.
Cada iteración de Rabin-Miller reduce las probabilidades de que el número esté compuesto por un factor de 1/4.
Entonces, después de 64 iteraciones, solo hay 1 posibilidad en 2 ^ 128 de que el número sea compuesto.
Suponiendo que los está utilizando para un algoritmo de clave pública (por ejemplo, RSA), y suponiendo que lo está combinando con un algoritmo simétrico utilizando (digamos) claves de 128 bits, un adversario puede adivinar su clave con esa probabilidad.
La conclusión es elegir el número de iteraciones para colocar esa probabilidad dentro del campo de juego de los otros tamaños que elija para su algoritmo.
[actualización, para elaborar]
La respuesta depende completamente de para qué algoritmos va a utilizar los números y cuáles son los ataques más conocidos contra esos algoritmos.
Por ejemplo, según Wikipedia :
A partir de 2003, RSA Security afirma que las claves RSA de 1024 bits tienen una fuerza equivalente a las claves simétricas de 80 bits, las claves RSA de 2048 bits a las claves simétricas de 112 bits y las claves RSA de 3072 bits a las claves simétricas de 128 bits.
Entonces, si planea usar estos números primos para generar (por ejemplo) una clave RSA de 1024 bits, entonces no hay razón para ejecutar más de 40 iteraciones de Rabin-Miller. ¿Por qué? Porque para cuando llegas a fallar, un atacante podría romper una de tus claves de todos modos.
Por supuesto, no hay razón para no realizar más iteraciones, si el tiempo lo permite. Simplemente no tiene mucho sentido hacerlo.
Por otro lado, si está generando claves RSA de 2048 bits, entonces son más apropiadas 56 (o así) iteraciones de Rabin-Miller.
La criptografía se construye típicamente como una composición de primitivos, como la generación principal, RSA, SHA-2 y AES. Si quieres hacer que una de esas primitivas sea 2 ^ 900 veces más fuerte que las otras, puedes hacerlo, pero es como poner una puerta de bóveda de acero de 10 pies en una cabaña de troncos.
No hay una respuesta fija a su pregunta. Depende de la fuerza de las otras piezas que entran en su sistema criptográfico.
Dicho todo esto, 2 ^ -128 es una probabilidad ridículamente pequeña, así que probablemente solo usaría 64 iteraciones :-).
De la fuente de libgcrypt: /* We use 64 Rabin-Miller rounds which is better and thus sufficient. We do not have a Lucas test implementaion thus we can''t do it in the X9.31 preferred way of running a few Rabin-Miller followed by one Lucas test. */ /* We use 64 Rabin-Miller rounds which is better and thus sufficient. We do not have a Lucas test implementaion thus we can''t do it in the X9.31 preferred way of running a few Rabin-Miller followed by one Lucas test. */ /* We use 64 Rabin-Miller rounds which is better and thus sufficient. We do not have a Lucas test implementaion thus we can''t do it in the X9.31 preferred way of running a few Rabin-Miller followed by one Lucas test. */ cipher / primegen.c line # 1295
Dirigiría dos o tres iteraciones de las pruebas de Miller-Rabin (es decir, fuerte probable de Fermat fuerte), asegurándome de que una de las bases sea 2.
Luego ejecutaría una fuerte prueba de probables pruebas de Lucas, eligiendo D, P y Q con el método descrito aquí: https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test
No hay compuestos conocidos que pasen esta combinación de pruebas de Fermat y Lucas.
Esto es mucho más rápido que hacer 40 iteraciones de Rabin-Miller. Además, como lo señalaron Pomerance, Selfridge y Wagstaff en https://math.dartmouth.edu/~carlp/PDF/paper25.pdf , hay rendimientos decrecientes con múltiples pruebas de Fermat: si N es una pseudoprima a una base, entonces es más probable que el número promedio sea una seudoprima para otras bases. Es por eso que, por ejemplo, vemos que la base 2 de psp también es la base 3 de psp.
Supongamos que selecciona una p principal seleccionando valores aleatorios hasta que encuentre una para la que Miller-Rabin diga: esa parece ser una prima. Usas n rondas como máximo para la prueba de Miller-Rabin. (Para una llamada "prima segura", las cosas no se cambian, excepto que se ejecutan dos pruebas anidadas).
La probabilidad de que un entero de 1024 bits aleatorio sea primo es aproximadamente 1/900. Ahora, no desea hacer nada estúpido por lo que genera solo valores impares (se garantiza que un entero par de 1024 bits no es primo) y, más generalmente, ejecuta la prueba de Miller-Rabin solo si el valor no es "obviamente "no principal, es decir, se puede dividir por una prima pequeña. Así que terminas probando unos 300 valores con Miller-Rabin antes de alcanzar un prime (en promedio). Cuando el valor no es primo, Miller-Rabin lo detectará con una probabilidad de 3/4 en cada ronda, por lo que el número de rondas de Miller-Rabin que ejecutará en promedio para un solo valor no primo es de 1+ (1/4 ) + (1/16) + ... = 4/3. Para los 300 valores, esto significa aproximadamente 400 rondas de Miller-Rabin, independientemente de lo que elija para n .
Entonces, si selecciona n para ser, por ejemplo, 40, entonces el costo implícito por n es menor que el 10% del costo computacional total. El proceso de selección de primos aleatorios está dominado por la prueba en primos, que no se ven afectados por el valor de n que elija. Hablé aquí sobre los enteros de 1024 bits; para números más grandes, la elección de n es aún menos importante ya que los números primos se vuelven más dispersos a medida que aumenta el tamaño (para enteros de 2048 bits, el "10%" de arriba se convierte en "5%").
Por lo tanto, puede elegir n = 40 y estar contento con él (o al menos saber que reducir n no le comprará mucho de todos modos). Por otro lado, el uso de una n mayor que 40 no tiene sentido, porque esto te llevaría a probabilidades más bajas que el riesgo de una simple falta de cómputo. Las computadoras son hardware, pueden tener fallas aleatorias. Por ejemplo, una función de prueba de primalidad podría devolver "verdadero" para un valor no primo debido a que un rayo cósmico (una partícula de alta energía que circula a través del Universo a alta velocidad) golpea justo el transistor correcto en el momento correcto, volteando el devuelva el valor de 0 ("falso") a 1 ("verdadero"). Esto es muy improbable, pero no menos probable que la probabilidad 2 -80 . Vea esta respuesta de para más detalles. La conclusión es que, independientemente de cómo se asegure de que un entero sea primo, todavía tenga un elemento probabilístico inevitable, y 40 rondas de Miller-Rabin ya le dan lo mejor que pueden esperar.
Para resumir, usa 40 rondas.
Una probabilidad menor suele ser mejor, pero tomaría el valor de probabilidad real con un grano de sal. Albrecht et al Prime and Prejudice: las pruebas de primalidad en condiciones adversas rompen una serie de rutinas de pruebas prime en bibliotecas criptográficas. En un ejemplo, la probabilidad publicada es 1/2 ^ 80, pero el número que construyen se declara primo 1 vez de 16.
En varios otros ejemplos, su número pasa el 100% del tiempo.
Las estimaciones promedio de error de caso del papel para la prueba principal fuerte probable de Damgard-Landrock-Pomerance señalan que, si selecciona aleatoriamente el número impar k bit n y aplica t pruebas independientes de Rabin-Miller en sucesión, la probabilidad de que n sea un compuesto Tiene límites mucho más fuertes.
De hecho, para 3 <= t <= k/9 y k >= 21 ,
Para un k=1024 bit prime, t=6 iteraciones le dan una tasa de error inferior a 10^(-40) .