> For the complete documentation index, see [llms.txt](https://0xb0b.gitbook.io/writeups/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://0xb0b.gitbook.io/writeups/tryhackme/2024/breaking-rsa.md).

# Breaking RSA

{% embed url="<https://tryhackme.com/room/breakrsa>" %}

The following post by 0xb0b is licensed under [CC BY 4.0<img src="https://mirrors.creativecommons.org/presskit/icons/cc.svg?ref=chooser-v1" alt="" data-size="line"><img src="https://mirrors.creativecommons.org/presskit/icons/by.svg?ref=chooser-v1" alt="" data-size="line">](http://creativecommons.org/licenses/by/4.0/?ref=chooser-v1)

***

We start with a Nmap scan and find two open ports. SSH on port 22 and a web server on port 80.

<figure><img src="/files/wvF1jASbMnlGVSsVfmH6" alt=""><figcaption></figcaption></figure>

We enumerate the directories of the web server using Gobuster, but only find one directory: `development`.

<figure><img src="/files/5OlQCekZVruPxgBPe1Hp" alt=""><figcaption></figcaption></figure>

Visiting the index page doesn't reveal anything of interest.

<figure><img src="/files/rNO4kWw4Uc2KBude8YAj" alt=""><figcaption></figcaption></figure>

On the `/development` page, we find an RSA public key and a `log.txt`.

<figure><img src="/files/DhVZ32vYdj5huHVV2TZB" alt=""><figcaption></figcaption></figure>

The log only repeats what we already know from the challenge description and indicates the source of the algorithm. Furthermore, we can assume that SSH is enabled for `root`. So we already have the user when we generate the private key later and try to access SSH.

<figure><img src="/files/p5wr3oYIOPiOkxYgPU5f" alt=""><figcaption></figcaption></figure>

We know from the challenge that we are dealing with a weak RSA implementation. Our task will probably be to extract `N` and `e` from the public key in order to factorize `N`, getting `p` and `q`, and finally calculate `d`. The value `d` is the private key. If we have the parameters `N`, `e`, and `d`, we can generate the private SSH key and thus access the machine. Check out <https://en.wikipedia.org/wiki/RSA_(cryptosystem)> for a brief overview of RSA.<br>

We download the public key.

{% code title="id\_rsa.pub" overflow="wrap" %}

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

{% endcode %}

To determine the length in bits of the public we can issue the following command:

<figure><img src="/files/PD8hwgTjDu4CT7re3gPk" alt=""><figcaption></figcaption></figure>

The following source gives an example of how the parameters `N` and `e` can be taken from the public key using Python.

{% embed url="<https://stackoverflow.com/questions/42504079/how-do-you-extract-n-and-e-from-a-rsa-public-key-in-python>" %}

We just do it manually for now, but we will integrate it into the final script to answer all RSA-related questions.

```python
>>>from Crypto.PublicKey import RSA
>>>f = open("id_rsa.pub", "r")
>>>key = RSA.importKey(f.read())
>>>print key.n #displays n
>>>print key.e #displays e
```

We can extract `N` and `e`, allowing us to answer the first RSA-related question: the last 10 digits of `N`. Now things are really taking off.

<figure><img src="/files/IAiKGLozHDhHUWnzuVtz" alt=""><figcaption></figcaption></figure>

The challenge description gives us a direct indication of how we can calculate `p` and `q` in this case of this weak implementation. We have to use **Fermat's Factorization method**. If we have `p` and `q`, we can calculate the private key `d` via the inverse of `e`.&#x20;

> In a recent analysis, it is found that an organization named JackFruit is using a deprecated cryptography library to generate their RSA keys. This library is known to implement RSA poorly. The two randomly selected prime numbers (`p` and `q`) are very close to one another, making it possible for an attacker to generate the private key from the public key using Fermat's Factorization method.

A rough overview of Fermat's factorization can be found here.

{% embed url="<https://en.wikipedia.org/wiki/Fermat's_factorization_method>" %}

Here is the snippet of pseudocode we have to implement:

<figure><img src="/files/OVSbH27hmPiAdOrjRRRA" alt=""><figcaption></figcaption></figure>

To be able to calculate with the large values, we use `gmpy2`.

> gmpy2 is an optimized, C-coded Python extension module that supports fast multiple-precision arithmetic. gmpy2 is based on the original gmpy module. gmpy2 adds support for correctly rounded multiple-precision real arithmetic (using the MPFR library) and complex arithmetic (using the MPC library).

{% embed url="<https://pypi.org/project/gmpy2/>" %}

Well, we now have almost everything together; we can calculate `p` and `q` using the Fermat factorization method. Using `p`, `q`, and `e`, we can calculate `d`. Also, we are able to get the difference between `p` and `q`. Now we just have to generate the private SSH key from our integer values of the parameters `N`, `e`, and `d`. The following source gives a short how-to:

{% embed url="<https://stackoverflow.com/questions/33337904/rsa-generate-private-key-from-data-with-python>" %}

Adding this snippet to our final script, for SSH key generation:

```python
from Crypto.PublicKey import RSA

# assume d was correctly calculated
n = 1234....L
e = 65537L
d = 43434...L
private_key = RSA.construct((n, e, d))
dsmg = private_key.decrypt(msg)
```

And here is the final Python-script:

{% code title="rsa-pwn.py" lineNumbers="true" %}

```python
import gmpy2
from Crypto.PublicKey import RSA

def fermat_factorization(n):
    """Fermat's Factorization Method"""
    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 p, q

def calculate_private_key(p, q, e):
    """Calculate the private key 'd'"""
    phi = (p - 1) * (q - 1)
    d = gmpy2.invert(e, phi)
    return d

# Open the RSA key file
with open("id_rsa.pub", "r") as f:
    # Import the RSA key
    key = RSA.import_key(f.read())

# Retrieve the modulus (n) and public exponent (e)
n = key.n
e = key.e

# Print the modulus and public exponent
print("\033[96mModulus (n):\033[0m", n)
print("\033[96mPublic Exponent (e):\033[0m", e)

# Factorize n into p and q using Fermat's Factorization
p, q = fermat_factorization(n)

# Calculate private key 'd' using p, q, and public exponent 'e'
d = calculate_private_key(p, q, e)

difference = abs(p - q)
print("\033[93mp:\033[0m", p)
print("\033[93mq:\033[0m", q)
print("\033[93mDifference between q and p:\033[0m", difference)
print("\033[96mPrivate Key (d):\033[0m", d)

key_params = (n, e, d, p, q)
key = RSA.construct((n,e,int(d)))

# Export the private key to a file
with open('id_rsa', 'wb') as f:
    f.write(key.export_key('PEM'))

print("\033[92mPrivate key generated and saved as 'id_rsa'.\033[0m")
```

{% endcode %}

After running our finished script, we can answer the questions about the last 10 digits of `N`, the difference between `p` and `q`, and get the private SSH key.

<figure><img src="/files/Hx8XdnMjBoM8Bc5zLIMx" alt=""><figcaption></figcaption></figure>

Lastly, we have to add the correct permissions to the key to log on the machine as `root`. In the home directory of `root`, we find the flag.

<figure><img src="/files/uqIuAyqTRVzF5hiUEFWL" alt=""><figcaption></figcaption></figure>