Codeblue CTF 2017 - Common Modulus 2by
November 10, 2017
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])