Esquema de firma ElGamal

El Esquema de firma ElGamal es un esquema de firma digital basado en la complejidad del cálculo del logaritmo discreto. Fue descrito por Taher ElGamal en 1984. El algoritmo de firma ElGamal descrito en su artículo es raramente utilizado en la práctica. Con más frecuencia se utiliza una de sus variantes llamada Algoritmo de firma digital (DSA). El esquema de firma ElGamal no debe confundirse con el cifrado ElGamal también propuesto por Taher ElGamal.

El esquema de firma ElGamal permite que un verificador pueda confirmar la autenticidad de un mensaje m enviado por un emisor sobre un canal de comunicación inseguro.

Los parámetros utilizados por el esquema ElGamal son:

• Una función de hash H resistente a colisiones.
• Un número primo p muy grande tal que el cómputo de logaritmos discretos módulo p sea difícil.
• un generador pseudoaleatorio g para el grupo multiplicativo ${\displaystyle Z_{p}^{*}}$.

Los parámetros utilizados pueden ser compartidos entre usuarios.

• Se selecciona una clave secreta x de forma aleatoria tal que ${\displaystyle 1<x<p-1}$.
• Se calcula ${\displaystyle y=g^{x}{\pmod {p}}}$.
• La clave pública será (p,g,y).
• La clave secreta será x.

Estos pasos son realizados una sola vez por el firmante.

Para firmar un mensaje m el firmante realiza los pasos siguientes.

• Selecciona un número aleatorio k tal que ${\displaystyle 0<k<p-1}$ y ${\displaystyle mcd(k,p-1)=1}$.
• Calcula ${\displaystyle r\,\equiv \,g^{k}{\pmod {p}}}$.
• Calcula ${\displaystyle s\,\equiv \,(H(m)-xr)k^{-1}{\pmod {p-1}}}$.
• Si ${\displaystyle s=0}$ reinicia el proceso.

El par (r,s) así obtenido es la firma digital de m. El firmante repite estos pasos para cada mensaje m que desea firmar.

La firma (r,s) de un mensaje m proveniente de un firmante con clave pública (p,g,y) y que utilizó una función de Hash H se verifica de la siguiente forma:

• Se verifica que ${\displaystyle 0<r<p}$ y que ${\displaystyle 0<s<p-1}$.
• Se verifica que ${\displaystyle g^{H(m)}\,\equiv \,y^{r}r^{s}{\pmod {p}}.}$.

El verificante acepta el mensaje únicamente si estas tres condiciones se cumplen.

El algoritmo es correcto en el sentido que una firma generada con este algoritmo de firma siempre será aceptada por un verificador.

La generación de firmas incluye

${\displaystyle H(m)\,\equiv \,xr+sk{\pmod {p-1}}.}$

Del pequeño teorema de Fermat se tiene

${\displaystyle {\begin{matrix}g^{H(m)}&\equiv &g^{xr}g^{ks}\\&\equiv &(g^{x})^{r}(g^{k})^{s}\\&\equiv &(y)^{r}(r)^{s}{\pmod {p}}.\\\end{matrix}}}$

Un tercero puede falsificar firmas si encuentra la clave secreta x del firmante o si encuentra colisiones en la función de Hash ${\displaystyle H(m)\equiv H(M){\pmod {p-1}}}$. Se considera que ambos problemas son suficientemente difíciles.

El firmante debe tener cuidado y escoger una k diferente de forma uniformemente aleatoria para cada firma. Así asegura que k o aún información parcial sobre k no es deducible. Malas selecciones de k pueden representar fugas de información que facilitan el que un atacante deduzca la clave secreta x. En particular, si dos mensajes son enviados con el mismo valor de k entonces es factible deducir el valor de la clave secreta x.

• Taher Elgamal. A public key cryptosystem and a signature scheme based on discrete logarithms. Lecture Notes in Comput. Sci., 196, Springer, Berlín, pages 10-18, 1985.

• Algoritmo de firma digital
• Cifrado ElGamal