Noticias #eXplora <a href="https://static2.abc.es/media/ciencia/2020/10/09/Imagen5_CVP-kBiF--620x349@abc.jpg">Media</a>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. Imagen 1: Peter Shor recibiendo la medalla Dirac en el Centro Internacional de Física Teórica (2017) - Licencia Wikimedia Commons 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…