Welcome, guest | Sign In | My Account | Store | Cart
```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 _ in xrange(s - 1):
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:
private = 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(privkey.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()

def 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, True)
p = decode(h, privkey, True)
print('-' * 20)
print(repr(msg))
print(h)
print(repr(p))

if __name__ == '__main__':
main()
```

#### Diff to Previous Revision

```--- revision 1 2013-12-26 15:39:24
+++ revision 2 2013-12-26 15:40:17
@@ -3,6 +3,7 @@
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
@@ -13,7 +14,7 @@
# 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
+        s, d = s + 1, d >> 1
assert 2 ** s * d == neg_one and d & 1

for i in xrange(k):
@@ -21,7 +22,7 @@
x = pow(a, d, n)
if x in (1, neg_one):
continue
-        for r in xrange(1, s):
+        for _ in xrange(s - 1):
x = x ** 2 % n
if x == 1:
return False
@@ -31,14 +32,17 @@
return False
return True

-def randprime(N=10**8):
+
+def randprime(n=10 ** 8):
p = 1
while not is_prime(p):
-        p = randrange(N)
+        p = randrange(n)
return p

+
def multinv(modulus, value):
-    '''Multiplicative inverse in a given modulus
+    """
+        Multiplicative inverse in a given modulus

>>> multinv(191, 138)
18
@@ -46,8 +50,7 @@
186
>>> multinv(120, 23)
47
-
-    '''
+    """
# http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
x, lastx = 0, 1
a, b = modulus, value
@@ -60,11 +63,13 @@
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.
+
+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).

@@ -74,13 +79,14 @@
>>> plain = pow(coded, *privkey)
>>> assert msg == plain

-    '''
+    """
# http://en.wikipedia.org/wiki/RSA
-    prime1 = randprime(N)
-    prime2 = randprime(N)
+    prime1 = randprime(n)
+    prime2 = randprime(n)
composite = prime1 * prime2
totient = (prime1 - 1) * (prime2 - 1)
if public is None:
+        private = None
while True:
private = randrange(totient)
if gcd(private, totient) == 1:
@@ -92,6 +98,7 @@
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
@@ -99,17 +106,19 @@
bmsg = msg.encode()
result = []
for start in range(0, len(bmsg), chunksize):
-        chunk = bmsg[start:start+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)
+        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))
+    chunksize = int(log(privkey.modulus, 256))
outchunk = chunksize + 1
outfmt = '%%0%dx' % (chunksize * 2,)
result = []
@@ -118,20 +127,24 @@
coded = int(hexlify(bcoded), 16)
plain = pow(coded, *privkey)
chunk = unhexlify((outfmt % plain).encode())
-        if verbose: print('Decode:', chunksize, chunk, plain, coded, bcoded)
+        if verbose:
+            print('Decode:', chunksize, chunk, plain, coded, bcoded)
result.append(chunk)
return b''.join(result).rstrip(b'\x00').decode()

-if __name__ == '__main__':
+def 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)
+    h = encode(msg, pubkey, True)
+    p = decode(h, privkey, True)
print('-' * 20)
print(repr(msg))
print(h)
print(repr(p))
+
+if __name__ == '__main__':
+    main()
```