La dificultad de generar primos de 1024 bits

• Es un experimento en el que se generan directamente en Rust los dos números primos de alrededor de 1024 bits necesarios para una clave RSA de 2048 bits, implementando desde la generación de números aleatorios hasta la aritmética de enteros grandes sin dependencias externas.
• La trial division simple era suficiente para 16 bits, con unos 40 ms, pero incluso en 64 bits tardó 6.4 segundos después de optimizarla, por lo que era difícil escalarla a 1024 bits.
• La prueba de Fermat es rápida, pero puede no filtrar pseudoprimes, así que para la decisión final se usa la prueba de Miller-Rabin con k=10.
• Para superar los límites de los tipos enteros básicos, se implementó un BigInt propio; al pasar de arreglos de bool a arreglos de bytes y luego a una estructura de chunks u64, el tiempo para generar un primo de 1024 bits bajó de unos 32 minutos a un rango de 60 a 90 segundos.
• La implementación final combina un BigInt con chunks u64, división rápida, trial division con primos pequeños, incremento de candidatos con +2 y ejecución paralela en 16 hilos, logrando encontrar un primo de 1024 bits en unos 40 ms en promedio, aunque no es una biblioteca criptográfica validada.

---

Crear directamente primos de 1024 bits para RSA

• El objetivo era generar directamente números primos que pudieran usarse para generar claves RSA.
  • Como una clave RSA de 2048 bits se construye como el producto de dos primos, se necesitan primos de alrededor de 1024 bits cada uno.
  • El reto se redujo de forma natural a la generación de primos de 1024 bits.
• El experimento tuvo tres restricciones.
  • Escribir el código desde cero y no usar dependencias externas.
  • Usar una laptop con CPU AMD Ryzen 7 y 16 GB de RAM, sin hardware externo ni nube.
  • Generar los primos en un “tiempo razonable”.
• El lenguaje elegido fue Rust, que estaba aprendiendo recientemente.
  • Lo consideré lo bastante cercano para trabajar con conceptos de bajo nivel, y lo bastante de alto nivel para entender fragmentos de código.

Los límites de la trial division revelados en 16 y 64 bits

• El flujo básico consiste en generar repetidamente números aleatorios de N bits y terminar cuando uno pasa la prueba de primalidad.
• Los números aleatorios se generan leyendo directamente /dev/urandom de Linux, en vez de usar el crate rand de Rust.
  • /dev/urandom es un archivo de dispositivo seudoaleatorio que da acceso al CSPRNG del kernel de Linux.
  • El kernel recopila entropía del entorno del usuario y siembra periódicamente un cifrador de flujo determinista basado en ChaCha20.
• En los números aleatorios de 16 bits, el primer y el último bit se configuran en 1.
  • El último bit 1 garantiza que el número sea impar.
  • El primer bit 1 sirve para usar todo el rango de bits necesario.
• En 16 bits, bastó con la trial division, probando divisiones desde 3 hasta sqrt(num), para encontrar un primo en unos 40 ms.
  • En una ejecución de ejemplo se obtuvo Prime found: 44809, con un tiempo total de unos 0.038 segundos.
• Al escalar a 64 bits, la trial division simple tardó unos 30 segundos.
  • Luego se mejoró probando solo candidatos de la forma 6k±1 y dividiendo primero por una lista de primos pequeños.
  • Tras la mejora, el tiempo para generar un primo de 64 bits fue de unos 6.414 segundos.
• Al tardar 6 segundos incluso en 64 bits, quedó claro que con este enfoque sería difícil llegar a la generación de primos de 1024 bits.

Cambio a pruebas probabilísticas de primalidad

• Entre los algoritmos deterministas, revisé APR-CL y ECPP, pero eran matemáticamente complejos y faltaban explicaciones accesibles, así que resultaban difíciles de implementar.
• Después de revisar el código fuente de OpenSSL y las recomendaciones de NIST, confirmé que en casos de uso reales, incluido RSA, se usan ampliamente las pruebas probabilísticas de primalidad.
• A partir de ahí, el algoritmo cambió de “probar que un número es primo” a determinar que es un probable prime con cierta precisión.

