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 lo que lleva a que la seguridad del mismo dependa de la dificultad de calcular logaritmos discretos en .

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 cualquiera tal que 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 (el generador) y (que actuará como clave privada) tal que .

Alicia calcula el valor de . La clave pública será , mientras que el valor de lo mantendrá en secreto.

Cifrado[editar]

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

El mensaje cifrado final corresponde a la tupla

Descifrado[editar]

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

donde representa el inverso de módulo (que, utilizando el Pequeño teorema de Fermat puede calcularse como ).

Veamos por qué esto da como resultado :

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

Ejemplo numérico[editar]

Alicia elige los valores:

(primo elegido al azar)
(generador)
(llave privada elegida al azar)
(llave pública)

La llave pública será y la privada .

Bruce tiene el texto claro . Escoge un aleatorio:

.

El texto cifrado está compuesto por la tupla .

El texto cifrado puede ser descifrado por Alicia utilizando la llave privada .

Utilizando el Pequeño Teorema de Fermat:

.

Generalización[editar]

Lo único que se utiliza de la congruencia módulo es que el conjunto forma un grupo con las operaciones módulo y que en dicho grupo el problema del logaritmo discreto resulta difícil.

Por lo tanto, puede cambiarse en este criptosistema al grupo por cualquier otro grupo en el que el logaritmo discreto sea complicado.

Por ejemplo, resulta bastante efectivo utilizar como grupo una curva elíptica sobre (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 del texto claro (ambos conocidos). Sabiendo esto se puede llegar a que el texto cifrado corresponde al texto plano . Si ahora la persona que cifró el mensaje anterior genera otro texto cifrado (utilizando el mismo con el que cifró anteriormente) el adversario debería ser capaz de llegar al texto plano correspondiente siguiente los siguientes pasos:

Calcular
Buscar un tal que tomando en cuenta que al igual que cumple con estar entre y
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 el módulo usado en ElGamal. Los procesos de cifrado y descifrado de ElGamal por lo tanto toman tiempos de .

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.