Criptografía: Cifrado de clave pública II

Cifrado RSA

El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Len Adleman (la sigla RSA es Rivest Shamir Adleman) en el MIT.

El cifrado RSA es un algoritmo de cifrado de clave pública (o asimétrico) por bloques, que como todos los cifrados de clave pública tiene dos claves: una pública, que se distribuye a los usuarios que quiera el propietario de ella, y otra privada, la cual es guardada en secreto por su propietario. Así cuando se envía un mensaje, el emisor usa la clave pública de cifrado del receptor para cifrar el mensaje y una vez que dicho mensaje llega al receptor, éste se ocupa de descifrarlo usando su clave oculta.

El algoritmo sigue los siguientes pasos:

1. Se construye un número «N», que resulta del producto de dos primos «p» y «q» (normalmente son números muy grandes). Teniendo N = p · q y Φ(N) = (p-1) · (q-1)
2. Se selecciona un número «e»,1 < e < Φ(N), tal que MCD (e, Φ(N)) = 1 («e» y Φ(N) son primos relativos).
3. Se calcula el inverso de «e», denotado por «d», tal que e · d = 1 (mod Φ(N))
4. Con esto se consiguen las claves (e, d), siendo la clave pública (e, N) y la clave privada (d, N).

Una vez tenemos las claves podemos pasar a cifrar/descfirar los mensajes:

• Cifrado: C = M^e (mod N) con MCD (M, N) = 1 y M < N
• Descifrado: M = C^d (mod N)

La seguridad de este algoritmo radica en que no hay maneras rápidas conocidas de factorizar un número grande en sus factores primos utilizando computadoras tradicionales.

(Más información en Wikipedia)

Cifrado Elgamal

Este algoritmo está basado en el algoritmo de Diffie-Hellman para el intercambio de claves, fue descrito en 1984 por Taher Elgamal. Actualmente se usa en el software libre GNU Privacy Guard (GPG), versiones de PGP y otros sistemas.

El algoritmo sigue los siguientes pasos:

1. El receptor selecciona un primo grande «p» y un generador g ∈ Z^*_p.
2. El receptor selecciona aleatoriamente un valor «x_r» tal que 0 < x_r < p-1. Siendo «x_r» la clave privada.
3. La clave pública es igual a y_r = g^x_r (mod p).
4. Ahora el emisor toma un «K» aleatorio tal que MCD (K, p-1) = 1, es decir, «K» sea primo relativo con p-1 y calcula r = g^K (mod p) y s = M · y^K_r (mod p).
5. El emisor manda el mensaje cifrado como C = (r, s), siendo «r» la clave pública del emisor y «s» el mensaje cifrado.
6. Ahora el mensaje cifrado se descifra calculando M = s/r^x_r.

La seguridad del algoritmo depende en la dificultad de calcular logaritmos discretos.

(Más información en Wikipedia Inglés)

Post anterior: Cifrado de clave pública I