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 el logaritmo discreto no es soluble en un tiempo asumible en (grupo multiplicativo módulo un primo p). Esto último se traduce en que tenga un factor primo grande (lo que hace que el problema del logaritmo discreto sea difícil[2]​).

Además Alicia elige dos números aleatorios (el generador del grupo cíclico ( 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. Despejando a de la ecuación obtenemos la relación siguiente entre los componentes de la clave pública y la clave privada con lo que el criptosistema es seguro siempre que sea difícil hallar el logaritmo discreto.

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 m entre 1 y (). 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 aprovechamos que:

Por tanto para descifrar se tiene que realizar el siguiente cálculo:

donde representa el inverso de módulo lo que indica que para calcular el descifrado, es necesario conocer , que es la clave privada de Alicia.

Por el pequeño teorema de Fermat se demuestra que y lo podemos aplicar.

Demostración: El pequeño teorema de Fermat indica que con p primo y x>0 coprimo con p. Elevando a la expresión obtenemos que . Por tanto . Despejando

Ejemplos

Simple

Alicia elige los valores:

(primo aleatorio y suponemos que p-1=15 tiene un factor primo grande lo cual no es cierto)
(generador aleatorio)
(clave privada aleatoria)

Alicia calcula

(valor calculado)

Por tanto la clave pública será .

Bruce tiene el texto claro

(el cual está entre 1 y p-1)

Bruce escoge un aleatorio entre 2 y p-1 Bruce calcula

.

Por lo que el texto cifrado es

Para descifrar Alicia usa la clave privada y el Pequeño Teorema de Fermat:

.

Complejo

Veamos una aplicación más real del algoritmo:

Alicia elige los valores:

(primo aleatorio y para suponemos que 52673 es sufientemente grande)
(generador aleatorio)
(clave privada aleatoria)

Alicia calcula

(valor calculado)

Por tanto la clave pública será .

Bruce tiene el texto claro "HIJO"

(el cual está entre 1 y p-1)

Bruce escoge un aleatorio entre 2 y p-1

Bruce calcula

.

Por lo que el texto cifrado es que al decodificarlo queda:

=BAGVLB
=SCEAZ

Con lo que el mensaje a enviar es (BAGVLB, SCEAZ)

Para descifrar Alicia usa la clave privada :

ya que por el pequeño teorema de fermat tenemos
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
українська: Схема Ель-Гамаля