Cifrado ElGamal 1

Cifrado ElGamalEl procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en problemasmatemticos de logaritmos discretos. Es un algoritmo de criptografa asimtrica basado en la idea de Diffie-Hellmany 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, yotros sistemas criptogrficos. Este algoritmo no esta bajo ninguna patente lo que lo hace de uso libre.La seguridad del algoritmo se basa en la suposicin que la funcin utilizada es de un slo sentido y la dificultad decalcular un logaritmo discreto.El procedimiento de cifrado (y descifrado) esta basado en clculos sobre un grupo cclico cualquiera lo que llevaa que la seguridad del mismo dependa de la dificultad de calcular logaritmos discretos en .

El algoritmoElGamal consta de tres componentes: el generador de claves, el algoritmo de cifrado, y el de descifrado. Acontinuacin se describe el algoritmo utilizando el grupo multiplicativo de enteros mdulo p.

Creacin de llaves de cifradoPara generar un par de llaves, se escoge un nmero primo cualquiera tal que tenga un factor primo grande.Adems se eligen dos nmeros aleatorios (el generador) y (que actuar como clave privada) tal que

.Se calcula entonces el valor de .

por lo tanto ser la llave pblica a utilizar.

En este caso se refiere al operador de mdulo de y es la llave privada mientras que los valores ,y son pblicos.

Nota

La definicin es correcta. Sin embargo, desde un punto de vista de seguridad, esta definicintiene casos que no hacen sentido ya que y constituyen casos que no brindan seguridad alguna yhacen que el cifrado no funcione. Dado esto se considera preferentemente que .

Ejemplo numricoLos valores:

(primo elegido al azar)(generador)(llave privada elegida al azar)

(llave pblica)forman la llave pblica y la privada

Cifrado ElGamal 2

CifradoSuponiendo que se tiene un texto claro que necesita ser cifrado. Lo primero por hacer es convertir este texto en unelemento de obteniendo un . Luego se escoge arbitrariamente un nmero tal que para finalmente calcular:

El mensaje cifrado final corresponde a la tupla

Ejemplo numricoDado un texto y se escoge un aleatorio:

.El texto cifrado est compuesto por la tupla .

DescifradoPara descifrar se tiene que realizar el siguiente clculo:

donde La resolucin de este problema queda entonces de la siguiente manera

(utilizamos elpequeo teorema de Fermat)

Tambin existe una expresin ms simplificada para el mismo proceso:

Ejemplo numrico

El texto cifrado cifrado con la llave pblica puedeser descifrado utilizando la llave privada .Utilizando el Pequeo Teorema de Fermat:

.Utilizando la Expresin Simplificada:

.

Anlisis

EfectividadHasta el momento el algoritmo ElGamal de cifrado/descifrado puede ser considerado un algoritmo efectivo.Un adversario con la habilidad de calcular logaritmos discretos podra ser capaz de romper un cifrado ElGamal. Sinembargo, en la actualidad, el algoritmo de computacin de logaritmos discretos es subexponencial con unacomplejidad de = 1/3 , la misma que la de factorizar dos nmeros primos, y por tanto, incapaz de realizar tal tareaen nmeros grandes en un tiempo razonable.

Cifrado ElGamal 3

MaleabilidadSin embargo existe un caso en que este algoritmo se vuelve maleable. Esto significa que bajo un ataque especfico laseguridad de ElGamal se puede quebrar. Este ataque usa el hecho de tener el texto cifrado del textoclaro (ambos conocidos). Sabiendo esto se puede llegar a que el texto cifrado correspondeal 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 debera 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 conestar entre y Tomando el peor caso, el atacante obtendr dos textos claros (debido a la funcin mdulo).

DesempeoEl anlisis de desempeo del algoritmo ElGamal es similar al de RSA. Concretamente tenemos el siguiente anlisis

Sea el mdulo usuado en ElGamal. Los procesos de cifrado y descifrado de ElGamal por lo tanto tomantiempos de .

Fuentes y contribuyentes del artculo 4

Fuentes y contribuyentes del artculoCifrado ElGamal Fuente: http://es.wikipedia.org/w/index.php?oldid=51605341 Contribuyentes: Alexav8, Death Master, Ferkte, Kronoman, Lucianobello, Mjcuevas, Nanovapor9, T4nn0,Varano, Waeswaes, 11 ediciones annimas

LicenciaCreative Commons Attribution-Share Alike 3.0 Unported//creativecommons.org/licenses/by-sa/3.0/

Cifrado ElGamalEl algoritmo Creacin de llaves de cifrado Nota Ejemplo numrico

CifradoEjemplo numrico

DescifradoEjemplo numrico

AnlisisEfectividadMaleabilidadDesempeo

Licencia