# 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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://0xb0b.gitbook.io/writeups/tryhackme/2024/breaking-rsa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.