Sistema criptográfico ElGamal

O criptosistema ElGamal ou criptografia El Gamal (ou sistema El Gamal ) é um protocolo de criptografia assimétrica inventado por Taher Elgamal em 1984 e construído a partir do problema de logaritmo discreto .

Este protocolo é utilizado pelo software livre GNU Privacy Guard , cujas versões recentes implementam inclusive sua versão em curvas elípticas . Ao contrário da criptografia RSA , ela nunca esteve sob proteção de patente .

O artigo fundador de Taher Elgamal apresenta um protocolo de criptografia , mas também uma assinatura digital , que apesar de suas semelhanças (ambas são construídas sobre o problema do logaritmo discreto ) não devem ser confundidas. Este artigo trata apenas do protocolo de criptografia .

Descrição do algoritmo

O algoritmo é descrito para um grupo cíclico finito dentro do qual o problema de decisão Diffie-Hellman (DDH) é difícil. Informações mais específicas são fornecidas na seção Resistência a ataques de CPA .

Podemos notar que o DDH é uma hipótese de trabalho mais forte do que a do logaritmo discreto, uma vez que é válida se alguma vez o problema do logaritmo discreto for difícil. Existem também grupos onde o problema de DDH é fácil, mas onde não existe um algoritmo eficiente para resolver o logaritmo discreto .

Por se tratar de um esquema de criptografia assimétrica , o criptosistema é composto por três algoritmos ( probabilísticos ): GenClefs , Encrypt e Decrypt .

Para a ilustração, assumiremos que Bob deseja enviar uma mensagem para Alice . Mas esta mensagem contém informações confidenciais, então Bob não deseja que seja compreensível por ninguém além de Alice. Então, Bob criptografará sua mensagem.

Como os esquemas de criptografia assimétrica são geralmente mais lentos do que seus análogos simétricos, a criptografia ElGamal é frequentemente usada na prática como parte da criptografia híbrida , como sua especificação PGP.

Uma maneira de ver esse esquema de criptografia é traçar um paralelo com o protocolo de troca de chaves Diffie-Hellman . O algoritmo de criptografia consiste então no envio de uma mensagem criptografada por uma máscara descartável sob a chave compartilhada , que pode ser calculada por Alice desde que ela o tenha feito (ver ilustração ao lado). $c_ {1}$ ${\ displaystyle h ^ {r} = g ^ {r \ cdot x}}$ ${\ displaystyle c_ {2} = g ^ {r}}$

Geração de chave

A primeira etapa do esquema de criptografia é produzir um par de chaves: a chave pública e a chave secreta . O primeiro será usado para criptografar as mensagens e o segundo para descriptografá-las.

Para gerar seu par de chaves, Alice começará tomando um grupo cíclico de ordem q no qual o problema da hipótese de decisão Diffie-Hellman é difícil, bem como um gerador deste grupo. $G$ $g$
Alice então puxará um elemento que será sua chave privada e fará o cálculo . ${\ displaystyle {\ mathsf {sk}} \ triangleq x \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ ${\ displaystyle h = g ^ {x}}$
Finalmente, Alice publicará como sua chave pública . ${\ displaystyle {\ mathsf {pk}} \ triangleq (G, q, g, h)}$

Algoritmo de criptografia

Então Bob tem acesso à chave pública de Alice . Para criptografar uma mensagem codificada como um elemento do grupo , Bob começa desenhando um número aleatório e o usará para cobrir a mensagem durante o cálculo . Para permitir que Alice para descriptografar a mensagem, Bob irá adicionar a esta parte da informação mensagem sobre o perigo: . ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h)}$ $m$ $G$ ${\ displaystyle r \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ $m$ ${\ displaystyle c_ {2} = m \ cdot h ^ {r}}$ ${\ displaystyle c_ {1} = g ^ {r}}$

Finalmente a cifra será composta por estas duas peças :, e Bob envia para Alice. ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle C \ in G ^ {2}}$

Algoritmo de descriptografia

Tendo acesso a e para , Alice pode, assim, calcular: ${\ displaystyle C = (c_ {1}, c_ {2})}$ ${\ displaystyle {\ mathsf {sk}} = x}$

