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](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) 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](https://crypto.stackexchange.com/questions/65965/determine-rsa-modulus-from-encryption-oracle)
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:

python
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](https://www.alpertron.com.ar/ECM.HTM):

p = 882152190529044698706991746907
q = 1068983182191997868299760689187


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

python
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).