Cifrado ElGamal
El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en el problema matemático del logaritmo 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 solo 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
Mostremos el criptosistema propuesto inicialmente por Tahar ElGamal en su artículo.
Para generar la clave, Alicia escoge un número primo
cualquiera tal que el logaritmo discreto no es soluble en un tiempo asumible en
Lo primero por hacer es convertir este texto en un entero m entre 1 y
Esto no es parte del cifrado, sino que es una manera de codificar estándar, conocida por todos.
Por el pequeño teorema de Fermat se demuestra que
aleatorio entre 2 y p-1 Bruce calcula Por lo que el texto cifrado es
y el Pequeño Teorema de Fermat: Veamos una aplicación más real del algoritmo: Alicia elige los valores: Alicia calcula Por tanto la clave pública será
aleatorio entre 2 y p-1 Bruce calcula Por lo que el texto cifrado es
: Lo único que se utiliza de la congruencia 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 ejemplo, resulta bastante efectivo utilizar como grupo una curva elíptica sobre
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.
Existe un caso en que este algoritmo se vuelve maleable.
Esto implica que bajo un ataque específico la seguridad de ElGamal se puede quebrar.
Sabiendo esto se puede llegar a que el texto cifrado
con el que cifró anteriormente) el adversario debería ser capaz de llegar al texto plano
En efecto si: entonces: Este tipo de cifrado permite probar el conocimiento del texto original cifrado sin tener que revelarlo (esta propiedad en inglés se llama plaintext aware).
entonces si P conoce b, entonces se puede recuperar m calculando
Por tanto el protocolo prueba que P conoce el texto original m.[5] El Protocolo de Chaum-Pedersen puede ser usado para que un texto cifrado
[6] El Protocolo de Cramer-Damgard-Schoenmakers permite demostrar que un texto cifrado con ElGamal es el correspondiente a un texto claro de entre los posibles (los textos claros posibles tienen que estar predeterminados) sin revelar cual es.
Esto es muy útil para votaciones electrónicas que usan este tipo de cifrado.
