Actualmente, muchos estados y actores individuales están interceptando y almacenando una gran cantidad de información encriptada, como contraseñas, información bancaria y números de seguridad social. Pero, ¿por qué lo hacen si no pueden abrir estos archivos? Bueno, creen que en los próximos 10 a 20 años tendrán acceso a una computadora cuántica que puede romper la encriptación en minutos. Este proceso se conoce como «almacena ahora, desencripta luego» o «sndl». Y funciona.
Hoy en día, hay información que aún tendrá valor en una década, como la investigación industrial y farmacológica y la inteligencia gubernamental secreta, y todos son conscientes de esta amenaza. La Administración de Seguridad Nacional dice que una computadora cuántica lo suficientemente grande, si se construyera, sería capaz de socavar todos los algoritmos de clave pública instalados en un marco de 5 a 10 años.
La computación cuántica podrá quebrar la encriptación como la conocemos, aunque las computadoras cuánticas lo suficientemente poderosas están a años de distancia, ya son una amenaza por el «almacena ahora, desencripta luego». Por eso, el Congreso estadounidense aprobó una legislación ordenando que todas las agencias comiencen a avanzar ahora mismo a nuevos métodos de criptografía que no puedan romperse con las computadoras cuánticas.
El pasado de la encriptación
Nuestros esquemas actuales de encriptación han sido realmente exitosos. Funcionaron durante 40 años, hasta la década de 1970. Antes, si querías intercambiar información privada con alguien, primero debías encontrarte en persona y compartir una clave secreta. Esta misma clave sería usada para encriptar y desencriptar mensajes. Se conoce como un algoritmo de clave simétrica. Mientras nadie más tuviera conocimiento de la clave, tus mensajes estarían seguros.
Pero, ¿qué pasaría si quisieras enviar información a alguien que no conoces en persona y fuera difícil coordinar una reunión en persona? No puedes compartir una clave a través de un canal inseguro, como una línea telefónica o un correo, porque podría ser interceptado. Es por eso que en 1977, tres científicos ({keywords_incluidas}) tuvieron un descubrimiento revolucionario en cuanto a la encriptación, conocido hoy como RSA.
Cada persona tiene dos números primos realmente grandes, todo suyos, que mantiene en secreto. Multiplican estos números entre sí para obtener un número aún más grande, que hacen público para que todos puedan ver. Si quiero enviarle a alguien un mensaje privado, uso su gran número público para cifrar mi mensaje.
Lo cifro de tal manera que sea imposible de descifrar sin conocer esos dos factores primos que hicieron ese número. Esto es un sistema de clave asimétrica, ya que se usan claves distintas para encriptar y desencriptar el mensaje. Así, es fácil desencriptarlo para el receptor, pero es imposible para cualquier otra persona, a menos que puedan factorizar el gran número público.
Alguien podría intentar factorizarlo usando una supercomputadora con el algoritmo más conocido, la criba general del cuerpo de números. Pero la criptografía moderna utiliza números primos de alrededor de 313 dígitos de largo. Factorizar un producto de dos primos tan grandes, incluso con una supercomputadora, tomaría 16 millones de años. Pero no con una computadora cuántica.
Los poderes de la computación cuántica
En las computadoras normales, un bit solo puede estar en un estado a la vez: un cero o un uno. Si tienes dos bits, pueden estar en uno de cuatro estados posibles: 00, 01, 10 o 11. Digamos que cada uno de estos estados representa un número: 0, 1, 2 o 3. Si queremos realizar un cálculo, por ejemplo, elevar 7 a la potencia de uno de estos números, solo podemos hacerlo con un estado a la vez. En este caso, 7 elevado al cuadrado nos daría como resultado 49.
Las computadoras cuánticas están compuestas por qubits, que también tienen dos estados: cero o uno. Pero a diferencia de los bits clásicos, un qubit no tiene que estar en un solo estado en cada momento. Puede estar en una combinación arbitraria de estos estados, una superposición. Así que, si tienes dos qubits, pueden existir simultáneamente en una superposición de 00, 01, 10 y 11.
Ahora, al repetir el mismo cálculo, efectivamente presentaríamos el cálculo para todos esos números al mismo tiempo. Y lo que nos queda es una superposición de los diferentes resultados: 1, 7, 49 y 343. Si agregamos otro qubit, duplicamos el número de estados posibles. Con tres qubits, podemos representar 8 estados y realizar 8 cálculos, todos a la vez. Aumenta ese número a tan solo 20 qubits, y ya puedes representar más de un millón de estados diferentes. Esto significa que puedes computar simultáneamente más de un millón de resultados diferentes. Con 300 qubits, puedes representar más estados de los que hay partículas en el universo observable. Esto suena increíblemente poderoso, ¡y lo es!
Sin embargo, hay un problema importante. Todos los resultados del cómputo están insertos en una superposición de estados. No puedes simplemente leer esta superposición. Cuando tomas una medida, solo obtienes un valor individual, básicamente uno aleatorio, y el resto de la información se pierde. Para emplear el poder de una computadora cuántica, necesitas una forma inteligente de convertir una superposición de estados en una que contenga solo la información que quieres. Esta es una tarea increíblemente difícil.
Pero, ¿cómo es que una computadora cuántica puede factorizar el producto de dos primos más rápido que una computadora convencional? Quiero explicarlo, comenzando por repasar un ejemplo sencillo que no requiere una computadora cuántica, y luego mostrar cómo una computadora cuántica puede ejecutar este método con un número muy grande en un corto período de tiempo.
El método de factorización cuántica
Digamos que tenemos un número n que es el producto de dos primos, p y q. Para nuestro ejemplo, supongamos que n es equivalente a 77. Apostaría a que puedes adivinar los factores primos, pero finjamos por el momento que no lo sabemos, porque con un producto de dos primos realmente grandes, no lo sabríamos.
Ahora, quiero usar un hecho sobre los números que parece mágico. Elijo un número G que no comparte factores con n. Si multiplicas G por sí mismo una y otra vez, siempre eventualmente alcanzarás un múltiplo de n más uno. En otras palabras, siempre puedes encontrar un exponente r, o sea, que G elevado a r es un múltiplo de n + 1.
Veamos cómo funciona esto. Elijo cualquier número que sea menor a 77. Elegiré el número 8. Este número no comparte factores con 77, y si estuvieras haciendo esto con primos grandes, también sería extremadamente improbable que elijas un número que comparta factores con n. Ahora, multiplica 8 por sí mismo una vez, dos veces, tres veces, cuatro veces, etc., elevando 8 a potencias más altas, y luego divide estos números por 77.
No nos interesa cuántas veces 77 entra en ese número, solo la diferencia, lo que sobra. Porque en cierto punto, 77 debería dividir uno de estos números con la restante exacta de uno. Así que 8 dividido entre 77 es 0, con una restante de 8. 64 dividido entre 77 es 0, con una restante de 64. 512 dividido entre 77 es 6, con una restante de 50. Y al seguir avanzando, obtenemos restantes de 15, 43, 36, 57, 71, 29 y finalmente 1. ¡Allí lo tenemos! 8 elevado a la potencia 10 es uno más que un múltiplo de 77, y encontramos el exponente r que satisface esta ecuación.
Pero, ¿Cómo ayuda esto a encontrar los factores de n? Bueno, reordenamos la ecuación para que el 1 quede en el lado izquierdo y luego podemos dividirlo en dos términos de esta forma:
1 = Gr – kn
Ahora, mientras r sea par, tenemos un número entero multiplicado por otro entero que resulta en un múltiplo de n. Esto se ve muy similar a «p multiplicado por q es igual a n». O sea, como sabemos que p y q están en el lado derecho de esta ecuación, también deben estar en el lado izquierdo, solo multiplicados por algunos factores adicionales.
Entonces, una forma de pensar acerca de lo que hicimos es que tomamos una mala estimación de uno de los factores, G, y al encontrar el exponente r, lo convertimos en dos estimaciones mucho mejores, que probablemente sí compartan factores con n. Como r era 10, los dos términos del lado izquierdo son 8 elevado a la quinta más uno (32.769) y 8 elevado a la quinta menos uno (32.767). Estos dos números probablemente compartan factores con n.
¿Cómo los encontramos? Usamos el algoritmo de Euclides. Si quieres encontrar el divisor común más grande de dos números, digamos 32.769 y 777, divides el número más grande entre el más pequeño y anotas el restante. En este caso, 32.769 dividido entre 77 da un restante de 44. Luego, mueve los números una posición hacia la izquierda y repite. Ahora, dividimos 77 entre 44 y obtenemos un restante de 33.
Repetimos el proceso: 44 dividido entre 33 da un restante de 11 y, nuevamente, 33 dividido entre 11 es igual a 3, con un restante de cero. Cuando el restante es cero, el divisor es el factor común más grande entre los dos números con los que comenzaste. En este caso, es 11, que es efectivamente un factor de 77 y de 32.769.
Podrías hacer el mismo procedimiento con el mismo número, o simplemente dividir 77 por 11 y obtener 7, su otro factor primo. Así que, repasemos. Si quieres encontrar los factores primos p y q de un número n:
- Haz una estimación mala G.
- Averigua cuántas veces r tienes que multiplicar G por sí mismo para alcanzar uno más que un múltiplo de n.
- Usa ese exponente para calcular dos nuevos números que probablemente compartan factores con n.
- Finalmente, usa el algoritmo de Euclides para hallar los factores compartidos entre esos números y n, que deberían resultar en p y q.
El futuro de la computación cuántica
No necesitas una computadora cuántica para hacer todos estos pasos, pero en una computadora clásica, este método no sería más rápido que otros. El proceso fundamental que una computadora cuántica acelera es el paso 2: hallar el exponente al que elevas G para que resulte en uno más que un múltiplo de n.
Ahora bien, mientras que r resulte ser par, podemos usar r para convertir nuestra mala estimación G en dos números que posiblemente compartan factores con n. Y mientras que estos términos en sí mismos no sean múltiplos de n, podemos usar el algoritmo de Euclides para hallar los factores de n y quebrar la encriptación.
Esto llevaría tan solo varios miles de cubits perfectos, pero los cubits que tenemos hoy son imperfectos. Así que necesitamos cubits adicionales para que actúen como información redundante. En 2012, se estimó que se necesitarían mil millones de cubits físicos para quebrar la encriptación RSA. Pero cinco años después, ese número había bajado a 230 millones. Y en 2019, luego de más avances tecnológicos, esa estimación cayó a tan solo 20 millones de cubits físicos.
¿Cuántos cubits tenemos en la actualidad? Bueno, si miramos el estado de las computadoras cuánticas de IBM, vemos que no estamos cerca de ese número de cubits. Pero el progreso parece ser exponencial. Ahora es solo cuestión de cuándo estas dos curvas van a colisionar para que toda nuestra encriptación de clave pública pueda ser quebrada.
Buscando soluciones poscuánticas
Como sabemos desde hace tiempo que esta amenaza está cerca, los científicos estuvieron buscando nuevas formas de encriptar información que puedan resistir ataques de computadoras normales y cuánticas. En 2016, el Instituto Nacional de Estándares y Tecnología (NIST) lanzó una competencia para encontrar nuevos algoritmos de encriptación que no sean vulnerables a las computadoras cuánticas. Criptógrafos de todo el mundo enviaron 82 propuestas diferentes que fueron rigurosamente evaluadas. Algunas fueron quebradas.
Luego, el 5 de julio de 2022, el NIST seleccionó cuatro de los algoritmos para que sean parte de su estándar criptográfico poscuántico. Tres de los algoritmos están basados en matemáticas de retículos. Veamos un ejemplo simple en un plano 2D. Tomemos dos vectores: R1 y R2. Al sumar entre sí las diferentes combinaciones de enteros de estos vectores (por ejemplo, tres veces R1 y una vez R2), podemos obtener dos puntos diferentes. Y todos los puntos que podemos obtener al combinar estos dos vectores de distintas formas es lo que llamamos retículos.
También voy a colocar el punto C, y tu tarea es decirme qué combinación de R1 y R2 me llevará al punto del retículo más cercano a C. Es sencillo ver que podemos llegar allí yendo en la dirección de R2 dos veces y en la dirección negativa de R1 dos veces. Bastante sencillo. Pero esos vectores R1 y R2 no son los únicos vectores que pueden darte este retículo. Por ejemplo, los vectores B1 y B2 también componen el mismo retículo.
Y si ahora hago la misma pregunta de antes, ¿puedes decirme la combinación de B1 y B2 que lleva al retículo lo más cerca posible de C? Esto se vuelve mucho más difícil. Cada vez que quedamos un paso más cerca en la dirección X o en la Y, con estos vectores B, también nos dejamos lejos en la otra dirección. Y es por eso que es mucho más difícil trabajar con estos vectores.
Finalmente, nos lleva una combinación de 8 veces B1 y -6 veces B2 para que el retículo llegue lo más cerca posible. Es mucho más difícil que antes. Pero sigue siendo un problema relativamente fácil de resolver. Sin embargo, si lo extendemos a tres dimensiones, esto se vuelve mucho más difícil, especialmente porque no tienes la colección de todos los puntos del retículo, solo tienes los vectores que lo componen.
Entonces, cuando encuentres un punto del retículo cercano al objetivo, aún debes hallar los otros puntos cercanos del retículo para asegurarte de que tu punto es el más cercano. Tomemos un círculo de radio r en dos dimensiones. El número de puntos del retículo dentro del círculo es proporcional a r². Agrega una tercera dimensión, y el número de puntos en la esfera es proporcional a r³.
Observa cómo el número de puntos del retículo aumenta al aumentar el número de dimensiones. Resolver el problema de la cercanía de vectores es algo fácil para tu computadora en tres dimensiones, hasta 100 dimensiones deberían ser manejables. Pero en los esquemas de futura encriptación propuestos, vamos a usar alrededor de 1000 dimensiones.
Das un paso en la dirección correcta en una de esas dimensiones y potencialmente podrías estar dando un paso incorrecto en las otras 999 dimensiones. Ganas un poco y pierdes todo lo demás. Con tantas dimensiones, se vuelve extremadamente difícil hallar el punto más cercano, incluso para las computadoras más poderosas, excepto si tienes un buen grupo de vectores.
Y aquí es donde entra en juego nuestro nuevo enfoque para encriptar información. Cada persona tiene un buen grupo de vectores que forma un retículo, pero mantienen estos vectores en secreto y solo comparten públicamente sus retículos. Usando un grupo de vectores con el que es difícil trabajar, si quiero enviarle un mensaje a alguien, elijo un punto de su retículo.
Por ejemplo, digamos que este punto corresponde al número 7. Así que, si quiero enviar el número 7, puedo tomar ese punto, pero luego agregarle ruido aleatorio. El mensaje que envío no es precisamente ese punto, pero es cercano a él. Ahora, para decodificar el mensaje, el receptor deberá averiguar qué punto del retículo es más cercano al punto del mensaje. En mil dimension
