Pastebin launched a little side project called HostCabi.net, check it out ;-)Don't like ads? PRO users don't see any ads ;-)
Guest

rsa.py

By: a guest on Nov 19th, 2010  |  syntax: Python  |  size: 3.75 KB  |  hits: 112  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #!/usr/bin/env python2.6
  2. """
  3. rsa.py
  4.  
  5. Key generation, encryption, decryption via standard RSA.
  6. http://programmingpraxis.com/2010/11/16/rsa-cryptography/
  7.  
  8. GRE, 11/19/10
  9. """
  10.  
  11. ##########################################
  12. #                                        #
  13. #            Preliminaries               #
  14. #                                        #
  15. ##########################################
  16.  
  17. import random
  18. try:
  19. # If we can use gmpy's fast procedures, we will...
  20.     import gmpy
  21.  
  22.     def prime_gen(k):
  23.         """
  24.        Prime number p in [2^(k/2-1), 2^(k/2).
  25.        """
  26.         assert k >= 1, "Sorry, need a bigger input"
  27.         p = 0
  28.         while not gmpy.is_prime(p):
  29.             p = random.randrange(pow(2, k//2-1) + 1, pow(2, k//2), 2)
  30.         return p
  31.  
  32.     def extended_euclid(a, m):
  33.         return [int(x) for x in gmpy.gcdext(a, m)]
  34.  
  35. except ImportError:
  36. # ...if we can't, we build our own.
  37.     def gcd(a, b):
  38.         while b:
  39.             a, b = b, a % b
  40.         return a
  41.  
  42.     def extended_euclid(a, b):
  43.         (x1, x2, x3) = (1, 0, a)
  44.         (y1, y2, y3) = (0, 1, b)
  45.         while (y3 != 0):
  46.             quotient = x3 / y3
  47.             tmp1 = x1 - quotient * y1
  48.             tmp2 = x2 - quotient * y2
  49.             tmp3 = x3 - quotient * y3
  50.             (x1, x2, x3) = (y1, y2, y3)
  51.             (y1, y2, y3) = (tmp1, tmp2, tmp3)
  52.         return x3, x1, x2
  53.  
  54. # Miller-Rabin primality stuff:
  55.  
  56.     def split(n):
  57.         """
  58.        Splits n into 2^s * r for an odd r; used in Miller-Rabin.
  59.        """
  60.         s = 0
  61.         while (n > 0) and (n % 2 == 0):
  62.             s += 1
  63.             n >>= 1
  64.         return (s,n)
  65.  
  66.  
  67.     def P(a,r,s,n):
  68.         """
  69.        Condition for primality in Miller-Rabin test.
  70.        """
  71.         if pow(a, r, n) == 1:
  72.             return True
  73.         elif (n - 1) in [pow(a, r*(2**j), n) for j in range(s)]:
  74.             return True
  75.         else:
  76.             return False
  77.  
  78.  
  79.     def miller_rabin(n, t):
  80.         """
  81.        Tests n for primality t times.
  82.        """
  83.         (s, r) = split(n - 1)
  84.         for i in xrange(t):
  85.             a = random.randint(2, n-1)
  86.             if not P(a, r, s, n):
  87.                 return False
  88.         return True
  89.  
  90.  
  91.     def prime_gen(k):
  92.         """
  93.        Generates an odd that passes the Miller Rabin primality test for t = 50
  94.        in the interval [2^(k-1), 2^k].
  95.        """
  96.         assert k >= 1, "Sorry, need a bigger input"
  97.         p = 0
  98.         while (p == 0):
  99.             p = random.randrange(pow(2,k//2-1) + 1, pow(2, k//2), 2)
  100.             if not miller_rabin(p, 50):
  101.                 p = 0
  102.         return p
  103.  
  104. finally:
  105. # Modular inversion
  106.     def mod_inv(a, m):
  107.         g, s, t = extended_euclid(a, m)
  108.         if g == 1:
  109.             return s % m
  110.         else:
  111.             return None
  112.  
  113. ##########################################
  114. #                                        #
  115. #              Main Work                 #
  116. #                                        #
  117. ##########################################
  118.  
  119. def key_gen(k = 32, e = prime_gen(32)):
  120.     """
  121.    Build keys for RSA
  122.    """
  123.     p = prime_gen(k)
  124.     q = prime_gen(k)
  125.     d = mod_inv(e, (p-1)*(q-1))
  126.     return p*q, d
  127.  
  128.  
  129.  
  130. def crypt(message, key, mod):
  131.     return pow(message, key, mod)
  132.  
  133.  
  134. ##########################################
  135. #                                        #
  136. #               Testing                  #
  137. #                                        #
  138. ##########################################
  139. if __name__ == '__main__':
  140.     k = 32
  141.     e = 65537
  142.     n, d = key_gen(k, e)
  143.     print "n = %s\nd = %s" % (n, d)
  144.     m = 42
  145.     print "Message m = %s" % m
  146.     c = crypt(m, e, n)
  147.     print "Encrypted c = %s" % c
  148.     m2 = crypt(c, d, n)
  149.     print "Decrypted m2 = %s" % m2