El Gamal
Em criptografia, o sistema de criptografia ElGamal é um algoritmo de criptografia de chave pública baseado na troca de chaves Diffie-Hellman. Foi descrito por Taher Elgamal em 1985. A criptografia ElGamal é usada no software livre GNU Privacy Guard, em versões recentes do PGP e em outros criptossistemas. O Algoritmo de Assinatura Digital (DSA) é uma variante do esquema de assinatura ElGamal, que não deve ser confundido com a criptografia ElGamal.
Imagem: EL Osboa الأسبوع · BY · Openverse
O algoritmo primeiro realiza a troca de chaves Diffie-Hellman para estabelecer um segredo compartilhado s {\displaystyle s} e, em seguida, usa este como uma cifra de uso único para criptografar a mensagem. A criptografia ElGamal é realizada em três fases: a geração de chaves, a criptografia e a descriptografia. A primeira é puramente a troca de chaves, enquanto as duas últimas misturam computações de troca de chaves com computações de mensagem.
Geração de chaves
A primeira parte, Alice, gera um par de chaves da seguinte forma:
Criptografia
Uma segunda parte, Bob, criptografa uma mensagem M {\displaystyle M} para Alice sob sua chave pública ( G , q , g , h ) {\displaystyle (G,q,g,h)} da seguinte forma: Note que se alguém conhece tanto o texto cifrado ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} quanto o texto claro m {\displaystyle m} , pode-se facilmente encontrar o segredo compartilhado s {\displaystyle s} , uma vez que c 2 ⋅ m − 1 = s {\displaystyle c_{2}\cdot m^{-1}=s} . Portanto, um novo y {\displaystyle y} e, consequentemente, um novo s {\displaystyle s} é gerado para cada mensagem para melhorar a segurança. Por esta razão, y {\displaystyle y} também é chamado de chave efêmera.
Descriptografia
Alice descriptografa um texto cifrado ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} com sua chave privada x {\displaystyle x} da seguinte forma:
Uso prático
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.
Imagem: mikerosebery · BY-NC-SA · Openverse
A segurança do esquema ElGamal depende das propriedades do grupo subjacente G {\displaystyle G} , bem como de qualquer esquema de preenchimento usado nas mensagens. Se a hipótese de Diffie-Hellman computacional (CDH) vale no grupo cíclico subjacente G {\displaystyle G} , então a função de criptografia é unidirecional. Se a hipótese de Diffie-Hellman decisional (DDH) vale em G {\displaystyle G} , então o ElGamal alcança segurança semântica. A segurança semântica não é implicada apenas pela hipótese de Diffie-Hellman computacional. Veja Hipótese de Diffie-Hellman decisional para uma discussão sobre grupos onde se acredita que a hipótese seja válida. A criptografia ElGamal é incondicionalmente maleável e, portanto, não é segura sob ataque de texto cifrado escolhido. Por exemplo, dada uma criptografia ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} de alguma mensagem (possivelmente desconhecida) m {\displaystyle m} , pode-se facilmente construir uma criptografia válida ( c 1 , 2 c 2 ) {\displaystyle (c_{1},2c_{2})} da mensagem 2 m {\displaystyle 2m} .
Imagem: Sahar Hassanein · BY-SA · Openverse
A criptografia ElGamal é probabilística, o que significa que um único texto claro pode ser criptografado em muitos textos cifrados possíveis, com a consequência de que uma criptografia ElGamal geral produz uma expansão de tamanho de 1:2 do texto claro para o texto cifrado. A criptografia sob ElGamal requer duas exponenciações; no entanto, essas exponenciações são independentes da mensagem e podem ser computadas antecipadamente, se necessário. A descriptografia requer uma exponenciação e um cálculo de um inverso de grupo, que podem, no entanto, ser facilmente combinados em apenas uma exponenciação.


