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 el algoritmo de firma digital se utiliza mucho más ampliamente. Hay varias otras variantes. [2] El esquema de firma de ElGamal no debe confundirse con el cifrado de 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 consta de una clave pública y una clave privada . La clave privada se utiliza para generar una firma digital para un mensaje, y dicha firma se puede verificar 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 lo ha hecho). firmó el mensaje).
Historia
El esquema de firmas de ElGamal fue descrito por Tahir Elgamal en 1985. [1]
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 firmas.
Generación de claves
La generación de claves tiene dos fases. La primera fase es una elección de parámetros de algoritmo que pueden compartirse entre diferentes usuarios del sistema, mientras que la segunda fase calcula un solo par de claves para un usuario.
Generación de parámetros
- Elija una longitud de clave .
- Escoge un -bit número primo
- Elija una función hash criptográfica con longitud de salida bits. Si, solo el más a la izquierda se utilizan bits de la salida hash.
- Elige un generador del grupo multiplicativo de enteros módulo p ,.
Los parámetros del algoritmo son . Estos parámetros pueden compartirse entre los usuarios del sistema.
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 de .
- Calcular .
es la clave privada y es la clave pública.
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 conservar la clave privada. secreto.
Firma
Un mensaje está firmado de la siguiente manera:
- Elija un número entero al azar de con relativamente primo para .
- Calcular .
- Calcular .
- En el improbable caso de que empezar de nuevo con un azar diferente .
La firma es .
Verificando una firma
Se puede verificar que una firma es una firma válida para un mensaje como sigue:
- Verificalo y .
- La firma es válida si y solo si
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 de durante la generación de firmas implica
Desde es relativamente primordial para ,
Seguridad
Un tercero puede falsificar firmas 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 partir de 2011 no se conoce una reducción estricta a un supuesto de dureza computacional .
El firmante debe tener cuidado de elegir una k diferente uniformemente al azar para cada firma y estar seguro de que k , o incluso información parcial sobre k , no se filtre. De lo contrario, un atacante puede deducir la clave secreta x con dificultad reducida, tal vez lo suficiente 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 falsificaciones: [3]
- La falsificación de un parámetro. Seleccione un tal que . Colocar y . Entonces la tupla es una firma válida para el mensaje .
- La falsificación de dos parámetros. Seleccione, y . Colocar 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.
Ver también
Referencias
- ↑ a b c d Taher ElGamal (1985). "Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos" (PDF) . Transacciones IEEE sobre teoría de la información . 31 (4): 469–472. CiteSeerX 10.1.1.476.4791 . doi : 10.1109 / TIT.1985.1057074 .(la versión de la conferencia apareció en CRYPTO '84, págs. 10–18)
- ^ K. Nyberg, RA Rueppel (1996). "Recuperación de mensajes para esquemas de firmas 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 .
- ^ Pointcheval, David; Stern, Jacques (2000). "Argumentos de seguridad para firmas digitales y firmas ciegas" (PDF) . J Criptología . 13 (3): 361–396. CiteSeerX 10.1.1.208.8352 . doi : 10.1007 / s001450010003 . S2CID 1912537 .