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.
