Esquema de firma ElGamal

Esquema de firma digital

El esquema de firma ElGamal es un esquema de firma digital que se basa en la dificultad de calcular logaritmos discretos . Fue descrito por Taher Elgamal en 1985. ^[1]

El algoritmo de firma ElGamal rara vez se utiliza en la práctica. Una variante desarrollada en la NSA y conocida como algoritmo de firma digital es mucho más utilizada. Existen otras variantes. ^[2] El esquema de firma ElGamal no debe confundirse con el cifrado ElGamal , que también fue inventado por Taher Elgamal.

Descripción general

El esquema de firma ElGamal es un esquema de firma digital basado en las propiedades algebraicas de la exponenciación modular, junto con el problema del logaritmo discreto. El algoritmo utiliza un par de claves que consiste en una clave pública y una clave privada . La clave privada se utiliza para generar una firma digital para un mensaje, y dicha firma puede verificarse utilizando la clave pública correspondiente del firmante. La firma digital proporciona autenticación del mensaje (el receptor puede verificar el origen del mensaje), integridad (el receptor puede verificar que el mensaje no ha sido modificado desde que fue firmado) y no repudio (el remitente no puede afirmar falsamente que no ha firmado el mensaje).

Historia

El esquema de firma ElGamal fue descrito por Taher Elgamal en 1985. ^[1] Se basa en el problema de Diffie-Hellman .

Operación

El esquema implica cuatro operaciones: generación de claves (que crea el par de claves), distribución de claves, firma y verificación de la firma.

Generación de claves

La generación de claves consta de dos fases. La primera fase consiste en la elección de parámetros de algoritmo que pueden ser compartidos entre distintos usuarios del sistema, mientras que la segunda fase consiste en calcular un único par de claves para un usuario.

Generación de parámetros

• Elija una longitud de clave . ${\displaystyle N}$
• Elija un número primo de -bit ${\displaystyle N}$ ${\displaystyle p}$
• Elija una función hash criptográfica con una longitud de salida de bits. Si , solo se utilizan los bits más a la izquierda de la salida hash. ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle L>N}$ ${\displaystyle N}$
• Elija un generador del grupo multiplicativo de números enteros módulo p , . ${\displaystyle g<p}$ ${\displaystyle Z_{p}^{*}}$

Los parámetros del algoritmo son . Estos parámetros pueden ser compartidos entre los usuarios del sistema. ${\displaystyle (p,g)}$

Claves por usuario

Dado un conjunto de parámetros, la segunda fase calcula el par de claves para un solo usuario:

• Elija un número entero al azar entre . ${\displaystyle x}$ ${\displaystyle \{1\ldots p-2\}}$
• Calcular . ${\displaystyle y:=g^{x}{\bmod {p}}}$

${\displaystyle x}$es la clave privada y es la clave pública. ${\displaystyle y}$

Distribución de claves

El firmante debe enviar la clave pública al receptor a través de un mecanismo confiable, pero no necesariamente secreto. El firmante debe mantener en secreto la clave privada. ${\displaystyle y}$ ${\displaystyle x}$

Firma

El mensaje está firmado de la siguiente manera: ${\displaystyle m}$

• Elija un número entero al azar entre , que sea relativamente primo a . ${\displaystyle k}$ ${\displaystyle \{2\ldots p-2\}}$ ${\displaystyle k}$ ${\displaystyle p-1}$
• Calcular . ${\displaystyle r:=g^{k}{\bmod {p}}}$
• Calcular . ${\displaystyle s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)}$
• En el improbable caso de que comience de nuevo con un número aleatorio diferente . ${\displaystyle s=0}$ ${\displaystyle k}$

La firma es . ${\displaystyle (r,s)}$

Verificar una firma

Se puede verificar que una firma es una firma válida para un mensaje de la siguiente manera: ${\displaystyle (r,s)}$ ${\displaystyle m}$

• Verifique que y . ${\displaystyle 0<r<p}$ ${\displaystyle 0<s<p-1}$
• La firma es válida si y sólo si ${\displaystyle g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.}$

Exactitud

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

El cálculo durante la generación de la firma implica ${\displaystyle s}$

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

Dado que es relativamente primo a , ${\displaystyle g}$ ${\displaystyle p}$

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

Seguridad

Un tercero puede falsificar firmas ya sea encontrando la clave secreta x del firmante o encontrando colisiones en la función hash . Se cree que ambos problemas son difíciles. Sin embargo, a fecha de 2011 no se conoce ninguna reducción estricta a un supuesto de dureza computacional . ${\displaystyle H(m)\equiv H(M){\pmod {p-1}}}$

El firmante debe tener cuidado de elegir un k diferente de manera uniforme y aleatoria para cada firma y de asegurarse de que no se filtre k ni información parcial sobre k . De lo contrario, un atacante podría deducir la clave secreta x con menor dificultad, tal vez lo suficiente como para permitir un ataque práctico. En particular, si se envían dos mensajes utilizando el mismo valor de k y la misma clave, entonces un atacante puede calcular x directamente. ^[1]

Falsificación existencial

El artículo original ^[1] no incluía una función hash como parámetro del sistema. El mensaje m se utilizó directamente en el algoritmo en lugar de H(m) . Esto permite un ataque llamado falsificación existencial , como se describe en la sección IV del artículo. Pointcheval y Stern generalizaron ese caso y describieron dos niveles de falsificación: ^[3]

1. La falsificación de un parámetro. Seleccione un tal que . Establezca y . Entonces la tupla es una firma válida para el mensaje . ${\displaystyle e}$ ${\displaystyle 1<e<p-1}$ ${\displaystyle r:=g^{e}y{\bmod {p}}}$ ${\displaystyle s:=-r{\bmod {(p-1)}}}$ ${\displaystyle (r,s)}$ ${\displaystyle m=es{\bmod {(p-1)}}}$
2. La falsificación de dos parámetros. Seleccione , y . Establezca y . Entonces la tupla es una firma válida para el mensaje . La falsificación de un parámetro es un caso especial de la falsificación de dos parámetros, cuando . ${\displaystyle 1<e,v<p-1}$ ${\displaystyle \gcd(v,p-1)=1}$ ${\displaystyle r:=g^{e}y^{v}{\bmod {p}}}$ ${\displaystyle s:=-rv^{-1}{\bmod {(p-1)}}}$ ${\displaystyle (r,s)}$ ${\displaystyle m=es{\bmod {(p-1)}}}$ ${\displaystyle v=1}$

Véase también

• Aritmética modular
• Algoritmo de firma digital
• Algoritmo de firma digital de curva elíptica
• Cifrado ElGamal
• Firma de Schnorr
• Algoritmo de firma de Pointcheval-Stern

Referencias

1. Taher ElGamal (1985). "Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos" (PDF) . IEEE Transactions on Information Theory . 31 (4): 469–472. CiteSeerX  10.1.1.476.4791 . doi :10.1109/TIT.1985.1057074. S2CID  2973271.(La versión de la conferencia apareció en CRYPTO '84, págs. 10-18)
2. K. Nyberg, RA Rueppel (1996). "Recuperación de mensajes para esquemas de firma basados ​​en el problema del logaritmo discreto". Diseños, códigos y criptografía . 7 (1–2): 61–81. doi :10.1007/BF00125076. S2CID  123533321.
3. Pointcheval, David; Stern, Jacques (2000). "Argumentos de seguridad a favor de las firmas digitales y las firmas ciegas" (PDF) . J Cryptology . 13 (3): 361–396. CiteSeerX 10.1.1.208.8352 . doi :10.1007/s001450010003. S2CID  1912537. Archivado desde el original (PDF) el 2021-04-22 . Consultado el 2019-08-17 .