> 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/06.-common-modulus-attack.md).
# 06. Common Modulus Attack
## Common Modulus Attack
### What it is
The Common Modulus Attack is an RSA weakness that happens when:
```
The same modulus n is reused
The same message M is encrypted
But with different public exponents (e1, e2)
```
So you get:
```
C1 = M^e1 mod n
C2 = M^e2 mod n
```
### Why this is a mistake
In proper RSA:
```
Each user should have a different n
```
But sometimes (bad implementation):
```
Same n is reused for multiple users
```
👉 This creates a vulnerability.
## 🧠 Why the attack works
We use **Bézout’s identity**:
```
If gcd(e1, e2) = 1
Then ∃ x, y such that:
e1·x + e2·y = 1
```
### 🔥 Key idea
We already have:
```
C1 = M^e1
C2 = M^e2
```
Now raise them:
```
C1^x = M^(e1x)
C2^y = M^(e2y)
```
Multiply:
```
C1^x * C2^y = M^(e1x + e2y)
```
But:
```
e1x + e2y = 1
```
So:
```
M = C1^x * C2^y mod n
```
## ⚠️ Important detail (VERY important)
If:
```
y is negative
```
Then:
```
C2^y = inverse(C2)^|y|
```
This is where modular inverse comes in.
***
## 📌 When to use this attack
Use it when you see:
```
Same n
Two ciphertexts
Different e values
Same message (or likely same)
```
## ❌ When NOT to use
```
Different n → doesn’t work
Different messages → doesn’t work
gcd(e1, e2) ≠ 1 → doesn’t work directly
```
## 🧪 Step-by-Step Process
### Step 1 — Given values
```
n, e1, e2, C1, C2
```
### Step 2 — Check condition
```
gcd(e1, e2) = 1
```
### Step 3 — Solve equation
```
e1·x + e2·y = 1
```
(using Extended Euclidean Algorithm)
### Step 4 — Handle negative values
```
If x < 0 → invert C1
If y < 0 → invert C2
```
### Step 5 — Compute message
```
M = (C1^x * C2^y) mod n
```
***
## 🐍 Python (clean and real)
```python
from sympy import mod_inverse, gcdex
n = 91
e1 = 5
e2 = 11
C1 = 47
C2 = 23
# Step 1: Solve e1*x + e2*y = 1
x, y, _ = gcdex(e1, e2)
# Step 2: Handle negatives
if x < 0:
C1 = mod_inverse(C1, n)
x = -x
if y < 0:
C2 = mod_inverse(C2, n)
y = -y
# Step 3: Recover M
M = (pow(C1, x, n) * pow(C2, y, n)) % n
print("Recovered M:", M)
```
## 🧠 Intuition (important)
```
We are “combining” two encryptions
to cancel out the exponents
```
Instead of:
```
breaking RSA
```
We:
```
reverse exponent math directly
```
## 🔥 Real-world analogy
```
You have:
M^5 and M^11
You combine them smartly
to get M^1
```
## 🚀 Why this matters in CTFs
In competitions like picoCTF:
```
Same n reused → common trick
```
👉 This attack appears a LOT
## 🧾 Final Summary
```
Same n + same message + different e
→ use Bézout to combine ciphertexts
→ recover M without factoring
```
---
# 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/06.-common-modulus-attack.md?ask=&goal=
```
`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.