title: RSA encryption in python
body: <p>I decided to write a simple RSA encryption implementation in Python, but every time I run it it prints the error <code>IndexError: list out of range</code> when it's decrypting and in <code>find_key</code>.</p>
  
  <p>Here's the error:</p>
  
  <pre>
  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
  </pre>
  
  <p>The code:</p>
  
  <pre><code>import fractions, sys, random, math
  
  def isPrime( no ):
      if no &lt; 2: return False
      if no == 2: return True
      if not no&amp;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~!@#$%^&amp;*()_+'";:[]/&lt;&gt;,."
  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&gt;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)
  </code></pre>