ABC, 11 de Octubre de 2020
CIENCIA - El ABCdario de las matemáticas
Iván Blanco Chacón

Iván Blanco Chacón, profesor e investigador en la Universidad de Alcalá de Henares, explica cómo los ordenadores cuánticos se enfrentarán a descifrar la mayoría de los protocolos criptográficos

Ilustración del problema del vector más próximo, especialmente intratable a la hora de ser descifrado

Del 21 al 23 de septiembre se celebró virtualmente el undécimo congreso internacional sobre criptografía postcuántica. Organizado en esta ocasión por el Instituto Nacional de Investigación en Informática y Automática (INRIA, por sus siglas en francés), se trata de un foro de comunicación a nivel mundial de una disciplina que cada año adquiere mayor relevancia por lo que hay en juego.

En efecto, de acuerdo con MIRACL Labs, multinacional de capital anglo-irlandés comercializadora de soluciones criptográficas, se estima que en 15 años se dispondrá de un ordenador cuántico con capacidad para romper en tiempo razonable los problemas sobre los que se sustenta la mayor parte de los protocolos criptográficos de clave pública. Estos algoritmos están en la base de la confidencialidad de millones de transacciones diarias en los ámbitos financiero, industrial, sanitario o gubernamental. En pocas palabras: no existe ciberseguridad sin criptografía.

Si bien otros centros de investigación se muestran más cautos, pocas estimaciones para tal escenario rebasan los 30 años. Y no se trata de mera rumorología: basta consultar la prensa especializada para descubrir que gigantes tecnológicos como IBM, Intel, Microsoft y Google ya avanzan a pasos acelerados en la carrera postcuántica, tanto a nivel físico como a nivel de software. Por si hubiese alguna sospecha de parcialidad, sesgo o inexactitud para tales fuentes, se puede acudir a las publicaciones académicas o industriales, en particular a aquellas de congresos internacionales tan poco sospechosos de falta de rigor como EUROCRYPT, ASIACRYPT, WCC o el que abre nuestro artículo.

El algoritmo de Shor

Un poco de historia reciente: en 1997 se abría la posibilidad teórica de romper de manera eficiente la mayoría de los sistemas de cifrado asimétrico e intercambio de claves usados desde principios de los 80. En efecto, el algoritmo de Shor aparecía publicado en la revista SIAM Journal of Computation, de la Sociedad Internacional de Matemática Aplicada. Así pues, una implementación de este algoritmo en un ordenador cuántico permitiría romper cifrados como RSA y métodos de intercambio de clave como Diffie-Hellman en tiempo polinomial. Trataremos a continuación de dar unas ideas básicas sobre el cifrado RSA. En cuanto al protocolo Diffie-Hellman, remitimos a la correspondiente entrada en Wikipedia o a este excelente tutorial del proyecto Class4Crypt de la Universidad Politécnica de Madrid.

El criptosistema RSA (Rivest, Shamir y Adleman, 1979) es un sistema de cifrado de clave pública que se basa en la dificultad computacional de factorizar números enteros grandes: dado un número compuesto de N cifras escogido al azar, el número de operaciones elementales que hay que realizar para encontrarle un factor propio por fuerza bruta es exponencial en N. Para hacerse una idea, un número de 10000 cifras requeriría del orden de 2^10000 operaciones en coma flotante, lo que incluso con una red de supercomputadoras de la presente generación trabajando en paralelo y con dedicación exclusiva llevaría más de un siglo. Para entonces, estamos convencidos de que nadie usará ya ningún criptosistema basado en factorización.

El criptosistema RSA

En concreto, el criptosistema RSA consiste, en primera aproximación, en lo siguiente:

Se escogen dos números primos p, q suficientemente grandes y se calcula el producto n=pq. Se escoge un entero c < (p – 1)(q – 1), que llamaremos exponente de cifrado. Se escoge otro entero d < (p – 1)(q – 1) de tal manera que el producto cd tenga resto 1 al dividir por (p –1)(q –1). Este entero se denomina exponente de descifrado y su existencia se demuestra fácilmente. Además, estos exponentes han de ser primos con (p – 1)(q – 1). Con estas elecciones, la clave pública (conocida por cualquier usuario del canal de comunicaciones) es el par (n, c) y la clave privada (conocida sólo por los usuarios premium de dicho canal, llamémosles Alicia y Roberto), es el exponente de descifrado.

Codificamos las letras y otros signos tipográficos mediante un código apropiado, como ASCII (American Standard Code for Interchange of Information). Para cifrar un texto, codificamos cada letra y dividimos el número resultante en bloques de tamaño a lo sumo n = pq. Ilustramos el sistema de cifrado/descifrado con un ejemplo de juguete: tomemos p =11 y q =13. Tomemos c =7, con lo que n =21 y la clave pública es (143, 7). Como exponente de descifrado buscamos d < por (p –1)(q – 1) = 120 (y primo con éste) tal que 7d tenga resto 1 módulo 120, es decir, al dividir por 120. El único entero que lo satisface es d =103, que es la clave privada, conocida sólo por Alicia y Roberto. Así, si Alicia le quiere enviar cifrada a Roberto la letra «C» (correspondiente al número 67 del código ASCII), debe calcular el resto de 67^7 módulo 143, que es 89.

Debido a un teorema de Euler, dado un bloque cifrado como b^c módulo n, (b se supone primo con n) al efectuar su exponenciación al módulo de descifrado y tomar de nuevo su resto al dividir por n, recuperamos el bloque original. Así, Roberto, que conoce la clave privada d =103, para descifrar 89, calcula el resto módulo 143 de 89^103, recuperando el 67, es decir, la letra «C».

¿Puede un intruso recuperar un mensaje?

Como vemos, la obstrucción para que un potencial intruso recupere un mensaje a través de su versión cifrada consiste en determinar el exponente d, que es un resto módulo (p – 1)(q –1). Ahora bien, para obtenerlo desde la clave pública (n=pq, c), se hace necesario factorizar el número n y eso, como hemos apuntado antes, en principio resulta prohibitivo si se toman determinadas precauciones en la elección de los factores primos p y q, como que tengan esencialmente el mismo número de cifras y que éste sea superior a 300.

Como decíamos al principio, el algoritmo de Shor es capaz de resolver este problema en un tiempo del orden de log(n)^3. Con nuestro anterior ejemplo de un número de 10000 cifras, el tiempo requerido para factorizarlo mediante este algoritmo sería del orden de 2^13 operaciones, perfectamente factible en algo más de un minuto.

El qubit

Dicho algoritmo se basa en la noción de qubit, objeto matemático que se puede entender como una esfera de radio 1, cada uno de cuyos puntos representa uno de los infinitos posibles estados de un sistema cuántico (un bit tiene sólo dos posibles estados: encendido o apagado). En el algoritmo se utilizan de manera crucial las nociones cuánticas de superposición de estados y de trasformada cuántica de Fourier. Remitimos al lector interesado en la computación cuántica al siguiente artículo debido a Sebastiá Xambó y Juanjo Rué, destacable por su claridad y rigor.

Representación gráfica de un qubit - Licencia Wikimedia Commons

Si bien en 1997 la posibilidad de implementar el algoritmo de Shor en un soporte cuántico parecía casi impensable, en 2001 se consiguió ejecutar en una computadora cuántica de 7 qubits, consiguiendo factorizar el número 15; las cosas comenzaban a ponerse serias. Desde entonces se ha asistido a una frenética carrera de hitos que ha culminado con el lanzamiento, en 2019, del primer ordenador cuántico comercial: IBM QSystem I, de 20 qubits y aún lejos de suponer una amenaza a nuestra privacidad. Meses después, en septiembre, IBM anunciaba el inminente lanzamiento de un nuevo ordenador de 53 qubits. Veremos en qué queda.

Frente a estos acontecimientos se hace cada vez más urgente la investigación en problemas matemáticos inmunes ante un ataque cuántico de iure, esto es, en el sentido de que se haya probado formalmente su carácter intratable, o de facto, es decir, porque hasta la fecha no se haya encontrado un ataque efectivo. Esta es la razón por la que, en 2017, el Instituto Nacional de Estándares y Tecnología (NIST) lanzó un concurso público para decidir y estandarizar los sistemas criptográficos para un mundo post-cuántico. En varias rondas, los algoritmos propuestos deben ser sometidos a riguroso examen y sólo pasan a la siguiente fase los que sobrevivan a tal escrutinio y no sean rotos mediante ningún método de criptoanálisis. Las propuestas supervivientes a fecha de Julio de 2020 pueden consultarse aquí.

