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)

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. — user149341
– user149341, Commented Jun 11, 2011 at 5:06

DSM · Accepted Answer · 2011-06-11 05:27:15Z

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!

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
(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.
Oh I'm so stupid... Thank you very much! I was way too tired :)

Sandipan Dey · Accepted Answer · 2022-01-08 01:02:52Z

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

Collectives™ on Stack Overflow

RSA encryption in python

2 Answers 2

3 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Related