El sistema criptográfico de clave pública RSA (iniciales de sus creadores: Ron Rivest, Adi Shamir y Leonard Adleman, del Instituto Tecnológico de Massachusetts (MIT)) que fue desarrollado en 1979, fundamenta su algoritmo en la factorización de números enteros. Es el algoritmo de este tipo válido tanto para cifrar como para firmar digitalmente.

Los mensajes de texto enviados son representados mediante números enteros asociados al orden el abecedario, y el funcionamiento se basa en el producto, de dos números primos grandes elegidos aleatoriamente y que deben mantenerse en privado. Actualmente estos primos son del orden de 10³⁰⁰, mismos que crecerán conforme al aumento de la capacidad de cálculo de las computadoras.

Siendo un algoritmo de encriptación asimétrica, cada usuario posee dos claves de cifrado: una pública y otra privada. Cuando se quiere enviar un mensaje confidencial, el emisor busca la clave pública del receptor, cifra su mensaje con esa clave, y una vez que el mensaje cifrado llega al receptor, este se ocupa de descifrarlo usando su clave privada.

Para el procedimiento de firma digital (propiedades de autenticidad, integridad y no repudio), el emisor obtiene un hash del mensaje a firmar y lo procesa con su clave privada obteniendo así la firma; se envía el mensaje y la firma; el receptor recalcula el hash y descifra el hash original con la clave pública del emisor, validando positiva o negativamente la firma del mensaje.

El futuro y seguridad de RSA depende de cuánto tiempo transcurrirá sin que se tengan formas rápidas de descomponer un número grande en producto de primos.

Algoritmo

El algoritmo RSA consta de tres pasos: generación de llaves, cifrado y descifrado.

El procedimiento general de generación de claves, cifrado y descifrado utilizando este algoritmo se detalla a continuación con los cálculos y un ejemplo de su funcionamiento.

Utilizando el algoritmo RSA, supóngase que una persona X (emisor del mensaje) envía un mensaje en texto plano (M), en forma de un número m que es menor que n. El mensaje cifrado (c) se calcula por medio de la siguiente operación:

Donde e es la llave pública del receptor.

La forma en la que el receptor descifra el mensaje de X es por medio de la función:

Donde d es la llave privada del emisor.

Basados en aritmética modular con exponente y módulo fijos, el sistema RSA funciona de la siguiente forma:

Inicio

1.  Se eligen los números primos p y q aleatoriamente.

2.  Calcular n = p ∙ q

3.  Calcular 𝜑 = (p - 1)∙(q - 1)

4.  Buscar un entero e t.q. 1 < e < 𝜑(n) y el MCD(e, 𝜑(n)) = 1; i.e., e y 𝜑(n) son coprimos

5.  Calcular d siendo d ≡ e−1 (mod 𝜑(n))

6.  Para encriptar, c = m^e(mod n), con m = mensaje original en números enteros.

7.  Para desencriptar, m = c^d(mod n).

Fin

El resultado de este algoritmo es una llave pública (n, e), donde n es el módulo y e el exponente de cifrado; y una llave privada (n, d), donde n es el módulo y d el exponente de descifrado.

Algoritmo en C++