# 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.

## Write-up

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
110010101100001011100110111100101100011011101000110011001111011010100110111010001110010001100000110111001100111010111110111000001110010011010010110110100110011011100110101111101101110001100000111010001011111011100110011000001011111011100110111010001110010001100000011000000110000011011100110011101111101

# rax2 -b 110010101100001011100110111100101100011011101000110011001111011010100110111010001110010001100000110111001100111010111110111000001110010011010010110110100110011011100110101111101101110001100000111010001011111011100110011000001011111011100110111010001110010001100000011000000110000011011100110011101111101
???????????`?ξ????f??`??`????```??
``````

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
easyctf{Str0ng_prim3s_n0t_s0_str000ng}
``````

Therefore, the flag is `easyctf{Str0ng_prim3s_n0t_s0_str000ng}`.