Codeblue CTF 2017 - Common Modulus 1

Next in the series Common Modulus 2

Quick summary of RSA
$cipher text = message^e \mod N$

We have a message (the flag) encrypted with the same $N$, but with two different $e$. As the name suggests the solution to this problem is a common modulus attack

The idea of the attack is that if we know

1. $m^{e_1} \mod N$
2. $m^{e_2} \mod N$
3. $MCD(e_1, e_2) = 1$

then we can recover $m$.

Luckily $e_1$ and $e_2$ and two random generated primes so it is very likely that (3) holds and we have (1) (2) because we have the two cipher texts.

Explanaition of the attack

The Bézout’s identity guarantees that we can find with the Extended Euclidean algorithm $x$ and $y$ so that $xe_1 + ye_2 = 1$. We can use this fact to compute $m$.

We are given the cipher texts $c_1 = m^{e_1} \mod N$ and $c_2 = m^{e_2} \mod N$

If we raise $c_1$ to the $x-th$ power modulo $N$ we get $c_1^{x} = (m^{e_1})^{x} = m^{xe_1} \mod N$ similary with $c_2$ and $y$ we get $c_2^{y} = m^{ye_2} \mod N$.

If we multiply them we get $m^{xe_1}m^{ye_2} = m^{xe_1 + ye_2} \mod N$, but we have proven that the exponent is actually equal to $1$! So what we really get is $m$!

N.B. One of $x$ and $y$ will be negative

Solution SageMath script

from binascii import unhexlify
def solve(e1, e2, n, c1, c2):
    d, x, y = xgcd(e1, e2)
    m = (pow(c1, x, n) * pow(c2, y, n)) % n
    print unhexlify(hex(long(m))[2:-1])