I decided to write a simple RSA encryption implementation in Python, but every time I run it it prints the error IndexError: list out of range
when it's decrypting and in find_key
.
Here's the error:
p 937 q 353 n 330761 phi 329472 e 5 d 264609 Traceback (most recent call last): File "rsa.py", line 94, in print dec_rsa(b, d, n) File "rsa.py", line 88, in dec_rsa char_array.append(decrypt_byte(i, d, n)) File "rsa.py", line 77, in decrypt_byte return find_key(alpha, (c**d)%n) File "rsa.py", line 67, in find_key return [k for k, v in dic.iteritems() if v == val][0] IndexError: list index out of range
The code:
import fractions, sys, random, math
def isPrime( no ):
if no < 2: return False
if no == 2: return True
if not no&1: return False
for x in range(3, int(no**0.5)+1, 2):
if no%x == 0:
return False
return True
def primes_range(low, high):
primes = []
for i in range(high-low):
if isPrime(i+low):
primes.append(i+low)
return primes
let = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789~!@#$%^&*()_+'";:[]/<>,."
a, alpha = 2, {}
for i in let:
alpha[i] = a
a+=1
Low = 29
High = 1000
p = random.choice(primes_range(Low, High))
q = random.choice(primes_range(Low, High))
while p == q:
q = random.choice(primes_range(Low, High))
print "p ",p
print "q ",q
#p = 104729
#q = 3
p, q = int(p), int(q)
n = p*q
phi = (p-1)*(q-1)
print "n ",n
print "phi ",phi
for i in range(2, q if q>p else p):
if fractions.gcd(i, phi) == 1:
e = i
break
print "e ",e
def egcd(a,b):
u, u1 = 1, 0
v, v1 = 0, 1
while b:
q = a // b
u, u1 = u1, u - q * u1
v, v1 = v1, v - q * v1
a, b = b, a - q * b
return u, v, a
def modInverse(e, phi):
return egcd(e, phi)[0]%n
d = modInverse(e, n)
print "d ",d
def find_key(dic, val):
#print "val ",val
#print "dic ",list(dic.iteritems())
return [k for k, v in dic.iteritems() if v == val][0]
def encrypt_byte(byte, e, n):
try:
m = alpha[byte]
except:
m = int(byte)
return (m**e)%n
def decrypt_byte(c, d, n):
return find_key(alpha, (c**d)%n)
def enc_rsa(string, e, n):
char_array = []
for i in range(len(string)):
char_array.append(encrypt_byte(alpha[string[i]], e, n))
return char_array
def dec_rsa(enc_arr, d, n):
char_array = []
for i in enc_arr:
char_array.append(decrypt_byte(i, d, n))
return ''.join(char_array)
a = "hello, world"
b = enc_rsa(a, e, n)
#print b
print dec_rsa(b, d, n)
I hope you're enjoying learning Python!
A couple of things:
(1) Your isPrime is broken: it thinks 1 is prime, 2 and 3 aren't, but all of 25, 35, 121, 143, 289, 323, 529, 841, 899 are. Getting a composite will lead to problems.
(2) You also don't check to see that p != q.
(3) Your alpha[str(byte)] should be alpha[byte] (otherwise you'll get "96llo, worl5").
(4) You're taking the wrong multiplicative modular inverse. You want modInverse(e, phi(n)), not modInverse(e, n); see this worked example.
After fixing those, it seems to work for me.
The following aren't bugs, but suggestions: you should probably use pow(c,d,n) rather than (c**d)%n; for large numbers the former will be much faster. As well, if you want to turn a letter into a number, and you don't really care what number, you could use the "ord"/"chr" functions, and not even need a dictionary. In any case, you might want to swap the keys and values in your dictionary: right now your find_key might as well be using a list, as you're simply searching over all the k,v pairs until you find a match.
Hope that helps!
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With