El Algortimo de Elgamal

En 1984 Taher ElGamal propuso un esquema de clave pública basado en la exponenciación discreta sobre el grupo multiplicativo de un cuerpo finito Zp . No obstante, aquí presentaremos un protocolo más general al propuesto por ElGamal sobre un cuerpo finito G. 

Suponemos, en primer lugar que los mensajes son elementos de G y que el usuario A desea enviar un mensaje m al usuario B. El protocolo a seguir es el siguiente: 

1. Se selecciona un grupo finito G y un elemento α de G. 
2. Cada usuario A elige un núemro aleatorio a, que será su clave privada, y calcula α a en G, que será su clave pública. 

Para que un usuario A envíe un mensaje m, a otro usuario B, suponiendo que los mensajes son elementos de G, realiza las siguientes operaciones: 

1. A genera un número aleatorio v y calcula α v en G. 
2. A mira la clave pública de B, α b , y calcula (α b ) v y m * α bv en G. 
3. A envía la pareja (α v , m*α bv ) a B. 

Para recuperar el mensaje original: 

1. B calcula (α v ) b en G. 
2. B obtiene m solo con calcular m*α vb / α vb 

Por seguridad y eficacia, el grupo G y el elemento α deberían elegirse de modo que verificaran las siguientes condiciones: 

• Por eficacia, la operación en G debería ser “fácil” de aplicar. 
• Por seguridad, el problema del logaritmo discreto en el subgrupo cíclico de G generado por α, <α>, debería ser “difícil”. 

Para simplificar el protocolo anterior, podemos suponer, tal y como fue descrito por ElGamal, que el grupo sobre el que se llevan a cabo las operaciones mencionadas en el protocolo anterior es el grupo multiplicativo del cuerpo Zp ; de esta forma, las potencias y productos anteriores se efectúan módulo un número primo p. 

Ataque al Criptosistema de ElGamal

 Un escucha, S, que quisiera romper el protocolo anterior, conocería G, n, α a , α b , α v y m*α vb y debería calcular m. Este problema se conoce como el problema de ElGamal(ElGamal Problem, EGP). Es fácil ver que la seguridad de este criptosistema es equivalente a del cambio de clave de Diffie-Hellman; por tanto, la seguridad del criptosistema de ElGamal está basada en la dificultad del logaritmo discreto. Baste decir que el ataque contra este sistema, hoy por hoy, se considera intratable, dado que los mejores tiempos de computación para calcular algoritmos discretos son de tipo subexponencial.