RSA Encriptación

Es un criptosistema de clave pública que sirve tanto para encriptar mensajes como para autenticación de documentos o transacciones (firma digital).
Fue inventado en 1977 por Rivest Ron, Shamir Adi y Adleman Leonard.
El algoritmo de encriptación RSA es el más utilizado y seguramente el más sencillo tanto como su comprensión, como por su implementación.
La seguridad de este algoritmo se basa en la factorización de números primos. El algoritmo RSA sera seguro  mientras no se conozca una manera de descomponer un número grande en productos primos.

Algoritmo

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

Generación de claves

1. Se obtiene 2 números primos p = 17 y q = 43.
2. Se calcula n = p * q = 731.
3. Se calcula φn = (p - 1)*(q - 1) = 672.
4. Se busca un número e tal que sea primo con φn, mcd(e, φn) = 1.
5. Como e y φn son primos entre si, entonces existe un d tal que d = e^(-1) mod  φn, e = 101, d = 173. Esto se suele calcular con el Algoritmo Extendido de Euclides.

Finalmente obtenemos la clave pública Ce = (e, n) = (101, 731), y la clave privada Cd = (d, n) = (173, 131).