Algoritmo de cifrado ElGamal

El cifrado ElGamal es un criptosistema de clave pública. Utiliza cifrado de clave asimétrica para comunicarse entre dos partes y cifrar el mensaje. 
Este criptosistema se basa en la dificultad de encontrar logaritmos discretos en un grupo cíclico, es decir, aunque sepamos g ^a y g ^k , es extremadamente difícil calcular g ^ak .
Idea del criptosistema ElGamal 
Supongamos que Alice quiere comunicarse con Bob. 
 

1. Bob genera claves públicas y privadas: 
   • Bob elige un número q muy grande y un grupo cíclico F _q .
   • Del grupo cíclico F _q , elige cualquier elemento g y
     un elemento a tal que mcd(a, q) = 1.
   • Luego calcula h = g ^a .
   • Bob publica F , h = g ^a , q y g como su clave pública y retiene a como clave privada.
2. Alice cifra los datos usando la clave pública de Bob: 
   • Alice selecciona un elemento k del grupo cíclico F 
     tal que mcd(k, q) = 1.
   • Luego calcula p = g ^k y s = h ^k = g ^ak.
   • Ella multiplica s con M.
   • Luego envía (p, M*s) = (g ^k , M*s).
3. Bob descifra el mensaje: 
   • Bob calcula s ^′ = p ^a = g ^ak .
   • Divide M*s por s ^′ para obtener M como s = s ^′ .

A continuación se muestra la implementación del criptosistema ElGamal en Python 
 

# Python program to illustrate ElGamal encryption
 
import random
from math import pow
 
a = random.randint(2, 10)
 
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    elif a % b == 0:
        return b;
    else:
        return gcd(b, a % b)
 
# Generating large random numbers
def gen_key(q):
 
    key = random.randint(pow(10, 20), q)
    while gcd(q, key) != 1:
        key = random.randint(pow(10, 20), q)
 
    return key
 
# Modular exponentiation
def power(a, b, c):
    x = 1
    y = a
 
    while b > 0:
        if b % 2 != 0:
            x = (x * y) % c;
        y = (y * y) % c
        b = int(b / 2)
 
    return x % c
 
# Asymmetric encryption
def encrypt(msg, q, h, g):
 
    en_msg = []
 
    k = gen_key(q)# Private key for sender
    s = power(h, k, q)
    p = power(g, k, q)
     
    for i in range(0, len(msg)):
        en_msg.append(msg[i])
 
    print("g^k used : ", p)
    print("g^ak used : ", s)
    for i in range(0, len(en_msg)):
        en_msg[i] = s * ord(en_msg[i])
 
    return en_msg, p
 
def decrypt(en_msg, p, key, q):
 
    dr_msg = []
    h = power(p, key, q)
    for i in range(0, len(en_msg)):
        dr_msg.append(chr(int(en_msg[i]/h)))
         
    return dr_msg
 
# Driver code
def main():
 
    msg = 'encryption'
    print("Original Message :", msg)
 
    q = random.randint(pow(10, 20), pow(10, 50))
    g = random.randint(2, q)
 
    key = gen_key(q)# Private key for receiver
    h = power(g, key, q)
    print("g used : ", g)
    print("g^a used : ", h)
 
    en_msg, p = encrypt(msg, q, h, g)
    dr_msg = decrypt(en_msg, p, key, q)
    dmsg = ''.join(dr_msg)
    print("Decrypted Message :", dmsg);
 
 
if __name__ == '__main__':
    main()

Salida de muestra: 
 

Original Message : encryption
g used :  5860696954522417707188952371547944035333315907890
g^a used :  4711309755639364289552454834506215144653958055252
g^k used :  12475188089503227615789015740709091911412567126782
g^ak used :  39448787632167136161153337226654906357756740068295
Decrypted Message : encryption

En este criptosistema, el mensaje original M se enmascara multiplicándole g ^ak . Para quitar la máscara, se da una pista en forma de g ^k . A menos que alguien conozca a , no podrá recuperar M . Esto se debe a que encontrar logaritmos discretos en un grupo cíclico es difícil y simplificar sabiendo g ^a y g ^k no es lo suficientemente bueno para calcular g ^ak .