Esquema de la firma de ElGamal

El esquema de la firma de ElGamal es un esquema de la firma digital que está basado en la dificultad de calcular logaritmos distintos. Fue descrito por Taher ElGamal en 1984.

El algoritmo de la firma de ElGamal descrito en este artículo raramente se usa en la práctica. Una variante desarrollada en la NSA y conocida como el Algoritmo de la Firma Digital es mucho más ampliamente usada. Hay varias otras variantes. El esquema de la firma de ElGamal no se debe confundir con la codificación de ElGamal que también fue inventada por Taher ElGamal.

El esquema de la firma ElGamal permite que un tercero confirme la autenticidad de un mensaje enviado sobre un canal inseguro.

Parámetros del sistema

Estos parámetros del sistema se pueden compartir entre usuarios.

Generación clave

Estos pasos son realizados una vez por el firmante.

Generación de la firma

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

Entonces el par (r, s) es la firma digital del m.

El firmante repite estos pasos para cada firma.

Verificación

Una firma (r, s) de un mensaje el m se verifica así.

El verificador acepta una firma si todas las condiciones se satisfacen y lo rechaza por otra parte.

Exactitud

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

La generación de la firma implica

:

De ahí el pequeño teorema de Fermat implica

:

Los \begin {alinean }\

g^ {H (m)} & G^ {xr} \equiv G^ {ks} \\

& \equiv (G^ {x}) ^r (G^ {k}) ^s \\

& \equiv (y) ^r (r) ^s \pmod p. \\

Los \end {alinean }\

</matemáticas>

Seguridad

Un tercero puede forjar firmas encontrando la llave secreta del firmante x o encontrando colisiones en la función del picadillo. Se cree que ambos problemas son difíciles. Sin embargo, desde 2011 ninguna reducción apretada a una asunción de la dureza computacional se conoce.

El firmante debe procurar elegir k diferente uniformemente al azar para cada firma y estar seguro que k, o hasta información parcial sobre k, no se escapa. Por otra parte, un atacante puede ser capaz de deducir la llave secreta x con la dificultad reducida, quizás bastante permitir un ataque práctico. En particular, si dos mensajes se envían usando el mismo valor de k y la misma llave, entonces un atacante puede calcular x directamente.

Véase también



Buscar