La computación cuántica no matará a la criptografía Blockchain

La computación cuántica no matará a la criptografía

24/08/20 16 min. de lectura

Fue a finales de 2017 cuando descubrí que personas ajenas al mundo de la criptografía o la física empezaron a mostrar interés en la computación cuántica. Parece el próximo gran éxito, con gente generando diferentes tipos de expectativas fabulosas y grandes compañías de TI luchando una batalla para liderar el progreso tanto en el ámbito científico como en el de la comercialización.

La computación cuántica es un avance muy prometedor en la ciencia de la computación que fue sugerido inicialmente por Richard Feynman en su conferencia de 1959 “Hay mucho sitio en el fondo” (originalmente en inglés llamada: “There’s plenty of room at the bottom”). Señaló que “Los átomos a pequeña escala se comportan totalmente diferente que a gran escala, ya que satisfacen las leyes de la mecánica cuántica. Así que, a medida que bajamos y jugueteamos con los átomos, trabajamos con diferentes leyes, y podemos esperar hacer cosas diferentes“.

Richard Feynman

Feynman volvió a la computación cuántica en su trabajo de 1981 “Simulando la física con computadorasdonde consideraba a las computadoras cuánticas como simuladores cuánticos universales.

Muchas otras personas han puesto sus cerebros y trabajos en la computación cuántica. Puedes ver una lista detallada con una bonita línea de tiempo en Wikipedia.

Pero fue en 1994 cuando el mundo supo de una aplicación de computación cuántica que atraería un interés sin precedentes en la tecnología. Peter Shor encontró un algoritmo que permitiría a un ordenador cuántico resolver el registro discreto y el problema de factorización en tiempo polinómico.

algorithms for quantum computing discrete log and factoring

En otras palabras, si existiera un ordenador cuántico práctico, nuestra actual criptografía de clave pública sería fácilmente descifrada.

Peter Shor

Índice

Criptografía de clave pública 👨‍💻

Alice y Bob solían enviarse mensajes privados, pero de repente apareció Eva escuchando cualquier conversación. Ahora, Bob quiere enviar un nuevo mensaje a Alice. ¿Cómo podría transmitir su mensaje de forma segura?

Con la criptografía simétrica tradicional, Alice y Bob necesitan acordar una clave que les permita cifrar y descifrar el mensaje. Sin embargo, Bob tendrá dificultades para encontrar la forma de enviar a Alice la clave que usó para encriptar su mensaje sin que Eva también aprenda la clave. Y si Eva conoce la clave… ¡será capaz de leer la carta!

Entra en escena la criptografía pública, que inicialmente fue diseñada para resolver la necesidad de acordar una clave secreta. Esto fue logrado por Whitfield Diffie y Martin Hellman en 1976. Más tarde, en 1978, Rivest, Shamir y Adleman (RSA) encontraron una forma de cifrar y firmar mensajes.

A un nivel muy alto, se puede pensar en la criptografía de clave pública de esta manera: Mientras que un criptosistema simétrico tiene una clave que permite el cifrado y descifrado, un criptosistema de clave pública se basa en un par de claves matemáticamente relacionadas, es decir:

Lo que una clave encripta sólo puede ser descifrado por la otra, y viceversa.

Veámoslo con este ejemplo:

Creación de claves

  1. Alice crea un par de llaves: A1 y A2
  2. Alice mantiene en secreto el A1. Llamaremos a esto su clave privada (Pv).
  3. Alice hace público el A2 enviándoselo a Bob o publicándolo en algún sitio. No hay problema en distribuirlo abiertamente ya que no revela nada. Llamaremos a esto su clave pública (Pb).

Encriptación

  1. Bob quiere enviar un mensaje privado a Alice.
  2. Bob encripta el mensaje usando la clave pública de Alice, Pb.
  3. Alice recibe el mensaje encriptado y lo desencripta con su clave privada, Pv (recuerda: lo que una clave encripta sólo puede ser desencriptado por la otra, y viceversa).
  4. Eva no puede leer el mensaje de texto claro ya que no tiene acceso a la clave privada de Alice, Pv.

