RSA Python implementation

rsa.py

# RSA Algorithm from Valentino Giudice
# This is just a toy exmaple. It's not ment for security purposes.

from random import randint

def mcd(a, b):
	if a < b:
		a, b = b, a
	x1 = 0
	x2 = 1
	y1 = 1
	y2 = 0
	q = a // b
	a, b = b, a % b
	while b != 0:
		x1, x2 = x2 - q * x1, x1
		y1, y2 = y2 - q * y1, y1
		q = a // b
		a, b = b, a % b
	return a, x1, y1

def keys(p, q):
	l = (p - 1) * (q - 1)
	div = 0
	while div != 1:
		e = randint(0, l - 1)
		div, x, y = mcd(l, e)
	n = p * q
	return (e, n), (y % l, n)

def encrypt(m, k):
	return m ** k[0] % k[1]

decrypt = encrypt

def get_prime(bits):
	def miller_rabin(m, a):
		d = 1
		for j in range(bits - 1, -1, -1):
			x = d
			d = (d * d) % m
			if d == 1 and x != 1 and x != m - 1:
				return True
			if (m >> j) % 2 == 0:
				d = (d * a) % m
		return d != 1
	prime = False
	while not prime:
		m = randint(5, 2 ** bits)
		if m % 2 == 0:
			m -= 1
		prime = True
		for i in range(20):
			a = randint(3, m - 1)
			if miller_rabin(m, a):
				prime = False
				break
	return m

k = 7
p, q = get_prime(k), get_prime(k)
print("p:", p)
print("q:", q)
n = p * q
print("n:", p * q)
m = randint(0, n - 1)
print("m:", m)
kpub, kpriv = keys(p, q)
print("kpub:", kpub)
print("kpriv:", kpriv)
c1 = encrypt(m, kpub)
print("c1:", c1)
c2 = encrypt(m, kpriv)
print("c2:", c2)
m1 = decrypt(c1, kpriv)
print("m1:", m1)
m2 = decrypt(c2, kpriv)
print("m1:", m1)