Rating: 5.0

# Encrypt0r

#### Description:
EU instance 4449

US instance 4449
#### Auther:
#### 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`:

tmp = 1
for guessed_e in range(2 ** 17):
if tmp == 405518048190558088634310202493589629933137815074909354184258:
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:

from Crypto.Util.number import long_to_bytes

def egcd(a, b):
if a == 0:
return (b, 0, 1)
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')
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)

## Flag:

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