[vertizor]

I'm working on a simple RSA implementation and I'm pretty sure I've got it right. By that I mean, for smaller numbers, when I compute the decryption key and then use that key to encrypt an already encrypted message I get the original number I encrypted.

However for some reason when I move into the more useful territory of long integers, this stops working. I've checked that the decryption key I generate is right, that is, d*e = 1 mod z. However, taking my encrypted text C and doing C^d mod n does not yield the original number.

Code follows:

def RSAEncrypt(e,n,c):
	if c > n:
		print "Break message into smaller blocks before encrypting"
		sys.exit
	E=decToBin.modExp(c,e,n)
	return E

#This is a little non-standard for factoring, but I'm assuming the RSA modulus has only 2 factors, that is, that p and q are not pseudo primes
#and as such, n would in fact have only 2 factors (p and q)
def RSAFactor(n):
	i = 2
	k = n
	factor = [0,0]
	while i < math.sqrt(n):
		if (k % i == 0):
			k = k / i
			factor = [i,k]
			return factor #Once I find the factors, stop ... or the loop will continue, potentially for a very long time
		else:
			i += 1
	return [0,0]

#Call this function to generate the decryption key for a particular n; e is assumed to be 3
#The first output is d, the decryption exponent, the second is the passed value n
def breakCode3(n):
	factors = RSAFactor(n)
	p = factors[0]
	q = factors[1]
	z = (p - 1)*(q - 1)
	d = (2*z + 1)/3
	return [d,n]

#Performs the fast algorithm for modular exponentiation where b is the base, e the exponent, and m the modulus
def modExp(b,e,m):
	x,i = 1,0
	power = b % m
	k = decToBin(e)
	length = math.floor(math.log10(k))
	while(i <= length):
		if(k%10 == 1):
			x = (x*power)%m
		power = (power*power)%m
		k=math.floor(k/10)
		i += 1
	return x

#Returns a string of ones and zeros that, read as binary, represent the input n
def decToBin(n):
	i,k = 0,0
	while n > 0:
		x = n % 2
		n = n - x
		n = n / 2
		k = k + x*pow(10,i)
		i = i + 1
	return k

I think that's everything I'm using for this problem. I would be very surprised if this was far from maximally efficient, and feel free to suggest efficiency improvements ... however I am primarily concerned with the apparent failure of RSAEncrypt for large n.

The way you use this code: first, for a give n you wish to break, run breakCode3(n) - this will give you the d exponent. Then to verify your success, run RSAEncrypt with 3 for e, your n for n, and the number you wish to encrypt for c. Then run RSAEncrypt again with d for the exponent, n for n, and the result of the previous encryption for c. You should get back the input you gave for the first encryption.

Some numbers to try - n = 55 is a valid number to use, with factors 5 and 11. 347*257=89179=n is another one that fits the requirements. The specific question for our assignment was to find d for n=140319361139007984335332069. As such, please do not post the value of d for this n.

To reiterate ... this code correctly encrypts and decrypts "messages" for the 2 smaller n given, but for the large one which was assigned, although my d is verifiable, the encryption/decryption does not work. I am of course using values for my message which are less than the modulus.

Thanks in advance!

[vertizor]

As I have received no responses, I condensed and rewrote my code slightly, to make my specific problem more obvious. All code can now be placed in the same file. When you run the file, what you SHOULD get is 3 sets of numbers. Each set contains a pair, the decryption exponent and the modulus, also known as the decryption key. The next number in each set is the number to be encrypted, followed by the number as encrypted with the key {e=3, n=the second number in the decryption key above}. The last number in the set should be the same as the number to be encrypted - it is calculated by "encrypting" the number above it using d and n from the printed decryption key.

My problem is that while this works exactly right for the first 2 examples, it generates the wrong decrytion for the last one, which suggests to me some python problem with large numbers. Is there a library I can import to solve the problem? Keep in mind I'm working strictly with integers here.

Thanks! (Code follows) - Note that the 3rd set of numbers will take from 5 to maybe as much as 30 seconds to appear, depending on your system speed

Final note: If you want to test your own numbers n, a couple points. The message to encrypt must be smaller than the modulus n, or the process will leave it unrecoverable (and generate an error). n must be the product of 2 prime numbers p and q, and those numbers must have the property that p%3=2 and q%3 = 2. Future work on this code would likely include a generating function for n ... but this gets into some more technical math concepts, i.e. fast primality testing, which I haven't quite gotten to yet.

import math

def decToBin(n):
	i,k = 0,0
	while n > 0:
		x = n % 2
		n = n - x
		n = n / 2
		k = k + x*pow(10,i)
		i = i + 1
	return k

def binToDec(n):
	i,k = 0,0
	while n > 0:
		x = n % 10 #Though %10 is used, only values 0,1 will be produced
		n = n - x
		n = n / 10
		k = k + (x << i)
		i = i + 1
	return k

def modExp(b,e,m):
	x,i = 1,0
	power = b % m
	k = decToBin(e)
	length = math.floor(math.log10(k))
	while(i <= length):
		if(k%10 == 1):
			x = (x*power)%m
		power = (power*power)%m
		k=math.floor(k/10)
		i += 1
	return x

def RSAEncrypt(e,n,c):
	if c > n:
		print "Break message into smaller blocks before encrypting"
		sys.exit
	E=modExp(c,e,n)
	return E

def primeFac(n):
	i = 2
	k = n
	while i < n:
		if (k % i == 0):
			k = k / i
			print str(i)
		else:
			i += 1

def RSAFactor(n):
	i = 2
	k = n
	factor = [0,0]
	while i < math.sqrt(n):
		if (k % i == 0):
			k = k / i
			factor = [i,k]
			return factor
		else:
			i += 1
	return [0,0]

def breakCode3(n):
	factors = RSAFactor(n)
	p = factors[0]
	q = factors[1]
	z = (p - 1)*(q - 1)
	d = (2*z + 1)/3
	return [d,n]

def Euclid(a,b):
	steps = []
	while b != 0:
		r = a % b
		q = a / b
		steps.append([a,b,q,r])
		a = b
		b = r
	return [a, steps]
		
if __name__ == "__main__":
	n = 55
	k = breakCode3(n)
	print str(k)
	d = k[0]
	C = RSAEncrypt(3,n,12)
	print str(12)
	print str(C)
	M = RSAEncrypt(d,n,C)
	print str(M)
	print ""

	n = 89179
	k = breakCode3(n)
	print str(k)
	d = k[0]
	C = RSAEncrypt(3,n,1234)
	print str(1234)
	print str(C)
	M = RSAEncrypt(d,n,C)
	print str(M)
	print ""

	n = 140319361139007984335332069
	k = breakCode3(n)
	print str(k)
	d = k[0]
	C = RSAEncrypt(3,n,12345)
	print str(12345)
	print str(C)
	M = RSAEncrypt(d,n,C)
	print str(M)
	print ""

	bar = input("Waiting")

This post has been edited by vertizor: 06 November 2008 - 03:17 PM

[KYA]

I've noticed when doing Euler challenge problems that python has a hard time with large numbers ( as you mentioned) and eventually wraps around. I've this problem in multiple languages. the only suggestion that i have heard is that one has to define a larger number set. There are third party libraries for this, but I do not know the name of them off of the top of my head. Sorry i could not be of more assistance.