Firma

  1. Alice quiere firmar un mensaje para que cualquiera pueda verificar que fue preparado por ella y que no ha sido manipulado.
  2. Alice encripta el mensaje usando su clave privada, Pv. Llamaremos a esto la Firma.
  3. Alice le envía a Bob el mensaje de texto y la Firma.
  4. Bob descifra la firma usando la clave pública de Alice, Pb.
  5. Si el mensaje de texto y la desencriptación de la Firma son idénticos, Bob puede estar seguro de que sólo puede ser preparado por Alice usando su clave privada, Pv.

Los protocolos de la vida real utilizan diferentes técnicas para mejorar la eficiencia y la seguridad, pero en resumen funcionan como este ejemplo.

Fundamentos matemáticos 🧠

Hasta ahora, las implementaciones prácticas de la criptografía de clave pública se basan en un par de problemas difíciles conocidos: Logaritmos discretos y factorización.

Estos problemas se hacen exponencialmente más difíciles a medida que aumenta el tamaño de los números involucrados. Por ejemplo, mientras que la factorización 35 es trivial (5×7), la factorización de un número de 1024 bits como el utilizado en RSA (llamado módulo RSA) no se ha logrado todavía. Por ello, a veces se denominan “funciones unidireccionales”.

Logaritmo discreto

El logaritmo es la operación que da como resultado el exponente que hay que aplicar a un cierto número, llamado base, para obtener algún número. Por ejemplo, ya que 10^2=100 tenemos que el logaritmo en base 10 de 100 es 2.

En este ejemplo 10 se llama la base, 100 se llama el antilogaritmo y 2 se llama el logaritmo.

La palabra “discreto” antes del logaritmo significa que la operación se define en un campo de números con un tamaño finito, en lugar del campo de números reales, que es infinito. Hay diferentes campos numéricos para definir la operación del logaritmo discreto. Los más utilizados son “Enteros módulo a primo” y “Curvas elípticas sobre enteros módulo a primo”.

El cálculo de un logaritmo discreto en ciertos campos numéricos se hace exponencialmente más difícil a medida que el antilogaritmo crece.

Véase el anexo I, Diffie-Hellman para una explicación detallada del protocolo de intercambio de claves de Diffie-Hellman, que se basa en los logaritmos discretos.

Factorización

Factorizar significa obtener los factores primarios que forman cualquier número. Todos los números pueden obtenerse multiplicando uno o varios números primos. Por lo tanto, el factoraje 15 es llegar a saber que se puede construir multiplicando 3×5.

Como dijimos antes, la factorización se hace exponencialmente más difícil a medida que el número a ser factorizado crece.

Consulta el Anexo I para una explicación detallada del criptosistema de clave pública RSA, que se basa en el problema de la factorización.

¿Qué significa “exponencialmente más complejo”?

En la figura 1 puedes ver el tiempo requerido en una prueba de muestra para factorizar un número construido multiplicando dos números primos aleatorios. Se puede ver fácilmente que a medida que el número a factorizar aumenta, el tiempo requerido para factorizarlo aumenta de forma acelerada. Las dos series muestran el esfuerzo utilizando dos algoritmos de factorización diferentes.

Utilizamos escalas logarítmicas para representar los gráficos exponenciales de manera que nos permite percibir los detalles a lo largo del conjunto de datos, como en la figura 2, que muestra los mismos datos en un formato (quizás) menos impactante visualmente pero que nos permite hacer algunas estimaciones.

Observa cómo el eje vertical difiere de un gráfico normal. En un gráfico normal tendríamos un crecimiento proporcional de valores como en la figura 1 (0, 500, 1000, 1500, …), donde cada 500 segundos se representan con el mismo espacio vertical. En la figura 2, por el contrario, los valores se incrementan de acuerdo con el incremento de un exponente (10-2, 10-1, 100, 101, 102, 103, …) y así un valor en el rango de los milisegundos se representa usando el mismo espacio que los valores en el rango de los miles o millones de segundos.

