Cifrado ElGamal

El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en problemas matemáticos de logaritmos discretos. Es un algoritmo de criptografía asimétrica basado en la 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 se usa en software GNU Privacy Guard, 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$.

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.

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 clave privada) tal que $a \in \{ 0, \ldots, p-1 \}$.

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.

Nota

La definición $a \in \{ 0, \ldots, p-1 \}$ 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-1 \}$.

Ejemplo numérico

Los valores:

$p = 17\,$ (primo elegido al azar)

$g = 3\,$ (generador)

$a = 6\,$ (llave privada elegida al azar)

$A = g^a\,\pmod p = 3^6\,\pmod {17} = 15\,$ (llave pública)

forman la llave pública $\,(17,3,15)$ y la privada $\,(6)$

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-1 \}$ 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)$

Ejemplo numérico

Dado un texto $\,m = 9$ y se escoge un $\,b = 5$ aleatorio:

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

$\,y_2 =\, A^b m \pmod p =\,15^5 \cdot 9 \pmod{17}=\, 1$.

El texto cifrado $\,C_b(m,b)$ está compuesto por la tupla $\,(y_1=5, y_2=1)$.

Descifrado

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

$y_1^x y_2 \pmod p$

donde $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^{b(p-1-a)}A^bm = (g^{p-1})^b (g^a)^{-b} A^b m$ $\,=$ (utilizamos el pequeño teorema de Fermat)

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

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

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

Ejemplo numérico

El texto cifrado $\,C_b(m,b) = (y_1=5, y_2=1)$ cifrado con la llave pública $\,(p=17,g=3,A=15)$ puede ser descifrado utilizando la llave privada $\,(a=6)$.

Utilizando el Pequeño Teorema de Fermat:

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

Utilizando la Expresión Simplificada:

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

Análisis

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, en la actualidad, el algoritmo de computación de logaritmos discretos es subexponencial con una complejidad de λ = 1/3 , la misma que la de factorizar dos números primos, y por tanto, incapaz de realizar tal tarea en números grandes en un tiempo razonable.

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 adversario debería ser capaz de llegar al texto plano $m'\,$ correspondiente siguiente los siguientes pasos:

Calcular $k= M'/M\,$

Buscar un $m'\,$ tal que $\, m' = m * k \pmod p$ tomando en cuenta que $m'\,$ al igual que $m\,$ cumple con estar entre $0\,$ y $p-1 \,$

Tomando el peor caso, el atacante obtendrá dos textos claros (debido a la función módulo).

Desempeño

El análisis de desempeño del algoritmo ElGamal es similar al de RSA. Concretamente tenemos el siguiente análisis

Sea $\,n$ el módulo usuado en ElGamal. Los procesos de cifrado y descifrado de ElGamal por lo tanto toman tiempos de $\,O(\log n)$.