El Gamal

A primeira parte, Alice, gera um par de chaves da seguinte forma:

• Gere uma descrição eficiente de um grupo cíclico ${\displaystyle G\,}$ de ordem ${\displaystyle q\,}$ com gerador ${\displaystyle g}$. Seja ${\displaystyle e}$ o elemento identidade de ${\displaystyle G}$.

  Não é necessário criar um grupo e um gerador para cada nova chave. De fato, pode-se esperar que uma implementação específica do ElGamal seja programada para usar um grupo específico, ou um grupo de um conjunto específico. A escolha do grupo diz respeito principalmente ao tamanho das chaves que se deseja usar.

• Escolha um inteiro ${\displaystyle x}$ aleatoriamente de ${\displaystyle \{1,\ldots ,q-1\}}$.
• Compute ${\displaystyle h:=g^{x}}$.
• A chave pública consiste nos valores ${\displaystyle (G,q,g,h)}$. Alice publica esta chave pública e mantém ${\displaystyle x}$ como sua chave privada, que deve ser mantida em segredo.

Uma segunda parte, Bob, criptografa uma mensagem ${\displaystyle M}$ para Alice sob sua chave pública ${\displaystyle (G,q,g,h)}$ da seguinte forma:

• Mapeie a mensagem ${\displaystyle M}$ para um elemento ${\displaystyle m}$ de ${\displaystyle G}$ usando uma função de mapeamento reversível.
• Escolha um inteiro ${\displaystyle y}$ aleatoriamente de ${\displaystyle \{1,\ldots ,q-1\}}$.
• Compute ${\displaystyle s:=h^{y}}$. Isso é chamado de segredo compartilhado.
• Compute ${\displaystyle c_{1}:=g^{y}}$.
• Compute ${\displaystyle c_{2}:=m\cdot s}$.
• Bob envia o texto cifrado ${\displaystyle (c_{1},c_{2})}$ para Alice.

Note que se alguém conhece tanto o texto cifrado ${\displaystyle (c_{1},c_{2})}$ quanto o texto claro ${\displaystyle m}$, pode-se facilmente encontrar o segredo compartilhado ${\displaystyle s}$, uma vez que ${\displaystyle c_{2}\cdot m^{-1}=s}$. Portanto, um novo ${\displaystyle y}$ e, consequentemente, um novo ${\displaystyle s}$ é gerado para cada mensagem para melhorar a segurança. Por esta razão, ${\displaystyle y}$ também é chamado de chave efêmera.

Alice descriptografa um texto cifrado ${\displaystyle (c_{1},c_{2})}$ com sua chave privada ${\displaystyle x}$ da seguinte forma:

• Compute ${\displaystyle s:=c_{1}^{x}}$. Como ${\displaystyle c_{1}=g^{y}}$, ${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$, e portanto é o mesmo segredo compartilhado que foi usado por Bob na criptografia.
• Compute ${\displaystyle s^{-1}}$, o inverso de ${\displaystyle s}$ no grupo ${\displaystyle G}$. Isso pode ser calculado de várias maneiras. Se ${\displaystyle G}$ é um subgrupo de um grupo multiplicativo de inteiros módulo ${\displaystyle n}$, onde ${\displaystyle n}$ é primo, o inverso multiplicativo modular pode ser calculado usando o algoritmo de Euclides estendido. Uma alternativa é calcular ${\displaystyle s^{-1}}$ como ${\displaystyle c_{1}^{q-x}}$. Este é o inverso de ${\displaystyle s}$ devido ao teorema de Lagrange, uma vez que ${\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e}$.
• Compute ${\displaystyle m:=c_{2}\cdot s^{-1}}$. Este cálculo produz a mensagem original ${\displaystyle m}$, porque ${\displaystyle c_{2}=m\cdot s}$; portanto ${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$.
• Mapeie ${\displaystyle m}$ de volta para a mensagem de texto claro ${\displaystyle M}$.

Como a maioria dos sistemas de chave pública, o criptossistema ElGamal é geralmente usado como parte de um criptossistema híbrido, onde a mensagem em si é criptografada usando um criptossistema simétrico, e o ElGamal é então usado para criptografar apenas a chave simétrica. Isso ocorre porque criptossistemas assimétricos como o ElGamal são geralmente mais lentos do que os simétricos para o mesmo nível de segurança, então é mais rápido criptografar a mensagem, que pode ser arbitrariamente grande, com uma cifra simétrica, e então usar o ElGamal apenas para criptografar a chave simétrica, que geralmente é bastante pequena em comparação com o tamanho da mensagem.