Cifrado ElGamal

"ElGamal" vuelve a dirigir aquí. Para el algoritmo de firma, consulte el esquema de firma de ElGamal .

En criptografía , el sistema de cifrado ElGamal es un algoritmo de cifrado de clave asimétrica para criptografía de clave pública que se basa en el intercambio de claves Diffie-Hellman . Fue descrito por Taher Elgamal en 1985. ^{[1] El} cifrado ElGamal se utiliza en el software gratuito GNU Privacy Guard , versiones recientes de PGP y otros criptosistemas . El algoritmo de firma digital (DSA) es una variante del esquema de firma de ElGamal , que no debe confundirse con el cifrado de ElGamal.

El cifrado ElGamal se puede definir sobre cualquier grupo cíclico , como un grupo multiplicativo de números enteros módulo  n . Su seguridad depende de la dificultad de cierto problema relacionado con el cálculo de logaritmos discretos .${\displaystyle G}$${\displaystyle G}$

El algoritmo

El cifrado de ElGamal consta de tres componentes: el generador de claves, el algoritmo de cifrado y el algoritmo de descifrado.

Generación de claves

La primera parte, Alice, genera un par de claves de la siguiente manera:

• Genere una descripción eficiente de un grupo cíclico de orden con generador . Dejemos que represente el elemento unitario de .${\displaystyle G\,}$${\displaystyle q\,}$ ${\displaystyle g}$${\displaystyle e}$${\displaystyle G}$
• Elija un número entero al azar .${\displaystyle x}$${\displaystyle \{1,\ldots ,q-1\}}$
• Calcular .${\displaystyle h:=g^{x}}$
• La clave pública consta de los valores . Alice publica esta clave pública y la conserva como clave privada , que debe mantenerse en secreto.${\displaystyle (G,q,g,h)}$${\displaystyle x}$

Cifrado

Una segunda parte, Bob, cifra un mensaje para Alice con su clave pública de la siguiente manera:${\displaystyle M}$${\displaystyle (G,q,g,h)}$

• Asigne el mensaje a un elemento del uso de una función de mapeo reversible.${\displaystyle M}$${\displaystyle m}$${\displaystyle G}$
• Elija un número entero al azar .${\displaystyle y}$${\displaystyle \{1,\ldots ,q-1\}}$
• Calcular . A esto se le llama secreto compartido .${\displaystyle s:=h^{y}}$
• Calcular .${\displaystyle c_{1}:=g^{y}}$
• Calcular .${\displaystyle c_{2}:=m\cdot s}$
• Bob envía el texto cifrado a Alice.${\displaystyle (c_{1},c_{2})}$

Tenga en cuenta que si uno conoce tanto el texto cifrado como el texto sin formato, puede encontrar fácilmente el secreto compartido , ya que . Por lo tanto, se genera una nueva y, por tanto, una nueva para cada mensaje para mejorar la seguridad. Por este motivo, también se denomina clave efímera .${\displaystyle (c_{1},c_{2})}$${\displaystyle m}$${\displaystyle s}$${\displaystyle c_{2}\cdot m^{-1}=s}$${\displaystyle y}$${\displaystyle s}$${\displaystyle y}$

Descifrado

Alice descifra un texto cifrado con su clave privada de la siguiente manera:${\displaystyle (c_{1},c_{2})}$${\displaystyle x}$

• Calcular . Dado que , y por lo tanto, es el mismo secreto compartido que utilizó Bob en el cifrado.${\displaystyle s:=c_{1}^{x}}$${\displaystyle c_{1}=g^{y}}$${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$
• Calcule , la inversa de en el grupo . Esto se puede calcular de varias formas. Si es un subgrupo de un grupo multiplicativo de números enteros módulo  n , el inverso multiplicativo modular se puede calcular usando el Algoritmo Euclidiano Extendido . Una alternativa es calcular como . Esta es la inversa de debido al teorema de Lagrange , ya que .${\displaystyle s^{-1}}$${\displaystyle s}$${\displaystyle G}$${\displaystyle G}$${\displaystyle s^{-1}}$${\displaystyle c_{1}^{q-x}}$${\displaystyle s}$${\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e}$
• Calcular . Este cálculo produce el mensaje original , porque ; por lo tanto .${\displaystyle m:=c_{2}\cdot s^{-1}}$${\displaystyle m}$${\displaystyle c_{2}=m\cdot s}$${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$
• Mapa de vuelta al mensaje de texto plano .${\displaystyle m}$${\displaystyle M}$

Uso práctico

Como la mayoría de los sistemas de clave pública, el criptosistema ElGamal se usa generalmente como parte de un criptosistema híbrido donde el mensaje en sí se encripta usando un criptosistema simétrico y luego ElGamal se usa para encriptar solo la clave simétrica. Esto se debe a que los criptosistemas asimétricos como ElGamal suelen ser más lentos que los simétricos para el mismo nivel de seguridad , por lo que es más rápido cifrar el mensaje, que puede ser arbitrariamente grande, con un cifrado simétrico, y luego usar ElGamal solo para cifrar la clave simétrica. , que suele ser bastante pequeño en comparación con el tamaño del mensaje.

Seguridad

La seguridad del esquema de ElGamal depende de las propiedades del grupo subyacente , así como de cualquier esquema de relleno utilizado en los mensajes.${\displaystyle G}$

Si la suposición computacional de Diffie-Hellman (CDH) se cumple en el grupo cíclico subyacente , entonces la función de cifrado es unidireccional . ^[2]${\displaystyle G}$

Si la suposición decisional de Diffie-Hellman (DDH) se mantiene , entonces ElGamal logra la seguridad semántica ; ^{[3] [2]} La seguridad semántica no está implícita únicamente en la suposición computacional de Diffie-Hellman. ^[4] Véase la suposición decisional de Diffie-Hellman para una discusión de los grupos en los que se cree que la suposición es válida.${\displaystyle G}$

El cifrado de ElGamal es incondicionalmente maleable y, por lo tanto, no es seguro bajo el ataque de texto cifrado elegido . Por ejemplo, dado el cifrado de algún mensaje (posiblemente desconocido) , se puede construir fácilmente un cifrado válido del mensaje .${\displaystyle (c_{1},c_{2})}$${\displaystyle m}$${\displaystyle (c_{1},2c_{2})}$${\displaystyle 2m}$

Para lograr la seguridad del texto cifrado elegido, el esquema debe modificarse más o debe usarse un esquema de relleno apropiado. Dependiendo de la modificación, la suposición de DDH puede ser necesaria o no.

También se han propuesto otros esquemas relacionados con ElGamal que logran seguridad contra ataques de texto cifrado seleccionados. El criptosistema Cramer-Shoup es seguro bajo el ataque de texto cifrado elegido asumiendo que DDH se mantiene . Su prueba no utiliza el modelo de oráculo aleatorio . Otro esquema propuesto es DHAES , ^[4] cuya prueba requiere una suposición que es más débil que la suposición de DDH.${\displaystyle G}$

Eficiencia

El cifrado de ElGamal es probabilístico , lo que significa que un solo texto sin formato se puede cifrar en muchos textos cifrados posibles, con la consecuencia de que un cifrado de ElGamal general produce una expansión de tamaño 1: 2 de texto sin formato a texto cifrado.

El cifrado bajo ElGamal requiere dos exponenciaciones ; sin embargo, estas exponenciaciones son independientes del mensaje y se pueden calcular con anticipación si es necesario. El descifrado requiere una potenciación y un cálculo de la inversa de un grupo que, sin embargo, se puede combinar fácilmente en una sola potenciación.

Ver también

• Taher Elgamal , diseñador de este y otros criptosistemas
• Esquema de la firma ElGamal
• Cifrado homomórfico

Lectura adicional

• AJ Menezes; PC van Oorschot; SA Vanstone. "Capítulo 8.4 Cifrado de clave pública de ElGamal" (PDF) . Manual de criptografía aplicada . Prensa CRC.
• Dan Boneh (1998). El problema de decisión Diffie-Hellman . Apuntes de conferencias en Ciencias de la Computación . 1423 . págs. 48–63. CiteSeerX  10.1.1.461.9971 . doi : 10.1007 / BFb0054851 . ISBN 978-3-540-64657-0.

Referencias

1. 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)
2. Mike Rosulek (13 de diciembre de 2008). "Esquema de cifrado de Elgamal" . Universidad de Illinois en Urbana-Champaign . Archivado desde el original el 22 de julio de 2016.
3. Tsiounis, Yiannis; Yung, Moti (24 de mayo de 2006). "Sobre la seguridad del cifrado basado en ElGamal". Criptografía de clave pública 1998 . Apuntes de conferencias en informática. 1431 : 117-134. doi : 10.1007 / BFb0054019 . ISBN 978-3-540-69105-1.
4. Abdalla, Michel; Bellare, Mihir; Rogaway, Phillip (17 de marzo de 1999). "DHAES: un esquema de cifrado basado en el problema Diffie-Hellman" . Biblioteca de Teoría de Criptografía .