Codeblue CTF 2017 - Common Modulus 3

by chq-matteo
November 10, 2017

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

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

Bigger public exponent? Check

e = 17 * get_random_prime(20)


while len(flag) * 4 < 8192:
flag += '00'

FLAG = long(flag[:-2], 16)


We have to:

2. take the seventeen-th root of the message (at least hope we can)

The bigger public modulus let’s us hope for the best ($8192 / 17 = 481$ bits or circa 60 bytes).

Since flag is parsed as a base 16 integer the 00 padding is just a multiplication by $2^4$. We don’t know how many 00 of padding there are, but we know that it is more than 0 and less that 8192/4 so we can happily brute force that!

Remember that multiplication for $2^{-4} \mod N$ is actually just like dividing by $2^{4} \mod N$ or cancelling a 00

for i in range(0, 2048):
try:
...


Then we try to take the 17-th root

m, _ = ZZ(m17unpadded).nth_root(d, truncate_mode=1)


And check for a known plaintext like CBCTF

flag = unhexlify(hex(long(m))[2:].replace('L', ''))
if 'CBCTF{' in flag:
print flag
break


I did mess up a couple of times during the competition, but in the end we got the flag.

N.B. I renamed a couple of variables and didn’t test the code again

Solution SageMath script

from binascii import unhexlify
import string
def solve(e1, e2, n, c1, c2):
d, x, y = xgcd(e1, e2)
print d
m17padded = (pow(c1, x, n) * pow(c2, y, n)) % n # (flag * 2**x)**17 = flag ** 17 * 2**17x
for i in range(0, 2048):
try: