El criptosistema de ElGamal

Durante 1984 y 1985 ElGamal desarrolló un nuevo criptosistema de clave pública basado en la intratabilidad computacional del problema del logaritmo discreto: obtener el valor de a partir de la expresión

es, como hemos comentado para RSA, computacionalemente intratable por norma general.

Aunque generalmente no se utiliza de forma directa, ya que la velocidad de cifrado y autenticación es inferior a la obtenida con RSA, y además las firmas producidas son más largas (<el doble de largo que el texto original!), el algoritmo de ElGamal es de gran importancia en el desarrollo del DSS (Digital Signature Standard), del NIST (National Institute of Standards and Technology) estadounidense.

En este sistema, para generar un par clave pública/privada, se escoge un número primo grande, , y dos enteros y , , , y se calcula

La clave pública será el número , y la privada el número .

Para firmar un determinado mensaje, el emisor elige un entero aleatorio , , no usado con anterioridad y con la restricción que sea relativamente primo a , y computa

,

donde es el inverso de ; así,

.

La firma del mensaje estará entonces formada por y ; un potencial receptor puede usar la clave pública y para calcular y comprobar si coincide con :

El criptosistema de ElGamal tiene una característica determinante que lo distingue del resto de sistemas de clave pública: en el cifrado se utiliza aparte de la clave pública del receptor, la clave privada del emisor.