Cifrado ElGamal

El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en el problema matemático del logaritmo discreto. Es un algoritmo de criptografía asimétrica basado en la idea de Diffie-Hellman y que funciona de una forma parecida a este algoritmo discreto.

El algoritmo de ElGamal puede ser utilizado tanto para generar firmas digitales como para cifrar o descifrar.

Fue descrito por Taher Elgamal en 1984[1] y se usa en software GNU Privacy Guard, versiones recientes de PGP, y otros sistemas criptográficos. Este algoritmo no está bajo ninguna patente lo que lo hace de uso libre.

La seguridad del algoritmo se basa en la suposición que la función utilizada es de un sólo sentido debido a la dificultad de calcular un logaritmo discreto.

El procedimiento de cifrado (y descifrado) está basado en cálculos sobre un grupo cíclico cualquiera lo que lleva a que la seguridad del mismo dependa de la dificultad de calcular logaritmos discretos en .

El algoritmo original

Mostremos el criptosistema propuesto inicialmente por Tahar ElGamal en su artículo.

Generación de la clave

Para generar la clave, Alicia escoge un número primo cualquiera tal que tenga un factor primo grande (esto se pide para que el problema del logaritmo discreto sea difícil[2] ). Además elige dos números aleatorios (el generador) y (que actuará como clave privada) tal que .

Alicia calcula el valor de . La clave pública será , mientras que el valor de lo mantendrá en secreto.

Cifrado

Supongamos que Bruce tiene un texto claro que quiere enviar cifrado a Alicia. Lo primero por hacer es convertir este texto en un entero entre 1 y , obteniendo un (esto no es parte del cifrado, sino que es una manera de codificar estándar, conocida por todos). Luego Bruce escoge arbitrariamente un número (que mantendrá secreto) para finalmente calcular:

El mensaje cifrado final corresponde a la tupla

Descifrado

Para descifrar se tiene que realizar el siguiente cálculo:

donde representa el inverso de módulo (que, utilizando el Pequeño teorema de Fermat puede calcularse como ).

Veamos por qué esto da como resultado :

Vale observar que para calcular el descifrado, es necesario conocer , que es justamente la clave privada de Alicia.

Ejemplo numérico

Alicia elige los valores:

(primo elegido al azar)
(generador)
(llave privada elegida al azar)
(llave pública)

La llave pública será y la privada .

Bruce tiene el texto claro . Escoge un aleatorio:

.

El texto cifrado está compuesto por la tupla .

El texto cifrado puede ser descifrado por Alicia utilizando la llave privada .

Utilizando el Pequeño Teorema de Fermat:

.
Other Languages
العربية: تشفير الجمل
azərbaycanca: El-Qamal sxemi
čeština: ElGamal
suomi: ElGamal
italiano: ElGamal
日本語: ElGamal暗号
polski: ElGamal
português: El Gamal
Türkçe: ElGamal
українська: Схема Ель-Гамаля