import random
import math

def RSA_cles():
    minPrime = 0
    maxPrime = 500
    cached_primes = [i for i in range(minPrime, maxPrime) if check_if_prime(i)]
    p = random.choice([i for i in cached_primes])
    q = random.choice([i for i in cached_primes])
    if p==q :
        RSA_cles()

    if not check_if_prime(p):
        print("Error p not prime")
        return {}
    elif not check_if_prime(q):
        print("Error q not prime")
        return {}
    else:
        try:
            n = p*q
            phi = (p-1)*(q-1)
            (e,d) = find_e_d(phi)
            keys = {}
            keys["cle_publique"] = {"e":e,"n":n}
            keys["cle_privee"] = {"d":d,"p":p,"q":q}
        except :
            keys = {'cle_publique': {'e': 115, 'n': 21389}, 'cle_privee': {'d': 2011, 'p': 73, 'q': 293}}
        return keys


def encode_private(private_key, message):
    d = private_key["d"]
    p = private_key["p"]
    q = private_key["q"]
    n = p*q
    numbers = [ord(d) for d in str(message)]
    res = ''
    for num in numbers:
        M = int(num)
        m = M**d % n
        res += str(m) + ' '
    return res

def decode_public(public_key, message):
    e = public_key["e"]
    n = public_key["n"]
    numbers = message.split()
    res = ''
    for num in numbers:
        m = int(num)
        M = m**e % n
        res += chr(M)
    return res

def encode_public(cle_publique, message):
    e = cle_publique["e"]
    n = cle_publique["n"]
    numbers = message.split()
    res = ''
    for num in numbers:
        m = int(num)
        M = m**e % n
        res += str(M) + ' '
    return res

def decode_private(cle_privee, message):
    d = cle_privee["d"]
    p = cle_privee["p"]
    q = cle_privee["q"]
    n = p*q
    numbers = message.split()
    res = ''
    for num in numbers:
        M = int(num)
        m = M**d % n
        res += str(m) + ' '
    return res


def transform_word_into_numbers(word):
    res = ''
    for char_index in range(len(word)):
        num = ord(word[char_index])
        res += str(num) + ' '
    print(word + " is written as " + res)
    return res


def transform_numbers_into_word(string_of_numbers):
    numbers = string_of_numbers.split()
    res = ''
    for num in numbers:
        char = chr(int(num))
        res += char
    print(string_of_numbers + " gives as word " + res)
    return res


def find_e_d(phi):
    i = random.randint(7,15)
    mul = phi*i+1
    divisors = get_divisors(mul)
    if len(divisors) <= 2:
        return find_e_d(phi)
    else:
        j = random.randint(2, len(divisors)-1)
        e = divisors[j]
        d = mul/e
        return (int(e),int(d))


def check_if_prime(n):
    for i in range(2, n):
        if (n % i) == 0:
            return False
    return True


def get_divisors(n):
    div = []
    i = 1
    while i <= math.sqrt(n):
        if (n % i == 0):
            if (n / i == i):
                div.append(i)
            else:
                div.append(i)
                div.append(n/i)
        i = i + 1
    return div


if __name__ == "__main__":
    keys = RSA_cles()
    print(keys)
    public = keys["cle_publique"]
    private = keys["cle_privee"]
    word = "We did IT!! "
    word_as_number = transform_word_into_numbers(word)
    message_coded = encode_public(public, word_as_number)
    message_decoded = decode_private(private, message_coded)
    number_as_word = transform_numbers_into_word(message_decoded)