Breaking RSA with the Common Modulus Attack

Breaking RSA with the Common Modulus Attack

Introduction

Generating a fresh RSA modulus means generating two large primes. That’s the most expensive step in key generation. It’s tempting to skip it. Pick one shared n, and hand out a different (e, d) pair to each user. Let them all encrypt against that same modulus. Nothing in the RSA formula seems to object. It doesn’t need to. The flaw doesn’t show up in one key pair’s own math. It shows up the moment the same message gets encrypted twice. That’s for two different users sharing the modulus. This post builds the attack that recovers the message from exactly that situation. Neither private key is ever touched.

Table of Contents

• Why Sharing a Modulus Fails
• The Attack: Recombining Two Ciphertexts
• A Worked Example
• Python Implementation
• Interactive Visualizer
• Common Modulus vs. This Site’s Other RSA Breakers
• Limitations of This Attack
• FAQ
• References

Why Sharing a Modulus Fails

A single RSA key pair is safe for a simple reason. Encryption and decryption lock together through one exponent pair, e and d. Both are defined relative to the same φ(n). Nothing about that safety depends on n being unique to that pair. That’s precisely the gap a shared-modulus scheme falls into. Two different exponent pairs, (n, e₁) and (n, e₂), both valid on their own. Both sit on top of the identical n.

The problem surfaces only when both keys touch the same plaintext. Suppose a message M gets encrypted once under e₁, and once under e₂. An eavesdropper holding both ciphertexts now has two views of the same unknown. As long as e₁, e₂ are coprime, one tool turns those views into the message. That tool is the Extended Euclidean Algorithm. Neither private key is ever computed, needed, or even threatened. The message just falls out of the relationship between the two exponents.

Sharing a modulus actually opens two separate dangers. First, any legitimate holder of one private exponent can factor n outright. They use the relation ed − 1 = k·φ(n), then compute every other user’s private key. Second, an eavesdropper who sees one plaintext encrypted under two coprime exponents can recover it. No factoring needed. This post covers only the second danger: the purely public, ciphertext-only recovery.

The Attack: Recombining Two Ciphertexts

Given c₁ = Mᵉ¹ mod n and c₂ = Mᵉ² mod n, with gcd(e₁, e₂) = 1:

1. Run the Extended Euclidean Algorithm on e₁ and e₂. It finds integers a and b satisfying a·e₁ + b·e₂ = 1. This is guaranteed whenever e₁ and e₂ are coprime, the exact condition required here. It’s the same algorithm RSA key generation uses, to find d from e and φ(n).
2. Exactly one of a or b will be negative. That always happens when e₁ and e₂ are both greater than 1. Two positive coefficients would push a·e₁ + b·e₂ past 1. A negative coefficient just means taking a modular inverse first. It’s the same trick RSA decryption uses elsewhere.
3. Recombine: M ≡ c₁ᵃ · c₂ᵇ (mod n). Substituting the definitions of c₁ and c₂ shows why: c₁ᵃ · c₂ᵇ = M^(ae₁) · M^(be₂) = M^(ae₁+be₂) = M¹ = M (mod n). That follows from Euler’s theorem, the same fact ordinary RSA decryption relies on. The exponent identity is just built from two public exponents. Compare that to one exponent and its private inverse.
4. No factoring, no private key, no brute force anywhere in this computation. The message comes directly out of public arithmetic: n, e₁, e₂, c₁, c₂.

The same idea scales past two ciphertexts. Any number of exponents work, as long as their overall gcd is 1. That needs a multi-variable extended gcd, not the two-variable version here. Two ciphertexts is the classic, simplest case. It’s the one this post builds.

A Worked Example

The visualizer’s defaults reuse n = 3233 (secretly 61 × 53) from the base RSA guide’s own worked example. This time there are two different public exponents: e₁ = 17 and e₂ = 7.

1. Setup, not part of the attack itself: message M = 65 gets encrypted under both exponents. c₁ = 65¹⁷ mod 3233 = 2790 and c₂ = 65⁷ mod 3233 = 1317.
2. Extended Euclidean Algorithm on e₁ = 17 and e₂ = 7. gcd(17, 7) = 1, confirming the attack applies. a = −2 and b = 5 satisfy (−2)(17) + (5)(7) = −34 + 35 = 1.
3. Recombine, using only c₁, c₂, a, and b. Since a is negative, the c₁ term needs a modular inverse first. That inverse comes from running the Extended Euclidean Algorithm again. This time on c₁ and n, not on the exponents. c₁⁻¹ mod 3233 = 1788, then 1788² mod 3233 = 2740. The c₂ term is ordinary: 1317⁵ mod 3233 = 2000.
4. Multiply: 2740 × 2000 mod 3233 = 65.
5. That’s M, recovered exactly, without ever computing either private key.

