Cifrado ElGamal

Criptosistema 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 gratuito GNU Privacy Guard , en versiones recientes de PGP y en 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 puede describirse como la realización primero de un intercambio de claves Diffie-Hellman para establecer un secreto compartido y luego usarlo como un bloc de un solo uso para cifrar el mensaje. El cifrado de ElGamal se realiza en tres fases: generación de clave, cifrado y descifrado. El primero es puramente intercambio de claves, mientras que los dos últimos combinan cálculos de intercambio de claves con cálculos de mensajes. ${\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 generador . Representemos el elemento de identidad de . ${\displaystyle G\,}$ ${\displaystyle q\,}$ ${\displaystyle g}$ ${\displaystyle e}$ ${\displaystyle G}$

  No es necesario crear un grupo y un generador nuevos para cada nueva clave. De hecho, se puede esperar que una implementación específica de ElGamal esté codificada 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 desea utilizar.

• Elija un número entero al azar de . ${\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 dirigido a Alice con 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 de . ${\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 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 un mensaje nuevo y, por lo tanto, uno nuevo para cada mensaje para mejorar la seguridad. Por este motivo, también se le llama 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, el inverso multiplicativo modular se puede calcular utilizando el algoritmo euclidiano extendido . Una alternativa es calcular como . Esto es lo inverso 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 eso . ${\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

Como la mayoría de los sistemas de clave pública, el criptosistema ElGamal generalmente se usa como parte de un criptosistema híbrido , donde el mensaje en sí se cifra usando un criptosistema simétrico, y luego ElGamal se usa 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 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 ElGamal depende de las propiedades del grupo subyacente, así como de cualquier esquema de relleno utilizado en los mensajes. Si el supuesto computacional de 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 se cumple el supuesto decisional de Diffie-Hellman (DDH) , entonces ElGamal logra seguridad semántica . ^{[2] [3]} La seguridad semántica no está implícita únicamente en el supuesto computacional de Diffie-Hellman. Consulte el supuesto decisivo de Diffie-Hellman para obtener un análisis 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 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, se debe modificar aún más el esquema o se debe utilizar un esquema de relleno apropiado. Dependiendo de la modificación, el supuesto DDH puede ser necesario 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, suponiendo que DDH sea válido para . Su prueba no utiliza el modelo de oráculo aleatorio . Otro esquema propuesto es DHIES , ^[4] cuya prueba requiere un supuesto que sea más fuerte que el supuesto DDH. ${\displaystyle G}$

Eficiencia

El cifrado ElGamal es probabilístico , lo que significa que un único texto sin formato puede cifrarse en muchos textos cifrados posibles, con la consecuencia de que un cifrado 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 pueden calcularse con anticipación si es necesario. El descifrado requiere una exponenciación y un cálculo de un grupo inverso, que, sin embargo, se puede combinar fácilmente en una sola exponenciación.

Ver también

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

Otras lecturas

• AJ Menezes; PC van Oorschot; SA Vanstone. "Capítulo 8.4 Cifrado de clave pública ElGamal" (PDF) . Manual de criptografía aplicada . Prensa CRC.
• Dan Boneh (1998). "El problema de la decisión Diffie-Hellman". Teoría algorítmica de números. Apuntes de conferencias sobre 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) . 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. 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 conferencias sobre informática. vol. 1431, págs. 117-134. doi :10.1007/BFb0054019. ISBN 978-3-540-69105-1.
4. Abdalla, Michel; Bellaré, 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 conferencias sobre informática. vol. 2020. págs. 143-158. doi :10.1007/3-540-45353-9_12. ISBN 978-3-540-41898-6.