Podemos imaginar, a grandes rasgos, lo difícil que es factorizar un gran número utilizando una escala de registro y algunos datos:

  1. El mayor módulo RSA factorizado públicamente (2009) a la fecha de este escrito (2020) tenía una longitud de 768 bits y requería un esfuerzo equivalente a 1500 años en un procesador AMD Opteron de 2,2GHz de un solo núcleo.
  2. Los autores de este logro afirman que factorizar un módulo RSA de 1024 bits requeriría un esfuerzo 1000 veces mayor.
  3. Los FLOPS públicos del núcleo de 2,2GHz del AMD Opteron 2427 y de diferentes supercomputadoras
  4. El esfuerzo estimado para factorizar un módulo de 2048bit RSA es 2^32 veces más difícil que un módulo de 1024bit.

Si agrupamos todo esto en una escala de registro, obtenemos la figura 3.

Figure 3: Rough estimation of the time required to factor large RSA moduli

La potencia combinada de las 500 supercomputadoras más poderosas del mundo necesitaría del orden de 10.000 años para factorizar un módulo RSA de 2048 bits. Por lo tanto, necesitaría lanzar su programa de factorización durante el final de la Edad de Hielo para obtener el resultado hoy.

El actual tamaño de clave por defecto utilizado por OpenSSH es de 3072 bits, lo que requeriría, aproximadamente la edad del universo para ser factorizada por el mismo grupo de supercomputadoras. Imagínate con ese clúster de computación, sin hablar del Big Bang.

Un módulo RSA de 4096 bits necesitaría aproximadamente un millón de veces la edad del universo para ser factorizado por el mismo clúster.

Así de difícil es actualmente romper la criptografía de clave pública, cuando se utiliza correctamente. Existen formas alternativas de atacar la criptografía de clave pública y se basan principalmente en implementaciones deficientes. Pero esto está fuera del alcance de este artículo.

Computación cuántica 💻

La característica principal de los ordenadores cuánticos es que se basan en bits cuánticos, qubits. En la computación clásica operamos con bits y tienen en todo momento un único valor, ya sea 0 o 1. Por el contrario, los qubits son especiales porque utilizan ciertos fenómenos cuánticos como la superposición y el entrelazamiento.

Superposición

Tal vez haya oído hablar del gato de Schrödinger, un “gato cuántico” imaginario que está vivo y muerto simultáneamente hasta que alguien lo observa. Las partículas cuánticas en superposición se comportan como si estuvieran en diferentes estados simultáneamente y sólo obtienen un estado final y único cuando son observadas o medidas. Se dice que “colapsan” a un estado específico.

Los Qubits son como el gato de Schrödinger: Mientras que en superposición se comportan como si estuvieran en el estado 0 y 1 SIMULTÁNEAMENTE. Sólo cuando lo medimos, el qubit colapsa a un solo estado. Antes de eso, podemos calcular la probabilidad del resultado, pero no podemos estar seguros de cuál será.

Entrelazamiento

Gracias al entrelazamiento, dos partículas cuánticas siempre tendrán una correlación entre sus estados. Tomemos, por ejemplo, dos fotones entrelazados. Mientras que en superposición no podemos saber qué spin (↑ or↓) mostrarán cuando se midan. Pero una vez que medimos uno de los fotones, sabemos que el otro se habrá colapsado al espín opuesto. Si el fotón A se mide con el espín ↑, sabemos que el fotón B se habrá colapsado al espín ↓.

Cuando dos qubits se entrelazan, podemos predecir la medida que obtendremos de un qubit al medir su par. Esta propiedad se utiliza en la computación cuántica para crear algoritmos de lógica cuántica.

Universos paralelos

Volviendo al gato de Schrödinger, una de las interpretaciones de la rareza de la física cuántica es el modelo de “muchos mundos. Esta interpretación considera que, cuando se observa el gato en superposición, el mundo “se divide” con cada posible estado del gato. De ahí que el mundo anterior genere dos ramas, un mundo en el que el observador ve un gato vivo y otro mundo en el que el observador ve un gato muerto.