• Prueba de Fermat

  • El pequeño teorema de Fermat usa la relación de que, si p es primo y a no es divisible por p, entonces se cumple a^(p-1) = 1 mod p.
  • Como la exponenciación simple provoca overflow en u128, se implementó exponenciación modular.
  • pow() recibe el exponente como u32, y elevar un u128 a exponentes mayores puede causar overflow.
  • La multiplicación misma también puede superar el rango de u128, así que provisionalmente se trabajó guardando números de 64 bits dentro de u128.
  • La prueba de Fermat es rápida, pero por los Fermat pseudoprime puede clasificar erróneamente números compuestos como primos.
  • Aunque esos compuestos son raros, son lo bastante numerosos como para considerar que la prueba de Fermat sola no es confiable.

• Prueba de Miller-Rabin

  • Miller-Rabin se basa en el mismo principio que la prueba de Fermat, pero se usa como un algoritmo probabilístico de primalidad más fuerte.
  • La implementación separa las potencias de 2 en la forma n-1 = 2^s × d y luego verifica varias condiciones.
  • a^d = 1 mod n
  • O bien, para algún 0 <= r < s, a^(2^r × d) = n - 1 mod n.
  • En experimentos de 128 bits, encontró un primo en unos 0.042 segundos, parecido a la prueba de Fermat.
  • El límite de error en el peor caso de Miller-Rabin es 4^-k; para n grandes, en promedio es del orden de 8^-k.
  • Para k=10, el cálculo de probabilidad de error promedio fue 0.000000000931323%.
  • Se compara con 2^-30, la probabilidad de lanzar una moneda 30 veces seguidas y que todas salgan cara.
  • En usos criptográficos reales hay que tener más cuidado con la selección aleatoria de bases y las condiciones adversarias.

Crear un BigInt propio

• Con los tipos enteros básicos de Rust es difícil trabajar con números suficientemente grandes más allá de 64 bits, así que hizo falta implementar enteros de precisión arbitraria (BigInt).
• Debido a la restricción de no usar crates bigint externos, el BigInt también se implementó directamente.

• Intento 1: arreglo de dígitos decimales

  • Al principio intenté almacenar números grandes como arreglos de dígitos en base 10.
  • La suma y la multiplicación podían implementarse como en cálculos manuales, pero me bloqueé al implementar la división y abandoné ese enfoque.

• Intento 2: arreglo binario basado en bool

  • El segundo enfoque guardaba el número como un arreglo de 0 y 1.
  • BigInt usa un arreglo [bool; 2048].
  • Al multiplicar números de 1024 bits entre sí, el resultado puede necesitar hasta 2048 bits, así que se reservaron 2048 bits.
  • La suma y la resta se implementaron con un esquema de full adder.
  • La multiplicación aprovechó las propiedades de los números binarios y se procesó con shift-and-add.
  • La división se implementó como long division binaria.
  • Con esta implementación se logró encontrar el primer primo de 1024 bits, pero el tiempo de ejecución fue de unos 32 minutos y 44.90 segundos.
  • Técnicamente se alcanzó el objetivo, pero no cumplía con la restricción de “tiempo razonable”.

• Intento 3: chunks de bytes

  • Confirmé que cada bool del arreglo de bool ocupa 1 byte, no 1 bit.
  • [bool; 2048] usa 2048 bytes, no 2048 bits.
  • Luego cambié a guardar 2048 bits en un arreglo de 256 bytes.
  • La suma, la resta y la multiplicación funcionaron sin grandes cambios, y la división se ajustó para tratar los chunks de bytes como una lista de bits.
  • Con este enfoque, el tiempo de generación de un primo de 1024 bits se redujo a 4 minutos y 43 segundos.

• Intento 4: chunks u64

  • El enfoque de chunks de bytes era, en la práctica, un BigInt basado en dígitos con una base más alta.
  • En el siguiente paso, se guardaron 2048 bits en 32 chunks u64.
  • Cada chunk funciona como un “dígito”.
  • Para almacenar el resultado de multiplicar dos chunks u64, se usa u128.
  • Con esta estructura, un número de 1024 bits puede representarse con 16 chunks u64 en vez de 309 dígitos decimales.
  • El tiempo de generación de primos de 1024 bits mejoró a 60-90 segundos.

