rsa.py

import numbertheory, time

def rsaKey(p, q):
	e = 65537
	phi = (p - 1) * (q - 1)
	d = numbertheory.inv(phi, e)
	
	return [e, d]
	
def rsaEnc(n, e, m):
	c = numbertheory.expm(n, m, e);
	return c
	
def rsaDec(n, d, c):
	m = numbertheory.expm(n, c, d);
	return m
	
def rsaKeyE(p, q):
	e, d = rsaKey(p, q)
	dp = d % (p - 1)
	dq = d % (q - 1)
	c2 = numbertheory.inv(q, p) # p^-1 mod q
	
	return [e, dp, dq, c2]
	
def rsaDecE(p, q, dp, dq, c2, c):
	cdp = numbertheory.expm(p, c, dp) # c^dp mod p
	cdq = numbertheory.expm(q, c, dq)
	u = ((cdq - cdp) * c2) % q

	return cdp + (u * p)

	
def rsaEncString(n, e, s):
	r, re = [], []
	si = int(s,36)
	while(si > n):
		r.append(si % n)
		si = si // n
		
	r.append(si)
	
	for i in range(0, len(r)):
		r[i] = rsaEnc(n, r[i], e)
		
	return r
	
def rsaDecString(n, d, il):
	si = 0
	i = len(il) - 1
	while i >= 0:
		si = (si * n) + rsaDec(n, il[i], d)
		i = i - 1

	return si
	

def RSAexample(p, q, e, m):
	n = p * q
	# Assume p and q to be prime
	phi = (p - 1) * (q - 1)
	
	if not (1 < e < phi) and not numbertheory.gcd(e, phi) == 1:
		print 'Invalid value for e';
		
	d = numbertheory.inv(phi, e)
	
	print 'public key is: '+`[n, e]`
	print 'private key is:'+`[p, q, phi, d]`
	
	print 'plaintext is: '+`m`
	ct = numbertheory.expm(n, m, e)
	print 'ciphertext is: '+`ct`
	pt = numbertheory.expm(n, ct, d)
	print 'plaintext is: '+`pt`

def RSAexample2(p, q, m):
	n = p * q
	e, d = rsaKey(p, q)
	print '---'
	print 'n    = '+`n`
	print 'e, d = '+`[e, d]`
	print 'p, q = '+`[p, q]`
	print 'm    = '+`m`
	c = rsaEnc(n, e, m)
	print 'c    = '+`c`
	p = rsaDec(n, d, c)
	print 'p    = '+`p`
	
def RSAexample3(p, q, s):
	n = p * q
	e, d = rsaKey(p, q)
	print '---'
	print 'n    = '+`n`
	print 'e, d = '+`[e, d]`
	print 'p, q = '+`[p, q]`
	print 's    = '+`s`
	c = rsaEncString(n, e, s)
	print 'c    = '+`c`
	p = rsaDecString(n, d, c)
	print 'p    = '+`p`

def RSAexample4(m):
	p = numbertheory.prime(128)
	q = numbertheory.prime(128)
	n = p * q
	e, dp, dq, c2 = rsaKeyE(p, q)
	print '---'
	print 'n    = '+`n`
	print 'e, dp, dq, c2 = '+`[e, dp, dq, c2]`
	print 'p, q = '+`[p, q]`
	print 'm    = '+`m`
	c = rsaEnc(n, e, m)
	print 'c    = '+`c`
	p = rsaDecE(p, q, dp, dq, c2, c)
	print 'p    = '+`p`

def RSAexample5(m):
	p = numbertheory.prime(128)
	q = numbertheory.prime(128)
	n = p * q
	e, dp, dq, c2 = rsaKeyE(p, q)
	print '---'
	print 'n    = '+`n`
	print 'e, dp, dq, c2 = '+`[e, dp, dq, c2]`
	print 'p, q = '+`[p, q]`
	print 'm    = '+`m`
	c = rsaEnc(n, e, m)
	print 'c    = '+`c`
	p = rsaDecE(p, q, dp, dq, c2, c)
	print 'p    = '+`p`

def RSAperf(m, b, t):
	p = numbertheory.prime(b)
	q = numbertheory.prime(b)
	n = p * q
	e, d = rsaKey(p, q)
	e, dp, dq, c2 = rsaKeyE(p, q)

	c = rsaEnc(n, e, m)

	timervalue = time.time()
	for i in range(1, t):
		rsaDec(n, d, c)
	t1 = time.time() - timervalue
	
	timervalue = time.time()
	for i in range(1, t):
		rsaDecE(p, q, dp, dq, c2, c)
	t2 = time.time() - timervalue
	
	return [t1, t2]