Modern cryptoRuns locallyNo account

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 ctfpal

If 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)) % n