Neither key pair’s private exponent was touched, at any point. The message came back purely from the relationship between two exponents sharing a modulus.

Python Implementation

The interactive visualizer above runs this exact recombination in JavaScript. Same extended Euclidean step, same modular-inverse handling, same final multiplication. Here’s the same attack in Python.

Key Features

• egcd is the same Extended Euclidean Algorithm the base RSA guide’s own mod_inverse uses for key generation. Here it’s applied to two exponents, not one exponent and a totient.
• Explicitly handles the negative coefficient by computing a modular inverse before exponentiating. It doesn’t rely on Python’s pow() doing anything special with a negative exponent.
• Never computes p, q, φ(n), or either d. The entire recovery only ever touches n, e₁, e₂, c₁, and c₂. That’s the whole point: this isn’t a factoring attack.

Code

# common_modulus_breaker.py
#
# Recovers a message encrypted twice under the same RSA modulus but two
# different, coprime public exponents. Given c1 = M^e1 mod n and
# c2 = M^e2 mod n, the Extended Euclidean Algorithm finds a, b with
# a*e1 + b*e2 = 1, and then M = c1^a * c2^b mod n -- straight from
# Euler's theorem, no private key required.

def egcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = egcd(b, a % b)
    return g, y, x - (a // b) * y


def mod_inverse(a, m):
    g, x, _ = egcd(a % m, m)
    if g != 1:
        return None
    return x % m


def common_modulus_attack(n, e1, e2, c1, c2):
    g, a, b = egcd(e1, e2)
    if g != 1:
        return None

    c1_term = pow(c1, a, n) if a >= 0 else pow(mod_inverse(c1, n), -a, n)
    c2_term = pow(c2, b, n) if b >= 0 else pow(mod_inverse(c2, n), -b, n)

    return (c1_term * c2_term) % n


if __name__ == '__main__':
    n = 3233
    e1, e2 = 17, 7
    message = 65

    c1 = pow(message, e1, n)
    c2 = pow(message, e2, n)
    print(f"c1 = {c1}, c2 = {c2}")

    recovered = common_modulus_attack(n, e1, e2, c1, c2)
    print(f"Recovered message: {recovered}")
    assert recovered == message

Running this against the same values as the visualizer produces:

c1 = 2790, c2 = 1317
Recovered message: 65

This matches the visualizer’s own result exactly. It matches the worked example above, step for step.

For Fun: The Whole Attack in 5 Lines

Same spirit as this site’s other golfed bonus sections. Not for learning the algorithm from. This version leans on a pow() detail, not just the Extended Euclidean Algorithm. It requires Python 3.8 or later.

n=3233; e1=17; e2=7; message=65; c1=pow(message,e1,n); c2=pow(message,e2,n); print(f"c1 = {c1}, c2 = {c2}")
a,b=e1,e2; x0,x1,y0,y1=1,0,0,1
while b: q=a//b; a,b=b,a%b; x0,x1=x1,x0-q*x1; y0,y1=y1,y0-q*y1
g,a,b=a,x0,y0
M=(pow(c1,a,n)*pow(c2,b,n))%n; print(f"Recovered message: {M}"); assert M==message

Verified to produce the identical c1 = 2790, c2 = 1317 and Recovered message: 65. There’s no separate branch for a negative exponent here. Since Python 3.8, pow(base, exp, mod) accepts a negative exp directly. It computes the modular inverse internally, whenever base and mod are coprime.

Bonus: When gcd(e₁, e₂) Isn’t 1

The visualizer above rejects non-coprime exponents outright, by design. The attack this post teaches needs gcd(e₁, e₂) = 1. But the recombination itself doesn’t just fail once that gcd, call it g, exceeds 1. It quietly recovers Mᵍ mod n instead of M.

Suppose M is small enough that Mᵍ never wraps around n. Then that recovered value is the exact integer Mᵍ, not just its residue. An ordinary integer g-th root then recovers M itself:

def common_modulus_partial(n, e1, e2, c1, c2):
    """When gcd(e1, e2) = g > 1, this recovers M**g mod n, not M."""
    g, a, b = egcd(e1, e2)
    c1_term = pow(c1, a, n) if a >= 0 else pow(mod_inverse(c1, n), -a, n)
    c2_term = pow(c2, b, n) if b >= 0 else pow(mod_inverse(c2, n), -b, n)
    return (c1_term * c2_term) % n, g


def integer_nth_root(value, g):
    """Exact integer g-th root, or None if value isn't a perfect g-th power."""
    lo, hi = 0, 1
    while hi ** g <= value:
        hi *= 2
    while lo < hi:
        mid = (lo + hi + 1) // 2
        lo, hi = (mid, hi) if mid ** g <= value else (lo, mid - 1)
    return lo if lo ** g == value else None


n, e1, e2, message = 3233, 15, 6, 5
c1, c2 = pow(message, e1, n), pow(message, e2, n)
recovered_power, g = common_modulus_partial(n, e1, e2, c1, c2)
print(f"gcd(e1, e2) = {g}, recovered M^g mod n = {recovered_power}")
print(f"Integer {g}-th root = {integer_nth_root(recovered_power, g)}")

gcd(e1, e2) = 3, recovered M^g mod n = 125
Integer 3-th root = 5

This only works because 5³ = 125 stayed under n = 3233, so no modular wraparound ever happened. Real messages are large. That trick almost never applies in practice. Recovering M from Mᵍ mod n otherwise needs a different technique, one this post doesn’t cover.

Interactive Visualizer

Try it above. Enter any shared modulus and two coprime exponents, plus a demo message. Watch the extended Euclidean algorithm find a and b. Watch the message come back out of the two ciphertexts alone. Neither private key ever appears in the computation.

Common Modulus vs. This Site’s Other RSA Breakers

This is the odd one out among the site’s RSA breakers, in one important way. Both keys can be generated correctly: properly random, properly distant primes, an ordinary e. The mistake here is entirely operational, reusing a modulus, not mathematical. That’s a good reminder. RSA’s security depends on more than how one key pair gets built.

Limitations of This Attack

This attack needs gcd(e₁, e₂) = 1. If the two exponents share a common factor g, the recombination recovers Mᵍ mod n instead of M. See the bonus section above for the details. Extracting M from that value needs g and M both to be small. Neither holds for realistic message sizes, so this case rarely helps an attacker in practice.

It also needs the same message encrypted under both exponents. Two different messages, never repeated between them, give an eavesdropper nothing this attack can use. The vulnerability is about message reuse across the shared modulus, not the sharing by itself.

Finally, this attack recovers exactly one plaintext: the one that was encrypted twice. It doesn’t recover either private key. It doesn’t help decrypt any other message sent to either user under their own key. It’s a narrow, message-specific break, not a full compromise of either key pair.

The fix is simple and absolute. Never reuse a modulus across key pairs. Generate fresh, independent primes for every key. Use proper padding, so identical plaintexts never produce related ciphertexts in the first place.

FAQ

Why would anyone actually share an RSA modulus between users?

Historically, some systems did this to save the cost of prime generation. They treated n as a shared “domain parameter,” issuing individual (e, d) pairs against it. It was a real, if misguided, engineering shortcut. This attack is exactly why standards now insist on independent n for every key pair.

Does the attacker need to factor n for this attack?

No, and that’s the point. This attack works entirely without factoring n or computing φ(n). It’s number theory applied directly to the two exponents and the two ciphertexts.

What if e₁ and e₂ aren’t coprime?

Then a·e₁ + b·e₂ = 1 has no integer solution. The recombination still runs, but it recovers Mᵍ mod n for g = gcd(e₁, e₂), not M itself. The bonus section above covers when that partial result can still yield M.

Is this the same vulnerability as sharing a prime factor between two different moduli?

No. That’s a related but distinct mistake. Two users, with entirely different moduli, happen to share one prime factor. Bad luck or bad randomness causes it. It’s caught by computing gcd across many public keys. This attack is about one modulus, deliberately reused. The same plaintext gets encrypted under two exponents on it.

How would a defender catch this before it’s exploited?

By never sharing a modulus between key pairs at all. That’s what every modern RSA library already does, generating fresh, independent primes each time. If an audit ever finds two public keys sharing an n, that’s a serious finding. It matters even if no message has been reused yet.

References

1. Menezes, A., van Oorschot, P., and Vanstone, S. “Handbook of Applied Cryptography.” CRC Press, 1996 (Section 8.2.2(vi), “Common modulus attack”).

2. Schneier, B. “Applied Cryptography.” 2nd ed., Wiley, 1996 (Section 19.3 covers the risks of a common modulus).

3. Boneh, D. “Twenty Years of Attacks on the RSA Cryptosystem.” Notices of the AMS, 1999. Available at: https://crypto.stanford.edu/~dabo/papers/RSA-survey.pdf