Cifrado ElGamal

De Wikipedia, la enciclopedia libre

(Redirigido desde ElGamal)

El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en problemas matemáticos de algoritmos discretos. Es un algoritmo de criptografía asimétrica basado en al idea de Diffie-Hellman y que funciona de una forma parecida a este algoritmo discreto.

El algoritmo de ElGamal puede ser utilizado tanto para generar firmas digitales como para cifrar o descifrar.

Fue descrito por Taher Elgamal en 1984 y es usado en GNU Privacy Guard software, versiones recientes de PGP, y otros sistemas criptográficos. Este algoritmo no esta bajo ninguna patente lo que lo hace de uso libre.

La seguridad del algoritmo se basa en la suposición que la función utilizada es de un sólo sentido y la dificultad de calcular un logaritmo discreto.

El procedimiento de cifrado (y descifrado) esta basado en cálculos sobre un grupo cíclico cualquiera $G\,$ lo que lleva a que la seguridad del mismo dependa de la dificultad de calcular logaritmos discretos en $\,G$ .

Tabla de contenidos

1 El algoritmo
2 Creación de llaves de cifrado
- 2.1 Nota
3 Cifrado
4 Descifrado
5 Análisis

[editar] El algoritmo

ElGamal consta de tres componentes: el generador de claves, el algoritmo de cifrado, y el de descifrado. A continuación se describe el algoritmo utilizando el grupo multiplicativo de enteros módulo p.

[editar] Creación de llaves de cifrado

Para generar un par de llaves, se escoge un número primo $p\,$ cualquiera tal que $p - 1\,$ tenga un factor primo grande. Además se eligen dos números aleatorios $g\,$ (el generador) y $a\,$ (que actuará como llave privada) tal que $a \in \{ 0, \ldots, p-2 \}$ .

Se calcula entonces el valor de $A=\, g^a \pmod p$ .

$A\,$ por lo tanto será la llave pública a utilizar.

En este caso $\pmod p \,$ se refiere al operador de módulo de $p$ y $a$ es la llave privada mientras que los valores $p\,$ , $g\,$ y $A\,$ son públicos.

[editar] Nota

La definición $a \in \{ 0, \ldots, p-2 \}$ es correcta. Sin embargo, desde un punto de vista de seguridad, esta definición tiene casos que no hacen sentido ya que $g^0=\, 1$ y $g^1=\, g$ constituyen casos que no brindan seguridad alguna y hacen que el cifrado no funcione. Dado esto se considera preferentemente que $a \in \{ 2, \ldots, p-2 \}$ .

[editar] Cifrado

Suponiendo que se tiene un texto claro que necesita ser cifrado. Lo primero por hacer es convertir este texto en un elemento de $G$ obteniendo un $m$ . Luego se escoge arbitrariamente un número $b$ tal que $b \in \{ 2, \ldots, p-2 \}$ para finalmente calcular:

$y_1 = g^b\,\pmod p$

$y_2 = A^b \, m\,\pmod p$

El mensaje cifrado final corresponde a la tupla $\, C_b(m, b) = (y_1, y_2)$

Un ejemplo sería que se tuviera un texto tal que $\,m = 9$ y escojemos un $\,b = 5$

$y_1 =\, g^b \pmod p =\, 3^5 \pmod {17} =\, 5$

y

$\,y_2 =\, A^b m \pmod p =\, 1$ .

Finalmente el nuestro texto cifrado estaría compuesto por $\,C_b(m,b) = (y_1=5, y_2=1)$ .

[editar] Descifrado

Para descifrar se tiene que realizar el siguiente cálculo:

$y_1^x y_2 \pmod p$

donde tenemos que $x\,$ cumple con $x =\, p - 1 - a$

La resolución de este problema queda entonces de la siguiente manera

$y_1^x y_2 \,= y_1^{p-1-a} y_2$ $\,= g^{b(p-1-a)} A^bm = (g^{p-1})^b (g^a)^{-b} A^b m$ $\,=$ (utilizamos el pequeño teorema de Fermat)

$\,= A^{-1} A^b m = m \pmod p$

Nuevamente a modo de ejemplo, y tomando los datos del ejemplo anterior, obtenemos que

$m = y_1^{p-1-a} y_2 \pmod p = 5^{10} \cdot 1 \pmod {17} = 9$ .

También existe una expresión más simplificada para el mismo proceso:

$d_K(y_1, y_2) = y_2(y_1^a)^{-1} \pmod p = m \pmod p$

[editar] Análisis

[editar] Efectividad

Hasta el momento el algoritmo ElGamal de cifrado/descifrado puede ser considerado un algoritmo efectivo.

Un "adversario" con la habilidad de calcular logaritmos discretos podría ser capaz de romper un cifrado ElGamal. Sin embargo, hasta la actualidad, no existen algoritmos suficientemente eficientes para realizar este tipo de cálculos en un tiempo razonable, considerando además que se utilizen números grandes para cifrar. Dados estos antecedentes se puede decir que hoy en día ElGamal es seguro.

[editar] Maleabilidad

Sin embargo existe un caso en que este algoritmo se vuelve maleable. Esto Significa que bajo un ataque específico la seguridad de ElGamal se puede quebrar. Este ataque usa el hecho de tener el texto cifrado $C_b=(B,M)\,$ del texto claro $m\,$ (ambos conocidos). Sabiendo esto se puede llegar a que el texto cifrado $C_b=(B, k*M)\,$ corresponde al texto plano $k*m \,$ . Si ahora la persona que cifró el mensaje anterior genera otro texto cifrado $C_b=(B, M')\,$ (utilizando el mismo $b\,$ con el que cifró anteriormente) el malo debería ser capaz de llegar al texto plano $m'\,$ correspondiente siguiente los siguientes pasos: