# Rozdział 8. - Algorytm ElGamal  

import random 
from math import pow

a = random.randint(2, 10) 

# Obliczanie NWD
def gcd(a, b): 
    if a < b: 
       return gcd(b, a) 
    elif a % b == 0: 
       return b; 
    else: 
       return gcd(b, a % b) 

# Generowanie dużych liczb losowych
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 

# Obliczanie potęg
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 

# Szyfrowanie wiadomości
def encrypt(msg, q, h, g): 

    en_msg = [] 

    k = gen_key(q)# Klucz prywatny nadawcy
    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: ", p) 
    print("g^ak: ", s) 
    for i in range(0, len(en_msg)): 
       en_msg[i] = s * ord(en_msg[i]) 

    return en_msg, p 

# Odszyfrowywanie wiadomości
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 


def main(): 
    
    msg = 'Nie pozwól naszym wrogom ustalić naszej pozycji.'
    print("Oryginalna wiadomość:", msg)
    print()
    
    q = random.randint(pow(10, 20), pow(10, 50)) 
    g = random.randint(2, q) 

    key = gen_key(q)# Klucz prywatny odbiorcy
    h = power(g, key, q) 
    print("g: ", g) 
    print("g^a: ", h) 

    en_msg, p = encrypt(msg, q, h, g) 
    dr_msg = decrypt(en_msg, p, key, q) 

    dmsg = ''.join(dr_msg) 
    print()
    print("Zaszyfrowana wiadomość:", en_msg)
    print()
    print("Odszyfrowana wiadomość:", dmsg); 
    print()


if __name__ == '__main__': 
    main() 


