# niteCTF 2021, Rabin to the Rescue Writeup

## Description

So we have the server’s network address and the source code. Let’s examine the source code:

First, this code generates two primes `p`

and `q`

. The generation function is pretty interesting:

It sets `p`

to 256-bit prime and `q`

to `p + 6`

and then checks if `p = 3 mod 4`

and `q = 3 mod 4`

and returns them if they are. Otherwise, function generates `p`

again but `q`

this time is the next prime for `p`

. And again it checks if `p = 3 mod 4`

and `q = 3 mod 4`

.

After primes generation, the code computes `n = p * q`

. So far this looks pretty much like an RSA problem.

Then, the code computes `e`

with function `mixer`

. Interesting thing is that `mixer`

function accepts integer parameter, and the code feeds `q — p`

into it. So we would think that `e`

is somehow depends on values `q`

and `p`

. But if we look closer to the `mixer`

code, we’ll see that the function will always return the value 1.

Note the `while`

loop. It terminates only when `num`

is lower or equal to `1`

. But `num`

is reduced only with division by 2, so it cannot ever become lower than `1`

. So `mixer`

returns 1 for any positive argument `num`

. And `num`

is always positive because `q`

is always greater than `p`

, so `q — p > 0`

.

Finally the value returned from `mixer`

is multiplied by 2. So `e`

will always be `2`

. Now for some people it might still look like an RSA challenge, but it is already not the case. This is because we can’t have public exponent equal to `2`

, because `f = (p — 1) * (q — 1)`

is even number and `2`

has no inversion modulo `f`

, so we can’t calculate `d`

. But let’s move on for now.

After parameters computation, the code enters the main loop, that’s where we interact with server. Server propose 3 options: encrypt some arbitrary value, print encrypted flag, and exit. Encryption function works similar to RSA.

You may notice that when we request the encrypted flag server runs `encrypt`

function random amount of times. It calculates the same value over and over again, so this doesn’t make problem harder. This is just a protection against timing attacks.

Note that server never prints parameters of cryptosystem. And although we know `e = 2`

anyway, we don’t know `n`

.

Let’s summarize all of this:

- We have some cryptosystem that looks like an RSA, but it is not an RSA.
- We don’t know any parameters of the cryptosystem.
- We have an encryption oracle
- We have an encrypted flag

## Solution

So what do we do? We have encrypted flag:

To decrypt it, we would have to calculate square root modulo `n`

. Well, first of all, we don’t know `n`

. How do we find it? That’s where the encryption oracle becomes useful.

Remember the definition of modulo operation:

So, if we ask server to encrypt some `x`

, such that `x^2`

is greater than `n`

, then we have:

where `k >= 1`

. Then

Now, the only value we need to calculate `n`

is `k`

. Well, we can find such value `x`

so that its square is only slightly bigger than `n`

, so `k`

will be equal to 1. But there is actually better idea, which also works for bigger powers. We take two numbers `x`

and `y`

such that `x^2 > n`

and `y^2 > n`

, and encrypt them both

Which gives us the following

And finally we can calculate

For `x`

and `y`

I used `2^256`

and `3^256`

, because `p`

and `q`

are both 256-bit long, so `n`

is 512 bits long, therefore `x^2 = 2^512`

, which is 513-bit number, will be greater than `n`

. Same logic is for `3^512`

.

Now that we have computed `n`

we have the second problem: we need to calculate square root modulo `n`

, and this is at least as hard as factorizing the `n`

.

I suppose we will have to factorize `n`

after all. We could use some existing services for that, like Alpertron, but recall the primes generation process. Primes generated in such a way that `p`

and `q`

are two adjacent primes. Therefore both `p`

and `q`

are really close to square root of `n`

. And that’s what we are going to use. We will calculate square root of `n`

and look for a number that divides `n`

around the root. There is a great chance that we will find such a number in no time.

Finally, once we have factorized `n`

the only thing left is to compute the flag. Remember that we cannot calculate `f = (p — 1) * (q — 1)`

and compute `d`

such that `e * d = 1 (mod f)`

because `GCD(e, f) = 2`

. So this is not an RSA cryptosystem. But what is it actually? This is a Rabin cryptosystem, so we use formulas from Wikipedia to decrypt the flag:

And one of `r1, r2, r3, r4`

will be the correct plaintext.

Below is the solution source code. Here I use my own package `ptCrypt`

where I have some useful functions, but you can find analogues of those functions in popular libraries, such as `PyCrypto`

.

Code run result:

**awawa@awawa-pc**:**~/Documents/CTF/niteCTF**$ python3 rabin_solution.py

[**+**] Opening connection to rabin.challenge.cryptonite.team on port 1337: Done

Obtaining x

Obtaining y

Calculating modulus

Obtaining flag

Factoring modulus

Decrypting

b'\x84\x14hMnf\xc7\xda\x12:\xac\xb7_\xdd\xe7\x06\xae\xc0\xf8\x99\x1a\xbbX\xf57\xc5\x9b\xde\xbc\x90&$\xfeq\x9d\x87\\U\xd4\xba\xcd2\xd0z\xe0\x06\td\x9e\xb4\xd1?\xe4\x06\x04\x84\x0e:\xec\x06\x19g}\x1c'

b'**nite{r3p34t3d_r461n_3ncrypt10n_l1tr4lly_k1ll5_3d6f4adc5e**}'

b'KQ\xbe0k\xdcCH\xa9u\xb6\x1eC\x1b\x9dk\r\xa8L\xea\xfa\x9f\x91\xa4\xf3\xbe\x88\xf3\xb44\x8aq\xe2t\xf2\x88\xef\\u\xae\xecI[\xd1\xd9\xb2\xc3&\x8e\x83\xc6;\xc7q`{\xdc\x8b\x8c\xcb\xdb=A\x8b'

b'8\xc2\xaa\x1d\x02\x8a\x84\xff\xd29\\\x14\x8e\xf5\xb9\xce\xd5\x8c\xdf\x12\x7f\x8d\xfb\x86uur\x1ev\xbf\x0e,\x8cp\xdc.\xdbX\xcb=U[\xa9\x15r\xcc\xa5\xa9A\x9dw9{\xc8\x08>\x97\xe3\xc0\x9e\xa1_\xa1\x0e'

**awawa@awawa-pc**:**~/Documents/CTF/niteCTF**$