Así es el futuro de la criptografía: física cuántica

En Internet, por desgracia, no todo el mundo es _bueno_ y desperdicia la oportunidad de mirar cuál es tu contraseña o tu tarjeta de crédito cuando te metes en una página web. Desde hace ya bastante tiempo, hay una necesidad muy fuerte de cifrar y proteger nuestras comunicaciones, y lo hemos logrado con bastante éxito con tecnologías como HTTPS.

HTTPS se basa en algoritmos de cifrado de clave pública, que permiten establecer una conexión segura e intercambiar claves entre ordenadores incluso usando canales comprometidos: aunque alguien escuche todas las transmisiones iniciales no será capaz de ver los datos que se envíen una vez establecida la conexión cifrada. Y de hecho, salvo algunos errores de programación, es una técnica que ha funcionado bastante bien. La cuestión es que esa técnica tiene fecha de caducidad.

¿Qué quiere decir que la criptografía de clave pública tiene fecha de caducidad? Recordemos un tema que vimos hace un tiempo en Xataka: computación cuántica. Uno de los algoritmos que se había desarrollado para ordenadores cuánticos es el algoritmo de Shor, que sirve para factorizar números en tiempo polinomial en lugar de exponencial. Y, aunque no lo parezca por la descripción que os acabo de dar, es muy interesante.

Resulta que la criptografía de clave pública se basa en un "hecho" computacional: multiplicar dos números y obtener un resultado es muy fácil y se tarda muy poco. Pero en el otro sentido, coger el resultado y ver qué dos números se han multiplicado para obtenerlo (factorización) es muy difícil y se tarda mucho. Para que os hagáis una idea, un número de 232 dígitos como RSA-768 ha sido factorizado en dos años por un grupo de investigadores; un tiempo equivalente a 2000 años de proceso en un ordenador de sobremesa.

Y no sólo es que se tarde mucho: es que se tarda un tiempo exponencial, que es el _argot_ matemático para "muchííííísimo tiempo y cada vez más". En otras palabras, si se añade un bit más a la longitud de la clave, el tiempo de factorización se multiplica por dos (con los algoritmos más eficientes, se multiplica por un número algo menor, pero se multiplica al fin y al cabo). No es que seamos lentos: es que no hay forma matemática de resolver este problema rápidamente con ordenadores tradicionales.

La cuestión es que con el algoritmo cuántico de Shor, sí que se puede resolver en poco tiempo. Al ser un algoritmo en tiempo polinomial, si añadimos un bit a la clave simplemente sumamos una cantidad de tiempo adicional para sacarla. La consecuencia la tenemos en el gráfico de arriba: aunque tengamos un ordenador tradicional rapidísimo, con una clave suficientemente larga va a ser impracticable sacarla. Por otra parte, con uno cuántico, va a ser posible romperla en relativamente poco tiempo.

En resumen, y como comentaba la investigadora del CSIC Verónica Fernández en una charla en la EPS-UAM: RSA está roto y sólo es cuestión de tiempo que haya que sustituirlo.

Física cuántica, la solución a RSA

¿Dónde está la solución si RSA está roto? ¿Cómo conseguiremos distribuir claves para cifrar datos en un mundo en el que la computación cuántica sea relativamente accesible? La respuesta está, de nuevo, en la física cuántica.

Recordemos una cosa que vimos en Genbeta al hablar de la física cuántica: la polarización de los fotones. Es una propiedad de estas partículas cuyos detalles físicos no nos importan demasiado. De hecho, podemos visualizar la polarización como la oscilación en una dirección de una partícula, como lo que podéis ver abajo. Es decir, que el fotón no va en línea recta sino que va haciendo como "ondas" a lo largo de la trayectoria en vertical y/o horizontal. Ya os digo que no es físicamente correcto pero para la explicación nos vale.

Ahora bien, podemos ponernos filosóficos. ¿Por qué dividir la oscilación en una componente horizontal y otra vertical? De hecho, ¿qué significa "horizontal"? ¿Por qué no voy a poder medir la oscilación en otras dos direcciones, como por ejemplo en diagonal?

Pues bien, resulta que esto se puede hacer sin problemas. De hecho, tiene hasta nombre y todo: elegir esos ejes para medir la oscilación se llama elegir una base.

Sólo nos falta un detalle físico más que ya vimos en su momento: qué ocurre cuando medimos la oscilación del fotón. Recordemos la analogía del muro con rendijas: si un fotón pasa por un muro con rendijas horizontales, entonces tiene oscilación horizontal. Si oscila verticalmente, está claro que no va a pasar. Y si oscila diagonalmente, igual pasa o igual no.

