Create a gist now

Instantly share code, notes, and snippets.

@TylerJFisher /maths.py Secret
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment