En mis clases de Matemática Discreta les hablo a mis alumno del RSA, incluso hacemos pequeños ejemplos con el algoritmo. Es una de las formas para ver cómo aplican esas cosas raras para ellos que llamamos «congruencias».
El RSA es un sistema criptográfico de clave pública desarrollado en 1979. Dicen que es el primero y más extendido algoritmo de este tipo, válido tanto para cifrar como para firmar digitalmente.
La seguridad del cifrado RSA radica en el hecho de que hasta el momento no existe un algoritmo eficiente para factorizar enteros; hablamos de un algoritmo que factorice enteros con $n$ dígitos en un tiempo polinomial del orden $\mathcal{O}(n^k)$. De modo que si elegimos dos primos suficientemente grandes, $n=p\cdot q$ no resulta práctico calcular su factorización, en un tiempo prudencial.
El funcionamiento de este sistema, descrito en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman, del Instituto Tecnológico de Massachusetts (MIT), aunque el matemático británico Clifford Cocks, que trabajaba para la agencia de inteligencia británica, formalizó un sistema equivalente en un documento interno en 1973, está extensamente explicado, véase por ejemplo en wikipedia RSA. Es de los sistemas de cifrado que se definen como sistema de clave pública; cada usuario posee dos claves de cifrado: una pública y otra privada. Esa calve pública es un $n$, muy grande, como el que hablábamos antes, y un entero $e$, el exponente de cifrado, con ciertas propiedades, muy prácticas para explicar conceptos de aritmética modular.
Pero veamos un poco más de su historia.
Según nos cuenta Richard Johnsonbaugh, en su libro Matemáticas Discretas, la primera descripción del sistema de cifrado RSA apareció en una columna de Martin Gardner en la edición de febrero de 1977 del Scientific American(Una observación, Rivest, Shamir y Adleman lo publicaron como una MIT «Technical Memo» en abril de 1977, y oficialmente en una publicación en 1978, lo que nos dice que Gardner estaba al tanto de los avances en criptografía de esos años). En esta columna se incluyó un mensaje codificado utilizando una clave dada por el producto de dos primos de 64 y 65 dígitos y e=9007, junto con un premio de 100 dólares para la primera persona que descifrase el código. Cuando se escribió el artículo, se estimaba que se necesitarían 40,000 billones de años para factorizar $n$. De hecho, en abril de 1994, Arjen Lenstra, Paul Leyland, Michael Graff y Derek Atkins, con la ayuda de 600 voluntarios de 25 países, utilizando más de 1600 computadoras, factorizaron $n$, coordinando la factorización mediante Internet. Antonio Ropero detalló este reto en su post Martin Gardner, RSA y otros pasatiempos matemáticos.
Y ahora, ¿en cuánto tiempo lo descifraríais? Os animáis a poner a trabajar a vuestros alumnos.
Este post forma parte del Carnaval de Matemáticas, que en esta septuagésima novena edición, también denominada X.6, está organizado por @juanfisicahr a través de su blog Esto no entra en el examen.
PD: Si te ha gustado este post, quizás también te guste otras cosas que cuento en mi novela Muret, la batalla que marcó a la Corona de Aragón
1 comentario
Los comentarios están cerrados.