Instantly share code, notes, and snippets.

# TylerJFisher/maths.pySecret Created May 2, 2017

What would you like to do?
 import random import gmpy2 def random_prime(k): r = gmpy2.mpz(random.getrandbits(k)) p = gmpy2.next_prime(r) if p.bit_length() != k: return random_prime(k=k) return gmpy2.next_prime(r) def is_prime(p): return gmpy2.is_bpsw_prp(p) def pow_mod(g, e, n): g, e, n = map(lambda x: gmpy2.mpz(int(x)), [g, e, n]) if e < 0: return pow_mod(modinv(g, n), -e, n) return int(pow(g, e, n)) def egcd(a, b): if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y) def modinv(a, m): a, m = map(lambda x: gmpy2.mpz(int(x)), [a, m]) return gmpy2.invert(a, m)
 # -*- coding: utf-8 -*- from cryptography.hazmat.backends import default_backend from cryptography.hazmat.primitives.asymmetric.rsa import ( RSAPrivateNumbers, RSAPublicNumbers ) import collections import random import gmpy2 import maths import abc class AbstractRSA(object): __metaclass__ = abc.ABCMeta def __init__(self, e, k, **kwargs): self.k = k self.keypair = self.generate_keypair(k=k, e=e, **kwargs) self.private = self.keypair.private_key(default_backend()) self.public = self.private.public_key() public = self.public.public_numbers() self.n = public.n self.e = public.e private = self.private.private_numbers() self.d = private.d self.dmp1 = private.dmp1 self.dmq1 = private.dmq1 self.iqmp = private.iqmp self.p = private.p self.q = private.q @abc.abstractmethod def generate_keypair(): """ Performs RSA asymmetric key generation """ @staticmethod def wrap_keypair(e, n, p, q, d): """ Wraps RSA public/private numbers within cryptography.io wrappers """ dmp1 = d % (p-1) dmq1 = d % (q-1) iqmp = maths.pow_mod(q, -1, p) e, n, p, q, d, dmp1, dmq1, iqmp = map(lambda x: int(x), [ e, n, p, q, d, dmp1, dmq1, iqmp ]) public_numbers = RSAPublicNumbers(e=e, n=n) return RSAPrivateNumbers(p=p, q=q, d=d, dmp1=dmp1, dmq1=dmq1, iqmp=iqmp, public_numbers=public_numbers) class RSA(AbstractRSA): def __init__(self, *args, **kwargs): super(RSA, self).__init__(*args, **kwargs) @staticmethod def generate_keypair(k, e): """ An honest RSA key generation routine """ bits = k//2 p = maths.random_prime(bits) q = maths.random_prime(bits) n = p * q phi = (p-1) * (q-1) if gmpy2.gcd(e, phi) == 1 and n.bit_length() == k: d = gmpy2.invert(e, phi) return RSA.wrap_keypair(e, n, p, q, d) else: return RSA.generate_keypair(k=k, e=e) class RSA_BDH(AbstractRSA): def __init(self, *args, **kwargs): super(RSA_BDH, self).__init__(*args, **kwargs) @staticmethod def manufacturer_setup(k, e): primes = { 128: 0x00a139b2b9ae4ba773adb3d801147fbbd, 256: 0x00bf039ffabdf9777cf570d2a3a63a0fd342bae05c8fead01ef43615b0efad4b3b, 384: 0x0091693be7349cbc0cda81710778e07eeaf4f3f97e9d989db91b0bf30895ac4948ca074aec3c9fc3c0ce5de168b5593f4b, 512: 0x009dff83d8f36665a0ba443057b66286af3f3afe2c4b352cd089628d155adfa5a4849fc547114b2f78f4cc4be159f99b5df9aa71c9b6992d93d53513a3c1e1412b, 768: 0x00fd0a79406689b651ff88f476669cb27c0dad08180865de0291f5168b9a20a770e56908110fc7f155bc7f10561966aa10bc5f28742a8f4c8ce3ce49aed77f8bbeaddd620b167356183d504fe5e44381f81abdb086dca88e80dd38b046488f36e3, 1024: 0x00c6abdc68da6d788eaa911cbd0339439fcac04edd8db285c849a79f08d44cf3e39527ee7b0d9ad219e3c2024f970656093b6c8a14880bcaa9645c65398847fed0af7927b2959c7ee2dd09395bc8690367e9993c46c69903fe59e842e9b6e07a08b85f3fc2ba9f90012fea1c7b04aa4e81054bf4a403d8d0214b40210649562393 } assert k/2 in primes, "Invalid key size: %d. Valid key sizes are: %s" % (k, map(lambda k: str(k), primes.keys())) r = primes[k//2] g = 2 x = random.randint(0, r-2) Y = maths.pow_mod(g, x, r) w = random.randint(0, r-2) return r, g, x, Y, w @staticmethod def recover_private_key(e, n, g, x, r, w): """ Implements the key escrow capability for RSA-BDH """ e, n, g, x, r, w = map(lambda X: gmpy2.mpz(int(X)), [e, n, g, x, r, w]) p = maths.pow_mod(n, x+1, r) if n % p != 0: p = (p * maths.pow_mod(g, w, r)) % r if n % p != 0: p = maths.pow_mod(n * g, w * (1 + x), r) if n % p != 0: p= maths.pow_mod(n * g, -w * (1 + x), r) * maths.pow_mod(g, w, r) % r q = n//p d = gmpy2.invert(e, (p-1) * (q-1)) return AbstractRSA.wrap_keypair(e=e, n=n, p=p, q=q, d=d) @staticmethod def generate_keypair(k, e, g=None, w=None, Y=None, r=None): """ An RSA-BDH key generation routine """ while True: cache = collections.defaultdict(dict) c = random.randint(0, r - 2) Ycr1 = maths.pow_mod(Y, c, r) Ycr2 = maths.pow_mod(Y, -c, r) for t1 in [0, 1]: p = gmpy2.mpz((maths.pow_mod(g, c + w * t1, r) * Ycr1) % r) if not (p.bit_length() == k//2 and gmpy2.is_bpsw_prp(p)): continue for t2 in [0, 1]: q = cache.get(t2, (maths.pow_mod(g, (-w) * t2, r) * Ycr2) % r) n = p * q if n.bit_length() == k and gmpy2.is_bpsw_prp(q): lcm = gmpy2.lcm(p-1, q-1) if gmpy2.gcd(e, lcm) == 1: d = gmpy2.invert(e, lcm) return AbstractRSA.wrap_keypair(e, n, p, q, d) else: return RSA_BDH.generate_keypair(k, e, g=g, w=w, Y=Y, r=r)