El criptosistema RSA

Este sistema de clave pública fué diseñado en 1977 por los profesores del MIT (Massachusetts Institute of Technology) Ronald R. Rivest, Adi Shamir y Leonard M. Adleman, de ahí las siglas con las que es conocido. Desde entonces, este algoritmo de cifrado se ha convertido en el prototipo de los de clave pública.

La seguridad de RSA radica en la dificultad de la factorización de números grandes: es fácil saber si un número es primo, pero es extremadamente difícil obtener la factorización en números primos de un entero elevado, debido no a la dificultad de los algoritmos existentes, sino al consumo de recursos físicos (memoria, necesidades hardware...incluso tiempo de ejecución) de tales algoritmos. Se ha demostrado que si n es el número de dígitos binarios de la entrada de cualquier algoritmo de factorización, el coste del algoritmo es , con un tiempo de ejecución perteneciente a la categoría de los llamados problemas intratables.

Veamos el funcionamiento del algoritmo RSA: si un usuario A desea enviar información cifrada, en primer lugar tiene que calcular un par de claves (pública y privada), para lo que ha de elegir aleatoriamente dos números primos grandes (del orden de cien dígitos), y , números que se han de mantener en secreto; si llamamos ( se conoce como módulo) al producto , el usuario ha de determinar otro entero, , llamado exponente privado, que cumpla

es decir, y el producto , que llamaremos función de Euler y denotaremos , han de ser primos. Con estos datos, ya tenemos la clave privada del cifrado: el par ; para obtener la clave pública, hallamos el inverso multiplicativo del número respecto de , de la forma . Calculado este entero , llamado exponente público, la clave pública será el par .

Una vez el emisor A dispone de sus claves pública y privada, podría enviar un mensaje cifrado, que llamaremos , a un posible receptor, mediante la operación

aplicada a cada elemento del mensaje.

Cuando el receptor del criptograma desee descifrar el mensaje recibido, ha de realizar la operación

para obtener el texto en claro del mensaje que acaba de recibir.

El sistema RSA ha permanecido invulnerable hasta hoy, a pesar de los numerosos ataques de criptoanalistas; teóricamente es posible despejar para obtener la clave privada, a partir de la función de descifrado, resultando

Sin embargo, el cálculo de logaritmos discretos es un problema de una complejidad desbordante, por lo que este tipo de ataque se vuelve impracticable: la resolución de congruencias del tipo , necesarias para descifrar el mensaje, es algorítmicamente inviable sin ninguna información adicional, debido al elevado tiempo de ejecución del algoritmo. Aunque cuando los factores de son pequeños existe un algoritmo, desarrollado por Pohlig y Hellman de orden , éste es otro de los algoritmos catalogados como intratables, vistos anteriormente.