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¡±.
Tu suscripci¨®n se est¨¢ usando en otro dispositivo
?Quieres a?adir otro usuario a tu suscripci¨®n?
Si contin¨²as leyendo en este dispositivo, no se podr¨¢ leer en el otro.
FlechaTu suscripci¨®n se est¨¢ usando en otro dispositivo y solo puedes acceder a EL PA?S desde un dispositivo a la vez.
Si quieres compartir tu cuenta, cambia tu suscripci¨®n a la modalidad Premium, as¨ª podr¨¢s a?adir otro usuario. Cada uno acceder¨¢ con su propia cuenta de email, lo que os permitir¨¢ personalizar vuestra experiencia en EL PA?S.
En el caso de no saber qui¨¦n est¨¢ usando tu cuenta, te recomendamos cambiar tu contrase?a aqu¨ª.
Si decides continuar compartiendo tu cuenta, este mensaje se mostrar¨¢ en tu dispositivo y en el de la otra persona que est¨¢ usando tu cuenta de forma indefinida, afectando a tu experiencia de lectura. Puedes consultar aqu¨ª los t¨¦rminos y condiciones de la suscripci¨®n digital.
