SHOW:
|
|
- or go back to the newest paste.
| 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 |
