Criptografía cuántica

El siguiente artículo tiene como finalidad introducirte en el tema de la criptografía cuántica, ya sea que tu interés sea general o que después decidas profundizar en él, al final se listan algunas referencias que te podrán servir de apoyo. Este trabajo consta de dos entregas: en la primera se tocan aspectos muy generales sobre criptografía, la evolución del cómputo (desde un punto de vista físico) y un ejemplo sencillo sobre cómo un algoritmo, desarrollado para su implementación en computadoras cuánticas, es aplicado para calcular la llave de descifrado del algoritmo RSA. Después, se te explicarán algunos conceptos sobre cómputo cuántico y su aplicación a través de la criptografía cuántica y se mencionarán algunos de los avances tecnológicos encaminados a crear una computadora cuántica.

A lo largo de la historia, la humanidad ha tenido, por diversas razones, la necesidad de transmitir mensajes cuyo contenido permanezca oculto. La criptografía nació, en principio, como la habilidad para esconder información a cualquier persona que no le estuviera permitido leerla. A través de los siglos, se desarrollaron distintas técnicas, métodos e instrumentos que permitieron el desarrollo de este arte; la criptografía clásica abarca éstas técnicas.

En 1948, Claude Shannon propuso la Teoría de la Información (la cual establece que la información es mesurable). Con la aparición de ésta, la criptografía dio un salto importante: dejó de ser un arte para convertirse en una ciencia considerada como una rama de las matemáticas. Ahora es llamada Criptografía Moderna.[1] Este hecho dio pie al surgimiento de diversos algoritmos criptográficos que se valen del uso de la computadora para su implementación. Algunos métodos de cifrado de este tipo son: DES (apareció en 1976[2] y  fue aceptado como un estándar por el gobierno de Estados Unidos en 1977[3]),  RSA (1977), CCE (1985),  3DES (1998) y, finalmente,  AES (2002)[4].

Tanto la Criptografía Clásica como la Criptografía Moderna tienen como objetivo principal el cifrar la información (por medio de métodos matemáticos simples o complejos) para que pueda ser transmitida a un receptor y que solo éste sea capaz de descifrarla. Básicamente, la criptografía es la ciencia encargada de transformar la información de tal manera, que ésta quede encubierta y sea incomprensible para todo aquel que no cuente con la autorización y los medios correspondientes para acceder a ella[5].

El cómputo es el procesamiento de ciertos datos (origen) para obtener otros (resultado) con el fin de que estos últimos puedan ser utilizados con algún propósito específico (predecir los fenómenos naturales, calcular la nómina de una empresa, navegar por las redes sociales, etc.). Para computar los datos, la humanidad, a través de los siglos, se ha valido de diversas herramientas, por ejemplo, las máquinas mecánicas como el ábaco, la Pascalina o la Enigma;  las máquinas electrónicas como las computadoras que conocemos actualmente y, finalmente, el cerebro humano, que es el instrumento primordial. Cada una de estas máquinas, contrario a lo que se pudiera pensar, tiene algo en común respecto a su funcionamiento. Para hacer su trabajo, se valen de las leyes de la naturaleza, es decir, obedecen a las leyes de la física. Así que la computación es un proceso físico[6].

Para diseñar y crear las máquinas mecánicas, primero, el hombre tuvo que estudiar las propiedades físicas de los fenómenos presentes en la naturaleza para aplicar estos conocimientos al crear una herramienta que le ayudara a resolver algún problema. Tal es el caso de la Pascalina que creó Blaise Pascal en 1642. En esta máquina, los datos se representaban mediante las posiciones de los engranajes[7]. Los fundamentos físicos y matemáticos usados por Pascal, los podemos explicar ampliamente en la actualidad gracias a las leyes de la mecánica clásica presentadas por Sir Isaac Newton en 1687.