Hay un bonito cortometraje que explora esta idea de entrelazarse en múltiples universos: La máquina del tiempo de un minuto. Sólo échale un vistazo y ríete.

¿Por qué los ordenadores cuánticos son diferentes?

Una forma de pensar en los ordenadores cuánticos es que aprovechando la superposición y el enredo pueden manipular varios estados a la vez. Consideremos un ordenador clásico que opera con bits. Sólo puede estar en un único estado en cualquier momento y sus n bits tendrán un único valor. Por el contrario, un ordenador cuántico con n qubits estará en estados simultáneamente y podrá operar en todos esos estados A LA VEZ.

A veces esto se compara con la computación paralela. Esto no es muy exacto y hay algunos argumentos en contra de esta comparación. De todos modos, la idea básica es que un ordenador cuántico puede proporcionar una velocidad exponencial al atacar algunos problemas complejos.

El objetivo de un algoritmo cuántico es llevar a cabo operaciones en estados cuánticos de tal manera que la medición de los qubits probablemente nos proporcione una respuesta a nuestro problema. Y esta “probabilidad” se maneja jugando con la superposición, el enredo, la interferencia y las probabilidades.

Consulta el Anexo II para más detalles sobre los fundamentos de la computación cuántica.

El algoritmo de Shor

Peter Shor encontró una forma de calcular logaritmos discretos y enteros factoriales de manera que no crezca exponencialmente con el tamaño de la variable. El algoritmo que diseñó es capaz de resolver esos problemas en lo que se llama “tiempo polinomial”. Esto es, si el tamaño en bits del antilogaritmo o la clave RSA es , la complejidad de calcular el logaritmo discreto o factorizar la clave estaría en el rango de n elevado a 2 utilizando el algoritmo de Shor, en lugar de x elevado a n utilizando los algoritmos clásicos, que es una función exponencial que crece mucho, mucho más rápido.

Esto significa, por ejemplo, que romper una clave RSA de 4096 bits podría llevar minutos, horas o días en lugar de varias veces la edad del universo.

Véase el Anexo I, el algoritmo de Shor para una explicación más detallada de su funcionamiento.

Criptografía postcuántica (o por qué lo cuántico no matará a la criptografía) ⭐️

Aunque el algoritmo de Shor puede romper los criptosistemas basados en registros y factorización discreta, su implementación requiere una computadora cuántica con un gran número de qubits. No hay predicciones precisas sobre cuándo existirá una computadora cuántica lo suficientemente grande como para romper los actuales criptosistemas de clave pública, pero las expectativas más cercanas estiman la década de 2030 para ese evento.

Mientras tanto, los investigadores y los organismos de normalización están trabajando en la llamada “criptografía post-cuántica”. Es decir, criptosistemas de clave pública que pueden ser ejecutados en computadoras clásicas pero que no pueden ser rotos por computadoras cuánticas. Puede encontrar más información sobre la criptografía postcuántica y los esfuerzos de normalización en los siguientes enlaces:

Se espera que los esfuerzos de la criptografía postcuántica proporcionen nuevas normas a principios de la década de 2020, por lo que se espera que tengamos pocos años para adaptar y migrar de los actuales criptosistemas de clave pública a la nueva criptografía de clave pública postcuántica.

Mientras tanto, tenemos que tener cuidado con el tiempo que se espera que nuestros datos y firmas encriptadas estén seguros. Esto dependerá en gran medida del caso de uso.

Anexos

Anexo I: Algunos detalles matemáticos de la criptografía de clave pública

Anexo II: Algunos detalles adicionales sobre la computación cuántica

¡Gracias a María José Ruiz Félez por las ilustraciones! 🙌

jaime gomez

Jaime Gómez García

Santander Global Tech

Experto en arquitectura de infraestructura IT y telecomunicaciones. Aprendo sobre Internet, redes y criptografía aplicada cada día desde mediados de los 90.

 

Otros posts