Rating: 4.0

# __X-MAS CTF 2018__

## _Hanukkah_

## Information

**Category:** | **Points:** | **Writeup Author**

--- | --- | ---

Crypto | 50 | MiKHalyCH

**Description:**

> Most of the old religions celebrate Christmas in one way or another!

>

> [hannukah.zip](src/hannukah.zip)

>

> Author: Gabies

## Solution

[Encryption file](src/Hanukkah.py) contains two interesting functions.

```py

def encrypt(m,pubkey):

c=m**2 % pubkey

return c

```

From `encrypt` we can understand that it uses [Rabin](https://en.wikipedia.org/wiki/Rabin_cryptosystem) cryptosystem.

```py

def genKey(k):

while True:

r=getrandbits(k)

while(r%2):

r=getrandbits(k)

p = 3 * r**2 + 2 * r + 7331

q = 17 * r**2 + 18 * r + 1339

n = p * q

if(isPrime(p) and isPrime(q)):

return (p,q) , n

```

`genkey` function shows that `p` and `q` are polynomials from same `r`.

So firstly we need to recover `r`.

We know that `N` is polynomial too:

```py

N = p*q =

= (3*r**2 + 2*r + 7331)*(17*r**2 + 18*r + 1339) =

= 51*r**4 + 88*r**3 + 128680*r**2 + 134636*r + 9816209

```

`r` is 256 bits long, but `N` coefficients are small. It means that `r = iroot(N - 9816209, 4)`. Now we can easy recover `p` and `q`.

Second step is decrypting Rabin. Just because `p = q = 3 (mode 4)` we can easily compute `x_p` and `x_q`:

```py

x_p = sqrt(ct) % p = pow(ct, (p + 1) // 4, p)

x_q = sqrt(ct) % q = pow(ct, (q + 1) // 4, q)

```

Now we have 4 candidates for `m`. We can choose the right one because we know that flag was padded with some `X` characters at end.

Original writeup (https://github.com/VoidHack/write-ups/tree/master/X-MAS%20CTF%202018/crypto/Hanukkah).