Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# rsa.py

By: a guest on Nov 19th, 2010  |  syntax: Python  |  size: 3.75 KB  |  views: 140  |  expires: Never
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
clone this paste RAW Paste Data
Top