Take the 2-minute tour ×

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
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):
    return primes

let = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789~!@#$%^&*()_+'";:[]/<>,."
a, alpha = 2, {}
for i in let:
    alpha[i] = a

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
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
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())

def encrypt_byte(byte, e, n):
        m = alpha[byte]
        m = int(byte)
    return (m**e)%n

def decrypt_byte(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)
share|improve this question
As a warning -- what you've implemented here is not RSA in any meaningful sense of the name. Don't use this code, or any derivative of this code, for security purposes. In fact, don't use it at all. –  duskwuff Jun 11 '11 at 5:06
I'm just fussing around –  tekknolagi Jun 11 '11 at 5:07

1 Answer 1

up vote 4 down vote accepted

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!

share|improve this answer
1. Fixed the prime function, thank you for that tip. 2. I check now that p != q 3. Fixed 4. I changed that to modInverse(e, phi) 5. It still gives an IndexError. 6. I will now re-post the code –  tekknolagi Jun 11 '11 at 6:15
(4) You didn't change it in the code, you merely changed the name of the second variable in the function modInverse from n to phi. You're still calling it with 'd = modInverse(e, n)'. This means that "phi" inside the modInverse function is still n. –  DSM Jun 11 '11 at 9:59
Oh I'm so stupid... Thank you very much! I was way too tired :) –  tekknolagi Jun 11 '11 at 17:03

Your Answer


