RSA encryption in python

Question

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)

Romaic

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. – Tamarind

Answer 1

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!

Picasso

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 – Romaic

(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. – Picasso

Oh I'm so stupid... Thank you very much! I was way too tired :) – Romaic

Answer 2

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

Maurya