Polinomios contra ordenadores cuánticos
El proceso de estandarización se completará a partir de 2025 y se comenzará una migración a los nuevos sistemas criptográficos
Gobiernos y multinacionales están invirtiendo grandes cantidades de dinero en la construcción del ordenador cuántico; a día de hoy IBM y Google son los más avanzados en esta dirección. Estos ordenadores podrán realizar simulación cuántica para modelar complejas reacciones químicas, o diseñar nuevos medicamentos, operaciones que están fuera del alcance de los más potentes ordenadores binarios. Pero este avance también tiene sus inconvenientes, por ejemplo, dejarán de ser seguros los sistemas criptográficos empleados hoy en día para garantizar el comercio electrónico y las comunicaciones en la red, ya que un ordenador cuántico podrá factorizar rápidamente los grandes números en los que se basa la seguridad de algoritmos de cifrado de clave pública o firma digital más empleados, como el RSA y DSA, empleando el algoritmo de Shor.
Frente a esta situación, en 2015 la Agencia Nacional de Seguridad (NSA) de EE UU anunció que los estándares actuales de criptografía de clave pública no son seguros a largo plazo y pidió que se iniciara cuanto antes la búsqueda de algoritmos de cifrado de clave pública seguros contra ordenadores cuánticos, también llamados postcuánticos. Motivado por este anuncio, el Instituto Nacional de Estándares y Tecnología (NIST) de EE UU lanzó en 2016 un concurso público para identificar, elegir y estandarizar algoritmos postcuánticos. Se buscaban sistemas de dos tipos: de cifrado e intercambio de claves, y de firma digital. Se han presentado 83 propuestas de 17 países, de los cuáles 56 mantienen su resistencia a los ataque con ordenadores clásicos y a los algoritmos cuánticos conocidos por el momento.
Las matemáticas juegan un papel importante en todos los sistemas de cifrado de clave pública y firma digital, y también en los sistemas postcuánticos. Los sistemas de clave pública usan una clave (PK) que es pública para cifrar, y una clave secreta (SK) para descifrar, que no se puede deducir de la primera. Para la firma digital se usa primero SK y luego PK. La seguridad de estos sistemas se basa en la dificultad de resolver determinados problemas matemáticos, incluso disponiendo de un ordenador de gran capacidad de cálculo. Por ejemplo, en el célebre y omnipresente algoritmo RSA, la seguridad se basa en la dificultad de factorizar un número N=p*q que es producto de dos números primos muy grandes (sin conocer ninguno de estos, que serían la clave privada (p,q)). En los sistemas de retículos, el problema difícil es el de encontrar un vector de longitud mínima; y los llamados sistemas multivariables se basan en la dificultad resolver sistemas de ecuaciones polinomiales en muchas variables.
Estos sistemas multivariable usan como clave pública un conjunto de polinomios de grado bajo (2,3,4..) en muchas variables. Funcionan de la siguiente manera: si la clave pública son los polinomios F(x, y) = 3y²+2x+y, G(x,y) = 18y³+12xy²-2x²+x+y y un mensaje es M= (3,11) el mensaje cifrado es el resultado de evaluar (substituir) el mensaje en los dos polinomios, es decir: (F(3,7), G(3,7))=(44, -4418). Una persona no autorizada que no dispone de la clave privada tiene que resolver las ecuaciones 3y²+2x+y = 134, 18y³+12xy²-2x²+x+y = -41462 para obtener el mensaje original. Cuando el número de polinomios empleados y sus variables crece, se obtienen sistemas de ecuaciones muy complicados de resolver, incluso para un ordenador.
Todos los sistemas multivariables propuestos al NIST utilizan polinomios cuadráticos (de grado dos) en un numero alto N de variables (por ejemplo N=512) salvo el sistema llamado DME que hemos desarrollado y patentado en la Universidad Complutense y el ICMAT, que usa polinomios en seis variables de grado muy alto (hasta 2^48) sobre cuerpos finitos. Este sistema, implementado en colaboración con la Universidad de Zaragoza, es muy rápido (al igual que los sistemas cuadráticos) y tiene la ventaja sobre estos que las claves son mucho más pequeñas. De momento se cree que estos sistemas son seguros contra ordenadores cuánticos y ahora se evalúa su resistencia a ataques con ordenadores “clásicos”. Por ahora el DME se mantiene en el concurso, como candidato a ser uno de los varios “ganadores” esperados del mismo (al menos, habrá uno por cada tecnología en concurso). Según los planes del NIST, el proceso de estandarización se completará a partir de 2025 y se comenzará una migración a los nuevos sistemas criptográficos, preparados para la revolución cuántica. Aunque no se sabe cuándo llegarán los ordenadores cuánticos, todos los datos confidenciales y el tráfico de Internet deberían de estar protegidos a partir de esa fecha, preparados para resistir al futuro cuántico.
Ignacio Luengo es catedrático de Álgebra de la Universidad Complutense de Madrid e investigador del ICMAT
Café y Teoremas es una sección dedicada a las matemáticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matemáticas (ICMAT), en la que los investigadores y miembros del centro describen los últimos avances de esta disciplina, comparten puntos de encuentro entre las matemáticas y otras expresiones sociales y culturales, y recuerdan a quienes marcaron su desarrollo y supieron transformar café en teoremas. El nombre evoca la definición del matemático húngaro Alfred Rényi: “Un matemático es una máquina que transforma café en teoremas”.
