How to crack a 4096 RSA private key

import gmpy2
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric.rsa import rsa_crt_dmp1,rsa_crt_dmq1, rsa_crt_iqmp, RSAPrivateNumbers, RSAPublicNumbers
from cryptography.hazmat.primitives.serialization import Encoding, PrivateFormat, NoEncryption
from cryptography import x509
from cryptography.hazmat.primitives.serialization import load_pem_private_key
from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

rootCA_cert_pem = b'-----BEGIN CERTIFICATE-----\n\
MIIFcTCCA1mgAwIBAgIIKHPI3kXlIHEwDQYJKoZIhvcNAQENBQAwRjELMAkGA1UE\
BhMCREUxGjAYBgNVBAoMEVNvbWVfT3JnYW5pemF0aW9uMRswGQYDVQQDExJNYXJj\
byBTdGllZ2VsbWFpZXIwHhcNMjMwMjA4MTI0NTAwWhcNMzMwMjA4MTI0NTAwWjBG\
MQswCQYDVQQGEwJERTEaMBgGA1UECgwRU29tZV9Pcmdhbml6YXRpb24xGzAZBgNV\
BAMTEk1hcmNvIFN0aWVnZWxtYWllcjCCAiIwDQYJKoZIhvcNAQEBBQADggIPADCC\
AgoCggIBAM32Y07HDEe6hYMO5iX9LOhFh14hhiffA6KEmIYZUP0F8SREGCs8EnSt\
sNnQ7EEFge8Ka7EGjD13uaTb39MPYK+zobiK+3oP6ZgNsEhydDY9JeXy17asVh+e\
Mp2yrEQsyTTiQ86pJo6XE6PpEZdGjxMjdSt9n50ydqKIVXJ+v0M3Szm98ZymjQxq\
5qGgJOtmO6KVUYczYdqYetBLZvT9zvzQmFL/lynSveGMfJxNVroUEDpZdUw91nXF\
c4htiixMzMk3u859OhJm5SXvNrWOVhcokWEZIRJIrReR2pMr6Qp6qoIIlJWDH5MA\
gNP8z6ytBHKCAaKNn8vvcm/8NoE8VXRNj5HbcN+Q7UuIytWJs77Ea8iK56xfi0Nc\
0fITRGeiKrDvtmbHUzuBrceadehuZjl97MJo2qr59wZiH383xqYhGCZQGLIpXIEt\
0nweKchuQfWnwaiSZMKIGWcLZhOGSsAU+mPkS28J2Cm4QSyq8WR2v5ANoAlO7zAe\
cR5fVB+l38rThcBZZZjGrBGshwo2cIp0T1o5LjkddwFrL3ZoVjO9j3Xd+RUwPabK\
NC4JqGQUvSeJcXJ7wz1DSvfTSPDZhxApWtsVfNc7dDtvRoSfVAqnAbtx1ShPNlsw\
EUnWT5pEQyebJy0K0QCFlxSY/kbw/DTgVhHyqxZEjuMRGbAvpYBrAgMBAAGjYzBh\
MA8GA1UdEwEB/wQFMAMBAf8wHQYDVR0OBBYEFPrQA9VIbDTIu28JqXaLiB2EKiJT\
MB8GA1UdIwQYMBaAFPrQA9VIbDTIu28JqXaLiB2EKiJTMA4GA1UdDwEB/wQEAwIB\
BjANBgkqhkiG9w0BAQ0FAAOCAgEAG4cutTc2EGNoOW+J0IHD0eXJ1QiMgnEBpVGg\
VYYmshyQZhFmZPzDjyGRS4Xobl3/cZiiTwYfpkpbgIyB9HTIdG/YLDGTCtO8cJmq\
wAmtEA4CFpMRcQHMMM56TG73q+hNlf0QwAT4+7gk+Bcxd5GlOr1C+XHdwaRU92Kg\
EGgDQ3pIKAmLPSVSj317g8aPnc++P//A7yJ2lC1D+Si3i3+fi33DHh1kS7Fy5FE5\
PLcll7kW06W6q7oEbkDOS+2fUxV/3hdvBizrm4goVY5PjWQjbf+9PSwgt257ag4p\
dihW5yInQkf1UpQ+sfMQIInkkQDYPIIfRD031pRdeOnMgef/0uNPsNmSXO9pU1cj\
8pll8IZNUaw9u63u+yANnG6bf3DHVOh8lzeLKEdrk2YcgTRXPW157x5jX7RE2d8Y\
IwE8nfIOTEqxRB4hbGVx4LWRFwxwpZ2XZ9u2a72kG0pdDu9AfvBt8slS1rRl9a/U\
fmcUa+wVokhOdGuzpwo+Z8J9rgO4cxSlOV4GtW9s8bFUlSxQY0/dhkVX9VIfsjlc\
iPnyAj5nXaXob9Xrkrfgw/eQT6T1GaPepIepgGWhMPPiFc8I/nsk8YhzR4v7qxXz\
r2cKANf9YWvhEfTzRZNBCHKQgD1iN//s5HxbsLC8xiCNJTkNPUcGkAzSbEURKGAs\
opoKuec=\n\
-----END CERTIFICATE-----'

rootCA_cert = x509.load_pem_x509_certificate(rootCA_cert_pem, default_backend())
public_key = rootCA_cert.public_key()
n = public_key.public_numbers().n
e = public_key.public_numbers().e

def fermat_factor(n):
    assert n % 2 != 0
    a = gmpy2.isqrt(n)
    b2 = gmpy2.square(a) - n
    while not gmpy2.is_square(b2):
    
        a = a + 1
        b2 = gmpy2.square(a) - n
        p = a + gmpy2.isqrt(b2)
        q = a - gmpy2.isqrt(b2)
        
    return int(p), int(q)
def get_private_exponent(p,q):

    def gcd(a, b):
        while a != 0:
            a, b = b % a, a
        return b

    def findModInverse(a, m):
        if gcd(a, m) != 1:
            return None
        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
    d = findModInverse(e, (p - 1) * (q - 1))
    return d

def get_RSAPrivateKey(p,q,d,e):
    iqmp = rsa_crt_iqmp(p,q)
    dmp1 = rsa_crt_dmp1(d,p)
    dmq1 = rsa_crt_dmq1(d,q)
    public_numers = RSAPublicNumbers(e,n)
    private_numers = RSAPrivateNumbers(p,q,d,dmp1,dmq1,iqmp,public_numers)
    private_key = private_numers.private_key()
    private_key_pem = private_key.private_bytes(Encoding.PEM, PrivateFormat.TraditionalOpenSSL, NoEncryption())
    print(private_key_pem.decode())
    return(private_key_pem)

if __name__ == "__main__":
    (p, q) = fermat_factor(n)
    d = get_private_exponent(p,q)
    private_key_hacked = get_RSAPrivateKey(p,q,d,e)

    msg = b"Hello World!"
    
    signature = load_pem_private_key(private_key_hacked,None).sign(msg,padding.PSS(padding.MGF1(hashes.SHA256()),padding.PSS.MAX_LENGTH), hashes.SHA256())
    public_key = x509.load_pem_x509_certificate(rootCA_cert_pem).public_key()
    
    try:
        public_key.verify(signature,msg,padding.PSS(padding.MGF1(hashes.SHA256()),padding.PSS.MAX_LENGTH), hashes.SHA256())
        print("Signature verification sucessfull")
    except:
        print("Signature verification not sucessfull")