TryHackMe Breaking RSA—Writeup

Welcome back to another write-up! In this post, I’ll be walking you through my detailed, step-by-step approach to solving the “Breaking RSA” challenge on TryHackMe. We’ll cover not only the exact commands and techniques I used, but also the reasoning and math behind each step, so you’ll gain a deeper understanding of how RSA can be attacked in practice.

Let's dive in!!

Question 1: How many services are running on the box?

For this, we will use Nmap to determine the running services

nmap 10.10.74.37

It has 2 open ports, ssh and http.

Question 2: What is the name of the hidden directory on the web server? (without leading '/')

For this question, we will use Gobuster to enumerate the directories in the server.

gobuster dir -u http://10.10.74.37/ -w /usr/share/wordlists/dirbuster/directory-list-2.3-medium.txt -t 50

Question 3: What is the length of the discovered RSA key? (in bits)

Now let's navigate to /development .

Within the /development directory, we can spot two files—a public key and a log.txt. Let’s start by examining the contents of log.txt.

Woah, a huge hint here. It is mentioned that the two prime numbers (p and q) are very close to each one another. I'll explain later and how to use the Fermat's factorization to break it.

Now let's check the the id_rsa.pub.

Now to extract the length of this public key, we'll just ssh-keygen for this.

ssh-keygen -l -f id_rsa.pub

Question 4: What are the last 10 digits of n? (where 'n' is the modulus for the public-private key pair) Question 5: What is the numerical difference between p and q? Question 6: What is the flag?

Now let me explain how RSA works again, xD!

The Core Idea RSA (Rivest–Shamir–Adleman) is an asymmetric encryption algorithm.

• Asymmetric means it uses two keys:

  • Public key → used to encrypt data.

  • Private key → used to decrypt data.

• Its security relies on the mathematical difficulty of factoring very large numbers (the product of two huge primes).

Key Generation (The Math Behind It)

1. Choose two large primes:

   • $p$ and $q$ (random large prime numbers).

   • Compute $n = p \times q$.

   • $n$ is called the modulus and is part of both public and private keys.

2. Compute Euler’s totient:

   • $\varphi(n) = (p-1)(q-1)$.

   • This represents how many numbers are relatively prime to $n$.

3. Choose public exponent e:

   • A number such that $1 < e < \varphi(n), \quad \gcd(e, \varphi(n)) = 1$.

   • Common choice is e=65537 (fast and secure).

4. Compute private exponent d:

   • $d \equiv e^{-1} \pmod{\varphi(n)}$

   • Meaning: $d \times e \equiv 1 \pmod{\varphi(n)}$

   • $d$ is the modular inverse of $e$.

Encryption If a message $m$ (as a number) is less than $n$:

$$c \equiv m^e \pmod{n}$$

Where:

• $c$ = ciphertext

• $e,n$ = public key

Decryption To recover the original message:

$$m \equiv c^d \pmod{n}$$

Where:

• $d,n$ = private key

This works because of number theory (Euler’s theorem):

$$(m^e)^d \equiv m^{ed} \equiv m \pmod{n}$$

Now that we know RSA, how can we break it? Here's our plan.

Note: If we know $p$ and $q$, computing $d$ is easy.

Let's factor the $n$

• Factoring $n$ is the hard part of RSA.

• Fermat’s Factorization works well if $p$ and $q$ are close.

Idea:

$$n = p \cdot q = a^2 - b^2 = (a - b)(a + b)$$

• Find integers $a$ and $b$ so that $a^2 - n = b^2$

• Then $p = a - b, \quad q = a + b$

Algorithm:

1. Start with $a = \lceil \sqrt{n} \rceil$

2. Compute $b^2 = a^2 - n$

3. Check if $b^2$ is a perfect square

4. If not, increment $a$ and repeat

Once $b^2$ is a perfect square, we have $p$ and $q$.

Compute the Private Key Once we know $p$ and $q$:

1. Compute $\varphi(n) = (p-1)(q-1)$

2. Solve $d \cdot e \equiv 1 \mod \varphi(n)$

   • This is the modular inverse of $e$ modulo $\varphi(n)$

