O ElGamal é um algoritmo de criptografia assimétrica desenvolvido por Taher Elgamal em 1985. É um algoritmo baseado na dificuldade da resolução do Problema do Logaritmo Discreto, que implementa um NONCE (Number used ONCE)1 para tornar confusa a relação entre texto legível e ilegível. Essa foi a maior inovação no ElGamal.
O algoritmo funciona sobre o grupo cíclico de ordem \(p\) primo, \(\mathbb{Z}_p\). Isso significa que, se deseja-se criptografar uma mensagem de outro formato com o ElGamal, deve-se usar uma função Hash para traduzir cada mensagem para o grupo cíclico de forma inversível.
Inicialmente, Alice toma um primo \(p>2\) longo e um inteiro \(g\) que seja gerador do grupo cíclio \(\mathbb{Z}_p\). Alice também escolhe um inteiro \(s\) e calcula o valor \(T = g^s \text{ mod }p\).
A chave pública que é compartilhada para Beto é \((p,g,T)\).
Primeiramente, Beto deve obter aleatoriamente um valor \(k \in \mathbb{Z}_{p-1}\) que deve ser usado para a criptografia de apenas uma mensagem. Dessa maneira, o valor \(k\) funciona essencialmente como um One-time pad, personalizando o texto ilegível a cada vez que o algoritmo é usado. Esse número \(k\) é chamado NONCE (Number used ONCE).
Para encriptar uma mensagem \(x \in \mathbb{Z}_p\), tendo recebido \((p,g,T)\), Beto calcula \(y = g ^{k} \text{ mod }p\) e \(z = x \cdot T^k \text{ mod }p\). A mensagem criptografada é \((y,z)\), que é enviada para Alice.
Tendo recebido \((y,z)\), Alice deve simplesmente calcular \(z \cdot (y^s)^{-1} \text{ mod }p\). De fato, \[ z \cdot (y^s)^{-1} = x \cdot T^{k} \cdot((g^{k})^{s})^{-1} \] \[ = x \cdot T ^{k}\cdot(g^{s})^{-k} = x \cdot T ^{k} \cdot T^{-k} = x \]
Curiosidade: apesar do Routo escrever isso no slide e no livro, a palavra nonce não é uma abreviação. Na realidade, é uma palavra que data do Inglês Médio (séculos XI ao XV) e significava algo provisório, a ser utilizado uma ou poucas vezes. Inclusive, existe o termo “nonce word”, uma palavra inventada que é usada apenas uma vez para algum propósito específico (e.g. humorístico).↩︎