PolyPKC - SCTF 2018 final

tags: Crypto

Attachments

• problem
  • ploblem.py
  • enc
• writeup
  • polyPKC.md
  • solver.sage
  • constants.py

Attachments are uploaded on gist.

A brief description

key generation

RSA처럼

$N=pq$ 를 잡는데,

$51|\varphi (N)$ 을 만족하는 소수

$p,q(512\mathrm{bits})$ 를 선택한다.
그 다음 랜덤한

$r$에 대해 비밀키

$t\equiv r^{\varphi (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}\mathrm{\_}\mathrm{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}\mathrm{\_}\mathrm{mul}(f(x),r(x))+m$ 이다.

decryption

비밀키

$t$를 사용해서

$c(t)\equiv m(\mathrm{mod}N)$ 처럼 복호화한다.
일반적으로

$\mathrm{poly}\mathrm{\_}\mathrm{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$는 예외라는 것을 알 수 있다.

따라서

$$\begin{gathered} c(t)\equiv \mathrm{poly}\mathrm{\_}\mathrm{mul}(f(t),r(t))+m \\ \equiv f(t)\cdot r(t)+m \\ \equiv 0\cdot r(t)+m \\ \equiv m(\mathrm{mod}N) \end{gathered}$$
이 성립한다.

Finding out private key

$t$

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

$N$과 서로 소가 아닌 수들은

$p+q-1$ 개밖에 없기 때문에

$gcd$를 통해 1차식까지 안전하게 내려갈 수 있다.
안 되면 다른

$s(x)$를 잡아서 돌리면 된다.