Esa incertidumbre va a ser una clave importante para la distribución de claves: nunca vamos a poder saber de forma exacta la oscilación de un fotón. No hay forma de saber si ha pasado por la rendija horizontal porque oscila en horizontal o porque está oscilando en diagonal y hemos tenido la suerte de que ha pasado de alguna forma.

Compartiendo claves fotón a fotón

Una vez que ya tenemos la base física, vamos a ver cómo se implementaría eso en la realidad, más concretamente en el protocolo BB84.

Vamos a suponer que Alicia y Bernardo quieren intercambiar una clave para cifrar sus comunicaciones, y tienen una forma de enviarse fotones uno a otro. Se ponen de acuerdo en dos bases para polarizar los fotones: horizontal/vertical y diagonal (como en la figura de arriba). También acuerdan una forma de codificar bits en los fotones: cuando un fotón esté oscilando en horizontal, lo considerarán como un "1", y en vertical como un "0". Igualmente asignarán un 1 y un 0 a cada dirección de oscilación en la base diagonal.

Ahora llega el momento de la transmisión. Alicia genera una cadena de bits aleatoria y los envía a Bernardo, cada uno codificado con una base aleatoria. Bernardo lee igualmente los fotones cada uno con una base aleatoria.

Después, Alicia y Bernardo comparten públicamente la base con la que han enviado y recibido los fotones. De media, Bernardo habrá usado la misma base que Alicia para leer un fotón el 50% de las veces. Los bits leídos con la misma base serán los que se queden y formarán la clave.

Una vez que Alicia y Bernardo tienen la clave, ya pueden usar cualquier otro canal (Internet, por ejemplo) para transmitirse los datos que quieran, cifrados con la clave que acaban de compartir.

¿Y por qué es seguro?

Ahora os preguntaréis que por qué es esto seguro, si simplemente es una forma exótica de transmitirse una clave. Los bits no están cifrados. ¿Qué pasa si alguien se pone en el medio y lee los fotones que se envían? ¿Tendría la clave?

La respuesta es que sí, pero no le serviría de nada. El algoritmo de distribución cuántica de claves permite detectar intrusos: si Eva, por ejemplo, se pone entre Alicia y Bernardo, ambos detectarán que hay alguien por en medio leyendo sus fotones y no establecerán una conexión segura.

¿Por qué ocurre esto? Pues precisamente por usar la polarización de los fotones para codificar los bits. Recordemos que al ser una propiedad cuántica, es imposible saber exactamente la polarización en ambas direcciones. Si Eva se pone en el medio, va a introducir un error: salvo que acierte siempre con la base en la que envía fotones Alicia, va a acabar pensando que fotones que oscilan en diagonal en realidad lo hacen en horizontal, por ejemplo, y va a introducir un error al reenviarlos. Vamos a verlo con algo más de detalle.

Además de la base, Alicia y Bernardo van a compartir de forma pública una secuencia de bits de control. Cuando Eva intercepta esos bits, como no sabe en qué base los está enviando Alicia, va a tener que usar bases aleatorias. Cuando los lea, se los guarda y luego envía fotones a Bernardo con la polarización que ha leído.

La cuestión es que no siempre va a acertar. Por ejemplo, Alicia envía un fotón 1 _|_ (oscilando verticalmente). Eva lee con la base que no es, la diagonal (×) y obtiene un 0 (_\_). Entonces, reenvía ese 0 (_\_) a Bernardo. Supongamos que en este fotón Bernardo usa la misma base que Alicia (+). Como lo que ha reenviado Eva es un fotón oscilando en diagonal, Bernardo va a leer un resultado aleatorio, como por ejemplo un 0 (_-_).

Cuando Alicia y Bernardo compartan las bases que ha usado cada uno, verán que en la secuencia de control habrá bits en los que, aunque han leído y enviado con la misma base, han obtenido resultados distintos. Si se encuentran muchos de estos errores, será indicación de que hay alguien por medio y por lo tanto sabrán que la clave que han obtenido no es segura. No hay forma física de que alguien lea esos fotones sin introducir cambios en la transmisión.

Vale, pero esto, ¿se puede hacer en el mundo real?

Sí, todo esto suena muy, muy futurista. Pero no es sólo ciencia ficción, y se están logrando avances en este campo. Sin ir más lejos, en el CSIC, en Madrid, han logrado montar un sistema que transmite claves a 300 metros de distancia a una velocidad de 1Mbit por segundo. Otros han conseguido transmitir claves por fibra óptica a 148.7 kilómetros de distancia.

Hay incluso sistemas comerciales ya disponibles. IdQuantique, por ejemplo, vende sistemas de distribución cuántica de claves. No deja de ser una tecnología experimental, pero es algo que ya está aquí y que garantiza que la seguridad de la información podrá mantenerse aunque llegue la computación cuántica.