Cifrado 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 libre GNU Privacy Guard , versiones recientes de PGP y otros criptosistemas . El algoritmo de firma digital (DSA) es una variante del esquema de firma ElGamal , que no debe confundirse con el cifrado ElGamal.

El cifrado ElGamal se puede definir sobre cualquier grupo cíclico , como un grupo multiplicativo de números enteros módulo  n si y solo si n es 1, 2, 4, p ^k o 2 p ^k , donde p es un primo impar y k > 0. Su seguridad depende de la dificultad de un determinado problema relacionado con el cálculo de logaritmos discretos .${\estilo de visualización G}$${\estilo de visualización G}$

El algoritmo se puede describir como un intercambio de claves Diffie-Hellman para establecer un secreto compartido y luego usarlo como un bloque de un solo uso para cifrar el mensaje. El cifrado ElGamal se realiza en tres fases: la generación de la clave, el cifrado y el descifrado. La primera es puramente un intercambio de claves, mientras que las dos últimas combinan los cálculos de intercambio de claves con los cálculos del mensaje.${\estilo de visualización s}$

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

• Generar una descripción eficiente de un grupo cíclico de orden con el generador . Sea . el elemento identidad de .${\estilo de visualización G\,}$ ${\estilo de visualización q\,}$ ${\estilo de visualización g}$${\estilo de visualización e}$${\estilo de visualización G}$

  No es necesario crear un grupo y un generador para cada nueva clave. De hecho, se puede esperar que una implementación específica de ElGamal esté codificada de forma rígida para utilizar un grupo específico o un grupo de una suite específica. La elección del grupo depende principalmente del tamaño de las claves que se deseen utilizar.

• Elija un número entero al azar entre .${\estilo de visualización x}$${\displaystyle \{1,\ldots ,q-1\}}$
• Calcular .$estilo de visualización h:=g^{x}}$
• La clave pública consta de los valores . Alice publica esta clave pública y la conserva como su clave privada , que debe mantenerse en secreto.${\displaystyle (G,q,g,h)}$${\estilo de visualización x}$

Una segunda parte, Bob, cifra un mensaje a Alice bajo su clave pública de la siguiente manera:${\estilo de visualización M}$${\displaystyle (G,q,g,h)}$

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

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

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

• Calcular . Dado que , y por lo tanto es el mismo secreto compartido que utilizó Bob en el cifrado.$estilo de visualización s:=c_{1}^{x}}$$estilo de visualización c_{1}=g^{y}}$${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$
• Calcular , la inversa de en el grupo . Esto se puede calcular de varias maneras. Si es un subgrupo de un grupo multiplicativo de números enteros módulo  , donde es primo, la inversa multiplicativa modular se puede calcular utilizando el algoritmo euclidiano extendido . Una alternativa es calcular como . Esta es la inversa de debido al teorema de Lagrange , ya que .${\displaystyle s^{-1}}$${\estilo de visualización s}$${\estilo de visualización G}$${\estilo de visualización G}$${\estilo de visualización n}$${\estilo de visualización n}$${\displaystyle s^{-1}}$$estilo de visualización c_{1}^{qx}}$${\estilo de visualización 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}$
• Regrese al mensaje de texto sin formato .${\displaystyle m}$${\displaystyle M}$

Al igual que la mayoría de los sistemas de clave pública, el criptosistema ElGamal se suele utilizar como parte de un criptosistema híbrido , donde el mensaje en sí se cifra utilizando un criptosistema simétrico, y luego se utiliza ElGamal para cifrar 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 utilizar ElGamal solo para cifrar la clave simétrica, que suele ser bastante pequeña en comparación con el tamaño del mensaje.

La seguridad del esquema ElGamal depende de las propiedades del grupo subyacente , así como de cualquier esquema de relleno utilizado en los mensajes. Si el supuesto computacional Diffie–Hellman (CDH) se cumple en el grupo cíclico subyacente , entonces la función de cifrado es unidireccional . ^[2]${\displaystyle G}$${\displaystyle G}$

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

El cifrado ElGamal es incondicionalmente maleable y, por lo tanto, no es seguro frente a ataques de texto cifrado seleccionado . Por ejemplo, dado el cifrado de un 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 seleccionado, se debe modificar aún más el esquema o se debe utilizar un esquema de relleno adecuado. Según 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 elegido. El criptosistema Cramer–Shoup es seguro ante ataques de texto cifrado elegido suponiendo que DDH se cumple para . Su prueba no utiliza el modelo de oráculo aleatorio . Otro esquema propuesto es DHIES , ^[4] cuya prueba requiere una suposición que es más fuerte que la suposición DDH.${\displaystyle G}$

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

El cifrado con 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 exponenciación y un cálculo de un grupo inverso, que, sin embargo, se pueden combinar fácilmente en una sola exponenciación.

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

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