# PolyPKC - SCTF 2018 final

###### tags: `Crypto`

## Attachments
- problem
- ploblem.py
- enc
- writeup
- polyPKC.md
- solver.sage
- constants.py

**Attachments are uploaded on** [gist](https://gist.github.com/lemonholic/da5f0b6811d8d64554a813377217525a).

## A brief description

### key generation
RSA처럼 $N=pq$ 를 잡는데, $51\ |\ \phi(N)$ 을 만족하는 소수 $p, q\ (512\ \mathrm{bits})$ 를 선택한다.
그 다음 랜덤한 $r$에 대해 비밀키 $t \equiv r^{\phi(N)/51}\ (\mathrm{mod}\ N)$ 를 얻는다.
여기서 $t^{51} \equiv 1\ (\mathrm{mod}\ N)$ 을 만족하게 된다.

공개키는 차수가 50인 다항식 $f(x) = c_0\cdot x^0 + c_1\cdot x^1 + ... + c_{50}\cdot x^{50}$ 의 계수들의 리스트이다.
계수들은 $0 \le c_i < N$ 의 무작위 난수로 정하고, $c_0$를 적당히 조정해서 $f(t) \equiv 0 \ (\mathrm{mod}\ N)$ 이 되도록 한다.

### encryption
$\mathrm{poly\_mul}$ 함수를 아래 코드처럼 정의한다.

def poly_mul(self, p, q):
    res = [0 for _ in range(self.order)]
    for i in range(self.order):
        for j in range(self.order):
            k = (i + j) % self.order
            res[k] = (res[k] + (p[i] * q[j])) % self.N
    return res

그 뒤 차수가 마찬가지로 50이고 $0 \le d_i < N$ 의 무작위 난수를 계수로 하는 $r(x)$를 잡는다.
이제 메시지 $m$이 주어졌을 때, 암호문 $c(x) = \mathrm{poly\_mul}(f(x), r(x)) + m$ 이다.

### decryption
비밀키 $t$를 사용해서 $c(t) \equiv m\ (\mathrm{mod}\ N)$ 처럼 복호화한다.
일반적으로 $\mathrm{poly\_mul}(f_1(x), f_2(x))|_{x=k} \ne f_1(k)\cdot f_2(k)$ 이지만, $k^{51} \equiv 0 \ (\mathrm{mod}\ N)$ 인 $k$는 예외라는 것을 알 수 있다.

따라서
$$
c(t) \equiv \mathrm{poly\_mul}(f(t), r(t)) + m\\ \equiv f(t)\cdot r(t) + m\\ \equiv 0\cdot r(t) + m\\ \equiv m \ (\mathrm{mod}\ N)$$
이 성립한다.

## Finding out private key $t$
1. $f(t) \equiv 0 \ (\mathrm{mod}\ N)$ 이다.
2. 공격자가 잡은 랜덤 다항식 $s(x)$에 대해 $\mathrm{poly\_mul}(f(x), s(x))|_{x=t}\mod N$ 또한 $0$이다.
3. 따라서 $f(x)$와 $\mathrm{poly\_mul}(f(x), s(x))$에 대해 $\gcd$를 하면 $x-t$ 를 얻을 수 있다.
4. $m \equiv c(t) \ (\mathrm{mod}\ N)$

$N$과 서로 소가 아닌 수들은 $p+q-1$ 개밖에 없기 때문에 $\gcd$를 통해 1차식까지 안전하게 내려갈 수 있다.
안 되면 다른 $s(x)$를 잡아서 돌리면 된다.