Criptosistema ElGamal

El criptosistema ElGamal , o cifrado El Gamal (o sistema El Gamal ) es un protocolo de criptografía asimétrica inventado por Taher Elgamal en 1984 y construido a partir del problema del logaritmo discreto .

Este protocolo es utilizado por el software libre GNU Privacy Guard , cuyas versiones recientes implementan incluso su versión en curvas elípticas . A diferencia del cifrado RSA , nunca ha estado protegido por patente .

El artículo fundacional de Taher Elgamal presenta un protocolo de cifrado , pero también una firma digital , que a pesar de sus similitudes (ambos se basan en el problema del logaritmo discreto ) no deben confundirse. Este artículo se ocupa únicamente del protocolo de cifrado .

Descripción del algoritmo

El algoritmo se describe para un grupo cíclico finito dentro del cual el problema de decisión de Diffie-Hellman (DDH) es difícil. Se proporciona información más precisa en la sección Resistencia a los ataques de CPA .

Podemos notar que DDH es una hipótesis de trabajo más fuerte que la del logaritmo discreto, ya que se cumple si alguna vez el problema del logaritmo discreto es difícil. También hay grupos donde el problema de DDH es fácil, pero donde no existe un algoritmo eficiente para resolver el logaritmo discreto .

Al tratarse de un esquema de cifrado asimétrico , el criptosistema está compuesto por tres algoritmos ( probabilísticos ): GenClefs , Encrypt y Decrypt .

Para la ilustración, asumiremos que Bob quiere enviar un mensaje a Alice . Pero este mensaje contiene información confidencial, por lo que Bob no quiere que nadie más que Alice pueda entenderlo. Entonces Bob cifrará su mensaje.

Dado que los esquemas de cifrado asimétrico son generalmente más lentos que sus análogos simétricos, el cifrado ElGamal se utiliza a menudo en la práctica como parte del cifrado híbrido , como su especificación PGP.

Una forma de ver este esquema de cifrado es establecer un paralelo con el protocolo de intercambio de claves Diffie-Hellman . El algoritmo de encriptación consiste entonces en enviar un mensaje encriptado por una máscara desechable bajo la clave compartida , que puede ser calculada por Alice ya que lo ha hecho (ver ilustración al lado). $c_ {1}$ ${\ Displaystyle h ^ {r} = g ^ {r \ cdot x}}$ ${\ Displaystyle c_ {2} = g ^ {r}}$

Generación de claves

El primer paso en el esquema de cifrado es producir un par de claves: la clave pública y la clave secreta . El primero se utilizará para cifrar los mensajes y el segundo para descifrarlos.

Para generar su par de claves, Alice comenzará tomando un grupo cíclico de orden q en el que el problema de hipótesis de decisión de Diffie-Hellman es difícil, así como un generador de este grupo. $GRAMO$ $gramo$
Alice luego extraerá un elemento que será su clave privada y lo calculará . ${\ Displaystyle {\ mathsf {sk}} \ triangleq x \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ ${\ Displaystyle h = g ^ {x}}$
Finalmente, Alice publicará como su clave pública . ${\ Displaystyle {\ mathsf {pk}} \ triangleq (G, q, g, h)}$

Algoritmo de cifrado

Entonces Bob tiene acceso a la clave pública de Alice . Para cifrar un mensaje codificado como un elemento del grupo , Bob comienza dibujando un número aleatorio y lo usará para cubrir el mensaje mientras realiza el cálculo . Para permitir que Alice para descifrar el mensaje, Bob se sumará a esta parte de la información de los mensajes sobre el peligro: . ${\ Displaystyle {\ mathsf {pk}} = (G, q, g, h)}$ $metro$ $GRAMO$ ${\ Displaystyle r \ hookleftarrow U (\ mathbb {Z} _ {q} ^ {*})}$ $metro$ ${\ Displaystyle c_ {2} = m \ cdot h ^ {r}}$ ${\ Displaystyle c_ {1} = g ^ {r}}$

Finalmente el cifrado estará compuesto por estas dos piezas :, y Bob envía a Alice. ${\ Displaystyle C = (c_ {1}, c_ {2})}$ ${\ Displaystyle C \ en G ^ {2}}$

Algoritmo de descifrado

Al tener acceso ay a , Alice puede así 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}

