Cifrado ElGamal

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en el problema matemático del logaritmo discreto. 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 [1] y se usa en software GNU Privacy Guard, versiones recientes de PGP, y otros sistemas criptográficos. Este algoritmo no está 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 debido a la dificultad de calcular un logaritmo discreto.

El procedimiento de cifrado (y descifrado) está 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 original[editar]

Mostremos el criptosistema propuesto inicialmente por Tahar ElGamal en su artículo.

Generación de la clave[editar]

Para generar la clave, Alicia escoge un número primo p\, cualquiera tal que p - 1\, tenga un factor primo grande (esto se pide para que el problema del logaritmo discreto sea difícil [2] ). Además elige dos números aleatorios g\, (el generador) y a\, (que actuará como clave privada) tal que a \in \{ 0, \ldots, p-1 \}.

Alicia calcula el valor de K=\, g^a \pmod p. La clave pública será (g, p, K), mientras que el valor de a lo mantendrá en secreto.

Cifrado[editar]

Supongamos que Bruno tiene un texto claro que quiere enviar cifradp a Alicia. Lo primero por hacer es convertir este texto en un entero entre 1 y p-1, obteniendo un m\, (esto no es parte del cifrado, sino que es una manera de codificar estándar, conocida por todos). Luego Bruno escoge arbitrariamente un número b\in \{ 2, \ldots, p-1 \} (que mantendrá secreto) para finalmente calcular:

y_1 = g^b\,\pmod p
y_2 = K^b \, m\,\pmod p

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

Descifrado[editar]

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

y_1^{-a} y_2 \pmod p

donde  y_1^{-a} representa el inverso de  y_1^a módulo  p (que, utilizando el Pequeño teorema de Fermat puede calcularse como  y_1^{p-1-a}).

Veamos por qué esto da como resultado m:

y_1^{-a} y_2 \,= (g^b)^{-a}K^bm= g^{-ab}(g^a)^bm = (g^a)^{-b} (g^a)^b m \,= m \pmod p

Vale observar que para calcular el descifrado, es necesario conocer  a, que es justamente la clave privada de Alicia.

Ejemplo numérico[editar]

Alicia elige los valores:

p = 17\, (primo elegido al azar)
g = 3\, (generador)
a = 6\, (llave privada elegida al azar)
K = g^a\,\pmod p = 3^6\,\pmod {17} = 15\, (llave pública)

La llave pública será \,(17,3,15) y la privada \,(6).

Bruno tiene el texto claro \,m = 9. Escoge un \,b = 5 aleatorio:

y_1 =\, g^b \pmod p =\, 3^5 \pmod {17} =\, 5
\,y_2 =\, K^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).

El texto cifrado puede ser descifrado por Alicia 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.

Generalización[editar]

Lo único que se utiliza de la congruencia módulo  p es que el conjunto  (\Z/p)^\times=\{x\in\Z: 1\leq x<p\} forma un grupo con las operaciones módulo  p y que en dicho grupo el problema del logaritmo discreto resulta difícil.

Por lo tanto, puede cambiarse en este criptosistema al grupo (\Z/p)^\times por cualquier otro grupo G en el que el logaritmo discreto sea complicado.

Por ejemplo, resulta bastante efectivo utilizar como grupo una curva elíptica sobre \Z/p (véase Criptografía de curva elíptica), ya que no se conoce un algoritmo de tiempo subexponencial capaz de resolver el problema del logaritmo discreto en curvas elípticas en general. [3]

Análisis[editar]

Efectividad[editar]

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 (cuando trabajamos módulo un primo) es subexponencial con una complejidad de λ = 1/3, la misma que la de factorizar dos números primos, y por tanto, no es accesible de realizar tal tarea en números grandes en un tiempo razonable. El logaritmo discreto es aún más difícil si trabajamos en otros grupos (como por ejemplo, curvas elípticas).

Véase Récords en logaritmos discretos para una muestra de las posibilidades que da la computación actual a la hora de resolver este problema.

Maleabilidad[editar]

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[editar]

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).

Referencias[editar]

  1. ElGamal, Taher (1985). «A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms». IEEE TRANSACTIONS ON INFORMATION THEORY 31 (4): 469–472. Consultado el 19 de junio de 2015. 
  2. Koblitz, Neal (2006). «Discrete log». A course in number theory and cryptography (en inglés) (segunda edición). Springer. pp. 102–103. ISBN 0-387-94293-9. 
  3. Qureshi, Claudio (2012). Criptografía de Curvas Elípticas y Logaritmo Discreto. Implementación de Autoreducibilidad aleatoria. (Maestría). Universidad de la República. Consultado el 19 de junio de 2015.