Optimización de cuellos de botella

• En benchmarks simples, la diferencia entre la implementación binaria y la de chunks u64 fue clara.
  • a + b y a - b: 5537.35 ns → 123.57 ns
  • a * b: 1292283.14 ns → 842.32 ns
  • a / b y a % b: 733446.76 ns → 44440.12 ns
  • a < b y a > b: 2506.02 ns → 58.91 ns
• Después, la optimización se concentró principalmente en la división, la multiplicación, las operaciones internas de Miller-Rabin y la lógica de generación de candidatos.

• División

  • El mayor cuello de botella era la división.
  • Incluso con la estructura de chunks u64, la división existente seguía realizando long division bit por bit.
  • Tomando como referencia el algoritmo de la página 598 del Handbook of Applied Cryptography, se implementó long division basada en radix.
  • El enfoque estima el “dígito” actual del quotient usando los 3 primeros “dígitos” del dividend y los 2 primeros “dígitos” del divisor.
  • Esta implementación ahorra unos 40,000 ns por división.
  • Cuando el divisor es un único chunk u64, se trata como caso especial para realizar una long division más directa usando u128.
  • Este caso aparece con frecuencia en Miller-Rabin.

• Multiplicación

  • La multiplicación se volvió unas 2 veces más rápida al reorganizar los loops para eliminar el BigInt usado para almacenar resultados intermedios.
  • Se cambió para calcular la cantidad de chunks ocupados y recorrer solo los chunks no nulos.
  • Como BigInt suele guardar números de hasta 1024 bits, con frecuencia queda vacía la mitad del espacio de 2048 bits.
  • También se consideraron multiplicaciones basadas en Karatsuba o FFT, pero eran complejas de implementar directamente y se juzgó que la multiplicación actual ya era lo bastante rápida.

• Optimización interna de Miller-Rabin

  • En la implementación de Miller-Rabin, el foco fue reducir las operaciones costosas.
  • En vez de x = mod_exp(x, 2, n), se ejecuta directamente x = (x * x) % n.
  • El primer mod_exp() se reemplazó por una versión inline simplificada para reducir el overhead de llamadas a funciones.
  • Se agregó num.is_even() para verificar si es par y evitar el cálculo % 2.
  • d / 2 se cambió por d >>= 1.
  • += 1 y -= 1 se trataron como casos especiales con increase() y decrease().
  • En particular, is_even() y d >>= 1 aportan alrededor de 70,000 ns de mejora cada uno.
  • En el benchmark final, la versión optimizada con chunks u64 se volvió mucho más rápida.
  • a * b: 842.32 ns → 295.04 ns
  • a / b y a % b: 44440.12 ns → 831.77 ns
  • a / 2: 75121.58 ns → 60.89 ns
  • a % 2 == 0: 78400.87 ns → 21.65 ns
  • a - 1: 103.15 ns → 67.54 ns

Generador final de primos de 1024 bits

• La función final primero lee un número aleatorio de 1024 bits desde /dev/urandom.
  • Activa el bit más significativo para garantizar el tamaño de 1024 bits.
  • Activa el bit menos significativo para garantizar que sea impar.
• Luego, en vez de volver a leer un número aleatorio cada vez, suma 2 al candidato para avanzar al siguiente candidato impar.
  • increase_by_2() normalmente solo realiza una suma sobre un chunk u64.
• Antes de Miller-Rabin, se realiza trial division con una lista de primos pequeños.
  • En el código final se usan los primeros 1000 primos pequeños.
  • Como los primos pequeños caben en un único chunk u64, puede aprovecharse el caso especial de división rápida con un solo chunk.
• Este problema puede tratarse como una forma embarrassingly parallel, sin memoria compartida ni sincronización entre hilos.
  • 16 hilos de CPU buscan primos cada uno por su cuenta, y se usa el valor del hilo que primero envía un resultado.
• Un ejemplo de ejecución final registró unos 0.086 segundos de elapsed time.
  • El uso de CPU se mostró como 690%.
