Criptografía (CCLXXXIV): el algoritmo ElGamal

El algoritmo ElGamal, un algoritmo de cifrado asimétrico que debe su nombre al criptógrafo egipcio Taher Elgamal que lo describió en 1984, se basa en el mismo principio que en el que se fundamenta el intercambio de clave de Diffie-Hellman (ver este post donde explico este protocolo criptográfico).

Como en todo criptosistema de clave pública un usuario dispone de dos claves: una pública, que debe estar en posesión de cualquier persona que pretenda enviarle un mensaje cifrado, y otra privada, que el usuario utilizará para descifrar los mensajes que le envíen y que sólo él posee. Es decir, el emisor cifrará el mensaje con la clave pública del receptor y sólo éste podrá descifrarlo utilizando su clave privada.

Pues bien, estableciendo una analogía entre este algoritmo de cifrado y el citado protocolo de intercambio de clave con dos intervinientes en la comunicación, que comparten una clave de sesión ('k'), el secreto compartido, que viene dada por: k = g^ab mod p, siendo 'a' y 'b' sendos números secretos; cada interviniente ha escogido uno de ellos y lo mantiene en secreto, podemos decir que g^a mod p sería la clave pública del primer interviniente y g^b mod p la clave publica del segundo, mientras que 'a' sería la clave privada del primer interviniente y 'b' la clave privada del segundo.

Además de este algoritmo de cifrado, Taher Elgamal propone otro algoritmo para firmar digitalmente, que será objeto de un próximo post.

Continuando con el algoritmo de cifrado, al igual que en RSA, lo que se cifra son números y su seguridad, al igual que en el intercambio de clave de Diffie-Hellman, se basa en que un atacante, conociendo la clave pública de un usuario, para hacerse con la clave privada se enfrentaría al problema del logaritmo discreto (PLD), de muy difícil solución en un tiempo razonable para números primos muy grandes, es decir, al igual que en el caso de RSA se utiliza una función de un solo sentido; muy fácil de resolver en un sentido pero cuya resolución en sentido contrario se vuelve inabordable para números lo suficientemente grandes, por mucha potencia de cálculo de la que se disponga con los ordenadores actuales.

Dicho lo anterior, la generación del par de claves de un usuario se realiza de la siguiente manera:

1.- Se elige un número primo 'p' muy grande y un generador 'g' o raíz primitiva módulo 'p'. Al igual que en el intercambio de clave de Diffie-Hellman y por el mismo motivo, se puede obviar que 'g' sea un generador 'g' o raíz primitiva módulo 'p', aunque es recomendable que lo sea.

2.- Se escoge aleatoriamente un número 'a' mayor que cero y menor que 'p'.

3.- Se calcula k = g^a mod p.

4.- La clave pública será (p, g, k).

5.- La clave privada será (a).

Veamos un ejemplo de cifrado y descifrado:

Supongamos que el usuario A tiene p = 997, g = 7 y a = 851, entonces: k = 7⁸⁵¹ mod 997 = 184 y, por tanto, tiene como clave pública (997, 7, 184)

a) Cifrado:

Supongamos ahora que el usuario B quiere enviar a A un número secreto ('m'), 783. Actuaría de la siguiente manera:

- Escoge un número entero aleatorio 'b' mayor que 0 y menor que 'p', 328.

- Con la clave pública de A y el número escogido en el paso anterior, B calcula y envía a A el siguiente par de valores: (g^b mod p, m * k^b mod p), que serán el mensaje cifrado o criptograma ('c'). Es decir:

 c = (7³²⁸ mod 997, 783 * 184³²⁸ mod 997) = (645, 63)

b) Descifrado:

A con su clave privada, calcula:

m = 645^p-1-a * 63 mod p = 645^997-1-851 * 63 mod 997 = 645¹⁴⁵ * 63 mod 997 = 783.

Quizás también te interese: