elgamal.py

#!/usr/bin/env python
# -*- vim: set sts=4 sw=4 fdm=marker: -*-

# Please put in your name and id number here
# Name:
# Matrikelnummer:

from collections import defaultdict
from functools import reduce

# --- PLEASE DO NOT CHANGE ANYTHING IN BETWEEN --- {{{

from sympy import primefactors, mod_inverse
from sympy.ntheory.modular import crt, solve_congruence

# DHKE public parameters
# Prime p
p = 11805217175667888115840516101006175607012549121531103
# Generator g
alpha = 5
# Order q
q = 11805217175667888115840516101006175607012549121531102

beta =  9199619193614813944648934614225402098247011523470872
kE = [5556958563193803433213344180576973929988203758920760, 6861072396780250038242486407600260502333347140916040, 2564146758969534959481992307553703030082342686810533]
m = [11053503936645671400425915245474777903372650256818722, 1390148566721466699697920165366343613955144699455472, 7132940762731222288957462143663778248297205067472059]

#decodes integers to the original message bytes
##from: https://github.com/RyanRiddle/elgamal/blob/master/elgamal.py
def decode(aiPlaintext, iNumBits):
    bytes_array = []
    k = iNumBits//8
    for num in aiPlaintext:
        for i in range(k):
            temp = num
            for j in range(i+1, k):
                temp = temp % (2**(8*j))
            letter = temp // (2**(8*i))
            bytes_array.append(letter)
            num = num - (letter*(2**(8*i)))
    decodedText = bytearray(b for b in bytes_array).decode('utf-8')
    return decodedText

# --- PLEASE DO NOT CHANGE ANYTHING IN BETWEEN --- }}}

# EEA {{{
def eea(r0, r1):
    if r0 <= r1:
        r0, r1 = r1, r0

    r = [r0, r1, 0]
    s = [1, 0, 0]
    t = [0, 1, 0]

    i = 2
    while r[(i + 2) % 3] != 0:
        r[i % 3] = r[(i + 1) % 3] % r[(i + 2) % 3]

        q = (r[(i + 1) % 3] - r[i % 3]) // r[(i + 2) % 3]

        s[i % 3] = s[(i + 1) % 3] - q * s[(i + 2) % 3]
        t[i % 3] = t[(i + 1) % 3] - q * t[(i + 2) % 3]

        i += 1
    return (s[(i + 1) % 3] % r1, t[(i + 1) % 3] % r0, r[(i + 1) % 3])
# }}}

# Square Multiply {{{
def square_multiply(b, e, m):
    l = len(bin(e)[2:])
    return reduce(lambda x, y: x * (x * b if (e & (1 << (l - 1 - y))) else x) % m, range(l), 1)
# }}}

# Exercise c)
def find_prime_factors(j):
    i, factors = 2, defaultdict(int)
    def multiples(i):
        nonlocal j
        while j % i == 0:
            j //= i
            factors[i] += 1
    while i * i <= j:
        if j % i == 0:
            multiples(i)
        i += 1
    if j > 1:
        multiples(j)
    return factors

# all([check_prime_factors(i + 1) for i in range(100000)]) == True
def check_prime_factors(j):
    return reduce(lambda x, y: x * y[0] ** y[1], find_prime_factors(j).items(), 1) == j

# Exercise d)
def calculate_subgrp_congruences(pub, pi):
    # I'm not sure whether we're allowed to use sympy.discrete_log for this or not.
    # We can't use baby step giant step, since `p` is too large, but bruteforcing this
    # works perfectly fine since in our case the discrete logarithm is always fairly
    # small.
    def brute_dlog(p, value, base):
        return next(i for i in range(1, p) if square_multiply(base, i, p) == value)

    order = q
    q_, e = pi[0], pi[1]
    a = square_multiply(alpha, order // q_, p)

    def f(x, j):
        # In 3.63 this was:
        # g = g * alpha ^ {l_{j - 1} * q ^ {j - 1}}
        # But since we're accumulating into `x` directly, we can do it this way.
        g = square_multiply(alpha, x, p)
        b = square_multiply(pub * eea(g, p)[1], order // q_ ** (j + 1), p)
        return brute_dlog(p, b, a) * q_ ** j

    return reduce(f, range(e), 0)

# Exercise e)
def solve_crt(dlogs, factors):
    def fn(y):
        ai, (a, e) = y
        ni = a ** e
        Ni = q // ni
        Mi = eea(Ni, ni)[0]
        return Ni * (ai * Mi % ni)
    return sum(map(fn, zip(dlogs, factors))) % q

# Exercise f)
def decrypt(key):
    print(decode([y * eea(square_multiply(k_e, key, p), p)[1] % p for y, k_e in zip(m, kE)], 168))

def main():
    factors = find_prime_factors(q).items()
    dlogs = [calculate_subgrp_congruences(beta, f) for f in factors]

    d = solve_crt(dlogs, factors)
    decrypt(d)

if __name__ == "__main__":
    main()