> 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/09.-dp-leak-attack.md).

# dp Leak Attack — Deep Explanation

## 1. Problem Setup

RSA parameters:

```
n = p · q
e = public exponent
d = private exponent
```

Normally:

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

***

## 2. What is leaked

Instead of full `d`, we are given:

```
dp = d mod (p − 1)
```

This is used internally in CRT-based RSA for fast decryption.

***

## 3. Core Mathematical Derivation

From:

```
d ≡ dp mod (p − 1)
```

So:

```
d = dp + t(p − 1)
```

Multiply both sides by `e`:

```
e·d = e·dp + t·e(p − 1)
```

But we know:

```
e·d ≡ 1 mod (p − 1)
```

So:

```
e·dp ≡ 1 mod (p − 1)
```

Which implies:

```
e·dp − 1 = k(p − 1)
```

***

## 4. Rearranging

```
p = (e·dp − 1)/k + 1
```

***

## 5. Key Insight

```
k is a small integer
```

Why?

Because:

```
e·dp − 1 < e(p − 1)
```

So:

```
k < e
```

This makes brute force feasible.

***

## 6. Attack Strategy

We compute:

```
A = e·dp − 1
```

Then loop:

```
for k in [1, e):
    if A % k == 0:
        p = A/k + 1
        check if p divides n
```

***

## 7. Full Attack Flow

```
Recover p
→ compute q = n / p
→ compute φ(n)
→ compute d
→ decrypt
```

***

## 8. Python Script (Clean)

```python
from sympy import mod_inverse

n = ...
e = ...
dp = ...
C = ...

A = e * dp - 1

for k in range(1, e):
    if A % k != 0:
        continue

    p = A // k + 1

    if p > 1 and n % p == 0:
        q = n // p
        break

phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)

M = pow(C, d, n)

print("p =", p)
print("q =", q)
print("d =", d)
print("M =", M)
```

***

## 9. Important Edge Cases

### Case 1 — Wrong k values

Most `k` values will fail:

```
A % k ≠ 0
```

Skip them.

***

### Case 2 — False positives

Even if divisible:

```
p = A/k + 1
```

You must check:

```
n % p == 0
```

***

### Case 3 — dp corresponds to q

Sometimes given:

```
dq = d mod (q − 1)
```

Same logic:

```
q = (e·dq − 1)/k + 1
```

***

## 10. When to Recognize This Attack

Look for:

```
dp or dq explicitly given
"CRT parameters leaked"
fast RSA hints
```

***

## 11. Why This Breaks RSA Completely

Because:

```
Knowing p → factoring n becomes trivial
```

Then:

```
Everything follows normally
```

***

## 12. Worked Example (Manual)

Given:

```
n = 55
e = 3
dp = 3
```

Step 1:

```
A = 3·3 − 1 = 8
```

Step 2:

```
k = 1 → p = 9 (invalid)
k = 2 → p = 5 (valid)
```

Check:

```
55 % 5 = 0
```

So:

```
p = 5, q = 11
```

***

## 13. Complexity

```
O(e) loop
```

Since `e` is usually small (like 65537), this is fast.

***

## 14. Practical Notes (CTF)

```
Often combined with:
- partial leaks
- CRT-based implementations
```

You should immediately try this when you see `dp`.

***

## 15. Summary

```
dp leak → derive equation
→ brute force k
→ recover p
→ break RSA
```

***

Next topic?

Suggested order:

```
partial d exposure
or
Franklin-Reiter attack
```


---

# 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/09.-dp-leak-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.