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.
© 2002 Antonio Villalón Huerta