Ocurrió lo mismo con el desarrollo de máquinas basadas en las leyes del electromagnetismo. El hombre, a través de diversos estudios y experimentos, entendió estas leyes y desarrolló instrumentos que le ayudarían a resolver problemas de la vida diaria. Uno de estos instrumentos es la computadora; las propiedades electromagnéticas de sus componentes (transformadores, transistores, capacitores, diodos, etc.) son las que permiten que cada uno se comporte con ciertas características y que, en conjunto, lleven a cabo el funcionamiento de la herramienta. También, el hombre añadió sus conocimientos sobre las leyes de la mecánica a estos nuevos descubrimientos. Un ejemplo, en donde se conjuntan los fundamentos de la mecánica clásica y del electromagnetismo en una computadora, es en el diseño de los discos duros.

La ciencia que se encarga del estudio de los fenómenos naturales, su comportamiento y propiedades, es la física. Fue al cobijo de esta ciencia que se descubrieron las leyes de la mecánica clásica y del electromagnetismo.

En el siglo XX se desarrolló otra rama de la física, la mecánica cuántica, la cual estudia el comportamiento de los sistemas en el nivel molecular, atómico y subatómico, es el ámbito en el cual se manifiestan fenómenos que no son evidentes en el mundo macroscópico[8]. Esta nueva rama de estudio estuvo auspiciada por científicos como M. Planck, A. Einstein, N. Bohr, B. Podolsky, N. Rosen, entre otros.

Entonces, similarmente a los ejemplos anteriores, aproximadamente hace 21 años[9], se comenzaron a dirigir los estudios sobre la mecánica cuántica hacia el desarrollo de herramientas basadas en estas leyes para el cómputo. A esta nueva ciencia se le llamó computación cuántica.

Con la criptografía moderna se han desarrollado diversos algoritmos de cifrado basados en las matemáticas. Estos son implementados en las computadoras y, mientras más complejo sea el algoritmo, más tardado y complejo será poder realizar un criptoanálisis (estudio del descifrado no autorizado de mensajes cifrados)^[10] sobre el mismo. A medida que crece la capacidad de cómputo de las máquinas, es posible realizar criptoanálisis más efectivos, como el caso de DES: en 1997 el grupo Electronic Frontier Foundation, a través de un ataque de fuerza bruta, tuvo éxito en la obtención de una llave, que fue generada por dicho algoritmo en 56 horas^[11], esto exige la necesidad, ya sea de crear nuevos algoritmos con mayor complejidad o de desarrollar otros acordes al uso de los nuevos paradigmas tecnológicos.

Con la computación cuántica, de acuerdo a los estudios y teorías desarrolladas, se podrá aumentar de manera exponencial el procesamiento de los datos respecto a las supercomputadoras de hoy. Esta gran capacidad de cómputo se podrá usar, por ejemplo, en las áreas de cómputo gráfico, para reducir significativamente el tiempo que se lleva a cabo en la terminación y producción (render) de objetos modelados, en bases de datos, mejoramiento de búsquedas en bases de datos de millones de registros, cómputo científico, aumento de precisión en los cálculos de modelos para la predicción de fenómenos físicos, químicos y biológicos con un costo de tiempo mucho menor.

En la seguridad de la información, específicamente en la criptografía, se verán cambios tanto en la capacidad de dotar de mayor integridad a la actual (a los datos enviados en una comunicación), como en la capacidad para realizar criptoanálisis sobre algoritmos de cifrado actuales, con el impacto que esto conllevaría en campos como la economía, las finanzas y la seguridad militar, es por eso la importancia del estudio de la Criptografía Cuántica.

Consideremos el siguiente ejemplo para tener una idea clara sobre el impacto que tendrán las computadoras cuánticas en la seguridad de la información. Éste es un ejemplo teórico sobre cómo el algoritmo actual de cifrado RSA podrá ser resuelto en un tiempo considerablemente corto a través del uso de una computadora cuántica.

Cifrado RSA