Y, por tanto, es capaz de encontrar el mensaje . $metro$

seguridad

Enfrentarse a los ataques de texto claro elegidos

Mirando la información pública ; nos damos cuenta de que los únicos elementos de se hacen visibles y no los exponentes (aquí X y S , respectivamente). De manera informal podemos advertir que el problema del logaritmo discreto puede interpretarse como el hecho de que es difícil encontrar la información secreta ( por ejemplo) que permitiría encontrar el mensaje. ${\ Displaystyle g ^ {x}, g ^ {s}}$ $GRAMO$ ${\ Displaystyle {\ mathsf {sk}} = \ log _ {g} (h)}$

Más precisamente, es el problema de decisión Diffie-Hellmann (o DDH ) el que permite garantizar la seguridad semántica del esquema.

Demostración Reducción

Suponiendo que tengamos un oponente contra la seguridad semántica del cifrado ElGamal que gane con una probabilidad no despreciable ε . Entonces es posible construir un oponente contra DDH, lo que contradeciría la supuesta dificultad de este problema. Esta reducción que acabamos de describir constituirá la prueba de seguridad del esquema. ${\ mathcal A}$ ${\ mathcal B}$

Para construir este oponente, que en adelante se denominará "  reducción  ", se supone que recibe un triple DDH  : su propósito es entonces decidir si o con una probabilidad no despreciable. Para ello cuenta con una interfaz con el adversario descrito anteriormente de cara a la seguridad semántica del criptosistema ElGamal. ${\ Displaystyle (g ^ {a}, g ^ {b}, g ^ {c})}$ ${\ Displaystyle c = a \ cdot b}$ ${\ Displaystyle c \ in _ {R} \ mathbb {Z} _ {p}}$

Por tanto, la reducción enviará la clave pública al adversario contra ElGamal . Al producir el desafío para el oponente contra la seguridad semántica del criptosistema, la reducción se enviará como encriptada: para su elección. Si alguna vez el triplete es un triplete DDH , es decir si , entonces se formaría como un cifrado válido para ElGamal con respecto a la clave pública . Por otro lado, si el exponente es aleatorio, entonces el oponente contra ElGamal no podrá distinguir los dos mensajes del desafío más que respondiendo al azar. ${\ 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 = (sol ^ {b}, m_ {i} \ cdot (sol ^ {a}) ^ {b}) = (sol ^ {b}, m_ {i} \ cdot h ^ {b}) }$ ${\ Displaystyle {\ mathsf {pk}}}$ $vs$

Solo tenemos que responder "1" (correspondiente al hecho de que el retador por DDH envió un triplete DDH) si alguna vez nuestro oponente tiene éxito, y "0" (correspondiente al hecho de que el retador por DDH envió un triple aleatorio) en caso contrario.

Análisis

Ahora limitaremos la ventaja de ganar de nuestra reducción de la ventaja ε del supuesto oponente contra nuestro esquema.

Comenzamos señalando que tenemos dos casos: o el desafío enviado por nuestro retador es un triplete DDH real , o es un triplete elaborado uniformemente.

{\ Displaystyle {\ begin {alineado} {\ textrm {Adv}} ^ {DDH} ({\ mathcal {B}}) & = | \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {B}} \ to 1 \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {DDH}}] - \ Pr [{\ mathcal {A}} \ to i \ mid {\ text {Random}}] | \\ & = | \ Pr [{\ mathcal {A}} \ to 0 \ mid i = 0 \ land {\ text {DDH}}] \ Pr [i = 0] + \ Pr [{\ mathcal {A}} \ to 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}} \ to 1 \ mid i = 0 \ land {\ text {DDH }}] + \ Pr [{\ mathcal {A}} \ to 1 \ mid i = 1 \ land {\ text {DDH}}] | \\ & = {\ frac {1} {2}} {\ textrm {Adv}} ^ {\ text {ElGamal}} ({\ mathcal {A}}) \\ & = {\ frac {\ varepsilon} {2}} \ end {alineado}}}

