import math
import random
import sympy

# extended_gcd, modinv:
# https://rosettacode.org/wiki/Modular_inverse#Iteration_and_error-handling


def extended_gcd(aa, bb):
    lastremainder, remainder = abs(aa), abs(bb)
    x, lastx, y, lasty = 0, 1, 1, 0
    while remainder:
        lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
        x, lastx = lastx - quotient * x, x
        y, lasty = lasty - quotient * y, y
    return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)


def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise ValueError
    return x % m


# prime computing based on the following code
# https://trinket.io/python3/2fb69ab246


key_size = 16


def get_primes():
    prime1 = 0
    prime2 = 0
    while prime1 == prime2 or (prime1 * prime2) > 2**key_size:
        prime1 = sympy.randprime(3, 2**key_size/2)
        prime2 = sympy.randprime(3, 2**key_size/2)
    return (prime1, prime2)


# build a list of all pseudo primes
def get_all_pseudo_primes():
    pp = []
    for n in range(3, phi - 1):
        if math.gcd(phi, n) == 1:
            pp.append(n)
    return pp


def encrypt(message):
    ca = []
    for c in message:
       ca.append((ord(c)**e) % r)
    return ca


def decrypt(cipher_message):
    message = ''
    for c in cipher_message:
        message += chr((c**d) % r)
    return message


def hexdump(cipher_array):
    return ''.join(format(x, '02x') for x in cipher_array)


# prime1, prime2
p, q = get_primes()

# RSA modulus
r = p * q

# Euler's totient
phi = (p-1) * (q-1)

pseudo_primes = get_all_pseudo_primes()
# print('number of pseudo primes :', len(pseudo_primes))

# choose one of the pseudo primes by random as public exponent
e = random.choice(pseudo_primes)
# compute the private exponent
d = modinv(e, phi)

# print data in use
print('prime1           (p)   :', p)
print('prime2           (q)   :', q)
print('RSA modulus      (r)   :', r)
print("Euler's totient  (phi) :", phi)
print('public exponent  (e)   :', e)
print('private exponent (d)   :', d)
print("Private Key            : (" + str(r) + "," + str(d) + ")")
print("Public Key             : (" + str(r) + "," + str(e) + ")")
print('')

plain_text = "Don't Panic!"

cipher_array = encrypt(plain_text)
message = decrypt(cipher_array)

print('plain text :', plain_text)
print('encrypt    :', hexdump(cipher_array))
print('decrypt    :', message)