Codeblue CTF 2017 - Common Modulus 2

Next in the series Common Modulus 3

If you haven’t already, check out Common Modulus 1 Writeup!

We have solved Common Modulus 1, but now there’s more!

e = 3 * get_random_prime(20)

Mmmmh now $MCD(e_1, e_2) = 3 \ne 1$ so we can’t get the flag as easily.

That is because the $x$ and $y$ we find with the Extended Euclidean algorithm will be so that $xe_1 + ye_2 = 3$ (again thanks to the Bézout’s identity). What we get is $m^3 \mod N$, still not that bad.

We notice that $m^3$ is quite smaller than $N$ and also that the flag is surely shorter that 2048/3 = 682 bits roughly 85 characters.

We can actually take the cube root of $m^3$ and recover the flag!

Solution SageMath script

from binascii import unhexlify
import string
def solve(e1, e2, n, m1, m2):
    d, x, y = xgcd(e1, e2)
    c = (pow(m1, x, n) * pow(m2, y, n)) % n
    print unhexlify(hex(long(pow(long(c), 1/3)))[2:-1])