> 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/cryptography/rsa/08.-wieners-attack.md).

# Wiener’s Attack (Small d Attack)

## What it is

Wiener’s attack breaks RSA when the **private key `d` is too small**.

```
If d is small → it can be recovered without factoring n
```

## 📌 Why this is dangerous

RSA relies on:

```
d being hard to compute from (e, n)
```

But if:

```
d < 1/3 * n^(1/4)
```

👉 then RSA becomes vulnerable.

## Core Idea

We use continued fractions on:

```
e / n
```

This gives approximations:

```
k / d ≈ e / n
```

From these, we can **guess d**.

## 🔍 Why this works

From RSA math:

```
e·d ≡ 1 mod φ(n)
```

Which implies:

```
e·d − k·φ(n) = 1
```

Rearrange:

```
| e/n − k/d | is very small
```

👉 So `k/d` appears as a **convergent** of `e/n`.

## ⚙️ Attack Steps

1. Compute continued fraction of `e / n`
2. Generate convergents `(k, d)`
3. For each candidate `d`:
   * Check if it satisfies RSA equation
4. If valid → recovered `d`

## 🐍 Python Implementation

```python
from sympy import Rational
from sympy.ntheory.continued_fraction import continued_fraction, continued_fraction_convergents

e = 17993
n = 90581

# Step 1: Continued fraction of e/n
cf = continued_fraction(Rational(e, n))

# Step 2: Get convergents
convergents = continued_fraction_convergents(cf)

for frac in convergents:
    k = frac.p
    d = frac.q

    if k == 0:
        continue

    # Check if possible
    if (e * d - 1) % k != 0:
        continue

    phi = (e * d - 1) // k

    # Solve quadratic: x^2 - (n - phi + 1)x + n = 0
    b = -(n - phi + 1)
    D = b*b - 4*n

    if D >= 0:
        sqrtD = int(D**0.5)
        if sqrtD * sqrtD == D:
            print("Found d:", d)
            break
```

## What’s happening in code

```
continued_fraction(e/n)
```

→ breaks fraction into parts

```
convergents
```

→ gives possible k/d

```
(e*d - 1) % k == 0
```

→ checks RSA condition

## 📌 When to use in CTF

Look for:

```
Large n
Given e
No easy factorization
Hint about "small key" or "fast decryption"
```

## ❌ When it won’t work

```
d is large (normal RSA)
```

## 🔥 Key Insight

```
Wiener doesn’t attack n
It attacks weak d
```

## 🧾 Summary

```
If d is small:
→ e/n reveals d via continued fractions
→ recover d
→ decrypt normally
```

<img src="https://github.com/user-attachments/assets/a51084e1-e955-45ae-95f8-774ce0d5300f" alt="image" height="693" width="1366">


---

# 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/cryptography/rsa/08.-wieners-attack.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.