stringtranslate.com

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 .

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.

Generación de claves

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

Encriptación

Una segunda parte, Bob, cifra un mensaje a Alice bajo su clave pública de la siguiente manera:

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 .

Descifrado

Alice descifra un texto cifrado con su clave privada de la siguiente manera:

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]

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.

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 .

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.

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

Lectura adicional

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. ^ de 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.