Cifrado ElGamal

Sistema criptográfico de clave pública

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 . ${\displaystyle G}$ ${\displaystyle G}$

El algoritmo

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. ${\displaystyle s}$

Generación de claves

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 . ${\displaystyle G\,}$ ${\displaystyle q\,}$ ${\displaystyle g}$ ${\displaystyle e}$ ${\displaystyle 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 . ${\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 su clave privada , que debe mantenerse en secreto. ${\displaystyle (G,q,g,h)}$ ${\displaystyle x}$

Encriptación

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

• Asigne el mensaje a un elemento utilizando una función de mapeo reversible. ${\displaystyle M}$ ${\displaystyle m}$ ${\displaystyle G}$
• Elija un número entero al azar entre . ${\displaystyle y}$ ${\displaystyle \{1,\ldots ,q-1\}}$
• Calcular . Esto se 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 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 . ${\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}}$
• 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}}$ ${\displaystyle s}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\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}$
• Regrese al mensaje de texto sin formato . ${\displaystyle m}$ ${\displaystyle M}$

Uso práctico

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.

Seguridad

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}$

Eficiencia

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.

Véase también

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

Lectura adicional

• 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.

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. Mike Rosulek (13 de diciembre de 2008). "Esquema de cifrado 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 . Apuntes de clase en informática. Vol. 1431. págs. 117–134. doi :10.1007/BFb0054019. ISBN. 978-3-540-69105-1.
4. Abdalla, Michel; Bellare, Mihir; Rogaway, Phillip (1 de enero de 2001). "Los supuestos de Oracle Diffie-Hellman y un análisis de DHIES". Temas de criptología — CT-RSA 2001 . Apuntes de clase en informática. Vol. 2020. págs. 143–158. doi :10.1007/3-540-45353-9_12. ISBN 978-3-540-41898-6.