Python script to crack weak RSA, using Fermat's Factorization Method

crackRSA.py

#!/usr/bin/env python

# Automated by Suman Roy
# Training by TryHackMe : https://tryhackme.com/room/breakrsa
# Video Tutorial Djalil Ayed : https://www.youtube.com/watch?v=pafx20wTBvI

import base64
import struct
from os import chmod
from sys import exit
from gmpy2 import isqrt
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
import argparse

class RSAData:
    def __init__(self,P=None,Q=None,N=None,e=None,output=None) -> None:
        self.p=P
        self.q=Q
        self.n=N
        self.e=e if e is not None else 65337
        self.output = output if output is not None else 'id_rsa.private'
        pass
    
    def generatePrivateKey(self):
        # Example prime factors of n (replace with actual values)
        p = int(self.p) # Your prime number p here
        q = int(self.q) # Your prime number q here
        e = 65537  # Commonly used public exponent

        # Calculate the necessary components for the private key
        n = p * q
        phi = (p - 1) * (q - 1)
        d = pow(e, -1, phi)  # Calculate the modular inverse of e modulo phi

        # Create the private key object
        private_key = rsa.RSAPrivateNumbers(
            p=p,
            q=q,
            d=d,
            dmp1=d % (p-1),
            dmq1=d % (q-1),
            iqmp=pow(q, -1, p),
            public_numbers=rsa.RSAPublicNumbers(e=e, n=n)
        ).private_key(default_backend())

        # Serialize the private key to PEM format
        pem = private_key.private_bytes(
            encoding=serialization.Encoding.PEM,
            format=serialization.PrivateFormat.TraditionalOpenSSL,
            encryption_algorithm=serialization.NoEncryption()
        )

        # Write the PEM to a file
        with open(self.output, "wb") as f:
            f.write(pem)

        print(f"Saving Private Key\t\t: {self.output}")
        mode=0o600
        chmod(self.output,mode=mode)
        

def decodePubKey(filePath):
    with open(filePath, 'r') as f:
        keyData = f.read().strip().split(None, 2)[1]
    keyBytes = base64.b64decode(keyData)

    parts = []
    while keyBytes:
        # Read the length of the data
        dlen = struct.unpack('>I', keyBytes[:4])[0]

        # Extract the data chunk
        data, keyBytes = keyBytes[4:4+dlen], keyBytes[4+dlen:]
        parts.append(data)

    # The modulus is in the third part for RSA (ssh-rsa)
    # Convert from bytes to a number
    modulus = int.from_bytes(parts[2], byteorder='big')
    return modulus

def factorize(modulus):
    if (modulus&1) == 0:
        return (modulus/2,2)
    
    # isqrt returns the integer square root of n
    a = isqrt(modulus)
    
    # if n is a perfect square the factors will be (sqrt(n),sqrt(n))
    if a*a==modulus:
        return a,a
    
    while True:
        a=a+1
        bsq=a*a-modulus
        b=isqrt(bsq)
        if b*b==bsq:
            break
        
    return a+b,a-b
    

if __name__=='__main__':
    try:
        parser=argparse.ArgumentParser(description='Cracking the RSA',epilog="""Automated by Suman Roy""")
        parser.add_argument("--file","-f",dest="filehandler",required=True,help='Pass the Public Key File, eg : id_rsa.pub')
        parser.add_argument("--output","-o",dest="output",required=False,help='Output Name for Private Key, eg : id_rsa')
        args=parser.parse_args()
        if args.filehandler:
            # First get the modulus from RSA Public Key
            modulus=decodePubKey(filePath=args.filehandler)
            p,q=factorize(modulus=modulus)
            if p and q:
                print(f"Last 10 Digits of Modulus\t: {str(modulus)[-10:]}")
                pass
            else:
                print("Didn't Get the P and Q Value :(")
                exit(0)
            print(f"Difference\t\t\t: {p-q}")
            rsaData=RSAData(P=p,Q=q) if args.output is None else RSAData(P=p,Q=q,output=args.output)
            rsaData.generatePrivateKey()
            exit(0)
        else:
            print('No Public Key Found!')
            exit(1)
    except Exception as e:
        print(f'Error\t\t\t:\t{e}')
        exit(1)
    except KeyboardInterrupt:
        exit(0)

id_rsa.pub

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDrZh8oe8Q8j6kt26IZ906kZ7XyJ3sFCVczs1Gqe8w7ZgU+XGL2vpSD100andPQMwDi3wMX98EvEUbTtcoM4p863C3h23iUOpmZ3Mw8z51b9DEXjPLunPnwAYxhIxdP7czKlfgUCe2n49QHuTqtGE/Gs+avjPcPrZc3VrGAuhFM4P+e4CCbd9NzMtBXrO5HoSV6PEw7NSR7sWDcAQ47cd287U8h9hIf9Paj6hXJ8oters0CkgfbuG99SVVykoVkMfiRXIpu+Ir8Fu1103Nt/cv5nJX5h/KpdQ8iXVopmQNFzNFJjU2De9lohLlUZpM81fP1cDwwGF3X52FzgZ7Y67Je56Rz/fc8JMhqqR+N5P5IyBcSJlfyCSGTfDf+DNiioRGcPFIwH+8cIv9XUe9QFKo9tVI8ElE6U80sXxUYvSg5CPcggKJy68DET2TSxO/AGczxBjSft/BHQ+vwcbGtEnWgvZqyZ49usMAfgz0t6qFp4g1hKFCutdMMvPoHb1xGw9b1FhbLEw6j9s7lMrobaRu5eRiAcIrJtv+5hqX6r6loOXpd0Ip1hH/Ykle2fFfiUfNWCcFfre2AIQ1px9pL0tg8x1NHd55edAdNY3mbk3I66nthA5a0FrKrnEgDXLVLJKPEUMwY8JhAOizdOCpb2swPwvpzO32OjjNus7tKSRe87w==