Recover RSA key from modulus and private exponent

recoverRSA.py

# recover RSA private key file using public key (n,e) and private exponent d
# python recover.py | openssl asn1parse -genconf - -out key.der

from math import gcd

# example Private-Key (512 bit, 2 primes)
modulus=0x00bacb716af4a701ea525c1fc45c7798598a966432a44a347d53054c691bd5a7c60fe717b5f55de46ea8afd1525a4b08b098b7eb0f51d58daf690ae85fcb9254b9
publicExponent=0x10001
privateExponent=0x217051f9679a8e09387d2d62a57af356f42c3ffba0d577d80788a74919a681c5f02b3e8422e79737fd9aff15046a91509788023aad60c39492ceddb301f0bcd1

# calculate x such that (x*e) mod m == 1 (see cryptography.io RSAPublicKey)
def modinv(e, m):
    x1, x2 = 1, 0
    a, b = e, m
    while b > 0:
        q, r = divmod(a, b)
        xn = x1 - q * x2
        a, b, x1, x2 = b, r, x2, xn
    return x1 % m

# find factor p from n,d,e (see https://nostarch.com/seriouscrypto, ch10 RSA):
def factor(n,d,e):
    kphi = d*e - 1 # k * phi(n)
    # calculate t such that k * phi(n) = 2^s * t, for some s 
    t = kphi
    while t % 2 == 0:
        t = divmod(t, 2)[0]
    # calculate a and k such that (a^k)^2 = 1 mod n,
    for a in range(2,100,2):
        k = t
        while k < kphi:
            x = pow(a, k, n)
            # check if we found a solution:
            if x != 1 and x != (n - 1) and pow(x, 2, n) == 1:
                p = gcd(x - 1, n)
                return p
            k = k*2
    raise Exception("could not find a factor")

p = factor(modulus , privateExponent, publicExponent)
# Verify prime factorisation:
q = modulus//p
assert (p*q) == modulus

# Calculate CRT params:
exp1 = privateExponent % (p - 1)
exp2 = privateExponent % (q - 1)
coeff = modinv(q,p)

print(f"""
asn1=SEQUENCE:private_key
[private_key]
version=INTEGER:0
modulus=INTEGER:{modulus}
publicExponent=INTEGER:{publicExponent}
privateExponent=INTEGER:{privateExponent}
prime1=INTEGER:{p}
prime2=INTEGER:{q}
exponent1=INTEGER:{exp1}
exponent2=INTEGER:{exp2}
coefficient=INTEGER:{coeff}
""")