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) >>>
(N, public=None)
| 64 | Key = namedtuple('Key', 'exponent modulus') |
| 65 | |
| 66 | def keygen(N, public=None): |
| 67 | ''' Generate public and private keys from primes up to N. |
| 68 | |
| 69 | Optionally, specify the public key exponent (65537 is popular choice). |
| 70 | |
| 71 | >>> pubkey, privkey = keygen(2**64) |
| 72 | >>> msg = 123456789012345 |
| 73 | >>> coded = pow(msg, *pubkey) |
| 74 | >>> plain = pow(coded, *privkey) |
| 75 | >>> assert msg == plain |
| 76 | |
| 77 | ''' |
| 78 | # http://en.wikipedia.org/wiki/RSA |
| 79 | prime1 = randprime(N) |
| 80 | prime2 = randprime(N) |
| 81 | composite = prime1 * prime2 |
| 82 | totient = (prime1 - 1) * (prime2 - 1) |
| 83 | if public is None: |
| 84 | while True: |
| 85 | private = randrange(totient) |
| 86 | if gcd(private, totient) == 1: |
| 87 | break |
| 88 | public = multinv(totient, private) |
| 89 | else: |
| 90 | private = multinv(totient, public) |
| 91 | assert public * private % totient == gcd(public, totient) == gcd(private, totient) == 1 |
| 92 | assert pow(pow(1234567, public, composite), private, composite) == 1234567 |
| 93 | return KeyPair(Key(public, composite), Key(private, composite)) |
| 94 | |
| 95 | def encode(msg, pubkey, verbose=False): |
| 96 | chunksize = int(log(pubkey.modulus, 256)) |