Algoritmo de Shor: como las computadoras cuánticas pueden romper los cimientos de la criptografía actual
La confidencialidad de la información que enviamos por internet, se basa en la encriptación asimétrica, que permite compartir las llaves de encriptación de manera pública. Los algoritmos de encriptación asimétrica (como Diffie-Hellman, RSA, ElGamal) basan su funcionamiento en 2 problemas matemáticos de difícil resolución: la dificultad de factorizar o calcular logaritmos discretos de números enormes.
Probar por fuerza bruta todas las posibilidades no va a funcionar para números lo suficientemente grandes como los que se usan en criptografía asimétrica (1024/2048/4096 bits). Y desafortunadamente (o afortunadamente, dependiendo de cómo se lo mire), no existen algoritmos computacionales eficientes que permitan reducir el tiempo significativamente respecto de la fuerza bruta. Al menos no en una computadora clásica.
Las computadoras cuánticas, fueron concebidas mentalmente en la década de 1980 por pioneros como Richard Feynman, Paul Benioff, Charles Bennett, Gilles Brassard y David Deutsch. Desde entonces, se han ganado la fama de poder hacer procesamiento paralelo masivo, usando la superposición cuántica. A pesar de los muchos artículos de revistas populares, intentar todo en paralelo no es exactamente lo que una computadora cuántica puede hacer.
En cierto sentido, una computadora cuántica puede a través de la superposición cuántica, probar todas la “alternativas posibles” (factores primos, en el cálculo de la factorization), pero para obtener un resultado concreto hay que realizar una medición y destruir la superposición, obteniendo una elemento de la superposición aleatorio que, con seguridad, no será el correcto.
Para poder crear un algoritmo cuántico rápido que nos ayude a factorizar (descomponer en sus factores primos) o calcular el logaritmo discreto de números enormes, necesitamos encontrar alguna característica especial de estos problemas.
Afortunadamente (o desafortunadamente, nuevamente, dependiendo de cómo se lo mire), ambos problemas comparten las mismas características, la periodicidad. Analizaremos el problema de la factorization porque es más fácil de visualizar pero también aplica al problema del logaritmo discreto.
La propiedad que explotaremos es la posibilidad de reducir el problema de la factorización a otro problema distinto, mas simple, llamado búsqueda de períodos.
Veamos la secuencia de potencias de 2 (2, 4, 8, 16, 32, 64, 128, 256, 512, 1024) mod 15 (resto cuando se divide cada potencia de 2 por 15), de 2 mod 17 y de 2 mod 21. Como puede verse las potencias de 2 mod 15 nos da una secuencia periódica, con período 4, mientras que las potencias de 2 mod 17 nos da una secuencia periódica, con período 8 y las potencias de 2 mod 21 nos da una secuencia periódica, con período 6.
Ahora bien, ¿existe alguna regla general a partir de la cual podamos predecir el período? Hay un patrón descubierto por Euler en la década de 1760.
Sea N el producto de dos números primos, p y q, y considere la secuencia:
Si g no es divisible por p o q, entonces siempre ocurrirá que existirá un r tal que:
Esto significa que existirá un exponente r que al elevar al g elegido será es un múltiplo de N más 1. Busquemos ese r :
Como:
O sea que:
Siempre que r sea par.
Si r es impar hay que elegir otro g y buscar un nuevo r.
Utilizamos el algoritmo de Euclides. Veámoslo con un ejemplo simple.
Digamos que N = 77 (número que es producto de 2 primos, p = 11 y q = 7.
Elijamos un numero g del orden de N, digamos 8 y busquemos el r tal que:
Y así obtenemos r = 10. Remplacemos g porn8 y r por 10:
Estos 2 números compartirán divisores con p y q (recordemos que son 11 y 7). En un ejemplo de criptografía real no sabremos que números son, porque serán números increíblemente grandes, cientos de dígitos.
Calculemos el MCD usando el algoritmo de Euclides:
Asi, 32769 y 77 comparten el divisor común 11 que resulta ser p y
32767 y 77 comparten el divisor común 7 que resulta ser q
En resumen:
Ahora bien, aunque la secuencia:
eventualmente comenzará a repetirse, el número de pasos antes de que se repita podría ser casi tan grande como el propio N, ¡y N en criptografía asimétrica RSA tiene más de 600 dígitos! Esta es la razón por la que encontrar el período no parece conducir a un algoritmo de factorización clásico rápido.
Repasemos: hemos logrado transformar el problema de la factorizacion (y el del logaritmo discreto) a otro problema, el se encontrar un periodo de repetición. Pero este problema es tan difícil como el anterior.
¡Y es aquí donde las computadoras cuánticas entran en escena! Para ellas encontrar ese periodo es una operación trivial. Como es esto posible?
En principio una computadora cuántica podría crear una enorme superposición cuántica de todos los números de nuestra secuencia:
Hay una operación cuántica que puede realizarse en esa superposición que puede revelar el período fácilmente.
El punto clave es que ya no estamos tratando de encontrar una aguja en un pajar exponencialmente grande, algo que sabemos que es difícil incluso para una computadora cuántica. En cambio, ahora estamos tratando de encontrar el período de una secuencia, que es una propiedad global de todos los números de la secuencia en conjunto. Y eso es una gran diferencia.
Aun si pensamos en la computación cuántica en términos de “computación en universos paralelos”, como sostienen muchos expertos (por ejemplo, David Deutsch, uno de los padres de la computación cuántica), no existe una forma factible de detectar un único universo que es diferente de todos los demás, el que tiene el termino correcto. Sin embargo, lo que se puede esperar detectar es una propiedad conjunta de todos los universos paralelos, una propiedad que sólo puede revelarse mediante un cálculo al que contribuyan todos los universos.
Para resolver este problema con una computadora cuántica primero debemos crear una superposición cuántica de todos los números enteros r, desde 1 hasta N aproximadamente. El problema es que, dada una r,
Si r fuera, digamos 100 cuatrillones, ¿tendríamos que multiplicar g por sí mismo 100 cuatrillones de veces? Seguramente esto no sería rápido.
Afortunadamente, esto no es necesario. Lo que podemos hacer en su lugar es lo que se llama elevar al cuadrado repetidamente. Quedará más claro con un ejemplo. Supongamos N = 17, g = 3 y r = 14. Entonces el primer paso es representar r como una suma de potencias de 2:
Entonces:
Nótese que podemos hacer todas las multiplicaciones mod N, evitando así que los números crezcan sin control en los pasos intermedios. En este caso no parece tan impresionante porque el expoente no es tan grande como en las implementaciones de croiptigrafia. Esto produce el resultado:
Bien, entonces podemos crear una superposición cuántica sobre todos los pares de números enteros de la forma:
donde r varía de 1 a N. ¿Como hacemos esto?
No vamos a entrar en detalles demasiado técnicos sobre mecánica cuántica aquí, solo aceptemos que un qbit es una propiedad especifica de una partícula elemental (como un electrón) y esta propiedad puede estar en una superposición de diferentes estados. Entonces, a diferencia de 1-bit clásico, que solo puede valer 0 o 1, un qbit puede estar en una superposición arbitraria de ambos valores, esto es:
En particular podemos hacer que esa superposición sea 50% – 50%, haciendo:
Entonces:
Entonces con 2 qbits podemos hacer simultáneamente el siguiente calculo:
En general, para n qbits podemos representar 2^n bits, ósea que con 3 qbits podemos hacer 8 cálculos simultáneos. Con 20 qbits, 1 millón de cálculos simultáneos y con 300 qbits ¡podemos hacer más cálculos simultáneos que partículas existen en el universo! Ese el poder de la exponenciación.
El problema es que todos estos cálculos, existen en una superposición. No podemos observarlos todos al mismo tiempo. Cuando intentemos observar esta superposición estaremos haciendo una medición, y al hacerlo, la superposición se destruye y solo veremos 1 al azar. El resto de los cálculos se perderán:
La clave de la computación cuántica es encontrar un algoritmo que seleccione el elemento correcto de la superposición y eso no es fácil.
A la fecha, solo hemos encontrado unos pocos algoritmos para unos pocos problemas. La factorización de números primos es uno de esos pocos problemas para el que hemos encontrado un algoritmo que funciona: el algoritmo de Shor, propuesto por Peter Shor en 1994.
Volviendo al tema, dada una superposición de todos los elementos de una secuencia periódica, ¿cómo extraemos el período de la secuencia? Para obtener el período, el algoritmo de Shor utiliza algo llamado transformada cuántica de Fourier (QFT).
En una codificación RSA-4096 bits, se multiplican 2 números primos (p y q) de 2048 bits, dando un N de 4096 bits. Esto implicara poner en superposición 10^1233 términos.
En cada termino se calcula:
y el resultado se lo asigna a otros tantos qbits:
Como vimos estos términos se repetirán en ciclos de periodo r:
La transformada cuántica de Fourier QFT (el equivalente cuántico del transformada de Fourier) nos permite encontrar periodicidades en la secuencia. En concreto no permite hallar 1/r y por ende r.
Encontramos r, podremos calcular:
Y luego con el algoritmo de Euclides encontrar p y q.
En resumen, para romper un algoritmo RSA (y de cualquier algoritmo que use el problama dificil de la factorizacion solo se necesita encontrar los factores primos de un numero enormemente grande. Para ello hay un método que explota una propiedad especifica de la factorización y nos permite traducir el problema en otro. Ese otro problema, sigue siendo un problema intratable para una computadora clásica, es decir, que el tiempo de resolución del problema mediante un algoritmo crece exponencialmente con la complejidad del problema. En una computadora cuántica (usando el algoritmo de Shor), este problema no es intratable.
Para ello es necesario poner en superposición unos pocos miles de qbits, aplicar la transformada cuántica de Fourier que nos permitirá encontrar el periodo de repetición de los restos de una operación del tipo g^r Mod N y mediante una serie de cálculos que surgen del teorema de Euler podremos obtener 2 números que comparten divisores con los 2 números primos que queremos encontrar. Y finalmente usando el algoritmo de Euclides podemos encontrar esos divisores que serán precisamente los números primos que queremos encontrar.
La misma logica aplica a todos los algoritmos asimetricos basados en el problema del logaritmo discreto.
En la práctica esos pocos miles de qbits necesarios, necesitan ser gbits netos (sin error) que, con la tecnología de hoy en día, implicaría varios millones de qbits brutos. En la actualidad aún no hemos logrado alcanzar los 1000 qbits.
Ahora bien, ¿cuánto falta para que podamos hacer esto? No lo sabemos con certeza, pero con la tendencia actual, se estima que entre 10 y 30 años. ¿Qué alternativas hay para cuando llegue este momento? Hace tiempo que se están ideando, desafíos matemáticos que sean intratables incluso para una computadora cuántica. Y hay muchas opciones. Existen muchos problemas matemáticos que no pueden ser resueltos de manera efectiva por una computadora cuántica. Entre ellos se encuentran los problemas basados en retículas, los basados en grafos y los basados en ecuaciones cuadráticas multivariables.