# -*- 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
Last modified: 2014/02/12 11:20