TwoForOne

3 minutes to read

We are given two public keys in PEM format:

And we have also two ciphertexts that match respectively with the above public keys. It is important to say that the message is the same:

RBVdQw7Pllwb42GDYyRa6ByVOfzRrZHmxBkUPD393zxOcrNRZgfub1mqcrAgX4PAsvAOWptJSHbrHctFm6rJLzhBi/rAsKGboWqPAWYIu49Rt7Sc/5+LE2dvy5zriAKclchv9d+uUJ4/kU/vcpg2qlfTnyor6naBsZQvRze0VCMkPvqWPuE6iL6YEAjZmLWmb+bqO+unTLF4YtM1MkKTtiOEy+Bbd4LxlXIO1KSFVOoGjyLW2pVIgKzotB1/9BwJMKJV14/+MUEiP40ehH0U2zr8BeueeXp6NIZwS/9svmvmVi06Np74EbL+aeB4meaXH22fJU0eyL2FppeyvbVaYQ==

TSHSOfFBkK/sSE4vWxy00EAnZXrIsBI/Y6mGv466baOsST+qyYXHdPsI33Kr6ovucDjgDw/VvQtsAuGhthLbLVdldt9OWDhK5lbM6e0CuhKSoJntnvCz7GtZvjgPM7JDHQkAU7Pcyall9UEqL+W6ZCkiSQnK+j6QB7ynwCsW1wAmnCM68fY2HaBvd8RP2+rPgWv9grcEBkXf7ewA+sxSw7hahMaW0LYhsMYUggrcKqhofGgl+4UR5pdSiFg4YKUSgdSw1Ic/tug9vfHuLSiiuhrtP38yVzazqOZPXGxG4tQ6btc1helH0cLfw1SCdua1ejyan9l1GLXsAyGOKSFdKw==

The public keys look very similar. Let’s import them with Python and check $n$ and $e$:

$ python3 -q
>>> from Crypto.PublicKey import RSA
>>> key1 = RSA.import_key(open('key1.pem').read())  
>>> key2 = RSA.import_key(open('key2.pem').read())
>>> key1.n == key2.n
True
>>> key1.e == key2.e
False
>>> key1.e
65537
>>> key2.e
343223

We see that both modulus are equal, so the keys only differ on the exponent $e$.

RSA background

Let’s review how RSA works: $n = p q$, where $p$ and $q$ are some large prime numbers. The exponent $e$ is used to encrypt a message $m$ as follows:

$$ c = m^e \mod{n} $$

The decryption process needs $\phi(n) = (p - 1) (q - 1)$ and $d = e^{-1} \mod{\phi(n)}$. Then to decrypt the ciphertext $c$ we can compute:

$$ m = c^d \mod{n} $$

Common modulus attack

Here we have two ciphertexts that use the same modulus but different exponents ($e_1$ and $e_2$), but the message $m$ is the same for both. So:

$$ c_1 = m^{e_1} \mod{n} $$

$$ c_2 = m^{e_2} \mod{n} $$

From Bezout’s identity, given non-zero integers $a, b$ there exist integers $u, v$ such that

$$ u \cdot a + v \cdot b = \gcd{(a, b)} $$

Since $\gcd{(e_1, e_2)} = 1$, we can find $u$ and $v$ such that

$$ u \cdot e_1 + v \cdot e_2 = 1 $$

The idea is find those values to calculate the message $m$ in this way:

$$ c_1^u \cdot c_2^v = (m^{e_1})^u \cdot (m^{e_2})^v = m^{u \cdot e_1} \cdot m^{v \cdot e_2} = m^{u \cdot e_1 + v \cdot e_2} = m \mod{n} $$

The values $u, v$ can be calculated using the extended GCD (Extended Euclidean algorithm).

This is a Python script to solve the challenge:

#!/usr/bin/env python3

from base64 import b64decode
from Crypto.PublicKey import RSA


def extended_gcd(a, b):
    if a % b:
        u, v, d = extended_gcd(b, a % b)
        return v, (d - a * v) // b, d

    return 0, 1, b


def main():
    c1 = int(b64decode(open('message1').read()).hex(), 16)  
    c2 = int(b64decode(open('message2').read()).hex(), 16)

    key1 = RSA.importKey(open('key1.pem').read())
    key2 = RSA.importKey(open('key2.pem').read())

    n = key1.n
    e1, e2 = key1.e, key2.e

    u, v, _ = extended_gcd(e1, e2)

    m = pow(c1, u, n) * pow(c2, v, n) % n

    print(bytes.fromhex(format(m, '0x')).decode())


if __name__ == '__main__':
    main()

Flag

$ python3 solve.py
HTB{C0mmon_M0dUlu5S_1S_b4D}

The full script can be found in here: solve.py.