# -*- coding: utf-8 -*-

import math
import random
import datetime
import copy

def gcd(first,second):
a = int(first)
b = int(second)
q = 0
r = 0
while b > 0:
q = a // b # Floor Division - The division of operands where the result is the quotient in which the digits after the decimal point are removed
r = a - q * b
a = b
b = r
return a

def rprime(a,b):
if gcd(a,b) == 1:
return True
return False

def isprime(number):
x = abs(long(number))
if x < 2:
return False
elif x == 2:
return True
elif x % 2 == 0:
return False
else:
for n in range(3, int(x**0.5)+2, 2):
if x % n == 0:
return False
return True

# Calculate module
def calculateModule(p,q):
n = p * q
return n

# Calculate totient
def calculateTotient(p,q):
phi = (p-1)*(q-1)
return phi

# Select key e,  1<e<\phi that gcd(e,\phi)=1 . (e and phi are relatively prime)
def calculateKey(phi):
prng = random.SystemRandom(datetime.datetime.now().time())
e = prng.randint(2,phi-1)
while True:
if rprime(e,phi) == True:
break
else:
e = prng.randint(2,phi-1)
return e

# Implementation from http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

# Calculate d, 1<d<\phi that ed == 1 ? so d=e^-1 mod phi (E.g use extended euclidean algotithm e*d+phi*k = 1)
def calculateD(e,phi):
g, x, y = egcd(e, phi)
if g != 1:
return None  # modular inverse does not exist
else:
return x % phi

# Select two small prime numbers p ja q
def selectPrimes():
while True:
prime1 = long(raw_input("Input first prime number: "))
if isprime(prime1) == True:
break
print(prime1," is not a prime")

while True:
prime2 = long(raw_input("Input second prime number: "))
if isprime(prime2) == True:
if prime2 > prime1:
break
else:
print prime2, " has to be bigger than ", prime1
else:
print prime2," is not a prime"

print "Selected primes:", prime1 ,"and", prime2
return prime1,prime2

# Encrypt:  m^e mod n = c
def encrypt(message, e, n):

encrypted = pow(message, e, n)

return encrypted

# Decrypt: c^d mod n
def decrypt(encrypted, d, n):

decrypted = pow(encrypted, d, n)

return decrypted

p,q = selectPrimes()

# Calculate n=pq and phi = (p-1)(q-1)
n = calculateModule(p,q)
print 'Calculated modulus n =',n

phi = calculateTotient(p,q)
print 'Calculated totient phi =',phi

# Select key e,  1<e<\phi that gcd(e,\phi)=1 . (e and  are relatively prime)
e = calculateKey(phi)
print 'Selected e =',e

# Calculate d, 1<d<\phi that ed == 1 ? so d=e^-1 mod phi (E.g use extended euclidean algotithm ed-phi*k = 1)
d = calculateD(e,phi)
print "Calculated d=", d, "gcd(e,d) =", gcd(e,d)

# Select a message to be encrypted
message = 7

# Encrypt
encrypted = encrypt(message, e, n)
print encrypted
# Decrypt
decrypted = decrypt(encrypted, d, n)
print decrypted