{\ displaystyle {\ frac {c_ {2}} {{c_ {1}} ^ {x}}} = {\ frac {m \ cdot h ^ {r}} {g ^ {r \ cdot x}}} = {\ frac {m \ cdot {\ cancel {g ^ {x \ cdot r}}}} {\ cancel {g ^ {r \ cdot x}}}} = m}

E, portanto, é capaz de encontrar a mensagem . $m$

segurança

Enfrentando ataques de texto claro escolhido

Olhando para a informação pública ; Percebemos que apenas elementos de são visíveis e não os expoentes (aqui x e s , respectivamente). Informalmente podemos notar que o problema do logaritmo discreto pode ser interpretado como o fato de que é difícil encontrar a informação secreta ( por exemplo) que tornaria possível encontrar a mensagem. ${\ displaystyle g ^ {x}, g ^ {s}}$ $G$ ${\ displaystyle {\ mathsf {sk}} = \ log _ {g} (h)}$

Mais precisamente, é o problema de decisão Diffie-Hellmann (ou DDH ) que permite garantir a segurança semântica do esquema.

Demonstração Redução

Assumindo que temos um adversário contra a segurança semântica da criptografia ElGamal que ganha com uma probabilidade não insignificante ε . Torna-se então possível construir um oponente contra o DDH, o que contradiz a suposta dificuldade desse problema. Esta redução que acabamos de descrever constituirá a prova de segurança do esquema. ${\ mathcal A}$ ${\ mathcal B}$

Para construir este oponente, que será doravante denominado "  redução  ", pressupõe-se receber um DDH triplo  : seu objetivo é então decidir se ou com uma probabilidade não desprezível. Para isso possui uma interface com o adversário descrito acima voltado para a segurança semântica do criptossistema ElGamal. ${\ displaystyle (g ^ {a}, g ^ {b}, g ^ {c})}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle c \ in _ {R} \ mathbb {Z} _ {p}}$

A redução vai, portanto, mandar a chave pública para o adversário contra ElGamal . Ao produzir o desafio para o oponente contra a segurança semântica do criptossistema, a redução será enviada como criptografada: para de sua escolha. Se alguma vez a trinca for uma trinca DDH , isto é , se , então seria formada como uma cifra válida para ElGamal no que diz respeito à chave pública . Por outro lado, se o expoente for aleatório, então o oponente contra ElGamal não será capaz de distinguir as duas mensagens do desafio a não ser respondendo aleatoriamente. ${\ displaystyle {\ mathsf {pk}} = (G, q, g, h = g ^ {a})}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot g ^ {c})}$ ${\ displaystyle i \ in \ {0,1 \}}$ ${\ displaystyle c = a \ cdot b}$ ${\ displaystyle C = (g ^ {b}, m_ {i} \ cdot (g ^ {a}) ^ {b}) = (g ^ {b}) = (g ^ {b}, m_ {i} \ cdot h ^ {b}) }$ ${\ displaystyle {\ mathsf {pk}}}$ $vs$

Só temos de responder "1" (correspondendo ao fato de que o desafiante para DDH enviou um tripleto DDH) se alguma vez nosso oponente obtiver sucesso, e "0" (correspondendo ao fato de que o desafiante para DDH enviou um triplo aleatório) por outro lado.

Análise

Vamos agora limitar a vantagem de ganhar com nossa redução da vantagem ε do suposto oponente contra nosso esquema.

Começamos observando que temos dois casos: ou o desafio enviado por nosso desafiante é um tripleto DDH real , ou é um trigêmeo desenhado uniformemente.

{\ displaystyle {\ begin {align} {\ textrm {Adv}} ^ {DDH} ({\ mathcal {B}}) & = | \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {B}} \ para 1 \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ para i \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {A}} \ para i \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ para 0 \ mid i = 0 \ land {\ text {DDH}}] \ Pr [i = 0] + \ Pr [{\ mathcal {A}} \ a 1 \ mid i = 1 \ land {\ text {DDH} }] \ Pr [i = 1] - {\ frac {1} {2}} | \\ & = | {\ frac {1} {2}} (1- \ Pr [{\ mathcal {A}} \ a 1 \ mid i = 0 \ land {\ text {DDH}}] + \ Pr [{\ mathcal {A}} \ a 1 \ mid i = 1 \ land {\ text {DDH}}]) - {\ frac {1} {2}} | \\ & = {\ frac {1} {2}} | - \ Pr [{\ mathcal {A}} \ a 1 \ mid i = 0 \ land {\ text {DDH }}] + \ Pr [{\ mathcal {A}} \ a 1 \ mid i = 1 \ land {\ text {DDH}}] | \\ & = {\ frac {1} {2}} {\ textrm {Adv}} ^ {\ text {ElGamal}} ({\ mathcal {A}}) \\ & = {\ frac {\ varepsilon} {2}} \ end {alinhado}}}

