GenPrivateKeyRsa

• I created this repository as a learning exercise by doing the HackTheBox machine called Charon.
• In this challenge, we had to generate a private key from a weak RSA public key to read a signed message that contains a passphrase.

Theory Behind RSA Keys

• RSA (Rivest-Shamir-Adleman) is one of the first public-key cryptosystems and is widely used for secure data transmission.
• The security of RSA relies on the practical difficulty of factorizing the product of two large prime numbers, the factoring problem.
• RSA keys are generated by selecting two large prime numbers and multiplying them to get a modulus.
• The public key consists of this modulus and an exponent, while the private key is derived from the same modulus and a different exponent.
• The security of RSA comes from the difficulty of factorizing the modulus back into its prime components.

# Compute the modulus n
n = p * q
print(f"Modulus (n): {n}")

# Compute the private exponent d
d = modinv(e, phi)
print(f"Private Exponent (d): {d}")

Factorizing Prime Numbers

• Factorizing a number means breaking it down into its prime factors.
• For RSA, if the modulus (product of two primes) can be factorized, the entire cryptosystem can be broken.
• The strength of an RSA key is directly related to its length. Longer keys are much harder to factorize, making the encryption more secure.

def extract_factors(factordb_html):
    # Extracts the prime factors 'p' and 'q' from FactorDB.
    soup = BeautifulSoup(factordb_html, 'html.parser')
    factor_links = soup.find_all('a', href=True)
    factors = []
    
    for link in factor_links:
        if "index.php?id=" in link['href']:
            factor_id = link.text.strip()
            if factor_id.isdigit():
                factors.append(int(factor_id))
    
    if len(factors) < 2:
        raise Exception("Could not extract both p and q from FactorDB.")
    
    return factors[0], factors[1]

• In this function, the code queries FactorDB to retrieve the prime factors p and q of the modulus n.

Euclid's Algorithm

• Euclid's algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers, which is crucial in the process of generating RSA keys.
• The algorithm is based on the principle that the GCD of two numbers also divides their difference.

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)

• In the code above, the egcd function recursively computes the GCD and the coefficients x and y such that a*x + b*y = gcd(a, b).

Totient Function

• The totient function is a crucial part of RSA key generation. It is calculated as n = (p - 1) * (q - 1), where p and q are the prime factors of n.
• This value represents the number of integers up to n that are coprime with n.

# Compute the totient phi(n)
phi = (p - 1) * (q - 1)
print(f"Totient (phi): {phi}")

Prerequisites

Dependencies

• Install the required Python libraries:

pip install pycryptodome requests beautifulsoup4 pwntools

Public Key File

• Ensure you have a public key file in PEM format (e.g., id_rsa.pub) before running the script.

Important

If FactorDB cannot factorize the modulus, the script will not work.

Caution

Do not use this tool maliciously or on keys you do not own. It is intended for educational purposes and recovery of lost keys.