miniaturadaimagem|Taher Elgamal é um renomado criptógrafo e cientista da computação egípcio-americano, amplamente reconhecido como o "pai do SSL" (Secure Sockets Layer). Ele propôs o algoritmo ElGamal, usado em sistemas de criptografia e assinatura digital.

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. (versão de conferência publicada em CRYPTO'84, pp. 10–18) 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.

A criptografia ElGamal pode ser definida sobre qualquer grupo cíclico , como o grupo multiplicativo de inteiros módulo n se e somente se n é 1, 2, 4, pk ou 2pk, onde p é um primo ímpar e . Sua segurança depende da dificuldade do Problema de Diffie-Hellman Decisional em .

Algoritmo O algoritmo primeiro realiza a troca de chaves Diffie-Hellman para estabelecer um segredo compartilhado 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:

Gere uma descrição eficiente de um grupo cíclico de ordem com gerador . Seja o elemento identidade de . 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 aleatoriamente de . Compute . A chave pública consiste nos valores . Alice publica esta chave pública e mantém como sua chave privada, que deve ser mantida em segredo.

Criptografia Uma segunda parte, Bob, criptografa uma mensagem para Alice sob sua chave pública da seguinte forma:

Mapeie a mensagem para um elemento de usando uma função de mapeamento reversível. Escolha um inteiro aleatoriamente de . Compute . Isso é chamado de segredo compartilhado. Compute . Compute . Bob envia o texto cifrado para Alice.

Note que se alguém conhece tanto o texto cifrado quanto o texto claro , pode-se facilmente encontrar o segredo compartilhado , uma vez que . Portanto, um novo e, consequentemente, um novo é gerado para cada mensagem para melhorar a segurança. Por esta razão, também é chamado de chave efêmera.

Descriptografia Alice descriptografa um texto cifrado com sua chave privada da seguinte forma: Compute . Como , , e portanto é o mesmo segredo compartilhado que foi usado por Bob na criptografia. Compute , o inverso de no grupo . Isso pode ser calculado de várias maneiras. Se é um subgrupo de um grupo multiplicativo de inteiros módulo , onde é primo, o inverso multiplicativo modular pode ser calculado usando o algoritmo de Euclides estendido. Uma alternativa é calcular como . Este é o inverso de devido ao teorema de Lagrange, uma vez que . Compute . Este cálculo produz a mensagem original , porque ; portanto . Mapeie de volta para a mensagem de texto claro .

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.

Segurança

A segurança do esquema ElGamal depende das propriedades do grupo subjacente , 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 , então a função de criptografia é unidirecional.

Se a hipótese de Diffie-Hellman decisional (DDH) vale em , 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 de alguma mensagem (possivelmente desconhecida) , pode-se facilmente construir uma criptografia válida da mensagem .

Para alcançar segurança contra texto cifrado escolhido, o esquema deve ser modificado, ou um esquema de preenchimento apropriado deve ser usado. Dependendo da modificação, a hipótese DDH pode ou não ser necessária.

Outros esquemas relacionados ao ElGamal que alcançam segurança contra ataques de texto cifrado escolhido também foram propostos. O criptossistema Cramer-Shoup é seguro contra ataques de texto cifrado escolhido assumindo que DDH vale para . Sua prova não usa o modelo do oráculo aleatório. Outro esquema proposto é o DHIES, cuja prova requer uma hipótese mais forte do que a hipótese DDH.

Eficiência

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.

Ver também Taher Elgamal, projetista deste e de outros criptossistemas Esquema de assinatura ElGamal Criptografia homomórfica

Referências

Leitura adicional

Categoria:Algoritmos de criptografia Categoria:Esquemas de encriptação de chave pública