• El promedio de 100 ejecuciones fue de 0.04109 ± 0.00307 segundos.
  • En promedio, encuentra un primo de 1024 bits en unos 40 ms.
  • Cada llamada individual a prime_1024bit() puede variar, por la aleatoriedad, desde unos 8 ms hasta unos 800 ms.
  • La ejecución paralela reduce la variación al elegir el resultado más rápido.

Código y límites

• El código completo y el repositorio están publicados en github.
• Los enlaces de discusión están en hackernews y reddit.
• Esta implementación difícilmente pueda considerarse segura desde el punto de vista criptográfico real, y su propósito tampoco es crear una biblioteca criptográfica, sino más bien el aprendizaje y la experimentación de implementación.

[GN⁺]

Comentarios de Hacker News

• Hubo algunas criptomonedas que usaban la búsqueda de números primos grandes como parte de su función de prueba de trabajo, y hace unos 8 años se podía ganar bastante dinero solo con una implementación muy rápida de prueba de primalidad
  Durante un tiempo fui autor y mantenedor del software de minería de riecoin; no sé muy bien por qué, supongo que simplemente porque me gustan los primos
  Este artículo omitió la optimización número uno para una prueba de primalidad rápida: la multiplicación de Montgomery: https://en.m.wikipedia.org/wiki/Montgomery_modular_multiplic...
  Esa es la base de una implementación práctica de exponenciación modular de alta velocidad
  Niall Emmart, que en ese entonces estaba en la academia y por lo que sé ahora está en Nvidia, publicó una biblioteca de enteros grandes para GPU realmente increíblemente rápida, CGBN: https://github.com/NVlabs/CGBN
  Sigue siendo la implementación de exponenciación modular por lotes más rápida que conozco, y si me permiten un momento de fanatismo geek, deja sin aliento
  Algún día debería escribir sobre cómo esto me permitió dominar la producción de una criptomoneda pequeña durante unos 5 años. Y Python incluye una exponenciación modular bastante buena en la forma de tres argumentos de pow(x, y, m) para calcular x^y % m
  Con eso puedes hacer muy fácilmente una prueba de primalidad de Fermat o Miller-Rabin si quieres implementarla tú mismo, y es bastante divertido. Si no quieres hacerla tú mismo, mpz_probab_prime() de la biblioteca gmp también está bien. Obviamente gmp es más rápida, pero es difícil superar la diversión de una prueba de Fermat de dos líneas cuando juegas con primos grandes

  • Niall también participó en una de las propuestas ganadoras de ZPrize relacionadas con multiplicación multiescalar rápida
    Está estrechamente relacionada con la exponenciación modular por lotes, pero con la diferencia de que opera sobre curvas elípticas y no en módulo primo. Lo veo como una continuación del trabajo de CGBN
    Dio una buena charla el año pasado en el seminario-almuerzo de criptografía de Stanford, y las diapositivas y la grabación están en línea
    https://cbr.stanford.edu/seminarTalks/slides_20230526_niall_...
    https://www.youtube.com/watch?v=KAWlySN7Hm8
  • Me pregunto por qué esas criptomonedas usaban funciones de prueba de trabajo personalizadas
    Me gustaría saber si era solo una idea vaga de que la criptografía usa primos de alguna manera sin saber cuándo ni por qué, o si había una razón más profunda
  • Me cambié de Perl a Python por pow(x,e,mod)

• Si tienes un rango máximo dado para los números, es sencillo hacer que Miller-Rabin sea efectivamente determinista
  Basta con elegir bases que se haya demostrado que descartan en conjunto todos los pseudoprimos dentro de ese rango
  Y la lista no se vuelve larga. Miller-Rabin es realmente poderoso

  • Me pregunto cuáles son esas bases para el rango de números de 1024 bits
    No pude encontrar la respuesta en línea
  • Además, si solo estás buscando primos, puedes elegir candidatos que parezcan primos y confirmarlos con una prueba determinista

