EasyCTF_2018: Souper Large Primes

Category: Cryptography Points: Description:

Technically I used strong primes. But are they really strong in this case? They are big, but there might still be an issue here. n.txt e.txt c.txt.


This challenge was relatively simple, except that it required a bit of tweaking to actually decrypt the mesage in time. Firstly, the values of p and q was easily factored with the help of Fermat's algorithm, particularly using the attackrsa tool.

# attackrsa -t fermat -n $(cat n.txt)
====== Cracked! =======
p is 0x42178a3d54[...]
q is 0x42178a3d53[...]

After getting p and q, we can easily calculate d with gmpy2 but instead of going that route, I chose to use CRT to decrypt the message. Even with CRT, it took my Macbook a good 20-30 minutes to decrypt the message. Lame.

# Use CRT to decrypt
dp = gmpy2.invert(e, (p-1))
dq = gmpy2.invert(e, (q-1))
qinv = gmpy2.invert(q, p)

# Get message
m1 = gmpy2.powmod(c, dp, p)
m2 = gmpy2.powmod(c, dq, q)
h = (qinv * (m1 - m2)) % p 
m = m2 + h * q

With that, quickly formulate a Python script to crack our message for us.

# ./solve.py 

# rax2 -b 110010101100001011100110111100101100011011101000110011001111011010100110111010001110010001100000110111001100111010111110111000001110010011010010110110100110011011100110101111101101110001100000111010001011111011100110011000001011111011100110111010001110010001100000011000000110000011011100110011101111101

Our m was this weird string of numbers, maybe it's binary? Well, decoding it from binary proved fruitless, let's add a 0 in front of it.

# rax2 -b 011001010110000110011001111011010100110111010001110010001100000110111001100111010111110111000001110010011010010110110100110011011100110101111101101110001100000111010001011111011100110011000001011111011100110111010001110010001100000011000000110000011011100110011101111101

Therefore, the flag is easyctf{Str0ng_prim3s_n0t_s0_str000ng}.