RSA common modulus attack
Recover a plaintext encrypted twice under the same modulus with two coprime exponents, using the extended Euclidean algorithm. No factoring needed.
Open in ctfpalIf the same message is encrypted under the same n with two different exponents e1 and e2, and those exponents are coprime, the plaintext falls out with no factoring at all. Bezout gives integers a and b with a*e1 + b*e2 = 1; then c1^a * c2^b = m^(a*e1 + b*e2) = m mod n.
The negative exponent detail
One of a and b is always negative, and a negative exponent means a modular inverse. That is the step people get wrong: replace c^(-k) with inverse(c, n)^k. The inverse exists as long as the ciphertext is coprime to n, which it will be unless you have stumbled onto a factor - in which case you have won anyway.
g, a, b = extended_gcd(e1, e2)
assert g == 1 # exponents must be coprime
if a < 0:
c1, a = pow(c1, -1, n), -a
if b < 0:
c2, b = pow(c2, -1, n), -b
m = (pow(c1, a, n) * pow(c2, b, n)) % nPart of a module
5. RSA and the parameters that break it
Work the RSA decision tree - small modulus, close primes, tiny exponent, shared modulus - and learn to read a key for its weakness.
Practise on real challenges
Go deeper
- The RSA attack decision treeRSA challenges are not solved by knowing every attack - they are solved by reading the parameters and picking the one attack that matches. A decision tree from e and n to Fermat, Wiener, Hastad, common modulus, and the oracle attacks.
Related tools
Hastad broadcast attack on RSA
Recover a message sent to several recipients under a small public exponent, using the Chinese remainder theorem and an exact integer root.
RSA decryption and attack runner
Paste n, e, and c and let ctfpal choose the attack: trial division, Fermat, Pollard’s rho, Wiener, common modulus, or Hastad broadcast. Arbitrary-precision, in-browser.
Modular arithmetic and number theory toolkit
Modular inverse, Chinese remainder theorem, Tonelli-Shanks square roots, Jacobi symbols, and integer nth roots - arbitrary precision, in the browser.
Fermat factorization for close RSA primes
Factor an RSA modulus whose primes were generated too close together. Fermat’s method finds them in a handful of steps where trial division never would.