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.
© 2002 Antonio Villalón Huerta
