Cifrado El Gamal

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. El cifrado ElGamal se usa 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.

Encriptación ElGamal se puede definir sobre cualquier grupo cíclico G{displaystyle G., como grupo multiplicativo de enteros modulo n. Su seguridad depende de la dificultad de un problema determinado en G{displaystyle G. relacionado con los logaritmos discretos.

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:

• Generar una descripción eficiente de un grupo cíclico G{displaystyle G,} de orden q{displaystyle q,} con generador g{displaystyle g}. Vamos e{displaystyle e} representar el elemento de identidad G{displaystyle G..
• Elija un entero x{displaystyle x} aleatoriamente desde {}1,...... ,q− − 1}{displaystyle {1,ldotsq-1}}.
• Computación h:=gx{displaystyle h:=g^{x}.
• El clave pública consiste en los valores ()G,q,g,h){displaystyle (G,q,g,h)}. Alice publica esta llave pública y conserva x{displaystyle x} como ella clave privada, que debe ser guardado en secreto.

Cifrado

Una segunda fiesta, Bob, encripta un mensaje M{displaystyle M} a Alice bajo su llave pública ()G,q,g,h){displaystyle (G,q,g,h)} como sigue:

• Mapa del mensaje M{displaystyle M} a un elemento m{displaystyle m} de G{displaystyle G. usando una función de mapeo reversible.
• Elija un entero Sí.{displaystyle y} aleatoriamente desde {}1,...... ,q− − 1}{displaystyle {1,ldotsq-1}}.
• Computación s:=hSí.{displaystyle s:=h^{y}. Esto se llama secreto compartido.
• Computación c1:=gSí.{displaystyle C_{1}:=g^{y}.
• Computación c2:=m⋅ ⋅ s{displaystyle C_{2}:=mcdot s.
• Bob envía el cifertexto ()c1,c2){displaystyle (c_{1},c_{2}} a Alice.

Tenga en cuenta que si uno conoce ambos el ciphertext ()c1,c2){displaystyle (c_{1},c_{2}} y el texto m{displaystyle m}, uno puede encontrar fácilmente el secreto compartido s{displaystyle s}, desde c2⋅ ⋅ m− − 1=s{displaystyle c_{2}cdot m^{-1}=s}. Por lo tanto, un nuevo Sí.{displaystyle y} y por lo tanto un nuevo s{displaystyle s} se genera para cada mensaje para mejorar la seguridad. Por esta razón, Sí.{displaystyle y} también se llama una llave efímera.

Descifrado

Alice descifra un ciphertext ()c1,c2){displaystyle (c_{1},c_{2}} con su llave privada x{displaystyle x} como sigue:

• Computación s:=c1x{displaystyle S:=c_{1} {x}. Desde c1=gSí.{displaystyle C_{1}=g^{y}, c1x=gxSí.=hSí.{displaystyle ¿Qué?, y por lo tanto es el mismo secreto compartido que fue utilizado por Bob encriptación.
• Computación s− − 1{displaystyle s^{-1}, el inverso de s{displaystyle s} en el grupo G{displaystyle G.. Esto puede ser calculado de varias maneras. Si G{displaystyle G. es un subgrupo de un grupo multiplicativo de integers modulon{displaystyle n}, donde n{displaystyle n} es primo, el inverso multiplicativo modular se puede computar usando el algoritmo de Euclidean extendido. Una alternativa es calcular s− − 1{displaystyle s^{-1} como c1q− − x{displaystyle c_{1} {q-x}. Este es el inverso de s{displaystyle s} por el teorema de Lagrange, desde s⋅ ⋅ c1q− − x=gxSí.⋅ ⋅ g()q− − x)Sí.=()gq)Sí.=eSí.=e{cdot scdot c_{1}{q-x}=g}cdot g^{(q-x)y}=(g^{q}=e^{y}=e}=e}.
• Computación m:=c2⋅ ⋅ s− − 1{displaystyle m:=c_{2}cdot s^{-1}. Este cálculo produce el mensaje original m{displaystyle m}, porque c2=m⋅ ⋅ s{displaystyle C_{2}=mcdot s; por lo tanto c2⋅ ⋅ s− − 1=()m⋅ ⋅ s)⋅ ⋅ s− − 1=m⋅ ⋅ e=m{displaystyle c_{2}cdot s^{-1}=(mcdot s)cdot s^{-1}=mcdot e=m}.
• Mapa m{displaystyle m} volver al mensaje de texto 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 encripta usando un criptosistema simétrico, y ElGamal luego 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 ElGamal depende de las propiedades del grupo subyacente G{displaystyle G. así como cualquier esquema de relleno utilizado en los mensajes. Si la suposición computacional Diffie-Hellman (CDH) se mantiene en el grupo cíclico subyacente G{displaystyle G., entonces la función de cifrado es de una sola dirección.

Si la suposición de decisión Diffie-Hellman (DDH) se mantiene G{displaystyle G., entonces ElGamal logra seguridad semántica. La seguridad semántica no está implícita por la suposición computacional Diffie-Hellman solo. Véase la suposición de Diffie-Hellman para una discusión de grupos en los que se cree que la suposición tiene.

La encriptación ElGamal es incondicionalmente maleable, por lo que no está segura bajo el ataque de cifertexto elegido. Por ejemplo, dada una encriptación ()c1,c2){displaystyle (c_{1},c_{2}} de algunos mensajes (posiblemente desconocidos) m{displaystyle m}, se puede construir fácilmente un cifrado válido ()c1,2c2){displaystyle (c_{1},2c_{2}} del mensaje 2m{displaystyle 2m}.

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

También se han propuesto otros esquemas relacionados con ElGamal que logran la seguridad contra los ataques de cifertexto elegidos. El criptosistema Cramer-Shoup está seguro bajo ataque de criptotexto elegido asumiendo que la DDH sostiene por G{displaystyle G.. Su prueba no utiliza el modelo de oráculo al azar. Otro esquema propuesto es el DHAES, cuya prueba requiere una suposición más débil que la suposición DDH.

Eficiencia

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