RSA encryption in python

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 d开发者_如何学Cecrypt_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!

---

The implementation of RSA can be further simplified as follows:

1.Choose two different large primes, here for the sake of simplicity let's choose p=937, q=353, as done in the example

2.Compute n = p*q

3.Compute Euler Totient φ(n) ≡ (p-1)*(q-1)

4.Choose the public key e as coprime with φ(n), for simplicity, let's choose e=5, which is a prime

5.Compute the private key d, s.t. d*e ≡ 1 (mod φ(n)), using the multiplicative inverse algorithm (extended Euclidean) from here:

Compute multiplicative inverse of a modulo n

# solution t to a*t ≡ 1 (mod n) 

def multiplicative_inverse(a, n):

    t, newt = 0, 1
    r, newr = n, a

    while newr != 0:
        q = r // newr
        t, newt = newt, t - q * newt
        r, newr = newr, r - q * newr

    if t < 0:
        t = t + n

    return t

Python code for steps 1-5:

p, q = 937, 353 # use large primes here
n = p*q
φ = (p-1)*(q-1)
e = 5 # choose public key e as a prime, s.t., gcd(φ, e) = 1
d = multiplicative_inverse(e, φ) # private key d
print(d)
# 131789

6.Encrypt the message (plaintext) with the receiver's public key (e) at sender's end

7.Decrypt the ciphertext received at the receiver end with his private key (d)

The following code shows how the encryption / decryption can be done:

def rsa_encrypt(plain_text, e, n):
    # ideally we should convert the plain text to byte array and 
    # then to a big integer which should be encrypted, but here for the sake of 
    # simplicity character-by-character encryption is done, which will be slow in practice
    cipher_text = [ord(x)**e % n for x in plain_text]        
    return cipher_text

def rsa_decrypt(cipher_text, d, n):
    decoded_text = ''.join([chr(x**d % n) for x in cipher_text])
    return decoded_text 

Now, let's use the above functions for encryption / decryption:

plain_text = 'Hello world'
cipher_text = rsa_encrypt(plain_text, e, n)
print(cipher_text)
# [296543, 169726, 215626, 215626, 293167, 147571, 122732, 293167, 217253, 215626, 102687]
decoded_text = rsa_decrypt(cipher_text, d, n)
decoded_text 
# Hello world