El 2 de diciembre de 2019, la lista de correo de teoría de números
nmbrthry@listserv.nodak.edu informó la
factorización del número RSA-240 (240 decimales, 795 bits). Este es un nuevo logro en criptografía y teoría de números y la próxima tarea completada de la lista
RSA Factoring Challenge .
Aquí está el número y sus factores:
RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447
Según la tendencia actual, puede imaginarse aproximadamente cuándo se piratearán RSA-1024 (309 dígitos decimales) y RSA-2048 (617 dígitos).
Logros anteriores han sido la
factorización de un número de 768 bits (232 decimales) en 2009 y el
logaritmo discreto de un número de 768 bits en 2016 .
Muchos algoritmos de cifrado de clave pública se basan en números extremadamente grandes, que son el producto de dos números primos. Otros confían en la dificultad de resolver algunos problemas logarítmicos discretos. Con tamaños de clave suficientemente grandes, no hay forma conocida de descifrar dicho cifrado. La factorización de números grandes y el cálculo del logaritmo discreto destruyen las garantías criptográficas para un tamaño de clave dado y obligan a los usuarios a aumentar el número de bits de entropía al generar un secreto.
Las cifras cada vez más sofisticadas se descifran gradualmente a medida que aumenta el rendimiento de la CPU y mejoran los algoritmos.
Después de la invención del algoritmo de tamiz de campo de número general (GNFS) a principios de los 90, no apareció nada revolucionario en el campo de la factorización de enteros, aunque se hicieron algunas optimizaciones significativas. Por ejemplo, en los últimos años, los investigadores han podido acelerar enormemente la fase de encontrar un polinomio adecuado.
La factorización de RSA-240 también está fuera de la fila general, porque se llevó a cabo no solo mediante el aumento de la potencia informática, sino también debido a la optimización de software y algoritmos. Para probar la efectividad de los cambios realizados, los investigadores lanzaron el programa en el mismo equipo que se utilizó para calcular el logaritmo discreto de 768 bits en 2016. Descubrieron que filtrar una matriz de números de 795 bits es un 25% más rápido que filtrar una matriz de números de 768 bits sin optimización.
El mismo grupo de investigadores calculó un logaritmo discreto del mismo tamaño. Por primera vez en la historia, los registros de logarización discreta y factorización de números del mismo tamaño se establecen simultáneamente, e incluso en el mismo hardware y software.
Gracias a la optimización de algoritmos y software, el logaritmo discreto de un número de 795 bits se aceleró en un 33% en comparación con el logaritmo de un número de 768 bits sin optimización en el mismo hardware.
Según la teoría, el logaritmo de un número de 795 bits es 2,25 veces más complicado que un número de 768 bits. Esto significa que el efecto de optimización es en realidad tres veces (2.25 × 1.33 = 3).
Ambos tipos de cálculos se realizaron utilizando el algoritmo de campo de número de tamiz en el programa
CADO-NFS de código abierto. Entre las optimizaciones, mejor paralelismo y uso de memoria, así como mucho trabajo para encontrar parámetros de cálculo más óptimos (se desarrolló un software especial para probar y clasificar diferentes parámetros de cálculo).
La cantidad de tiempo de cálculo para ambos nuevos registros es de aproximadamente 4000 años de funcionamiento de los núcleos físicos de los procesadores Intel Xeon Gold 6130 (a una frecuencia de 2,1 GHz), si este procesador se toma como referencia.
Un desglose aproximado del tiempo en factorización y logaritmo:
- Cribado RSA-240: 800 años centrales
- Matriz RSA-240: 100 años centrales
- Cribado DLP-240: 2400 años centrales
- Matrix DLP-240: 700 años centrales
El logro fue atribuido por un equipo de investigación dirigido por Emmanuel Thomé, un destacado investigador del
Instituto Nacional de Informática y Matemática Aplicada de Francia .
Los inventores del cifrado RSA han publicado
números RSA
de todos los tamaños hasta RSA-2048. Todos pueden intentar hackearlos.
Según la tendencia actual, puede calcular cuándo se piratearán RSA-1024 (309 caracteres) y RSA-2048 (617 caracteres). Si extrapola el horario, obtendrá aproximadamente 2031 y 2073, respectivamente. Pero vemos que la optimización de software y algoritmos puede acercar significativamente este término. Quizás RSA-2048 será pirateado durante nuestra vida.
En la práctica, el RSA recomienda usar el tamaño mínimo de clave RSA de 2048 o 4096 bits.
A juzgar por el desarrollo de las computadoras cuánticas, pronto no se acercarán a romper claves de este tamaño, aunque es difícil predecir algo aquí. En 2012,
el algoritmo Shore hizo frente a la
factorización de 21 (3 × 7), cinco bits de entropía. Este número ha permanecido durante mucho tiempo un registro de factorización cuántica, pero en 2018, la factorización del producto de los primos
4088459 se demostró en procesadores IBM de 5 y 16 qubits, que ya tiene 22 bits.
