Welcome, guest | Sign In | My Account | Store | Cart

Simple code to create and use public/private keypairs. Accompanied by a rudimentary encoder.

Python, 137 lines
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 from fractions import gcd from random import randrange from collections import namedtuple from math import log from binascii import hexlify, unhexlify def is_prime(n, k=30): # http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test if n <= 3: return n == 2 or n == 3 neg_one = n - 1 # write n-1 as 2^s*d where d is odd s, d = 0, neg_one while not d & 1: s, d = s+1, d>>1 assert 2 ** s * d == neg_one and d & 1 for i in xrange(k): a = randrange(2, neg_one) x = pow(a, d, n) if x in (1, neg_one): continue for r in xrange(1, s): x = x ** 2 % n if x == 1: return False if x == neg_one: break else: return False return True def randprime(N=10**8): p = 1 while not is_prime(p): p = randrange(N) return p def multinv(modulus, value): '''Multiplicative inverse in a given modulus >>> multinv(191, 138) 18 >>> multinv(191, 38) 186 >>> multinv(120, 23) 47 ''' # http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm x, lastx = 0, 1 a, b = modulus, value while b: a, q, b = b, a // b, a % b x, lastx = lastx - q * x, x result = (1 - lastx * modulus) // value if result < 0: result += modulus assert 0 <= result < modulus and value * result % modulus == 1 return result KeyPair = namedtuple('KeyPair', 'public private') Key = namedtuple('Key', 'exponent modulus') def keygen(N, public=None): ''' Generate public and private keys from primes up to N. Optionally, specify the public key exponent (65537 is popular choice). >>> pubkey, privkey = keygen(2**64) >>> msg = 123456789012345 >>> coded = pow(msg, *pubkey) >>> plain = pow(coded, *privkey) >>> assert msg == plain ''' # http://en.wikipedia.org/wiki/RSA prime1 = randprime(N) prime2 = randprime(N) composite = prime1 * prime2 totient = (prime1 - 1) * (prime2 - 1) if public is None: while True: private = randrange(totient) if gcd(private, totient) == 1: break public = multinv(totient, private) else: private = multinv(totient, public) assert public * private % totient == gcd(public, totient) == gcd(private, totient) == 1 assert pow(pow(1234567, public, composite), private, composite) == 1234567 return KeyPair(Key(public, composite), Key(private, composite)) def encode(msg, pubkey, verbose=False): chunksize = int(log(pubkey.modulus, 256)) outchunk = chunksize + 1 outfmt = '%%0%dx' % (outchunk * 2,) bmsg = msg.encode() result = [] for start in range(0, len(bmsg), chunksize): chunk = bmsg[start:start+chunksize] chunk += b'\x00' * (chunksize - len(chunk)) plain = int(hexlify(chunk), 16) coded = pow(plain, *pubkey) bcoded = unhexlify((outfmt % coded).encode()) if verbose: print('Encode:', chunksize, chunk, plain, coded, bcoded) result.append(bcoded) return b''.join(result) def decode(bcipher, privkey, verbose=False): chunksize = int(log(pubkey.modulus, 256)) outchunk = chunksize + 1 outfmt = '%%0%dx' % (chunksize * 2,) result = [] for start in range(0, len(bcipher), outchunk): bcoded = bcipher[start: start + outchunk] coded = int(hexlify(bcoded), 16) plain = pow(coded, *privkey) chunk = unhexlify((outfmt % plain).encode()) if verbose: print('Decode:', chunksize, chunk, plain, coded, bcoded) result.append(chunk) return b''.join(result).rstrip(b'\x00').decode() if __name__ == '__main__': import doctest print(doctest.testmod()) pubkey, privkey = keygen(2 ** 64) msg = 'the quick brown fox jumped over the lazy dog' h = encode(msg, pubkey, 1) p = decode(h, privkey, 1) print('-' * 20) print(repr(msg)) print(h) print(repr(p))

Working RSA crypto functions with a rudimentary interface. Currently, it is good enough to generate valid key/pairs and demonstrate the algorithm in a way that makes it easy to run experiments and to learn how it works.

This is an early draft. Future updates will include: