RSA y el poder de los números primos

Espiral de Ulam representando patrones en la aparición de números primos

La película Mercury Rising de 1998 es un thriller policial donde un sistema criptográfico es la chispa que inicia toda la acción. Bruce Willis encarna a un agente del FBI envuelto en una intriga del gobierno que - al mejor estilo de duro de matar - debe proteger a un niño autista de asesinos despiadados. El niño pudo desencriptar un millonario criptosistema que la NSA había puesto dentro de un crucigrama de una revista.

El costado criptográfico en la película es una mera excusa para la acción y la presentación de ciertos personajes truculentos. Pero, como siempre, la realidad supera a la ficción. Los casos de claves secretas en los medios de comunicación, asesinatos para mantener el silencio y criptosistemas cuya seguridad penden de un principio que puede ser vulnerado se amontonan en la historia.

Los sistemas criptográficos son objeto de estudio constante. Se busca debilidades dentro de ellos para quebrarlos y obtener el mensaje. Los sistemas criptográficos toman un mensaje y lo transforman mediante el proceso de encriptado en un código no entendible o legible. La transformación es una función particular que debe cumplir algunas cuestiones. La primera es que debe ser reversible, es decir que no se debe perder información en el proceso y que la misma se pueda volver para atrás para leer el mensaje original. La segunda es que debe ser privado: La reversión no la puede realizar cualquier individuo que intercepte el mensaje, sino solo aquellos autorizados.

La invención de la escritura introdujo la capacidad de transmitir ideas, situaciones y ordenes entre personas que compartían el lenguaje utilizado. La transmisión de mensajes privados requería lenguajes privados que solo los destinatarios correctos pudieran comprender. Así nacen los primeros criptosistemas. Todos ellos contienen una "llave" que permite abrir o descifrar el código. La llave o clave puede ser de diferente naturaleza: una tabla de sustitución de letras o palabras, un número que indique rotación de letras o algún parámetro para alguna función matemática. La necesidad de intercambiar esa clave es un punto de debilidad de estos sistemas. Conocida la clave el secreto cae.


El problema del intercambio de la clave fue una constante en los métodos criptográficos hasta que en 1976 se publica un revolucionario artículo llamado "New Directions in Cryptography" por Whitfield Diffie y Martin Hellman. Una nueva rama de la criptografía conocida como de clave pública es presentada a la comunidad científica. Los criptosistemas de clave publica reciben su nombre por contar con un par de claves para su funcionamiento: una clave para encriptar (clave pública) y una clave para desencriptar (clave privada). Si una persona le quiere enviar un mensaje encriptado a otra debe obtener la clave pública del destinatario (su nombre ya lo indica es de dominio público) y utilizarla para codificar el mensaje. Únicamente el destinatario mediante la clave privada puede realizar la reversión y obtener el texto original.

Rivest, Shamir y Adleman

El método más utilizado de clave pública es el conocido con el nombre de RSA. Creado en 1977 por Rivest, Shamir y Adleman. Aunque no es el único, ni el primero, es el más popular. Estando por cumplir 40 años sigue siendo un método seguro. Es un criptosistema que utiliza una particularidad matemática para generar la codificación. Desde la escuela primaria nos enseñan un mecanismo sencillo para realizar cualquier multiplicación. Al mismo tiempo nos enseñan a factorizar un número (es decir determinar cuales son sus números primos divisores). La factorización es más compleja, puesto que no hay un algoritmo directo para su cálculo, sino que hay que probar número a número si es divisor o no (existen, por supuesto, algunos atajos para ciertos casos. Ejemplo si es un número es par, el número 2 es divisor. Si termina en 0 o 5, el 5 es divisor. Etc).

RSA utiliza para generar sus claves 2 números primos muy grandes que multiplica para generar un valor aun mayor. El nuevo número, para quien no conoce sus divisores, es muy complejo de factorizar. Mediante el número calculado y varias cuestiones matemáticas que no vamos a detallar (entre ellas la aritmética modular, la función indicatriz de Euler, entre otras) generan una clave privada y una pública. Acá una serie de videos que explican en detalle como funciona el criptosistema.

