Algoritmo de Shor: como las computadoras cuánticas pueden romper los cimientos de la criptografía actual
La base de la criptografía moderna, es decir, de la confidencialidad de la Informacion que enviamos por internet, se basa en la encriptación asimétrica, que permite compartir las llaves de encriptación de manera pública. Diffie-Hellman (DH), RSA o ECC son los algoritmos más populares de encriptacion asimétrica.
Romper este tipo de algoritmo (RSA o DH) se reduce a encontrar los factores primos de un número entero muy grande (N). Para entender cómo funciona DH ver aqui. Para RSA ver aquí.
Probar por fuerza bruta todas las posibilidades no va a funcionar para números lo suficientemente grandes como los que se usan en RSA (RSA-2048 bits y RSA-4096 bits). Y desafortunadamente (o afortunadamente, dependiendo de cómo se lo mire), no existe un algoritmo computacional eficiente para factorizar números primos, que permita 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, las computadoras cuánticas se han ganado la fama de poder hacer procesamiento paralelo masivo, usando la superposición cuántica. A pesar de los cientos de artículos de revistas populares, intentar todo en paralelo no es exactamente lo que una computadora cuántica puede hacer. En cierto sentido puede “probar todos los divisores posibles”, pero para obtener un resultado concreto hay que realizar una medición y destruir la superposición, obteniendo un divisor aleatorio que, con seguridad, no será el correcto.
Para poder crear un algoritmo cuántico rápido que nos ayude a factorizar números (es decir, descomponer un número en sus factores primos), necesitamos encontrar alguna característica especial del problema de la factorización. Necesitamos usar alguna propiedad única de la factorización (algo matemático que solo ocurre en la factorización y no en otros problemas difíciles) para hacerlo más rápido. Afortunadamente (o desafortunadamente, nuevamente, dependiendo de cómo se lo mire), el problema de la factorización tiene muchísimas propiedades especiales.
Por ejemplo: ¡es posible que no conozcas la factorización prima de un número entero positivo, pero sí sabes que solo tiene una! Por el contrario, podemos resolver un Sudoku, pero no tenemos forma de saber si es la única solución o tiene otras. Saber que hay exactamente una aguja en un pajar no es de mucha ayuda para encontrar la solución, pero esta unicidad es un indicio de que el problema de factorización podría tener otras buenas propiedades matemáticas disponibles para la elección.
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 una secuencia de números enteros: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …
Veamos las potencias de 2 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 un 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 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.
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.
Veamos entonces el algoritmo de Euclides consiste en:
32769 y 77 comparten el divisor común 11 que resulta ser p
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 RSA tiene más de 500 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.
¡Y es aquí donde las computadoras cuánticas entran en escena! En principio una computadora cuántica podría crear una enorme superposición cuántica sobre todos los números de nuestra secuencia:
Entonces tal vez haya alguna operación cuántica que podamos realizar en esa superposición que revelara el período.
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 hace 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:
Además, nótese que podemos hacer todas las multiplicaciones mod N, evitando así que los números crezcan sin control en los pasos intermedios. 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-2048 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 resultada 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 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.
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.