> For the complete documentation index, see [llms.txt](https://alham-rizvi.gitbook.io/alhamrizvi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://alham-rizvi.gitbook.io/alhamrizvi/picoctf-writeups/picoctf/cryptography/small_trouble.md).

# small\_trouble

Certainly! This is a classic example of an RSA challenge where the "familiar parameters" have a hidden flaw. Here is a writeup explaining the vulnerability and how to break it.

### 1. What is this?

This is a **Public Key Cryptography** challenge involving **RSA**. Normally, RSA is incredibly secure because it relies on the difficulty of factoring a massive number $n$ into its two prime components $p$ and $q$.

However, in this specific case, the setup uses a **Small Private Exponent**. Even though the primes are 1048 bits each (very strong), the "shortcut" taken during key generation makes the entire system crumble.

### 2. Understanding the Source Code

The script follows the standard RSA generation process but makes one critical mistake:

1. **Prime Generation:** It creates two massive 1048-bit primes ($p$ and $q$).
2. **The Modulus ($n$):** $n = p \times q$. This is the public part of the key.
3. **The Flaw ($d$):** `d = getPrime(256)`. Usually, $d$ is a massive number derived from a small public exponent (like 65537). Here, $d$ is explicitly chosen to be very small (only 256 bits) compared to the 2096-bit modulus $n$.
4. **Public Exponent ($e$):** Since $d$ is small, $e$ (the inverse of $d$ modulo $\phi$) becomes extremely large—nearly the same size as $n$.
5. **Encryption:** The flag is converted to a number ($m$) and encrypted using $c = m^e \pmod n$.

***

### 3. The Attack: Wiener's Attack

When the private exponent $d$ is less than $\frac{1}{3} n^{1/4}$, the RSA system is vulnerable to **Wiener's Attack**.

Because $e \cdot d \equiv 1 \pmod{\phi(n)}$, we know that: $$\frac{e}{n} \approx \frac{k}{d}$$

This means that the fraction $\frac{e}{n}$ is very close to the unknown fraction $\frac{k}{d}$. We can use **Continued Fractions** to find all the "best guesses" (convergents) for $\frac{e}{n}$. One of those guesses will be the actual $d$ used to encrypt the message.

#### The Attack Script (`attack.py`)

To solve this, we use a script that calculates the continued fraction of $e/n$, iterates through the convergents, and tests if that $d$ can decrypt the ciphertext.

```python
from Crypto.Util.number import long_to_bytes, inverse

# 1. Define the continued fraction expansion of e/n
def continued_fraction(e, n):
    cf = []
    while n:
        cf.append(e // n)
        e, n = n, e % n
    return cf

# 2. Generate convergents (k/d) from the continued fraction
def get_convergents(cf):
    nm, dn = [0, 1], [1, 0]
    for x in cf:
        nm.append(x * nm[-1] + nm[-2])
        dn.append(x * dn[-1] + dn[-2])
        yield nm[-1], dn[-1]

# 3. Test each convergent to find the flag
def crack_rsa(n, e, c):
    cf = continued_fraction(e, n)
    for k, d in get_convergents(cf):
        if k == 0: continue
        # Try to decrypt with this d
        m = pow(c, d, n)
        flag = long_to_bytes(m)
        if b'picoCTF' in flag:
            return flag

# Insert your n, e, and c values here
# result = crack_rsa(n, e, c)
# print(result.decode())
```

***

### 4. Explaining the Flag

Once the script runs, it finds the correct $d$ that satisfies the mathematical relationship. It then performs the decryption: $$m = c^d \pmod n$$ The resulting number $m$ is converted back into bytes, revealing the flag. The vulnerability exists because the "search space" for $d$ was narrowed down from the entire 2096-bit range to just a few possible candidates generated by the continued fraction of $e/n$.

**Lesson learned:** Never use a small private exponent in RSA!


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

```
GET https://alham-rizvi.gitbook.io/alhamrizvi/picoctf-writeups/picoctf/cryptography/small_trouble.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.