Assim, temos uma vantagem que permanece significativa: para obter a mesma segurança entre o DDH e nosso criptosistema, é suficiente que o problema do DDH permaneça seguro com um bit de segurança adicional.

Diante de ataques de cifras escolhidas

Em modelos com um atacante com mais poder, como em ataques de cifra escolhidos, o criptosistema ElGamal não é seguro devido à sua maleabilidade ; na verdade, dada uma cifra para a mensagem , podemos construir a cifra , que será válida para a mensagem . ${\ displaystyle C = (c_ {1}, c_ {2})}$ $m$ ${\ displaystyle C '= (c_ {1}, 2 \ cdot c_ {2})}$ ${\ displaystyle 2 \ cdot m}$

Essa maleabilidade (é um homomorfismo multiplicativo), por outro lado, possibilita seu uso para votação eletrônica, por exemplo.

No entanto, existem variantes que alcançam segurança contra ataques de cifras escolhidos, como o criptossistema Cramer-Shoup, que pode ser visto como uma extensão da cifra ElGamal.

Exemplo

Para o exemplo, podemos tomar o grupo , com como gerador g = 5 ( Atenção : este não é um grupo seguro, estes valores foram tomados apenas para produzir um exemplo simples). ${\ displaystyle G = (\ mathbb {Z} / 100000007 \ mathbb {Z} ^ {*}, \ times)}$

Uma possível chave pública poderia ser : e como uma chave secreta . ${\ displaystyle {\ mathsf {pk}} = (G, 100000006,5,29487234)}$ ${\ displaystyle {\ mathsf {sk}} = 81996614}$

Observe que, como a criptografia é um algoritmo probabilístico , existem diferentes saídas possíveis para a mesma mensagem. Uma possível cifra para a mensagem 42 poderia ser (58086963, 94768547) , mas também (83036959, 79165157) para os riscos r iguais a 6689644 e 83573058, respectivamente.

No entanto, se fizermos o cálculo para nossos dois números, obteremos 42 na saída. ${\ displaystyle {\ dfrac {c_ {2}} {c_ {1} ^ {sk}}}}$

Notas e referências

(fr) Este artigo foi retirado parcial ou totalmente do artigo da Wikipedia em inglês intitulado " Criptografia ElGamal " ( veja a lista de autores ) .

ElGamal 1984 .
RFC4880 , (en) " OpenPGP Message Format "
Log de mudanças GnuPG 2.1
Joux e Nguyen 2003 .
Katz e Lindell 2014 , Capítulo 10.5 O esquema de criptografia ElGamal.
Belenios, (en) " Especificações de Belenios "

Apêndices

Bibliografia

[ElGamal 1984] (en) Taher ElGamal, " A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms " , Crypto , Springer,1984( DOI 10.1007 / 3-540-39568-7_2 )
[Katz and Lindell 2014] (en) Jonathan Katz e Yehuda Lindell, Introdução à Criptografia Moderna, 2ª Edição , Boca Raton, Chapman e Hall ,2014, 583 p. ( ISBN 978-1-4665-7026-9 , leia online ) , "Capítulo 10.5 The El Gamal Encryption Scheme"
[Menezes, van Oorschot e Vanstone 1996] (en) AJ Menezes , PC van Oorschot e SA Vanstone , Handbook of Applied Cryptography , CRC Press,1996, 810 p. ( ISBN 978-1-4398-2191-6 , leia online [PDF] ) , "Capítulo 8.4 Criptografia de chave pública ElGamal"
[Joux and Nguyen 2003] (en) Antoine Joux e Kim Nguyen, “ Separating Decision Diffie - Hellman from Computational Diffie - Hellman in Cryptographic Groups ” , Journal of Cryptology , vol. 16,2003, p. 239-247 ( DOI 10.1007 / s00145-003-0052-4 )