$$d = e^{-1} \mod \varphi(n)$$

Script Planning Now we know the steps we need in the code:

1. Load the public key from file → get $n$ and $e$

2. Factor n using Fermat’s method → get $p$ and $q$

3. Compute d using modular inverse

4. Construct the private key using $(n, e, d, p, q)$

5. Save private key as a PEM file

Here's the full Python code I've made to get the Modulus, the numerical difference between p and q, and to generate the private key.

import gmpy2
from Crypto.PublicKey import RSA
from pathlib import Path
from typing import Tuple

class RSAKeyRecovery:
    """Class for recovering RSA private keys via Fermat's factorization."""
    def __init__(self, pubkey_path: str):
        self.pubkey_path = Path(pubkey_path)
        self.public_key = self._load_public_key()
        self.n = self.public_key.n
        self.e = self.public_key.e
        self.p, self.q = None, None
        self.d = None

    def _load_public_key(self) -> RSA.RsaKey:
        """Load an RSA public key from file."""
        with self.pubkey_path.open("r") as f:
            return RSA.import_key(f.read())

    @staticmethod
    def fermat_decomposition(n: int) -> Tuple[int, int]:
        """
        Fermat's Factorization Method.
        Efficient if p and q are close to each other.
        """
        a = gmpy2.isqrt(n) + 1
        b2 = gmpy2.square(a) - n
        while not gmpy2.is_square(b2):
            a += 1
            b2 = gmpy2.square(a) - n
        p = a + gmpy2.isqrt(b2)
        q = a - gmpy2.isqrt(b2)
        return int(p), int(q)

    @staticmethod
    def compute_private_exponent(p: int, q: int, e: int) -> int:
        """Compute RSA private exponent (d) from primes and public exponent."""
        phi = (p - 1) * (q - 1)
        return int(gmpy2.invert(e, phi))

    def recover_primes_and_private_exponent(self) -> None:
        """Recover p, q, and d from the modulus and public exponent."""
        self.p, self.q = self.fermat_decomposition(self.n)
        self.d = self.compute_private_exponent(self.p, self.q, self.e)

    def export_private_key(self, output_file: str = "id_rsa") -> None:
        """Construct and export the recovered private key in PEM format."""
        rsa_key = RSA.construct((self.n, self.e, self.d, self.p, self.q))
        Path(output_file).write_bytes(rsa_key.export_key("PEM"))

    def display_summary(self) -> None:
        print(f"\033[96mModulus (n):\033[0m {self.n}")
        print(f"\033[96mPublic Exponent (e):\033[0m {self.e}")
        print(f"\033[93mPrime p:\033[0m {self.p}")
        print(f"\033[93mPrime q:\033[0m {self.q}")
        print(f"\033[93m|p - q|:\033[0m {abs(self.p - self.q)}")
        print(f"\033[96mPrivate Exponent (d):\033[0m {self.d}")
        print("\033[92m[+] Private key successfully generated.\033[0m")

if __name__ == "__main__":
    recovery = RSAKeyRecovery("id_rsa.pub")
    recovery.recover_primes_and_private_exponent()
    recovery.display_summary()
    recovery.export_private_key("id_rsa")

Here's the output

Now a new file has been generated, which is the private key!

All we need to do is to set the permission of our id_rsa .

chmod 600 id_rsa

Next thing that we will do is to use the private key to login via SSH.

ssh root@10.10.74.37 -i id_rsa

Here's the result

We've successfully logged in!!!

We've successfully broken the RSA!!!

RSA remains one of the cornerstones of modern cryptography, and when implemented correctly with sufficiently large key sizes and carefully chosen parameters, it is extremely secure. However, as demonstrated, weaknesses in how the primes ppp and qqq are generated—such as choosing values that are too close together—can make the system vulnerable to classical factorization methods like Fermat’s. This highlights that the strength of RSA does not lie solely in the algorithm itself, but in the proper generation and management of keys. Used correctly, RSA is resilient; misused, it can be broken.