Por lo tanto, tenemos una ventaja que sigue siendo significativa: para lograr la misma seguridad entre DDH y nuestro criptosistema, es suficiente que el problema de DDH permanezca seguro con un bit de seguridad adicional.

Frente a los ataques de cifrado elegidos

En modelos con un atacante con más poder, como bajo ataques de cifrado elegido, el criptosistema ElGamal no es seguro debido a su maleabilidad ; de hecho, dado un cifrado para el mensaje , podemos construir el cifrado , que será válido para el mensaje . ${\ Displaystyle C = (c_ {1}, c_ {2})}$ $metro$ ${\ Displaystyle C '= (c_ {1}, 2 \ cdot c_ {2})}$ ${\ Displaystyle 2 \ cdot m}$

Esta maleabilidad (es un homomorfismo multiplicativo) por otro lado hace posible su uso para la votación electrónica por ejemplo.

Sin embargo, existen variantes que logran seguridad contra ataques de cifrado elegidos, como el criptosistema Cramer-Shoup, que puede verse como una extensión del cifrado ElGamal.

Ejemplo

Para el ejemplo, podemos tomar el grupo , con el generador g = 5 ( Advertencia : este no es un grupo seguro, estos valores se tomaron solo para producir un ejemplo simple). ${\ Displaystyle G = (\ mathbb {Z} / 100000007 \ mathbb {Z} ^ {*}, \ times)}$

Por tanto, una posible clave pública podría ser :, y como clave secreta . ${\ Displaystyle {\ mathsf {pk}} = (G, 100000006,5,29487234)}$ ${\ Displaystyle {\ mathsf {sk}} = 81996614}$

Tenga en cuenta que, dado que el cifrado es un algoritmo probabilístico , existen diferentes salidas posibles para el mismo mensaje. Por lo tanto, un posible cifrado para el mensaje 42 podría ser (58086963, 94768547) , pero también (83036959, 79165157) para los peligros r igual a 6689644 y 83573058 respectivamente.

Sin embargo, si hacemos el cálculo de nuestras dos cifras, obtendremos 42 en la salida. ${\ Displaystyle {\ dfrac {c_ {2}} {c_ {1} ^ {sk}}}}$

Notas y referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Cifrado de ElGamal " ( ver la lista de autores ) .

ElGamal 1984 .
RFC4880 , (en) " Formato de mensaje OpenPGP "
Registro de cambios de GnuPG 2.1
Joux y Nguyen 2003 .
Katz y Lindell 2014 , Capítulo 10.5 El esquema de cifrado de ElGamal.
Belenios, (en) " Especificaciones de Belenios "

Apéndices

Bibliografía

[ElGamal 1984] (en) Taher ElGamal, " Un criptosistema de clave pública y un esquema de firma basado en logaritmos discretos " , Crypto , Springer,1984( DOI 10.1007 / 3-540-39568-7_2 )
[Katz y Lindell 2014] (en) Jonathan Katz y Yehuda Lindell, Introducción a la criptografía moderna, segunda edición , Boca Raton, Chapman y Hall ,2014, 583 p. ( ISBN 978-1-4665-7026-9 , leer en línea ) , "Capítulo 10.5 El esquema de cifrado de El Gamal"
[Menezes, van Oorschot y Vanstone 1996] (en) AJ Menezes , PC van Oorschot y SA Vanstone , Handbook of Applied Cryptography , CRC Press,1996, 810 p. ( ISBN 978-1-4398-2191-6 , leer en línea [PDF] ) , "Capítulo 8.4 Cifrado de clave pública de ElGamal"
[Joux y Nguyen 2003] (en) Antoine Joux y Kim Nguyen, " Separando Decisión Diffie - Hellman de Computational Diffie - Hellman en Grupos Criptográficos " , Journal of Cryptology , vol. dieciséis,2003, p. 239-247 ( DOI 10.1007 / s00145-003-0052-4 )