Rating: 5.0

Encrypt0r

Description:

EU instance 161.97.176.150 4449

US instance 185.172.165.118 4449

Auther:

Soul

Points and solvers:

At the end of the CTF, 36 teams solved this challenge and it was worth 492 points.

Solution:

In this challenge once you connected to the remote server a prompt appeared, "this is the flag":

848630917051893087050233654298398605870572417880786546004017

Then you were able to encrypt whatever number you wanted and see the result.

Fisrt let's try to encrypt some stuff see if we understand what encryption is that.
0 -> 0,
1 -> 1, 2 -> 405518048190558088634310202493589629933137815074909354184258
We know that raising to some power will keep 0 at 0 and keep 1 at 1, this leads us to thinking we are dealing with RSA here.

For us to decrypt then we need to find, n than e and than d, after that we will be able to decrypt.
Normally in order to find n when you are have an encryption oracel you can use a method explained here and this was indid the intended solution. But when encrypting -1 (this option should have been patched) we get n - 1 due to modular arithmetics. So we have n, it is:

943005855809379805541572246085636463198876208104363395594608 + 1

And now in order to find e we can simply iterate over may powers untill we will find a power that matches the fact that we know the encryption of 2:

tmp = 1
for guessed_e in range(2 ** 17):
    if tmp == 405518048190558088634310202493589629933137815074909354184258:
        print(guessed_e)
        break
    tmp *= 2
    tmp = tmp % n

We get e = 65537. Now lets factorize n using the following Integer factorization calculator website:

p = 882152190529044698706991746907
q = 1068983182191997868299760689187

Great! Now find d as usual using a modinv function, decrypt, and print the result:

from Crypto.Util.number import long_to_bytes


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
        

e = 65537
d = modinv(e, (p-1)*(q-1))
print(pow(pow(2, e, n), d, n))
f = pow(enc_flag, d, n)
print(long_to_bytes(f))

Flag:

flag{y0u_d0nt_n33d_4nyth1ng}
Original writeup (https://github.com/yonlif/0x41414141-CTF-writeups/blob/main/Encrypt0r.md).