Existen diversos problemas aparentemente seguros sustentando las distintas propuestas del concurso NIST. Para concluir, comentamos tres de los enfoques más relevantes, omitiendo el resto por motivos de complejidad y extensión.

Criptografía basada en códigos

Un código corrector de errores se puede entender como un par (F, G), donde:

Dado un código genérico (F, G) y dado un vector v = F(u) + e de {0,1}R, si no se conoce G, la cantidad de operaciones que se ha de hacer para recuperar u a partir de v es exponencial en r.

Este hecho sustenta el criptosistema de McEliece, una de las propuestas para la criptografía post-cuántica. Este criptosistema ha sido roto para un buen número de códigos clásicos y presenta además el inconveniente del gran tamaño de las claves necesarias para garantizar un nivel aceptable de seguridad, lo que redunda en un problema tanto de almacenamiento como de velocidad.

El uso más importante de este criptosistema es el de cifrado/descifrado, y es uno de los temas de investigación de, por ejemplo, el grupo de criptografía de la Universidad de La Laguna, en Tenerife.

Criptografía basada en polinomios multivariables

Se basa en el hecho de que dado un sistema de ecuaciones polinomiales cuadráticas en varias variables con coeficientes binarios (o más en general en un cuerpo finito), encontrar sus soluciones es un problema de orden exponencial en el número de variables. Un tal sistema, por ejemplo, sería el dado por:

Este problema permite definir un criptosistema que se usa para firmas digitales autenticadas. Una variante del mismo llamada DME (Double Matrix Exponentiation) ha sido patentada y fue presentada al concurso NIST por Ignacio Luengo y Martín Avendano, ambos profesores de la Universidad Complutense de Madrid.

Criptografía basada en retículos

Se basa en el problema del vector más próximo (closest vector problem o CVP), del que se sabe que es esencialmente intratable. El problema se refiere a retículos, una estructura algebraica que se puede entender como un mallado discreto de puntos en el espacio de dimensión n. Podemos pensar en un retículo como una versión estirada y rotada del conjunto Z^n formado por los vectores de n componentes y coordenadas enteras. Estos vectores se pueden sumar componente a componente, y para un tal retículo, el CVP consiste en, dado un vector v de n componentes con coordenadas reales, encontrar el vector del retículo de menor distancia a v.

Ilustración del problema del vector más próximo. En negro, varios puntos de un retículo. En verde, el punto a aproximar. En rojo, el punto del retículo más próximo - Licencia Wikimedia Commons

Existen diversas propuestas dentro de esta categoría, entre las que destacamos LWE (Learning With Errors), RLWE (Ring Learning With Errors) y PLWE (Polynomial Learning With Errors). Todos ellos son criptosistemas de gran simplicidad de implementación y salvo LWE, tienen la ventaja de necesitar un tamaño de clave moderado con respecto a, por ejemplo, el criptosistema de McEliece. Sustentan además tanto esquemas de cifrado como intercambio de claves o firmas digitales.

Otra ventaja es que son criptosistemas homomorfos, es decir, permiten operar sobre datos cifrados trasladando esa operación a los datos descifrados, funcionalidad de enorme interés a día de hoy, especialmente en ámbitos como computación y almacenamiento en sistemas distribuidos, o sobre la nube, con aplicaciones aún por explotar en sanidad, sistemas de votaciones electrónicas u otros contextos en que el proveedor de servicios no necesita (ni debe) conocer los datos sobre los que debe actuar, haciéndolo a través de sus versiones cifradas.

En el grupo TENCALCRYPT de la Universidad de Alcalá de Henares, del que el autor es miembro, se encuentra entre nuestros temas de investigación la equivalencia entre PLWE (más adecuado para implementaciones) y RLWE (más adecuado para análisis teóricos), así como su criptoanálisis mediante técnicas de aprendizaje automático y su aplicación a cifrados homomorfos.

Iván Blanco Chacón es profesor e investigador en la Universidad de Alcalá de Henares.

El ABCDARIO DE LAS MATEMÁTICAS es una sección que surge de la colaboración con la Comisión de Divulgación de la Real Sociedad Matemática Española (RSME)