RSA-260 ha caído: un número de 862 bits que llevaba décadas esperando una factorización
El número
4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581
divide exactamente el número RSA-260.
El otro factor es
5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379
Y multiplicando ambos, efectivamente se obtiene el RSA-260:
22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
Ambos factores tienen 130 cifras, y al multiplicarlos se obtiene número original de 260 cifras decimales y 862 bits, un pseudoprimo. Los dos factores pasan además las pruebas de primalidad, de modo que son primos. El resultado ha aparecido hoy en un mensaje en X [perdón por el enlace] de Eric Lu (@penlume), que se limitó, elegantemente, a decir que el enorme número «divide el RSA-260».
Este tipo de problemas matemáticos tienen la elegancia de las funciones de un solo sentido: son fáciles de calcular en un sentido («multiplicar dos números»), pero computacionalmente muy difíciles de resolver en sentido contrario («encontrar los factores primos de un número»). Matemáticamente, la comprobación es inmediata: se multiplican los dos valores y se compara el número, algo que puede ser tedioso pero podría hacer incluso un niño de primaria a mano.
El conocido reto criptológico/matemático de los Números RSA consiste en encontrar la factorización de números cada vez con más cifras (bits). El RSA-250, de 250 cifras y 829 bits, se factorizó en febrero de 2020 y requirió el equivalente a 2.700 años-núcleo de CPU. El RSA-260 tiene 33 bits más (diez cifras decimales) y ha requerido 6 años más.
¿Es inseguro el RSA entonces, o qué?
¡Que no pande el cúnico! La importancia criptográfica de este hallazgo requiere verlo con cierta perspectiva. No significa que se haya roto el RSA-2048, que es el que se usa comúnmente hoy en día: El RSA-260 tiene 862 bits, mientras que una clave RSA-2048 utiliza un módulo de 2.048 bits, enormemente más difícil de factorizar con los algoritmos conocidos. (Y sí: es un poco lío que originalmente se refirieran a cierto «número de cifras decimales» y luego a «número de bits», pero es que en los Laboratorios RSA cambiaron de idea a medio camino, concretamente a partir del RSA-576.)
Lo interesante ahora será saber cómo se ha obtenido la factorización del RSA-260: el algoritmo, software, hardware y la cantidad de cálculo empleada. Porque eso es lo que cuenta.
Si se consiguió con una implementación convencional de métodos conocidos (como la Criba general del cuerpo de números, NFS en inglés) y simplemente más potencia de cálculo, supondrá un nuevo récord de cálculo, algo propio del progreso tecnológico. Si en cambio requirió muchos menos recursos de los previstos, sería bastante más relevante para estimar la seguridad futura de RSA.
Por ahora la factorización es correcta; lo que falta es saber cuánto trabajo costó encontrarla.
Relacionados:
La criptografía de las claves RSA-2048 todavía NO la ha roto ninguna computadora cuántica, ni tampoco una «normal», según los expertos
La seguridad de las claves RSA-2048 y los algoritmos cuánticos
Factorizar enteros como el RSA-2048 en 177 días usando 13.436 qubits
RSA de 1.024 bits ya no es suficiente (dicen)
Ron Rivest, criptógrafo y la «R» de RSA, explica reto RSA‑129
Nuevo récord de factorización de números «casi-primos»: 307 dígitos
Factorizado un número RSA de 200 dígitos
El número RSA-576, factorizado
# Enlace permanente
4397328654844826923795068102505872571721883526553349659561256924505973939597593482272505698004801207988043088656411102133523080581
divide exactamente el número RSA-260.
El otro factor es
5028695206842569864686141618253083416610081090075366674776775706538324961364412200138116378509733307971876652984898985905923678379
Y multiplicando ambos, efectivamente se obtiene el RSA-260:
22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
Ambos factores tienen 130 cifras, y al multiplicarlos se obtiene número original de 260 cifras decimales y 862 bits, un pseudoprimo. Los dos factores pasan además las pruebas de primalidad, de modo que son primos. El resultado ha aparecido hoy en un mensaje en X [perdón por el enlace] de Eric Lu (@penlume), que se limitó, elegantemente, a decir que el enorme número «divide el RSA-260».
Este tipo de problemas matemáticos tienen la elegancia de las funciones de un solo sentido: son fáciles de calcular en un sentido («multiplicar dos números»), pero computacionalmente muy difíciles de resolver en sentido contrario («encontrar los factores primos de un número»). Matemáticamente, la comprobación es inmediata: se multiplican los dos valores y se compara el número, algo que puede ser tedioso pero podría hacer incluso un niño de primaria a mano.
El conocido reto criptológico/matemático de los Números RSA consiste en encontrar la factorización de números cada vez con más cifras (bits). El RSA-250, de 250 cifras y 829 bits, se factorizó en febrero de 2020 y requirió el equivalente a 2.700 años-núcleo de CPU. El RSA-260 tiene 33 bits más (diez cifras decimales) y ha requerido 6 años más.
¿Es inseguro el RSA entonces, o qué?
¡Que no pande el cúnico! La importancia criptográfica de este hallazgo requiere verlo con cierta perspectiva. No significa que se haya roto el RSA-2048, que es el que se usa comúnmente hoy en día: El RSA-260 tiene 862 bits, mientras que una clave RSA-2048 utiliza un módulo de 2.048 bits, enormemente más difícil de factorizar con los algoritmos conocidos. (Y sí: es un poco lío que originalmente se refirieran a cierto «número de cifras decimales» y luego a «número de bits», pero es que en los Laboratorios RSA cambiaron de idea a medio camino, concretamente a partir del RSA-576.)
Lo interesante ahora será saber cómo se ha obtenido la factorización del RSA-260: el algoritmo, software, hardware y la cantidad de cálculo empleada. Porque eso es lo que cuenta.
Si se consiguió con una implementación convencional de métodos conocidos (como la Criba general del cuerpo de números, NFS en inglés) y simplemente más potencia de cálculo, supondrá un nuevo récord de cálculo, algo propio del progreso tecnológico. Si en cambio requirió muchos menos recursos de los previstos, sería bastante más relevante para estimar la seguridad futura de RSA.
Por ahora la factorización es correcta; lo que falta es saber cuánto trabajo costó encontrarla.
Relacionados:
La criptografía de las claves RSA-2048 todavía NO la ha roto ninguna computadora cuántica, ni tampoco una «normal», según los expertos
La seguridad de las claves RSA-2048 y los algoritmos cuánticos
Factorizar enteros como el RSA-2048 en 177 días usando 13.436 qubits
RSA de 1.024 bits ya no es suficiente (dicen)
Ron Rivest, criptógrafo y la «R» de RSA, explica reto RSA‑129
Nuevo récord de factorización de números «casi-primos»: 307 dígitos
Factorizado un número RSA de 200 dígitos
El número RSA-576, factorizado
# Enlace permanente
Fuente: Artículo original