La base del algoritmo de cifrado asimétrico RSA, desarrollado en 1977 por Rivest, Shamir y Adleman, consiste en utilizar el producto de dos números primos (que deben permanecer en secreto) bastante grandes (de al menos cien dígitos cada uno), cuyos valores no estén demasiado próximos. A partir de estos dos números se calculan tanto la llave pública como la llave privada. La seguridad del algoritmo radica en que, sin conocer estos dos números primos, es necesario hacer el cálculo de la factorización de su producto, lo cual implica, para un número tan grande, una complejidad exponencial; por lo que, poder hacer ésta factorización con la capacidad de cómputo actual, puede tomar varias décadas.[12] Este algoritmo es ampliamente usado como soporte de seguridad en varios protocolos, por ejemplo, en el protocolo SSL[13], en redes virtuales privadas[14] (VPN) y en esquemas de infraestructura de llave pública[15] (PKI).

Para el ejemplo vamos a considerar a tres actores, Alice, Bob y Eve. Alice desea enviar un mensaje secreto a Bob a través de un medio inseguro, como lo es un correo electrónico, es decir, un medio en el cual cualquier persona no autorizada podría interceptar este mensaje; para enviar este mensaje, Alice utiliza el concepto de criptografía asimétrica,[16] por lo que utiliza la llave pública de Bob para cifrar el mensaje.

Para generar sus llaves de cifrado y descifrado, Bob, previamente, tuvo que escoger y mantener en secreto dos números primos a partir de los cuales generó su llave pública (que puso a disposición de cualquiera que le quisiera mandar un mensaje cifrado en un servidor de llaves públicas) y su llave privada, la cual solamente debe conservar él y que le servirá para descifrar los mensajes que hayan sido cifrados con su llave pública. Siguiendo el algoritmo RSA; entonces, siendo la llave pública de Bob la pareja de números primos  15 y 3 indentificada como K_pub

K_pub(n,e) = K_pub(15,3),

El mensaje que enviará Alice será “ALMA”, identificado como M_cla, a cada letra le asignará un número de acuerdo a su posición en el alfabeto, quedando el mensaje

M_cla = A L M A,

M_cla = 01 12 13 01,

Alice procede a realizar el cálculo del mensaje secreto o criptograma a través de la fórmula matemática 

Cripto = M_cla^e(mod n)

 

Mensaje (Mcla)	Mcla numérico	Criptograma Cripto = Mclae(mod n)
A	01	01
L	12	03
M	13	07
A	01	01

 

Entonces, Alice envía a Bob por correo electrónico el criptograma 01030701, Bob será el único que podrá descifrar el mensaje con su llave privada.

Algoritmo de Shor

En 1994, Peter Shor, quien trabajaba en AT&T, publicó su algoritmo de factorización de números enteros. Este algoritmo utiliza las propiedades de la computación cuántica y, con él, es posible resolver de una manera eficiente el problema de factorización de números enteros grandes en sus factores primos. Algunos algoritmos de cifrado, como RSA, lo usan como base, es decir, será posible hacer el criptoanálisis de los mensajes cifrados con estos algoritmos tan usados en la actualidad, usando una computadora cuántica[17].

El algoritmo de Shor utiliza el concepto del paralelismo cuántico para encontrar los factores primos a partir de un producto dado, es decir, un criptoanalista podrá obtener los datos necesarios para generar la llave que descifrará el mensaje.

Siguiendo con el ejemplo, durante el envío del mensaje de Alice a Bob, sin que ellos lo noten, éste es interceptado por un tercero llamado Eve. Bob es el único que cuenta con la llave (su llave privada) para descifrar el mensaje, Eve desea encontrar el mensaje secreto, para esto podrá hacer uso del algoritmo de Shor para el criptoanálisis.

La llave pública de Bob es K_pub(n,e) = K_pub(15,3) disponible para cualquiera, también lo es para Eve. A partir de la llave pública de Bob y del mensaje secreto enviado por Alice, Eve podrá aplicar el criptoanálisis para obtener el mensaje.