La fortaleza de RSA es la inexistencia de un método matemático para factorizar un numero grande. El método por fuerza bruta debe probar gran cantidad de números. Obviamente no todos los números, pero una gran cantidad - los números primos. Pero lo que complica aun más las cosas es que no hay un algoritmo eficiente para ver si un número es primo. Por lo tanto, para factorizar un número grande, hay que buscar sus divisores, probando también si aquellos son primos... buscando sus divisores.

Buscar números primos o la forma de determinar si un número es primo es un pasatiempo más común de lo que se sospecha (la página "The prime pages" es una muestra ). Continuamente se busca encontrar números primos más grandes y algún patrón que ayude a simplificar el problema de la determinación.

La espiral de Ulam es una representación que hace suponer de la existencia de algún diseño oculto. Fue creada por el matemático Stanisław Marcin Ulam en 1963 como un proceso lúdico durante una conferencia científica que le estaba resultado tediosa. Consiste en, partiendo del numero 1, ir escribiendo los números en forma de espiral. Luego se marcan aquellos que son primos. Ulam noto que aparecían diagonales de números primos. Estos patrones siguen apareciendo a medida que se continua con la espiral. El fortuito descubrimiento fue tapa de la revista Scientific American un año después y de gran interés para sus colegas matemáticos. De todas formas, aun no se ha encontrado una representación matemática que pueda predecir la aparición de esos patrones.

Si en algún momento se encuentra un mecanismo para determinar los números primos sin esfuerzo, RSA sufriría una merma en su seguridad importante. Por ahora el método aparenta ser seguro, pero...

Una historia dentro del libro, de 1985, "El hombre que confundió a su mujer con un sombrero" de Oliver Sacks parece indicar lo contrario. El neurólogo y divulgador científico nos cuenta su encuentro con gemelos que sufrían el síndrome del sabio: una variante del autismo donde el afectado cuenta con habilidades extraordinarias en un campo determinado. En su narración estos hermanos, que no poseían habilidades matemáticas, parecían felices intercambiándose números de 6 dígitos alternativamente uno al otro. Sacks analizó los números y descubrió que eran números primos. Decidido a probar su teoría buscó un libro con tablas de números primos y se presentó antes ellos el día siguiente. Para iniciar pronunció un número primo de 8 dígitos. Los gemelos luego de pensar menos de un minuto sonrieron, como dando a entender que el juego continuaba. Pasados 5 minutos uno respondió con un número primo de 9 dígitos. El neurólogo compartió un primo de 10 dígitos. Poco tiempo después la respuesta fue un número primo de 12 dígitos. En otra ocasión, una caja de fósforos se cayó dejando desperdigado su contenido por el suelo. Rápidamente los gemelos exclamaron 111 y luego repitieron 37 tres veces. Es decir que factorizaron el numero (3x37=111). Sacks contó los fósforos y efectivamente eran la cantidad declamada.

Existen varios críticos de la historia de Sacks. Entre ellos Makoto Yamaguchi, que en una publicación de 2006 no duda de la capacidad de los gemelos en realizar cálculos matemáticos. Pone en tela de juicio los conocimientos matemáticos de Oliver Sacks. Primero critica que el neurólogo no haya anotado los números primos pronunciados puesto que esto impide verificar la veracidad de la historia. Tal vez los gemelos hayan seleccionado números primos característicos que ya se conocen (por ejemplo los números primos de Mersenne). O simplemente mentalmente realizaban chequeos para seleccionar números con alta probabilidad de ser primos.

Los famosos gemelos no están para validar su poder. Al momento de publicar su historia habían sido separados y cada uno vivía en lugares diferentes. Con la distancia su poder matemático había desaparecido. Eso nos hace suponer que por el momento RSA sigue siendo seguro.