> 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/07.-crt-attack.md).

# CRT Attack (Håstad’s Broadcast Attack)

The CRT attack exploits a flawed use of RSA where the **same message** is encrypted for multiple recipients using the **same small public exponent** (typically `e = 3`) but **different moduli**.

Each recipient has a different modulus:

```
n1, n2, n3, ...
```

The same message `M` is encrypted:

```
C1 = M^e mod n1
C2 = M^e mod n2
C3 = M^e mod n3
```

If enough such ciphertexts are available, the attacker can recover the original message **without factoring any modulus**.

## Mathematical Idea

We have a system of congruences:

```
C1 ≡ M^e (mod n1)
C2 ≡ M^e (mod n2)
C3 ≡ M^e (mod n3)
```

Using the **Chinese Remainder Theorem**, we combine them into a single integer `C` such that:

```
C ≡ M^e (mod N)
```

where:

```
N = n1 × n2 × n3
```

If:

```
M^e < N
```

then:

```
C = M^e   (no modular reduction occurs)
```

So we can recover:

```
M = e-th root of C
```

For `e = 3`:

```
M = ∛C
```

## Conditions for the Attack

The attack works only when:

```
Same message M
Same exponent e (usually small, like 3)
Different moduli (n1, n2, n3)
Moduli are pairwise coprime
Number of ciphertexts ≥ e
```

If any of these fail, the attack may not work.

## Step-by-Step Process

1. Collect `(ni, Ci)` pairs
2. Apply CRT to compute combined value `C`
3. Ensure `C` is small enough (no wraparound)
4. Compute the integer `e`-th root of `C`
5. Recover the message `M`

## Example

Given:

```
e = 3

n1 = 11413
n2 = 11447
n3 = 11489

C1 = 5472
C2 = 5472
C3 = 5472
```

## Python Implementation

```python
from sympy.ntheory.modular import crt
import sympy

# Given values
n = [11413, 11447, 11489]
c = [5472, 5472, 5472]
e = 3

# Step 1: Combine using CRT
C, _ = crt(n, c)

# Step 2: Take e-th root
M = int(sympy.integer_nthroot(C, e)[0])

print("Recovered M:", M)
```

## Line-by-Line Explanation

```python
from sympy.ntheory.modular import crt
```

Imports CRT implementation.

```python
import sympy
```

Used for integer root calculation.

```python
C, _ = crt(n, c)
```

Combines all congruences into one value `C`.

```python
sympy.integer_nthroot(C, e)
```

Returns `(root, exact)` where:

* `root` is the integer root
* `exact` tells if it was perfect

## Important Notes

* Always use `integer_nthroot`, not floating point roots
* If root is not exact, the attack assumptions may not hold
* Works best when no padding is used

## When to Use in CTF

Look for:

```
Multiple ciphertexts
Different n values
Same e (often 3)
Same or repeated ciphertext patterns
```

## When It Fails

```
Messages are different
Exponent is large
Not enough ciphertexts (need ≥ e)
Padding is used
```

## Common Mistakes

```
Trying to pip install "crt"
Using float cube root instead of integer root
Not checking coprime condition
Using fewer than e ciphertexts
```

## Helpful Tools

* SymPy — CRT and number theory utilities
* SageMath — powerful for large-number math
* RsaCtfTool — automated RSA attack toolkit
* FactorDB — quick factor lookup

## Key Insight

CRT removes modular reduction by combining multiple equations. Once the modulus disappears, RSA reduces to simple exponentiation, which can be reversed using roots.

## Summary

```
Same message + same small exponent + different moduli
→ combine using CRT
→ get M^e
→ take root
→ recover M
```

<img src="https://github.com/user-attachments/assets/6fd3e957-fa64-447b-8696-567fe6d0b496" alt="image" height="453" width="674">


---

# 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/07.-crt-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.