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))