• Una línea de ensamblador inline simplifica la multiplicación escolar de enteros grandes: https://github.com/jcalvinowens/toy-rsa/blob/master/bfi.c#L4...
  Si pudiera volver al pasado y cambiar una sola cosa en C, me gustaría introducir el concepto de multiplicación extendida. Me da pena que Rust tampoco la tenga. El soporte de hardware está en todas partes. Cortex M0 ni siquiera tiene división, pero sí tiene multiplicación extendida
  Es código de una implementación de juguete de RSA muy fea que escribí hace mucho tiempo: https://github.com/jcalvinowens/toy-rsa
  La razón por la que bastaba con la prueba de Fermat era que, si los primos no eran realmente primos, el algoritmo no funcionaba. La prueba de Fermat es rápida, y una sola operación de cifrado/descifrado elimina incluso la probabilidad extremadamente pequeña de que uno de los dos sea un mentiroso de Fermat
  Pero no sé si se puede demostrar que no existen pares de claves RSA con valores P/Q no primos que aun así puedan cifrar y descifrar mensajes con éxito. En una implementación real, por supuesto, no sería lo correcto, pero nunca encontré la respuesta

  • Curiosamente, C ahora sí tiene enteros grandes
    C23 añadió el tipo _BitInt(N), así que por ejemplo puedes usar _BitInt(1024) como un tipo de 128 bytes
    Eso sí, el soporte de compiladores es limitado. En Clang puedes pasar la bandera -fexperimental-max-bitint-width=N para permitir N mayor que 128. Si N es mayor que 128 y divides un _BitInt(N), el compilador simplemente se cae, pero +, - y * funcionan como se espera
  • En Zig esto es relativamente fácil
    Tiene el builtin @mulWithOverflow, que devuelve el resultado junto con el bit de overflow, y hay enteros hasta (u|i)65535
    Dependiendo de lo que hagas, puedes detectar overflow y luego promover a un tipo más grande, o promover primero y luego recortar opcionalmente
    También soporta el operador separado *| para multiplicación saturada y *% para multiplicación con wraparound. Puedes usarlos cuando necesites esas semánticas. Fuera de eso, el overflow es comportamiento indefinido sujeto a verificaciones de seguridad, así que en los modos de compilación Debug y ReleaseSafe provoca pánico
  • Si p y q son números de Carmichael coprimos entre sí, RSA todavía puede cifrar y descifrar mensajes correctamente
    Pero p*q terminará teniendo factores primos más pequeños, así que será más fácil factorizarlo y la seguridad será menor
  • Según entiendo, en la mayoría de los compiladores de C y en Rust, si haces cast a un tipo más grande y luego multiplicas, se genera exactamente la instrucción de máquina que quieres
  • El Pretty Good Privacy (PGP) original de Philip Zimmermann en 1994 solo usaba un tamiz de división por todos los primos conocidos de 16 bits, y esa tabla se generaba con la criba de Eratóstenes. Después aplicaba la prueba de Fermat

• Me pregunto cuánto tiempo tomó este trabajo.
  Hice multiplicación de enteros grandes como proyecto de investigación de licenciatura y me tomó casi dos semestres. Implementé Karatsuba, Toom-Cook, FFT compleja, algunas NTT y Schönhage-Strassen.
  Los números primos son casi magia matemática. Para quien tenga interés, A Friendly Introduction to Number Theory de Silverman es un excelente libro de matemáticas.
  Como referencia, el enlace de la página aparece como 4025051 en lugar de 40250519.

• Buen artículo. Yo también escribí recientemente algo de código de enteros grandes para una versión temprana de [0], y recuerdo lo frustrante que es llevar la descripción de alto nivel de un paper matemático a operaciones reales.
  Pero tengo una objeción menor.
  Si usas todo el rango de u64, entonces el número está en base 2^64, no en base 2^64-1. Cada palabra tiene un rango de 0 a 2^64-1, igual que cada dígito en decimal va de 0 a 9.
  [0] https://github.com/LegionMammal978/bigfoot-sim

• Si, como en la optimización final, cuando falla no generas un nuevo número aleatorio sino que aumentas el número de 2 en 2, la seguridad se rompe un poco.
  Como los primos no están distribuidos uniformemente, eso introduce un sesgo hacia los primos que vienen justo después de un gran intervalo entre primos.

  • Leí sobre eso mientras investigaba.
    Es un compromiso entre velocidad de ejecución y aleatoriedad del primo, y concluí que si 16 hilos compiten, cada uno empezando desde un número aleatorio para encontrar un primo, eso añade suficiente aleatoriedad, así que prioricé la velocidad.
    Si uno quisiera más aleatoriedad que velocidad, sería fácil cambiar +=2 por una llamada a rng().

• Buen artículo y bien escrito.
  Creo que el autor quiso decir base-256, no base-255.

• Unos cuantos números de 1~2 KB caben de sobra en la caché L1, e incluso si no, hay más de un megabyte de caché L2 con un tiempo de acceso de alrededor de 3 ns.
  En el artículo se decía que probablemente se esperó a lecturas/escrituras de RAM por fallos de caché L1, pero luego ya no vuelve sobre ese punto.
  Además, esto solo trata de generación de primos, así que evita la mayoría de las trampas de RSA, y urandom debería ser seguro. Si el código funciona correctamente, no parece haber mucho que pueda salir mal.
  Hay algunos temas con primos débiles que conviene evitar en RSA, pero no sé si en este caso serían lo bastante comunes como para ser un problema real.

• Me recordó a un proyecto de primer año de universidad de hace varias décadas.
  La idea la propuso mi compañero de proyecto y amigo, que después fue el orador de la generación, e implementó la matemática central: construir cifrado RSA de 4096 bits.
  Recuerdo lo lenta que era la generación de primos en la implementación final. Tardaba unos 20 minutos en una estación de trabajo PA-RISC.
  Mi amigo, que era un fanático de las matemáticas, siguió optimizando el código incluso después de terminado el proyecto, y recuerdo verlo leer papers sobre implementación de pruebas de primalidad y aritmética de enteros grandes.
  Por ejemplo, hubo una mejora enorme al hacer que, si algún número era 0 en la multiplicación de composición, se saltara la multiplicación y se devolviera 0 como resultado.

  • En hardware lento, es mucho mejor generar una clave de curva elíptica.
    O esperar mucho, o sacrificar seguridad que aguante hasta el futuro.

• Entiendo poner el bit bajo en 1, porque un número par nunca puede ser primo. Claro, 2 es la excepción.
  Pero no entiendo por qué también se pone en 1 el bit alto. No sé mucho de primos o criptografía, pero parece como renunciar innecesariamente a 1 bit de entropía. ¿Qué me estoy perdiendo?

  • Si el bit alto siempre está activado y el primo se codifica incluyendo ese bit, entonces el primo siempre se codifica con la misma cantidad de bytes.
    Una codificación de bytes de longitud variable puede causar problemas al intercambiar datos entre distintos programas si la especificación no es muy clara y no está bien probada.
    Basta ver los problemas que aparecen en DHE basado en RSA cuando una clave pública de servidor tiene un 0 inicial.
  • Es como generar un número de dos dígitos.
    Si el primer dígito es 0, entonces no es un número de dos dígitos.
  • Poner el primer bit en 1 hace que pierdas 1 bit de entropía, pero garantiza que el primo sea lo bastante grande.
    Y una cosa más: en RSA se multiplican dos primos. Si uno es de 1024 bits, el otro podría ser, si mal no recuerdo, de unos 200 bits y aun así alcanzar la cantidad de bits de entropía necesaria para la clave.
    Así que si ambos primos son de 1024 bits, también queda un pequeño margen extra.
  • Es cierto que renuncias a 1 bit de entropía, pero aun así quedan 1022 bits.
    Parece más seguro esto que ponerse a pensar si alguien pidió un primo de 1024 bits pero uno de 1020 bits también estaría bien. Es como que normalmente no consideras 00042 un número de 5 dígitos.
    Técnicamente, la mejor decisión podría cambiar según para qué se use exactamente, pero el enfoque del artículo parece un valor predeterminado más seguro.
  • Sin duda, perder 1 bit de entropía para asegurarte de no terminar con un primo de apenas 50 bits parece un compromiso totalmente razonable.