Common Modulus Attack — same n, two coprime exponents on the same message

Same message m encrypted under the same modulus n with two coprime exponents e1, e2: combine the two ciphertexts via the Bezout coefficients of e1, e2 to recover m directly — no factoring of n required.

The signal that betrays it

- One n reused across two `(e, c)` pairs that encrypt the same plaintext — e.g. the same secret sent to two "users"/services that share a modulus, or a challenge that hands you two (e, n, c) triples with identical n. - The two exponents are different, e1 != e2, and — this is the condition that actually gates the attack — gcd(e1, e2) = 1. - Distinguish it from three lookalikes: - **Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring**: *different* ns, *same* small e — combined via CRT, not Bezout. Common-modulus is the mirror case: same n, different e. - **Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD**: same n, but the two ciphertexts encrypt *related* (not identical) messages with a known offset/relation — solved by polynomial GCD, not Bezout. - Same n and same e reused across ciphertexts is not this attack at all — that's plain deterministic RSA / an oracle scenario, there is no second exponent to combine against.

How to exploit

1. Run the extended Euclidean algorithm on e1, e2 to get a, b such that a*e1 + b*e2 = gcd(e1, e2). 2. If gcd(e1, e2) = 1 (the case you want), then c1^a * c2^b ≡ m^(a*e1 + b*e2) ≡ m (mod n). 3. You cannot just call pow(c, negative_exponent, n) — negative exponents need a modular inverse first. And you will hit a negative coefficient: whenever e1, e2 > 1 (the normal case — real RSA exponents are odd integers ≥ 3), the identity a*e1 + b*e2 = 1 forces exactly one of a, b to be negative. Proof: if both were ≥ 0 and not both zero, then e1*a + e2*b ≥ min(e1, e2) ≥ 2, which contradicts the sum equaling 1. (The only escape is the degenerate case where one exponent is 1 — but then there's nothing to attack: that exponent alone already gives m = c^1 mod n.) So convert whichever coefficient is negative to a modular inverse: pow(pow(c, -1, n), -exponent, n). 4. Field-tested snippet (Python, sympy for the extended Euclid step, everything else stdlib-level):

```python from sympy import gcdex

a, b, g = gcdex(e1, e2) # a*e1 + b*e2 = g assert g == 1 # gate: must be coprime, see below if not a, b = int(a), int(b)

def powmod_signed(c, x, n): return pow(c, x, n) if x >= 0 else pow(pow(c, -1, n), -x, n)

m = (powmod_signed(c1, a, n) * powmod_signed(c2, b, n)) % n ```

5. Verify by converting m back to bytes (long_to_bytes(m)) and checking it looks like plaintext — the whole attack is silent-fail if you swap c1/c2 with a/b mismatched, you just get garbage, not an error. 6. The modular inverse step needs gcd(c2, n) = 1 (or whichever ciphertext gets the negative exponent). In practice this basically always holds for real RSA ciphertexts — it only fails in the astronomically unlikely event a ciphertext shares a factor with n, which is itself a much bigger win (it factors n) if it ever happens.

What does NOT work

- `gcd(e1, e2) != 1`: you don't get m, you get m^gcd(e1,e2) mod n. This is *not* automatically useless — if the gcd is small (2 or 3 in practice; anything larger and root extraction stops being tractable), you can try an integer gcd-th root the same way as Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n. But it only comes out clean if m^gcd(e1,e2) < n, i.e. the same "no modular wraparound" condition that gates the small-exponent attack — if the power wraps around n, the integer root gives you nothing and you're stuck without factoring n some other way. - Skipping straight to `pow(c, exponent, n)` with the raw signed coefficient — Python's pow() with a negative exponent and a modulus only works via the built-in modular-inverse path in newer Python versions, and even then it's easy to get the sign/pairing wrong. Compute the inverse explicitly and sanity-check the final long_to_bytes(m) output; don't trust an unverified result. - Reaching for this attack when only one `n` is genuinely shared but `e1 == e2`: there's no second independent exponent equation to combine, so Bezout gives you nothing new. That symptom (same n, same e, different ciphertexts) belongs to oracle/padding attacks, not here. - **Trying it across two *different* moduli**: without a shared n there's no single ring to combine c1^a * c2^b in — that's the Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring setup instead, and it needs CRT, not Bezout. - This attack does not factor `n` — it recovers m directly. Don't confuse it with attacks in the Integer Factorization Methodology — which factoring attack to try, in what order family (Fermat, Pollard rho, Pollard p-1): those solve a different problem (breaking the key permanently) and are irrelevant/overkill here.

Related

RSA Fundamentals — the routing hub: which artifact points to which attack Håstad's Broadcast Attack — recovering one plaintext from many small-e ciphertexts, no factoring Franklin–Reiter Related-Message Attack — recovering RSA plaintexts from a known relation via polynomial GCD Small Public Exponent Attack — recovering m by an exact integer e-th root when m^e never wraps mod n Chinese Remainder Theorem — recombining residues across coprime moduli