from Crypto.PublicKey import RSA
from base64 import b64decode
from gmpy2 import invert

def findModInverse(a, m):
    u1, u2, u3 = 1, 0, a
    v1, v2, v3 = 0, 1, m
    while v3 != 0:
        q = u3 // v3
        v1, v2, v3, u1, u2, u3 = (u1 - q * v1), (u2 - q * v2), (u3 - q * v3), v1, v2, v3
    return u1 % m

pubkey = b64decode("MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBALgR/vfjBQ0EyuIl5AE+3UrlHSgzU5yRs+pg4Lzwv9wErzHbn+rI0pHAStoOpEM3F0GeYCw7G+FRJ15klYfIez8CAwEAAQ==") #aus weak_pub
r = RSA.importKey(pubkey)
print(r.n) # 9640543689585112556450998579422564855633524831313534737934634573166750126769105229624001689064786292047232170704131903674012950145389088141063272685665087
print(r.e) # 65537
# we see that n is fairly small -> FactorDB

p = 85808933370531870609859306825598553446977355131859172055304205392849791600423
q = 112348951454229659434863381917360166800011983956305986266648870447917250083369

n = p * q
assert r.n == n, "die beiden N stimmen nicht ueberein"

e = r.e
d = findModInverse(e, (p - 1) * (q - 1))
e1 = d % (p-1)
e2 = d % (q-1)
coeff = int(invert(q, p))

print("D: ", d)
print("p: ", p)
print("q: ", q)
print("n: ", n)
print("e1: ", e1)
print("e2: ", e2)
print("coeff: ", coeff)