Cifrado ElGamal

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

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

  No es necesario crear un grupo y un generador para cada clave nueva. De hecho, es probable que una implementación específica de ElGamal esté programada para usar un grupo concreto, 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.

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

Una segunda persona, Bob, cifra un mensaje.${\displaystyle M}$a Alice bajo su clave pública${\displaystyle (G,q,g,h)}$como sigue:

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

Tenga en cuenta que si uno conoce ambos textos cifrados${\displaystyle (c_{1},c_{2})}$y el texto plano${\displaystyle m}$, uno puede encontrar fácilmente el secreto compartido${\displaystyle s}$, desde${\displaystyle c_{2}\cdot m^{-1}=s}$Por lo tanto, un nuevo${\displaystyle y}$y por lo tanto un nuevo${\displaystyle s}$se genera para cada mensaje para mejorar la seguridad. Por esta razón,${\displaystyle y}$También se le llama llave efímera .

Alice descifra un texto cifrado${\displaystyle (c_{1},c_{2})}$con su llave privada${\displaystyle x}$como sigue:

• Calcular${\displaystyle s:=c_{1}^{x}}$. Desde${\displaystyle c_{1}=g^{y}}$,${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$y, por lo tanto, es el mismo secreto compartido que utilizó Bob en el cifrado.
• Calcular${\displaystyle s^{-1}}$, lo contrario de${\displaystyle s}$en el grupo${\displaystyle G}$Esto se puede calcular de varias maneras. Si${\displaystyle G}$es un subgrupo de un grupo multiplicativo de enteros módulo ${\displaystyle n}$, dónde${\displaystyle n}$es primo, el inverso multiplicativo modular se puede calcular utilizando el algoritmo euclidiano extendido . Una alternativa es calcular${\displaystyle s^{-1}}$como${\displaystyle c_{1}^{qx}}$Esto es lo contrario de${\displaystyle s}$debido al teorema de Lagrange , ya que${\displaystyle s\cdot c_{1}^{qx}=g^{xy}\cdot g^{(qx)y}=(g^{q})^{y}=e^{y}=e}$.
• Calcular${\displaystyle m:=c_{2}\cdot s^{-1}}$Este cálculo produce el mensaje original.${\displaystyle m}$, porque${\displaystyle c_{2}=m\cdot s}$; por eso${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$.
• Mapa${\displaystyle m}$Volver al mensaje en texto plano${\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 se cifra mediante un criptosistema simétrico y ElGamal se utiliza únicamente para cifrar 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 resulta más rápido cifrar el mensaje, que puede ser arbitrariamente grande, con un cifrado simétrico y, a continuación, utilizar ElGamal solo para cifrar la clave simétrica, que suele ser bastante pequeña en comparación con el tamaño del mensaje.