Sin mas espera...
¿Que es ElGamal?
El procedimiento de cifrado/descifrado ElGamal se refiere a un esquema de cifrado basado en problemas matemáticos de algoritmos 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. [wikipedia]
Ademas ElGamal comparte con RSA el uso de operaciones matematicas como el calculo de la exponenciacion modular y la generacion de numeros primos, que ya estan posteadas en la entrada correspondiente asi que ya no las incluire aqui para evitar saturar el post con informacion repetida (aunque si en el codigo fuente al final y para descargar, que ahi no molesta)
Aviso: como sabreis, esta implementacion (como toda esta serie), no se deberia usar para nada real, no solo porque es mas lento que un i286 (lo dicho, esta en python solo para que sea mas facil de entender), sino porque ademas seguro que los programas y librerias que existen cumplen las funciones que necesarias mejor y con mas seguridad
Generando claves
Para generar las claves se realizan las siguientes operaciones (he intentado mantener el mismo nombre de las variables que la Wikipedia para simplificar)
1. Se genera un numero primo (p), a ser posible con un (p-1) que al factorizarlo se obtengan numeros grandes (aqui simplemente se espera que con un p grande p-1 cumpla su condicion )
def genkeys(bitn):
p = genprime(bitn)
2. Se obtienen dos numeros aleatorios (g y a), g es el generador, parte de la clave publica, mientras que a es la clave privada, g puede ser cualquier numero (aunque se recomienda que se tomen algunas consideraciones de seguridad), mientras que a es un numero entre 0 y p-2 (aunque por seguridad se recomienda usar un numero de 2 a p-2):
g = random.randint(2**(bitn-1),2**bitn)#Esto se puede sustituir por una lectura a /dev/random, por ejemplo
a = random.randint(2,p-2)
3. La ultima variable a generar (a2 , A en la Wikipedia) es el resultado de elevar g a la potencia a, y obtener el resultado modulo p
a2 = modex(g,a,p)
Asi, la clave publica esta formada por las variables p , g y a2 , mientras que la clave privada es a
Por comodidad, la clave publica se carga en un diccionario:
public = {'p':p,'g':g,'a2':a2}
private = a
return public, private
Cifrado y descifrado
De nuevo, el cifrado y descifrado necesitaran convertir el mensaje en un numero, como las funciones ya estan en el post de RSA, no tiene sentido repetirlas
Cifrando...
1. Para cifrar, se convierte el mensaje en un numero n
def cipher(s, public):
n = msg2num(s)
2. Despues se obtiene un numero pseudo-aleatorio b entre 2 y p-2 (recordemos que p forma parte de la clave publica)
b = random.randint(2, (public ['p'] -2) )
3. Se eleva g a b modulo p, para conseguir la variable y1
y1 = modex(public ['g'], b, public['p'])
4. Lo que falta, y2 se obtiene al elevar a2 a b y multiplicarlo por n , el resultado se obtiene modulo p
... o, para evitar dejarse el procesador en la operacion, se eleva a2 a b modulo p, el resultado se multiplica por n y se hace modulo p ( esto aprovecha que hacer la operacion de exponenciacion modular es mas rapida que una exponenciacion normal )
y2 = modex(public ['a2'], b, public['p'])
y2 = ( y2 * n ) % public ['p']
El mensaje cifrado son las variables y1 y y2
return (y1,y2)
Descifrando...
Para descifrar necesitaremos el mensaje cifrado, la clave privada y la publica (al contrario de RSA, que no necesita la clave publica)
1. Recuperamos el numero que corresponde al texto elevando y1 a p - 1 - a , multiplicando el resultado por y2 y obteniendo todo modulo p
... o con exponenciacion modular haciendo y1 elevado a p - 1 - a modulo p, multiplicado por y2, y con el resultado modulo p
def decipher(n, public, private):
d = modex(n[0], public['p'] -1 -private, public['p'])
d = (d * n[1]) % public ['p']
2. Solo queda volver a convertir el numero a texto
s = num2msg(d)
return s
Y ya esta :D, el codigo fuente esta aqui [ elgamal.py ]
[Referencias]
http://es.wikipedia.org/wiki/ElGamal
http://en.wikipedia.org/wiki/ElGamal
No hay comentarios:
Publicar un comentario