> 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/16.-boneh-durfee-attack.md).

# Boneh–Durfee Attack (Very Small d)

## 1. Overview

This is a stronger version of Wiener’s attack.

```
Wiener works if: d < n^0.25
Boneh–Durfee works if: d < n^0.292
```

So it breaks RSA even when:

```
d is not extremely small, but still “too small”
```

***

## 2. Problem Setup

RSA:

```
n = p · q
e · d ≡ 1 mod φ(n)
```

Rewrite:

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

***

## 3. Core Idea

We want to solve:

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

But we don’t know `φ(n)`.

Use approximation:

```
φ(n) ≈ n − (p + q) + 1
```

Since:

```
p + q is small compared to n
```

***

## 4. Key Transformation

Let:

```
φ(n) = n − x
```

Then:

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

Rearrange:

```
e·d − k·n + k·x = 1
```

***

## 5. Unknowns

```
d is small
k is small
x is small (≈ p + q)
```

So we now have a **multivariable small root problem**.

***

## 6. Key Insight

```
Treat equation as polynomial
Solve using lattice reduction
```

Using:

```
LLL algorithm + Coppersmith method
```

***

## 7. Why It Works

```
d is small → solution lies in small region
```

Lattice finds:

```
small integer solutions to polynomial equations
```

***

## 8. Attack Strategy

1. Build polynomial:

```
f(d, k, x) = e·d − k(n − x) − 1
```

2. Construct lattice
3. Apply LLL
4. Recover small roots
5. Extract `d`

***

## 9. Practical Implementation

This is **not doable in raw Python**.

Use:

```
SageMath + lattice libraries
```

***

## 10. SageMath Skeleton

```python
# Simplified structure (conceptual)

n = ...
e = ...

# parameters
delta = 0.26   # threshold (< 0.292)

# Build polynomial ring
PR.<x, y> = PolynomialRing(ZZ)

# Construct polynomial
f = x*(e) - y*n + 1

# Apply lattice-based small root finding
# (actual implementation is complex)

# Use existing scripts/tools in practice
```

***

## 11. Real Usage

In practice, people use:

* **SageMath**
* prebuilt scripts from CTF repos
* lattice helper functions

***

## 12. When to Recognize

Look for:

```
Given n and e
Wiener fails
Hint: “small private key”
```

Or:

```
d slightly larger than Wiener bound
```

***

## 13. Comparison with Wiener

| Attack       | Condition   |
| ------------ | ----------- |
| Wiener       | d < n^0.25  |
| Boneh–Durfee | d < n^0.292 |

***

## 14. Why This Breaks RSA

Because:

```
Small d leaks structure in equation
```

And lattice methods recover:

```
hidden small values
```

***

## 15. Limitations

```
Requires d small enough
Complex implementation
Heavy math (LLL)
Not common in beginner CTFs
```

***

## 16. Summary

```
d moderately small
→ build polynomial
→ apply lattice (LLL)
→ recover d
→ decrypt
```

***

## 17. Practical Advice

```
Try Wiener first
If it fails → consider Boneh–Durfee
Use Sage, not raw Python
```

***

## 18. Practice Idea

```
Given n, e
Wiener fails
d is small but not too small
```

***

## Task

```
Recover d using Boneh–Durfee
```


---

# 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/16.-boneh-durfee-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.