¿Criptografía RSA rota? ¡O tal vez no!

¿Criptografía RSA rota? ¡O tal vez no!

Sello de tiempo: 6 de enero de 2023 12:59 p.m.
¿Cripto RSA crackeado? ¡O tal vez no! PlatoBlockchain Inteligencia de Datos. Búsqueda vertical. Ai.
by Paul patito

Ha habido un poco de alboroto en los medios tecnológicos en los últimos días acerca de si el venerable criptosistema de clave pública conocido como RSA pronto podría ser descifrado.

RSA, como probablemente sepa, es la abreviatura de Rivest-Shamir-Adleman, los tres criptógrafos que idearon lo que se convirtió en un sistema de encriptación sorprendentemente útil y duradero mediante el cual dos personas pueden comunicarse de forma segura...

…sin reunirse primero para acordar una clave de cifrado secreta.

En pocas palabras, RSA no tiene una llave, como una cerradura de puerta tradicional, sino dos llaves diferentes, uno para bloquear la puerta y el otro para desbloquearla.

Puede generar con bastante rapidez un par de claves una para bloquear y otra para desbloquear, pero dado solo una de ellas, no puede averiguar cómo se ve la otra.

Entonces, designa uno de ellos como su "clave pública", que comparte con el mundo, y mantiene el otro como su "clave privada".

Esto significa que cualquiera que quiera enviarte un mensaje privado puede bloquearlo con tu clave pública, pero (asumiendo que realmente tratas tu clave privada como privada), solo tú puedes desbloquearlo.

Trabajando al revés, alguien que quiere que pruebes tu identidad puede enviarte un mensaje y pedirte que lo bloquees con tu clave privada y lo devuelvas.

Si su clave pública la desbloquea correctamente, entonces tienen alguna razón para pensar que usted es quien dice.

Estamos ignorando aquí los problemas de cómo se asegura de que una clave pública realmente pertenezca a la persona que cree, qué hace si se da cuenta de que le han robado su clave privada y muchas otras complejidades operativas. El gran problema es que RSA introdujo un sistema de dos claves en el que una clave no se puede descifrar de la otra, en contraste con el sistema tradicional de una clave, con la misma clave para bloquear y desbloquear sus secretos, que había estado en uso durante siglos.

criptografía de clave pública

Verá que este tipo de proceso se denomina de diversas formas como criptografía de clave pública, cifrado público-privadoo cifrado asimétrico (el cifrado simétrico, como AES, es donde se usa la misma clave para bloquear y desbloquear sus datos).

De hecho, si realmente conoces tu historial criptográfico, es posible que incluso hayas oído llamarlo con el curioso nombre de cifrado no secreto (NSE), porque los criptógrafos en el Reino Unido habían tenido una idea similar algunos años antes que R, S y A, pero en lo que resultó ser una gran oportunidad perdida, el gobierno británico decidió suprimir el descubrimiento y no desarrollar o incluso publicar el proceso.

Aunque existen alternativas a RSA en estos días que le permiten tener claves públicas y privadas más pequeñas, y que se basan en algoritmos que se ejecutan más rápido, RSA todavía se usa ampliamente y todavía hay una gran cantidad de datos potencialmente descifrables en archivos, archivos de registro y capturas de red que estaban protegidas por RSA cuando se transmitieron.

En otras palabras, si RSA resulta ser fácil de descifrar (en algunos sentidos de facilidad, al menos), por ejemplo porque aparece una gran computadora cuántica rápida, tendríamos motivos razonables para preocuparnos.

Bueno, como dice el experto en ciberseguridad Bruce Schneier recientemente observado, un gran equipo de informáticos chinos acaba de publicar un artículo titulado Factorización de enteros con recursos sublineales en un procesador cuántico superconductor.

Lo importante de la factorización de números enteros (cuando descubres, por ejemplo, que 15 = 3 × 5, o que 15538213 x 16860433 = 261980999226229) es que hacer precisamente eso es lo más importante para descifrar RSA, que se basa en cálculos que involucran dos enormes números primos aleatorios.

En RSA, todos saben el número que obtienes cuando multiplicas esos números (llamado el PRODUCTO), pero solo la persona que originalmente ideó los números iniciales sabe cómo se creó el producto: los factores juntos forman esencialmente su clave privada.

Entonces, si pudiera dividir el producto nuevamente en su par único de factores primos (como se les conoce), podría descifrar el cifrado de esa persona.

La cuestión es que si sus números primos iniciales son lo suficientemente grandes (en estos días, 1024 bits cada uno, o más, para un producto de 2048 bits o más), simplemente no tendrá suficiente poder de cómputo para separar el producto.

A menos que pueda fabricar, comprar o alquilar una computadora cuántica lo suficientemente poderosa, eso es.

Grandes productos de primera

Aparentemente, el producto principal más grande hasta ahora factorizado por una computadora cuántica es solo 249919 (491 x 509), que mi computadora portátil de ocho años puede manejar de manera convencional, incluido el tiempo necesario para cargar el programa e imprimir la respuesta, en un tiempo tan corto. que la respuesta se informa de diversas formas como 0 milisegundos o 1 milisegundo.

Y, como informan los investigadores chinos, las formas estándar de abordar el craqueo de RSA con una computadora cuántica requerirían millones de los llamados qubits (bits de tipo de computadora cuántica), donde la computadora más grande conocida hoy en día tiene poco más de 400 qubits.

Como puede ver, si RSA-2048 necesita millones de qubits para romperse, necesita cargar más qubits que bits en el número que desea factorizar.

Pero los investigadores sugieren que es posible que hayan encontrado una manera de optimizar el proceso de descifrado para que requiera no solo menos de un millón de qubits, sino incluso menos qubits que la cantidad de bits en el número que está tratando de descifrar:

Estimamos que se necesita un circuito cuántico con 372 qubits físicos y una profundidad de miles para desafiar a RSA-2048 usando nuestro algoritmo. Nuestro estudio muestra una gran promesa para acelerar la aplicación de las actuales computadoras cuánticas ruidosas y allana el camino para factorizar números enteros grandes de significado criptográfico realista.

La pregunta candente es…

¿Tienen razón?

Si ya tenemos computadoras con cientos de qubits, ¿el final de RSA-100 está realmente a la vuelta de la esquina?

Simplemente no tenemos la experiencia matemática para decírselo: su artículo de 32 páginas no es para los pusilánimes ni para los generalistas matemáticos, pero el consenso, por ahora al menos, parece ser - estar…

No.

Sin embargo, este es un buen momento para pensar en que tan listo estas para cualquier algoritmo de cifrado o hash que de repente se encuentre deficiente, ya sea por razones cuánticas o no.

Sello de tiempo:

Mas de Seguridad desnuda