La siguiente aplicación del algoritmo de Shor fue tomada del desarrollo de la Fís. Verónica Arreola. El número n = 15, calculado previamente por Bob, es el dato conocido que resulta del producto de dos números primos p y q que deben mantenerse en secreto, este número entero positivo n será el número a factorizar por Eve. Para ello, Eve seguirá el siguiente procedimiento: primero va a elegir otro número entero ‘y’ positivo menor a n que cumpla con que el máximo común divisor (mcd) entre ellos sea 1,

mcd(y,n)=1,

y se apoya en el algoritmo de Euclides para el cálculo del mcd.

Eve elige

y = 13,

tiene entonces que

mcd(13,15) = 1

Ahora, a partir de estos números, calculará su periodo r de la siguiente forma

13¹ mod 15 = 13

13² mod 15 = 4

13³ mod 15 = 7

13⁴ mod 15 = 1

13⁵ mod 15 = 13

13⁶ mod 15 = 4

13⁷ mod 15 = 7

13⁸ mod 15 = 1

13⁹ mod 15 = 13

Entonces genera la sucesión 

13, 4, 7, 1, 13, 4, 7, 1, 13,…

Por lo tanto, dirá que,

13 tiene periodo r = 4 con respecto a 15,

pues cada 4 términos la sucesión se repite.

El periodo de la sucesión anterior

r = 4 es de la forma 2*s,

con s número entero distinto de cero (en este caso s = 2), es decir, es un número par. Además,

y^s ≠ -1 mod (n),

estas últimas condiciones son necesarias para llevar a cabo el algoritmo de Shor. Observemos ahora que

y^2*s - 1 = (y^s - 1)( y^s + 1) ≡ 0 mod (n),

es decir, n divide a (y^s - 1)( y^s + 1), por lo que para algún entero k diferente de cero se cumple

(ys + 1)(ys -1 ) = kn.

Bastará entonces que Eve calcule, haciendo uso del algoritmo de Euclides, el mcd(y^s ± 1, n) para así obtener factores no triviales de n. 

Para el ejemplo,

(y^s - 1) = 132 - 1 =168 (y^s + 1) = 132 + 1 =170,

calculando los máximos comunes divisores se obtiene

mcd(168,15) = 3
mcd(170,15) = 5,
en donde 3 y 5 son los factores de n = 15.

Estos dos factores

p = 5  y  q = 3

obtenidos por Eve, son los números primos a partir de los cuales Bob calculó tanto su llave pública como su llave privada, para poder hacer el criptoanálisis del mensaje secreto, Eve solo tendrá que seguir el algoritmo RSA para obtener el valor de la llave privada de Bob.

La llave privada de Bob calculada por Eve es

Kpriv(n,d) = K_priv(15,11),

y descifrando el criptograma obtiene el mensaje:

 

Criptograma (Cripto)	Mcla numérico Mcla = Criptod(mod n)	Mensaje (Mcla)
01	01	A
03	12	L
07	13	M
01	01	A

Se podrá advertir rápidamente que no es necesario utilizar una computadora actual para obtener, a partir de una llave pública calculada con el algoritmo RSA (aplicando el algoritmo de Shor), sus números generadores. Pero en este ejemplo sencillo (usado solamente para plantear los conceptos), se usan los números p y q con un dígito solamente, y el producto n de ellos tiene dos dígitos. El algoritmo RSA plantea consideraciones para elegir a los números p y q, que dictan que cada uno sea un número con al menos 100 dígitos (aproximadamente de 500 bits) y que dichos números no deban estar relativamente próximos el uno del otro. Entonces, a partir de estas consideraciones, el tiempo necesario para encontrar los factores de n (n de al menos 1024 bits) llevaría a las computadoras actuales algunas décadas (problema computacionalmente intratable), mientras que con una computadora cuántica tomaría solo algunos minutos.

En la próxima entrega se explicará cómo es que una computadora cuántica podría realizar todos estos cálculos en minutos haciendo uso de las propiedades descubiertas por la mecánica cuántica.