"Twenty Years of Attacks on the RSA Cryptosystem" - Dan Boneh
RSA에 대한 공격을 가장 자세하게 잘 다루는 review paper인 것 같다. 인용 횟수가 900번 근처다...
논문 리딩은 기본적으로 복습을 하면서 더 배우려고 하는 것이기 때문에, 내가 배운 내용도 조금씩 추가하면서 쓰겠다.
또한, Lattice를 제대로 알아야 (특히 LLL) 더욱 자세하게 글을 쓸 수 있을 것으로 보인다. 일단은 맛만 보는 걸로.
#1: Introduction
RSA는 카이사르 암호와 함께 가장 유명한 암호체계 중 하나일 것이다. 1977년 공개된 이 암호체계는 지금도 사용되고 있다.
많이 사용되는 체계인만큼, 많은 암호학자들은 이 체계의 허점을 찾기 위해서 수많은 공격 방법들을 제시해왔다.
공격 방법을 탐구하는 과정을 통해서, 암호학자들은 RSA를 안전하게 구현하고 활용하는 방법을 더욱 알아가게 되었다.
논문의 목적은 이러한 공격들을 돌아보면서, 공격을 위한 수학적 도구에는 어떤 것이 있으며, 이를 막는 방법을 알아보는 것이다.
먼저 Textbook RSA를 살펴보자. $p, q$를 크기가 비슷한 큰 소수라 하고, $N=pq$라 하자. 두 자연수 $e, d$는 $ed \equiv 1 \pmod {\phi(N)}$을 만족하는 자연수다. 여기서 $\phi(N) = (p-1)(q-1)$이다. 이때 $N$을 RSA modulus, $e$를 encryption exponent, $d$를 decryption exponent라고 부른다. $\langle N, e \rangle$은 모두 공개되어 있고 (공개키), 메세지를 암호화하는데 사용할 수 있다. 한편, $\langle N, d \rangle$은 비밀이며 (비밀키), 암호화된 메세지를 받는 사람만이 알고 있다. 메세지를 받는 사람은 비밀키를 이용하여 실제 메세지를 확인할 수 있다. 여기서 메세지란, $M \in \mathbb{Z}_N^{*}$을 말한다. $M$을 암호화하려면, $C \equiv M^e \pmod{N}$을 계산하면 된다.
이를 복호화하려면, $M \equiv C^d \pmod{N}$을 계산하면 된다. 여기서 $ed \equiv 1 \pmod{ \phi(N)}$과 오일러의 정리를 이용한다.
RSA 함수를 $x \rightarrow x^e \pmod{N}$으로 정의하자. $d$를 알면, 이 함수의 역을 쉽게 구할 수 있다.
슬슬 One-Way Function의 느낌이 나온다. 이러한 상황에서, 암호학자들은 $d$를 trapdoor라고 부른다.
trapdoor가 있는 one-way function은 전자서명 등에서 활용될 수 있다. 여기서 RSA의 유용함을 알 수 있다.
메세지 $M$을 내가 보냈다는 것을 인증하려면, 비밀키 $d$를 이용하여 $M^d \pmod{N}$을 사람들에게 주면 된다.
그렇다면, 다른 사람들은 공개키 $e$를 이용하여 $M \equiv (M^d)^e \pmod{N}$, 즉 실제 메세지를 얻는다.
여기서는 $d$에 대한 정보가 없을 때, RSA 함수의 역함수를 계산하는 난이도에 대해서 다루도록 한다.
즉, $N, e, C$가 주어진 경우, $C$의 discrete $e$-th root modulo $N$을 구하는 난이도에 대해 다루는 것이다.
당연히 전수조사의 방법이 있으나, 이는 역시 당연하게도 매우 비효율적이다. 불가능하다고 보는 게 맞겠다.
우리가 관심이 있는 대상은 당연히 실제로 사용될 수 있는 공격들, 특히 다항식 시간을 필요로 하는 공격들이다.
실제 RSA를 이용한 암호체계는 단순한 RSA 함수 응용의 범주를 넘어간다. 안전한 암호가 되려면 빡빡한 기준을 통과해야 한다.
단순하게 RSA 함수를 이용하여 암호화를 하면, 메세지 $M$에 대한 non-trivial information을 손쉽게 얻을 수 있다.
대표적으로, $M$의 modulo $N$에 대한 Jacobi Symbol의 값을 매우 간단하게 얻을 수 있다.
또한, 단순하게 RSA 함수를 이용하여 암호화를 하면 adaptive chosen ciphertext attack에 아주 간단하게 당한다.
복호화를 하고 싶은 $C \equiv M^e \pmod{N}$이 있다고 하자. $2^eC$를 복호화하는 쿼리를 날려보자.
그러면 얻는 답은 $(2^eC)^d \equiv 2C^d \equiv 2M \pmod {N}$이다. 여기서 $M$을 복원하는 것은 쉬운 일이다.
그러니 실제로 RSA를 이용해서 암호화를 하려면, "랜덤함"으로 적당히 간을 쳐서 암호화를 할 필요가 있다. 여기서는 다루지 않는다.
RSA를 사용하기 위해서는, 먼저 큰 소수 $p, q$를 잡는다. 랜덤하게 큰 수를 잡고 적당한 소수 판정법을 쓰면 된다.
그 후 $N = pq$를 얻은 뒤, 적당한 $e$를 잡고 modulo inverse를 계산하는 알고리즘으로 $d$를 계산한다.
물론, 소수는 충분히 많기 때문에, 이러한 방법으로도 RSA key pair를 효율적으로 생성할 수 있다.
RSA를 공격하는 가장 생각하기 쉬운 방법은 사실 그냥 $d$를 찾는 것이다. $d$를 어떻게 찾을 수 있을까?
가장 쉬운 접근은 역시 $\phi(N)$을 찾는 것이다. 그런데 이는 $N$을 소인수분해하는 것과 동치임을 쉽게 파악할 수 있다.
소인수분해가 얼마나 어려운 문제인지는 꽤 잘 알려져 있다. GNFS가 현재까지는 가장 빠르지만, 여전히 느리다.
여기서 우리는 $g^{2^K uvw} \equiv 1 \pmod {N}$이고, $g^{2^{K-1}uvw}$는 우리가 원하는 형태를 갖춤을 알 수 있다.
$k = 2^{2K+C} uvw$이니, 위 알고리즘을 사용하면 우리가 원하는 $g^{2^{K-1}uvw}$를 마주치고 소인수분해에 성공한다.
두 경우 모두에서, 성공 확률이 50% 이상임을 쉽게 파악할 수 있다. 그러니 이를 충분히 반복하면 인수분해에 성공한다.
#2: Elementary Attacks
첫 번째로 살펴볼 것은 메세지 자체가 크기가 작은 경우이다. 만약 $M$이 크기가 작고, 크기가 비슷한 두 자연수의 곱으로 표현될 수 있다고 하자. 이 경우, 간단한 meet-in-the-middle attack을 통해서 메세지를 복원할 수 있다. Key의 크기가 커도 메세지의 크기가 작으면 소용없다는 점을 간과한 경우 발생하는 문제다.
이와 같이 RSA를 잘못 활용한 경우 이를 공격하는 방법을 여기서 더 소개한다.
두 번째로 살펴볼 것은, 모든 사람들에게 공통된 $N$을 사용하게 하는 경우 발생하는 문제점이다.
각 사람들마다 서로 같은 $N$을 주는 대신, 각 사람들에게 $e_i, d_i$를 부여하면 어떻게 될까? (물론, $p, q$는 알려주지 않는다)
다른 사람의 공개키 $e_i$를 봐서 $d_i$를 계산할 수 없으므로 ($p, q$는 모르니까) 이 방법은 잘 먹힐 것처럼 생겼다.
하지만 앞에서 보았듯이, $e_i, d_i, N$을 알면 효율적으로 $N$을 소인수분해 할 수 있다. 그러니 이렇게 하면 나라 망한다.
즉, 모든 사람들이 서로 다른 $N$을 갖도록 해야 안전한 암호체계를 만들 수 있다.
세 번째로 살펴볼 것은, "blinding"이란 것이다. Eve가 Alice에게 메세지 $M \in \mathbb{Z}_N^{*}$에 대한 전자서명을 원한다고 하자.
즉, $M^d \pmod{N}$을 원하는 것이다. 물론 호구가 아닌 이상 Alice가 Eve의 말을 듣고 전자서명을 하지는 않는다.
하지만, Eve가 적당한 $r \in \mathbb{Z}_N^{*}$를 랜덤하게 잡고, $M' \equiv r^eM \pmod{N}$을 계산했다고 하자.
이제 Eve는 Alice에게 $M'$에 대한 전자서명을 부탁한다. Alice는 $r$의 존재도 모르고 그러니 $M$도 모른다.
이제 Alice는 큰 문제가 없게 생긴 $M'$에 대한 전자서명을 줄 수도 있다. 이때, 그 전자서명의 값은 $rM^d \pmod{N}$이 된다.
결국 Eve는 $r$의 modulo inverse를 취해줘서 $M^d \pmod{N}$의 값을 얻게 된다. 전자서명이 뚫린 것이다.
물론, 실제 RSA를 이용한 전자서명이 이렇게 간단하지는 않으므로, 걱정은 하지 않아도 된다.
또한, 논문에 의하면 blinding이 가능하다는 점을 이용하여 "anonymous digital cash"를 구현할 수 있다고 한다.
#3: Low Private Exponent
애초에 작은 $d$ 값을 왜 사용하고 싶어하는 걸까? 이유는 시간에 있다. $d$가 작을수록 decryption에 필요한 시간이 줄어들기 때문이다.
적은 계산 시간은 솔깃하지만, 작은 $d$ 값은 보안성 입장에서 볼 때 매우 위험하다. 다음 공격을 소개한다.
Theorem. (Wiener's Attack) $N = pq$고, $q < p < 2q$라 하자. $d < \frac{1}{3} N^{1/4}$라 하자.
$ed \equiv 1 \pmod{\phi(N)}$인 $N$과 $e < \phi(N)$이 주어졌을 때, $d$를 효율적으로 복원할 수 있다.
앞선 논문 리딩에서도 사용된 연분수를 이용한 rational approximation이 다시 등장한다.
$ed \equiv 1 \pmod{\phi(N)}$이므로, 적당한 $k$가 있어 $ed - k \phi(N) = 1$이다. 그러니, 이를 다시 쓰면 $\displaystyle \left| \frac{e}{\phi(N)} - \frac{k}{d} \right| = \frac{1}{d\phi(N)}$이다.
즉, $\displaystyle \frac{k}{d}$는 $\displaystyle \frac{e}{\phi(N)}$의 근사가 된다. 그런데 $\phi(N)$은 몰라도, $N$은 이미 알고 있다.
또한, $\phi(N) = N -p - q + 1$이고 $p+q-1 < 3 \sqrt{N}$이므로, $|N - \phi(N)| < 3\sqrt{N}$이다.
즉, $\phi(N)$ 대신 $N$을 사용해도 꽤 강력한 근사가 나올 것임을 추측할 수 있다.
그러면 $N_1 , N_2, N_3$가 전부 서로소라고 가정하자. (아니라면, 소인수분해가 간단하게 될 것이다)
이제 중국인의 나머지 정리에서, $M^3 \pmod{N_1N_2N_3}$를 얻을 수 있다. 그런데 $M^3 < N_1N_2N_3$이니, $M$을 얻는다.
이 공격에 대한 간단한 방어를 생각할 수 있다. 각 사람들에게 메세지의 아주 일부를 바꿔서 보내는 것이다.
즉, $i$번째 사람에게 $M^{e_i} \pmod{N_i}$ 대신 $(M+i \cdot 2^m)^{e_i} \pmod{N_i}$를 (물론 $i$와 함께) 보내는 것이다.
여기서 $m$은 $M$의 비트 개수이다. 이 방법은 매우 간단하지만, 위 공격을 막을 수 있을 것으로 보인다.
더욱 일반적으로, 메세지를 전달하고 싶은 사람 $P_1, P_2, \cdots, P_k$가 있을 때, $i$번째 사람에게 $M$을 직접 암호화하는 대신, $f_i \in \mathbb{Z}_{N_i} [x]$를 하나 잡은다음 $f_i(M)$을 암호화하여 (물론, $f_i$와 함께) 보내는 방법을 생각할 수 있다. 이제, Eve가 얻을 수 있는 정보는 다항식 $f_i$와 $e_i, N_i$, $C_i \equiv f_i(M)^{e_i} \pmod{N_i}$이다.
이 상태에서 Eve가 $M$을 도출하는 것은 매우 어려워보인다. 하지만 충분히 많은 정보를 확보하면 가능하다. Coppersmith's Theorem의 위력을 확인해보자.
Theorem. (Hastad's Attack) $N_1, N_2, \cdots , N_k$는 서로소인 자연수이다. $N_{min} = \operatorname{min}(N_1, N_2, \cdots, N_k)$라 하자. 각 $1 \le i \le k$에 대하여, $g_i \in \mathbb{Z}_{N_i}[x]$는 차수가 $d$ 이하인 다항식이라 하자. $g_i(M) \equiv 0 \pmod{N_i}$이 각 $1 \le i \le k$에 대해서 성립하는 $M < N_{min}$이 유일하고, $k>d$가 성립한다고 가정하자. 이때, $1 \le i \le k$에 대하여 $N_i , g_i$를 전부 알 경우 $M$을 다항식 시간에 찾을 수 있다.
먼저, 각 $g_i$가 전부 최고차항의 계수가 $1$임을 가정할 수 있다. $g_i$의 최고차항의 계수가 $N_i$와 서로소가 아니라면, $N_i$를 소인수분해 할 수 있다.
이는 RSA를 다루는 우리의 문맥에서 맞지 않다. 이제 $g_i$의 최고차항의 계수의 modulo inverse를 구해서, $g_i$의 최고차항의 계수를 $1$로 바꿀 수 있다.
또한, $M$이 $N_i$들과 서로소가 아닌 경우 역시 RSA를 다루는 우리의 문맥에 맞지 않다.
그러니, $M$이 $N_i$들과 서로소라고 가정하자. 이러면, $g_i$들에 $x$의 거듭제곱을 적당히 곱해서 모두 차수가 $d$이도록 할 수 있다.
$T_i \equiv \delta_{i, j} \pmod{N_j}$를 만족하는 $T_i$를 CRT로 찾고, $g(x) \equiv \sum_{i=1}^k T_i g_i(x)$를 잡자. $\overline{N} = N_1N_2 \cdots N_k$라 하고, $g(x)$를 $\mathbb{Z}_{\overline{N}}[x]$의 원소로 보자.
$g(x)$의 최고차항의 계수를 각 $i$에 대하여 $\pmod{N_i}$로 보면 $1$임을 확인할 수 있고, 그러니 $g(x)$는 최고차항의 계수가 $1$이다.
또한, $g(x)$의 차수는 $d$이다. 우리가 원하는 $M$은 $g$의 근이며, $M < N_{min} \le \overline{N}^{1/k} < \overline{N}^{1/d}$다.
그러니, $g(x)$와 $\overline{N}$에 대한 Coppersmith's Theorem을 이용하면 $M$을 찾을 수 있다.
그러니 Eve는 $g_i = f_i^{e_i} - C_i$를 잡은 다음, Hastad's Attack을 활용하여 $M$을 복원할 수 있다.
위 정리의 statement를 다시 읽어보면, 이 공격은 $e_i$의 값들이 작을 때 더욱 강력함도 알 수 있다.
실제로 Broadcast Attack에 대한 방어를 하고 싶다면, "랜덤함"으로 적당히 간을 쳐주면 된다고 한다.
두 번째 공격은 Franklin-Reiter Related Message Attack이다. $N, e$가 Alice의 공개키라고 하자.
이제 Bob이 $M_1, M_2 \in \mathbb{Z}_{N}^{*}$를 Alice에게 보내려고 한다.
그런데, 알려진 다항식 $f \in \mathbb{Z}_N [x]$가 있어 $M_1 \equiv f(M_2) \pmod{N}$이 성립한다고 하자.
이제, $C_1, C_2$가 주어졌을 때 Eve가 $M_1, M_2$를 복원할 수 있음을 보일 수 있다.
이 공격은 일반적으로 $\mathcal{O}(e^2)$ 정도의 시간을 필요로 한다고 한다.
일반적인 경우의 증명은 빡센 대수학을 필요로 한다고 하므로, 여기서는 $e=3$이고 $f$가 일차식인 경우를 보인다.
Lemma. $e=3$이라 하고, $N, e$가 RSA를 위한 공개키라고 하자. $M_1 \neq M_2 \in \mathbb{Z}_N^{*}$가 적당한 $f = ax+b \in \mathbb{Z}_N [x]$에 대하여 $M_1 \equiv f(M_2) \pmod{N}$을 만족한다고 하자. 단, $b \neq 0$이다. 이때, $N, e, C_1, C_2, f$를 알면 $M_1, M_2$를 $\mathcal{O}(\log^2 N)$ 시간에 구할 수 있다.
아주 특수한 경우를 다루는 만큼, 증명 역시 크게 어렵지 않다. 먼저 $e$와 관련이 없는 큰 그림을 그려보자.
$M_1 \equiv f(M_2) \pmod{N}$을 알고 있으므로, $M_2$는 $g_1(x) = f(x)^e - C_1 \in \mathbb{Z}_N [x]$의 근이다.
또한, $M_2$는 $g_2(x) = x^e - C_2 \in \mathbb{Z}_N [x]$의 근이기도 하다. 즉, $(x-M_2)$는 $g_1(x), g_2(x)$의 공통 약수다.
그러므로, 유클리드 호제법을 이용하여 $g_1(x), g_2(x)$의 최대공약수를 구한 다음, 그 결과가 일차식이라면 $M_2$를 얻을 수 있다.
Note: 조금 생각을 해보면 유클리드 호제법을 하다가 "문제"가 생기면 $N$의 소인수분해를 얻을 수 있다. 이 점 참고.
특히, $e=3$인 경우에는, 최대공약수가 무조건 일차식이 된다. $g_2(x) = x^3 - C_2$를 생각해보자.
$\text{gcd}(3, \phi(N))=1$이므로, $N=pq$라 할 때 $p, q$는 전부 $2 \pmod{3}$ 형태의 소수이다. 이 경우, $x \rightarrow x^3$은 전단사함수가 된다.
그러므로, $g_2(x) = x^3 - C_2$의 근은 유일하게 존재한다. 즉, $g_2$는 일차식 하나와 irreducible 이차식 하나로 분해된다.
여기서 일차식은 $g_1(x)$와 무조건 공유가 되어야 한다. 공통근이 존재해야 하기 때문이다.
또한, $g_1$과 $g_2$는 서로 나눌 수 없으므로, $g_1$과 $g_2$의 최대공약수는 일차식이 될 수 밖에 없다. 증명 끝.
$e>3$인 경우에는, 최대공약수가 거의 항상 일차식이 되지만, 아닌 경우도 존재한다. 이 경우, 공격은 실패한다.
위 공격을 더욱 강화한 것이 Coppersmith's Short Pad Attack이다. 메세지 $M$에 "랜덤함"으로 간을 해서 암호화를 해야 안전하다고 이미 언급했다.
"랜덤함"으로 간을 하는 가장 간단한 방법은, $M$의 끝에 몇 개의 random bit를 추가하는 것이다.
하지만 이렇게 간을 대충하면 위험하고, 이를 보여주는 것이 Coppersmith's Short Pad Attack이다.
시나리오는 대강 이런 느낌이다. Alice가 Bob에게 메시지 $M$을 전달하려고 한다.
이때 Alice는 $M$의 끝에 몇 개의 random bit를 추가하여 암호화한 다음 Bob에게 전송한다. 이를 Eve가 중간에 연결망을 끊어 Bob이 이를 받지 못하게 한다.
그러면 Alice는 $M$의 끝에 몇 개의 random bit를 다시 추가하여 암호화한 다음 Bob에게 다시 전송하게 될 것이다.
이렇게 되면 Eve는 중간에서 같은 메시지의 (물론, 다른 random bit를 갖는) 암호문을 두 개 확보한다. 이제 Eve는 $M$을 복원할 수 있다.
Theorem. (Coppersmith's Short Pad Attack) $N, e$는 RSA 공개키이고, $N$은 $n$-bit이다. $m=\lfloor n/e^2 \rfloor$라 하자. $M \in \mathbb{Z}_N^{*}$는 길이가 $n-m$ 이하인 메시지이고, $M_1 = 2^m M +r_1$, $M_2 = 2^m M+r_2$라 하자. 이때, $r_1, r_2$는 $0 \le r_1, r_2 < 2^m$을 만족하는 서로 다른 정수다. $N, e$와 $C_1, C_2 \equiv M_1^e, M_2^e \pmod{N}$을 알 때, $M$을 다항식 시간에 얻을 수 있다.
$g_1(x,y) = x^e - C_1$, $g_2(x, y) = (x+y)^e - C_2$라고 하자. 만약 $y = r_2 - r_1$이라면, 두 다항식은 공통근 $M_1$을 갖는다.
논문을 읽어가면서 블로그 포스팅을 쓰는거라, 꽤 부족한 점이 많을 것 같다. 많은 지적과 보완은 환영이다.
"Minimalism in Cryptography: The Even-Mansour Scheme Revisited" - Orr Dunkelman, Nathan Keller, Adi Shamir
#1: Introduction
논문의 제목이 보여주듯이, 이 논문의 주제 Even-Mansour Scheme은 가장 단순한 암호화 방법을 고안하는 과정에서 등장한 개념이다. 특히, Even-Mansour Scheme은 가장 단순하고 안전한 블록암호를 고안하는 과정에서 등장했다. 이 논문에서는 Even-Mansour Scheme에 대한 기본적인 내용과 함께, 그의 변형에 대한 공격과 보안성에 대해서 다룬다. 여기서 제시한 공격이 다른 곳에서도 꽤 잘 먹히는듯 하다. 자세한 내용은 후술한다.
#2: The Even-Mansour Scheme
먼저 Even-Mansour Scheme을 정의하고, 기본적인 보안성에 대한 증명과 공격에 대한 내용을 다루어보자.
$n$-bit string에 대한 공개된 permutation $\mathcal{F}$ 하나를 잡는다. 또한, $n$-bit whitening key $K_1, K_2$를 비밀키로 하자.
이제 $EM_{K_1, K_2}^{\mathcal{F}} (P) = \mathcal{F}(P \oplus K_1) \oplus K_2$로 정의한다. 정말 간단한 암호화 과정이다.
우리가 가정하는 adversary는 다음 두 쿼리를 (다른 말로는, oracle을) 활용해서 공격을 할 수 있다.
adversary는 $E(P) = EM_{K_1, K_2}^{\mathcal{F}} (P)$를 계산할 수 있고, $D(C) = (EM_{K_1, K_2}^{\mathcal{F}})^{-1} (C)$를 계산할 수 있다. 이를 $E$-oracle이라고 한다.
또한, 우리의 adversary는 $\mathcal{F}$-oracle을 불러서, $\mathcal{F}(x)$와 $\mathcal{F}^{-1} (y)$를 계산할 수 있다.
즉, plaintext의 암호화 결과, ciphertext의 복호화 결과를 oracle을 통해서 알 수 있고, $\mathcal{F}$를 이용한 연산도 할 수 있다.
adversary의 목표로 가능한 것은 크게 두 가지로 나뉜다. 첫 번째는 "existential forgery attack"이란 것으로, adversary가 $E(P)=C$가 성립하는 새로운 순서쌍 $(P, C)$를 찾는 것이다. 두 번째는 조금 더 전형적인, 암호화된 메세지 $C$가 주어졌을 때 $E(P)=C$가 성립하는 $P$를 찾는 것이다. 공격의 복잡도는 $E$-oracle의 횟수와 그 종류와 (즉, known/chosen/adaptive chosen) $\mathcal{F}$-oracle의 횟수로 결정된다. $\mathcal{F}$ 자체는 알려져 있지만, $\mathcal{F}$-oracle을 지나치게 많이 활용하면 시간상 문제가 있을 것이다. $E$-oracle은 실제로 뚫어서 얻어내야 하는 것이니, 이 역시 지나치게 많이 쓰기에는 어려움이 있을 것이다. 그러니, 두 oracle의 활용 횟수를 모두 고려하도록 한다. 공격의 성공 확률이란, (첫 번째 경우) 한 번의 시도를 통해서 새로운 $(P, C)$ 순서쌍을 찾거나, (두 번째 경우) $E(P)=C$인 $P$를 찾을 확률으로 정의한다. 이제 본격적으로 보안성과 공격 방식에 대해서 논의할 수 있겠다.
adversary가 $D$번 $E$-oracle을 사용하고, $T$번 $\mathcal{F}$-oracle을 사용했다고 하자. 여기서 $D$는 data의 약자이고, $T$는 time의 약자인 것 같다. 왜 이런 약자를 사용하는지는 꽤 당연한 것 같다. 중요한 사실은, adversary의 성공 확률이 $\mathcal{O}(DT/2^n)$이라는 것이다. 그러니, 기본적으로 공격을 하려면 $DT$가 $\Omega (2^n)$ 정도는 되어야 한다. 여기서 oracle의 총 사용 횟수가 $\Omega(2^{n/2})$ 정도는 되어야 함도 알 수 있다. 증명의 outline을 살펴보자.
$E$-oracle을 $s$번, $\mathcal{F}$-oracle을 $t$번 활용하면 얻는 것은 $E$-pair와 $\mathcal{F}$-pair의 집합 $S = \{ (P_i, C_i) \}_{i=1,2, \cdots s}$와 $T = \{(X_j, Y_j)\}_{j=1,2, \cdots ,t}$다.
이제 $K_1$이 $S, T$에 대하여 나쁘다는 것은, $i, j$가 존재하여 $P_i \oplus K_1 = X_j$가 성립한다는 것이다. 그렇지 않다면, $K_1$은 좋다고 하겠다. 비슷하게, $K_2$가 $S, T$에 대하여 나쁘다는 것은, $i, j$가 존재하여 $Y_j \oplus K_2 = C_i$가 성립한다는 것이다. 그렇지 않다면 $K_2$는 좋다고 하겠다. 또한, $K_1, K_2$가 둘 다 좋다면 $(K_1, K_2)$를 $S, T$에 대하여 좋은 쌍이라고 하겠다. 좋은 쌍의 개수는 적어도 $(2^n-st)^2$ 이상이니, $2^{2n} - 2st \cdot 2^n$만큼은 있다. 또한, $(K, \mathcal{F})$가 (물론, $K = (K_1, K_2)$다) $S, T$와 consistent 하다는 것은, $C_i = K_2 \oplus \mathcal{F}(P_i \oplus K_1)$과 $\mathcal{F}(X_j) = Y_j$이 모든 $i, j$에 대하여 성립한다는 것이다.
Step 1: 비밀키와 permutation에 대한 모든 분포가 uniform하다고 가정했을 때, $(K, \mathcal{F})$가 $S, T$와 consistent하다는 가정에서 $K=k$가 성립할 조건부확률이 모든 $S, T$에 대해 좋은 키 $k \in \{0, 1\}^{2n}$에 대하여 같다는 것을 보인다. 베이즈 정리에서, 이는 $K=k$일 때 $(K, \mathcal{F})$가 $S, T$와 consistent 할 확률이 모든 좋은 키 $k \in \{0, 1\}^{2n}$에 대하여 같음을 보이면 충분하다. $k=(k_1, k_2)$가 좋은 키라고 가정하자. $k$를 고정하고 생각을 하면, $E$-pair의 집합 $S$를 $\mathcal{F}$-pair의 집합 $S'$으로 바꿀 수 있다. $(P_i, C_i)$를 $(P_i \oplus k_1, C_i \oplus k_2)$로 바꿔주면 된다. 또한, $k$가 좋은 키이므로 $S'$과 $T$는 아예 겹치지 않는다. 그러니 consistent 할 확률은 결국 $\mathcal{F}$가 서로 다른 $s+t$개의 pair와 consistent 한 것과 동치이다. 이는 $k$와 무관함이 자명하다. 증명 끝.
Step 2: 성공 확률은 정답에 해당하는 키가 나쁜 키가 되어있을 확률과 정답에 해당하는 키가 좋은 키인 상황에서 adversary가 답을 얻어내는데 성공할 확률의 합 이하임을 증명한다. 이걸 열심히 계산하고 식을 정리하면, 우리가 원하는 결과를 얻을 수 있다고 한다. 논문에서는 뒤에 관련 논의가 사용되지 않는다는 이유로 자세한 설명을 생략했다. Step 2의 내용은 Even-Mansour를 제시한 오리지널 논문에 있다. 이는 나중에 정리해서 올리도록 노력해보겠다.
이 증명을 통해서, 키에 대한 non-trivial information을 얻는 것 역시 $DT = \Omega (2^n)$을 필요로 함을 알 수 있다.
증명 자체가 "좋은 키는 그냥 adversary가 보기엔 다 똑같다"라는 느낌이 강하니까, 직관적으로도 잘 이해되는 부분이다.
이전에 제시된 Even-Mansour에 대한 attack이 간략하게 설명되어 있는데, 간략하게 설명되어 있어서 그런지 이해하기가 조금 어려운 것 같다.
이 논문에 제시된 공격들이 더욱 강력하므로, 그 공격들만을 우선 읽어보고 다시 돌아와야 할 것 같다.
#3: The Slidex Attack and a Tight Bound on the Security of the Even-Mansour Scheme
우선 기존에 알려진 공격 방법인 Slide with a Twist Attack을 살펴보자.
만약 두 plaintext $P, P^*$가 $P \oplus P^* = K_1$을 만족한다고 하자. 이제 이를 암호화하면 어떻게 될까?
$E(P) = \mathcal{F}(P \oplus K_1) \oplus K_2 = \mathcal{F}(P^*) \oplus K_2$고, 마찬가지로 $E(P^*) = \mathcal{F}(P) \oplus K_2$가 성립한다.
그러니 결론적으로 $E(P) \oplus \mathcal{F}(P) = E(P^*) \oplus \mathcal{F}(P^*)$를 얻는다. 이제 공격을 설계해보자.
adversary가 이미 알고 있는 plaintext/ciphertext 순서쌍 $(P_i, E(P_i))$을 총 $2^{(n+1)/2}$개 들고 있다고 하자.
즉, $E$-oracle을 "known" 형태로 이용한다. 이제 $\mathcal{F}$-oracle을 $2^{(n+1)/2}$번 사용하여, $\mathcal{F}(P_i)$를 얻는다.
커다란 배열을 하나 준비하고, $(E(P_i) \oplus \mathcal{F}(P_i), i)$를 정렬된 형태로 저장한다.
이제 $E(P_i) \oplus \mathcal{F}(P_i) = E(P_j) \oplus \mathcal{F}(P_j)$인 $i, j$를 효율적으로 찾을 수 있다.
이제, $K_1 = P_i \oplus P_j$, $K_2 = E(P_i) \oplus \mathcal{F}(P_j)$를 계산하고 이를 실제 키로 추측한다.
birthday paradox의 입장으로 생각하면, $P_i \oplus P_j = K_1$이 성립하는 $i, j$가 존재할 확률은 꽤 높다.
또한, 실제로 collision이 일어나는 순서쌍의 개수는 평균적으로 크지 않을 것이라는 점도 직관적으로 이해할 수 있다.
이 공격에서 $D = T = 2^{(n+1)/2}$이고, $DT = 2^{n+1}$이다. 여기서 $DT = \Omega (2^n)$임도 확인할 수 있다.
Slidex Attack은 위 과정을 일부분 변형해서 생각한다. 두 plaintext $P, P^*$가 $P \oplus P^* = K_1 \oplus \Delta$를 만족한다 하자.
이 경우, 식을 전개해보면 $E(P) = \mathcal{F}(P^* \oplus \Delta) \oplus K_2$와 $E(P^*) = \mathcal{F}(P \oplus \Delta) \oplus K_2$를 얻는다.
즉, $E(P) \oplus \mathcal{F}(P \oplus \Delta) = E(P^*) \oplus \mathcal{F}(P^* \oplus \Delta)$를 얻는다.
이제 $d \le n$을 하나 잡고, 다음과 같은 공격을 시도할 수 있겠다.
먼저 이미 알고 있는 plaintext/ciphertext 순서쌍 $(P_i, E(P_i))$를 $2^{(d+1)/2}$개 들고 있다고 하자.
즉, $E$-oracle을 "known" 형태로 이용한다. 이제 $\Delta_1, \Delta_2, \cdots $를 총 $2^{n-d}$개 준비한다.
각 $\Delta_l$에 대하여, $\mathcal{F}$-oracle을 이용하여 $\mathcal{F}(P_i \oplus \Delta_l)$을 각 $i = 1, 2, \cdots , 2^{(d+1)/2}$에 대해 계산한다.
커다란 배열을 하나 준비하고, $(E(P_i) \oplus \mathcal{F}(P_i \oplus \Delta_l) , i)$를 정렬된 형태로 저장한다. 배열은 총 $2^{n-d}$개 있을 것이다. 이 중 아무 곳에서나 collision이 일어나면, 즉 $E(P_i) \oplus F(P_i \oplus \Delta_l) = E(P_j) \oplus F(P_j \oplus \Delta_l)$이면, $K_1 = P_i \oplus P_j \oplus \Delta_l$, $K_2 = E(P_i) \oplus F(P_j \oplus \Delta_l)$을 실제 키로 추측한다.
비슷하게, $P_i \oplus P_j \oplus \Delta_l = K_1$인 $i, j, l$이 있을 확률은 꽤 높다.
또한, 실제로 collision이 일어나는 순서쌍의 개수는 평균적으로 크지 않을 것이라는 점도 직관적으로 이해할 수 있다.
이 새로운 공격의 장점은 역시 $d \le n$을 마음대로 선택할 수 있다는 점이 되겠다.
#4: The New Single-Key Even-Mansour Scheme
이제 Even-Mansour Scheme의 변형에 대해서 다룬다. 지금까지는 비밀키가 $K_1, K_2$ 두 개가 있었다. 비밀키를 두 개 사용하지 말고, 그냥 하나의 비밀키를 두 번 사용하면 어떨까? 이 생각으로 등장한게 Single-Key Even-Mansour Scheme이다.
$\mathcal{F}$는 $n$-bit string에 대한 공개된 permutation이고, $K$는 $n$-bit 비밀키다.
이때, $SEM_{K}^{\mathcal{F}} (P) = \mathcal{F}(P \oplus K) \oplus K$라 하자. $K_1 = K_2 = K$라고 보면 되겠다.
공격에 대한 기본적인 정의는 동일하다. 또한, 놀랍게도 보안성에 대한 증명은 기존 Even-Mansour와 동일하다고 한다.
결국, Single-Key Even-Mansour에서도 공격을 제대로 하려면 $DT = \Omega (2^n)$을 필요로 한다고 한다.
그러니, 비밀키로 필요한 bit의 개수를 절반으로 줄이면서 동일한 수준의 보안성을 유지할 수 있다는 결론을 얻는다.
Single-Key Even-Mansour에 대한 공격을 생각해보자. 당연히 위에서 다룬 모든 공격은 여기서 적용된다.
하지만, Single-Key의 경우에는 더욱 간단한 공격 방식이 존재한다. 물론, 복잡도는 여전히 $DT = \Omega (2^n)$이다.
$P$를 plaintext라고 하고, $x = P$, $y = P \oplus K$, $z = \mathcal{F}(P \oplus K)$, $w = E(P) = \mathcal{F}(P \oplus K) \oplus K$라 하자.
여기서 중요한 점은 $x \oplus w = y \oplus z$라는 점이다. 이제 $D \le 2^n$을 아무거나 하나 잡자.
adversary가 이미 plaintext/ciphertext 순서쌍 $(P_i ,E(P_i))$를 $D$개 들고 있다고 하자.
즉, $E$-oracle을 "known" 형태로 이용한다. 이제 배열을 준비하고 $(P_i \oplus E(P_i), i)$를 정렬된 상태로 들고 있는다.
이제 임의의 값 $X_1 , X_2, \cdots X_{2^n/D}$를 잡고, $\mathcal{F}$-oracle을 이용한다.
각 $j$에 대하여, $X_j \oplus \mathcal{F}(X_j)$를 들고 가서 미리 준비해놓은 배열에서 탐색한다.
그러니 식을 정리하면 $C \oplus K_2 = P^* \oplus K_1$이고, 즉 $P \oplus C = P^* \oplus C^*$를 얻는다.
이제 쉽다. $E$-oracle을 "known" 형태로 $2^{(n+1)/2}$번 사용한 다음, $(E(P_i) \oplus P_i, i)$를 정렬한 상태로 준비하고 collision을 찾기만 하면 된다.
여기서 $E(P_i) \oplus P_i = E(P_j) \oplus P_j$라면, $P_i \oplus E(P_j) = K_1 \oplus K_2$를 추측하면 된다.
즉, adversary는 $DT = \Omega (2^n)$을 만족하지 않으면서 non-trivial information을 얻을 수 있다.
즉, 기존 Even-Mansour의 보안성을 가지지 않는 variant임을 알 수 있다. 왜 그럴까?
기존 증명을 생각해보면, 비밀키를 고정했을 때 주어진 input/output 쌍과 consistent 하게 될 확률이 비밀키와 무관함을 이용하여 증명을 했다. 그런데 여기서는 involution 구조가 있어서, $\mathcal{I}(x)=y$라는 정보는 강제로 $\mathcal{I}(y)=x$라는 정보를 추가한다. 이 점을 더 생각해보면, consistent 하게 될 확률이 비밀키에 의해 달라질 수 있음을 알 수 있다. 어떻게 보면, 공격 자체가 이 점을 상당히 활용하고 있음도 알 수 있다.
신기한 점은, involution 구조에 Single-Key Even-Mansour를 덮으면 이런 문제가 없다는 것이다. 다른 말로 하면, involution 구조를 가정하면 Single-Key가 Two-Key보다 보안성이 강력하다는 것이다. 암호화 과정 전체가 involution이 되고, 계산을 조금 해보면 consistent 하게 될 확률이 비밀키에 의해 달라지지 않음을 확인할 수 있다. 정확하게 말하면, 증명에서 등장하는 $S'$과 $T$ 사이의 dependency가 비밀키와 무관함을 알 수 있다. 여러모로 흥미로운 결과가 된다.
추가적인 관찰은, Two-Key로 암호화를 한 상태에서 $K_1 \oplus K_2$의 값이 유출이 되면, 결과적으로 비밀키 하나로 암호화를 한 것과 동일하다는 것이다.
어쨌든, involution을 활용하고자 할 때 비밀키를 두 개 쓰는 것은 위험하다.
이제 involution 구조에 XOR 대신 덧셈을 사용하면 어떻게 되는지 보자.
동일한 과정을 거쳐서 $K_1 + K_2$를 복원할 수 있다. $C^* - P = K_1 + K_2$를 가정으로 하고 계산하면 된다.
이제 $K_1 + K_2$를 안다는 가정에서, 암호화 과정은 결국 $CISEM(P) = \mathcal{I}(P+K_1) - K_1$과 동일하게 된다.
이는 기존 Even-Mansour과 동일한 보안성을 가짐을 알 수 있다. 공격도 비슷하게 할 수 있다.
한편, involution 구조에 XOR 대신 덧셈을 사용할 때 두 키가 같다면, 즉 $K_1 = K_2$라면, 여기서 $2K_1$을 복원할 수 있다.
즉, $K_1$을 사실상 (비트 하나 제외하고) 복원할 수 있다. 이건 그냥 암호가 제대로 깨진 것이라고 봐야 한다.
그러니 덧셈을 활용한 Even-Mansour에 single-key variant를 추가하고 싶다면, $CSEM(P) = \mathcal{F}(P+K_1) - K_1$을 이용하는 것이 더욱 보안성 측면에서 좋다. $\mathcal{F}$가 involution인 경우에도 보안성이 입증되어 있기 때문이다.
이 모든 내용을 정리하는 표가 논문의 Table 2로 제시되어 있다. 중요한 표이니, 여기에도 올린다.
#6: Memoryless Attacks on the Even-Mansour Scheme
이제 목표는 메모리를 적게 사용하면서 Even-Mansour를 공격하는 것이다. 지금까지 살펴본 공격들은 배열에 $E$-oracle을 통해서 얻을 값들을 정렬된 상태로 저장한다. 하지만 우리가 $2^{n/2}$ 스케일의 데이터를 저장하기에는 무리가 있다. 그러니 메모리를 절약하면서 Even-Mansour를 공격하는 방법을 다루는 것은 충분한 가치가 있는 일이라고 볼 수 있다. 여기서는 $D, T$가 $\mathcal{O}(2^{n/2})$이면서, 메모리는 상수만큼만 필요한 공격을 제시한다.
특히, 이는 앞서 제시한 slide with a twist 공격을 변형한 것으로 볼 수 있는 공격 방식이다.
메모리를 절약하는 알고리즘 중 잘 알려진 것은 Floyd의 cycle detection 알고리즘이다. 여기서도 이를 활용한다.
결국 우리는 $E(P) \oplus F(P)$가 겹치는 것을 찾고 싶은 것이니, cycle detection을 활용할 수 있다.
$P_1$을 임의로 잡고, $P_1$에 대한 $E, \mathcal{F}$-oracle을 이용하여 $E(P_1)$, $\mathcal{F}(P_1)$을 계산한다. 이를 통해서 $P_2 = E(P_1) \oplus \mathcal{F}(P_1)$을 계산한다. 이 과정을 총 $\mathcal{O}(2^{n/2})$번 반복하여, $P_1, P_2, \cdots $를 얻는다. 여기에서 Floyd의 cycle detection 알고리즘을 돌리면, $E(P_i) \oplus \mathcal{F}(P_i) = E(P_j) \oplus \mathcal{F}(P_j)$인 $P_i, P_j$를 찾을 수 있고, 여기서 키를 추측할 수 있다. 기본적인 분석은 slide with a twist attack과 동일하다. 여기서 중요한 점은, Floyd의 알고리즘을 이용했기 때문에 메모리는 상수만큼만 필요하며, $E$-oracle을 날리는 $P_i$가 이전 계산 결과에 depend 하기 때문에 여기서는 "known" 형태로 $E$-oracle을 사용하는 것이 아니라, "adaptive chosen" 형태로 $E$-oracle을 사용해야 한다. 조금 더 강력한 oracle을 사용해야 한다고 보면 되겠다.
또한, 여기서는 $E$-oracle을 $\mathcal{O}(2^{n/2})$ 급으로 사용할 수 없는 경우, 확장하기가 어려움을 알 수 있다.
slidex attack은 $E$-oracle의 사용횟수와 $\mathcal{F}$-oracle의 사용 횟수에 대한 tradeoff를 제공하지만, 이를 memoryless 방식으로 확장하기에는 어려움이 있다. 그래서 $D << 2^{n/2}$를 가정한 상태에서 memoryless attack을 하는 방법은 이 논문에서 제시한 하나의 open problem이다. single-key variant에서도 마찬가지로 이를 생각할 수 있다. $D, T$가 $\mathcal{O}(2^{n/2})$이면서 memoryless attack을 하는 것은 어렵지 않으나, $D << 2^{n/2}$를 가정한 상태에서 memoryless attack을 하는 것은 어렵다. 이 역시 하나의 open problem으로 남기면서, 논문의 main text는 끝난다.
우선 $P, Q$가 서로 다른 $3 \pmod {4}$ 소수라 하고, $N=PQ$라 하자. 여기서 우리는 $N$과 서로소인 quadratic residue만을 다루겠다.
$QR_N$을 $N$과 서로소인 $N$의 이차잉여들의 집합이라 하자. $QR_N$의 집합의 크기가 $\phi(N)/4$임은 자명하다.
간단한 정수론으로, 다음 사실들을 쉽게 증명할 수 있다. 증명은 기초적이므로 생략한다.
Fact 1: 각 quadratic residue는 총 4개의 서로 다른 discrete square root를 가진다.
Fact 2: 4개의 서로 다른 discrete square root 중, 정확히 하나가 quadratic residue가 된다.
Fact 3: 여기서 우리는 $x \rightarrow x^2 \pmod{N}$이 $QR_N$에서 $QR_N$으로 가는 전단사함수임을 알 수 있다.
이제 $x_0 \in QR_N$, $x_{i+1} = x^2_i \pmod{N}$, $b_i = x_i \pmod{2}$라 할 때, 우리가 무엇을 할 수 있는지 생각해보자.
Fact 1: $N$을 알고, $x_0$를 알면, 빠르게 $x_1, x_2, \cdots $와 $b_1, b_2, \cdots$를 계산할 수 있다. 자명하다.
Fact 2: $N$의 소인수분해를 알고 $x_k$를 알면, 빠르게 $x_{k-1}, x_{k-2}, \cdots$와 $b_k , b_{k-1}, \cdots$를 알 수 있다.
이는 discrete square root를 계산하는 것이 어렵지 않기 때문이다. Tonelli-Shanks를 생각해도 되고, 애초에 $3 \pmod{4}$ 소수를 다루니 그냥 단순하게 계산할 수도 있다. 이제 CRT를 덮어주면 계산을 다항식 시간에 충분히 할 수 있을 것이다. 어렵지 않은 이야기.
Fact 3: $x_k$를 알 때 $x_{k-1}, x_{k-2} , \cdots$를 계산하는 것은 $N$의 소인수분해를 찾는 것 이상으로 어렵다.
강력한 사실이다. 이걸 보이기 위해서는, $x_k$를 알 때 $x_{k-1}$을 쉽게 계산할 수 있다면 $N$의 소인수분해 역시 쉽게 계산할 수 있음을 보이면 충분하다. $N$에 대한 Jacobi Symbol의 값이 $-1$인 $x$를 하나 잡고, $y \equiv x^2 \pmod {N}$을 생각하자. 이제 $y$를 기준으로 역추적을 하면, $x'^2 \equiv y \pmod{N}$인 이차잉여 $x'$을 얻을 수 있을 것이다. 이제 $x'+x$와 $N$ 사이의 최대공약수를 찾아서 $N$을 소인수분해할 수 있다.
그런데 사실 우리의 진짜 목표는 $x_i$들이 아니라 그들의 parity인 $b_i$들이다.
$x_i$라는 정보들이 우리에게 $b_i$를 역추적/예측을 하는데 있어서 얼마나 도움을 줄까? 이를 엄밀하게 정의할 필요가 있다.
다항식 $f$를 고정하고, $0 < \epsilon \le 1/2$인 실수 $\epsilon$를 고정하자. 다항시간에 작동하는 확률적 알고리즘이 $N$에 대하여 $x_0 \in QR_N$가 주어졌을 때 $x_{-1}$의 parity를 guessing 하는데 $\epsilon$-advantage가 있다는 것은, $\frac{\sum_{x_0 \in QR_N} P(\text{correct})}{\phi(N)/4} \ge \frac{1}{2} + \epsilon$이라는 것이다. 여기서 $P(\text{correct})$란, $x_0$가 input으로 주어졌을 때 $x_{-1}$의 parity를 성공적으로 출력할 확률이다. 비슷한 방식으로, $x_0$가 주어졌을 때 $x_0$가 quadratic residue인지 guessing 하는데 $\epsilon$-advantage가 있다는 것이 무엇인지를 정의할 수 있다. 여기서 주의할 점이 있는데, Jacobi Symbol을 활용하여 이차잉여가 아닌 값들 일부를 다항시간에 분류할 수 있다. quadratic residue에 대한 $\epsilon$-advantage를 정의할 때는, Jacobi Symbol의 값이 $1$인 원소가 주어졌을 때 이 값이 quadratic residue인지 판별하는 문제를 생각한다. 당연하지만, Jacobi Symbol이 $1$인 원소 중 정확히 절반이 quadratic residue다. 그러니 위 정의와 비슷한 정의를 그대로 가져다가 쓸 수 있겠다. 분모만 $\phi(N)/2$로 바꾸면 된다.
이제 다음을 순서대로 증명한다. 아이디어가 확실히 느낌 있다.
Step 1: $\epsilon$-advantage for guessing parity can be converted to $\epsilon$-advantage for guessing quadratic residuosity
Step 2: $\epsilon$-advantage for guessing QR can be amplified to a $1/2-\epsilon$-advantage for guessing QR
이 시점에서 우리는 $\epsilon$-advantage가 있다면 QRP의 난이도에 대한 우리의 가정에 모순이 발생함을 얻는다.
즉, $N$의 소인수분해를 모르는 시점에서 우리는 $\epsilon$-advantage 조차 얻을 수 없다. 그냥 동전 던지라는 거다.
Step 1: $x$가 Jacobi Symbol $1$을 갖는 원소라고 하자. 우리의 목표는 $x$가 quadratic residue인지 판별하는 것이다.
$x_0 = x^2 \pmod{N}$이라 하면, $x_0$의 discrete square root 중 Jacobi Symbol $1$을 갖는 것은 $x$와 $N-x$다.
$N$이 홀수이므로, 두 값은 다른 parity를 갖는다. 그러니 parity를 잘 찍는 것과 quadratic residue를 잘 찍는 것은 동치다.
Step 2: 통계학에 가깝다. 그냥 테스트를 반복해서 적용하면 된다. 실제로 서술하는 것은 꽤 까다로울 듯.
내 이해가 맞다면 Step 2가 없어도 어쨌든 QRP의 난이도에 대한 가정에 모순이 발생할 것이다.
이제 $x_0$ 하나를 가지고 $x_{-1}$의 parity를 보는 것에 대한 논의가 끝났다. 이제 진짜 우리가 다루고자 하는 것을 보자.
$b_1, b_2, b_3, \cdots b_k$를 알고 있을 때, $b_0$를 높은 확률로 결정할 수 있을까? 다시 엄밀하게 정의를 하자.
Predictor $P$는 $N$과 $b_1b_2 \cdots b_k$를 (단, $k$는 $|N|$에 대한 다항식에 bound 된다) 입력 받아서, $0$ 또는 $1$을 출력하는 확률적 알고리즘이다. $P$가 $\epsilon$-advantage가 있다는 것은, 적당한 $k \le \operatorname{poly}(|N|)$이 있어 $x \in QR_N$에 대하여 $b_i(x)$를 $x^{2^i} \pmod {N}$의 parity라 할 때, $b_1(x), b_2(x), \cdots b_k(x)$와 $N$을 input으로 받아서 predictor가 $b_0(x)$를 출력할 평균적인 확률이 (모든 $x$를 고려했을 때) $\frac{1}{2} + \epsilon$ 이상이라는 것이다.
말이 많지만, 어쨌든 위에서 다룬 $\epsilon$-advantage와 큰 그림의 차이는 없다. 목표는 역시 $\epsilon$-advantage가 없다는 것이다.
증명은 어렵지 않다. $x_0 \in QR_N$을 잡은 다음 $x_0x_1 \cdots x_k$를 predictor에게 주자.
그러면 이 predictor는 $x_{-1}$의 parity를 줘야 하는데, 이건 앞에서 불가능하다고 설명했다.
직관적으로도 크게 받아들이기 힘든 내용은 아니라고 생각한다. $x$와 $x^2 \pmod{N}$ 사이의 one-way 느낌을 잘 써먹는 것 같다.
next-bit test를 통과하면 모든 polynomial statistical test를 통과함이 잘 알려져 있다.
여기서는 증명까지 제시하는 것 같은데, 통계학이 꽤 필요한 것 같아서 잠시 남긴다. 직관적으로 이해 불가능하지는 않은듯.
생각을 해보면, 우리는 $x^2 \pmod{N}$에서 (가장 작은) 비트 하나씩을 PRNG에 써먹고 있다.
비트를 여러 개 PRNG에 넣는 것은 어떨까? 그러면 효율은 꽤 좋아질 것이다. 이 질문은 2005년에 답이 나온 것 같다.
일단 결론만 말하자면, $\mathcal{O}(\log \log N)$개의 비트까지는 뽑아도 된다고 한다. 얘는 나중에 읽는 걸로.
가뜩이나 비효율적인 알고리즘으로 평가받는 Blum-Blum-Shub의 성능을 조금이나마 높일 수 있는 좋은 질문거리다.
#8: Lengths of periods of sequences produced by the $x^2 \pmod N$ generator
이제 이 generator를 제대로 써먹으려면 실제로 어떤 성질을 가지는 수열이 생성되는지 탐구할 필요가 있다.
일단 처음으로 볼 내용은 역시 주기성이다. 주기의 길이가 길었으면 좋겠는게 우리의 마음이니, 이를 위해서 $P, Q, x_0$를 어떻게 잡으면 좋을지 생각해보자.
(주기가 있는 점은 자명한 것이, $x \rightarrow x^2$이 $QR_N$에서 $QR_N$으로 가는 전단사함수다)
논문 내용을 그대로 옮기는게 아니라, 내 생각/이해가 꽤 섞여있으니 참고. 틀린 점 있으면 지적 환영 :)
"A Simple Unpredictable Pseudo-Random Number Generator" - Blum, Blum, Shub
1. Introduction
PRNG는 seed라고 하는 일종의 초기값을 주었을 때, 빠른 방식으로 랜덤해보이는 비트 수열 하나를 생성하는 방법이다.
여기서 중요한 단어는 "랜덤해보이는"인데, 이게 참 애매한 단어다. 결정론적인 알고리즘을 통해서 랜덤해보이는 수열을 생성한다는 것 자체가 꽤 신기한 접근이다. 하지만 암호론에서 우리는 공격자가 PRNG와 진짜 랜덤한 수열을 구분하지 못하기를 원하면서 PRNG를 활용한다. 그러니 우리는 PRNG의 "랜덤해보이는" 점을 실제로 확인할 여러 통계적 방법을 (Frequency Test/Serial Test/Poker-k Test/Run Test) 쓴다. 하지만 이 방법들은 naive한 방법이라는 생각이 든다.
그래서 여기서 새로운 접근을 하는데, 어떤 PRNG로 제작한 길이 $L$ 비트 수열을 보고, 다음 $L+1$번째 비트를 예측하는 것이 얼마나 어려운지를 따지는 것이다. 우리의 궁극적인 목표는, 다항식 시간에 $\frac{1}{2}$ 초과의 확률로 $L+1$번째 비트를 예측하지 못하도록 하는 것이다. 즉, 다항식 시간으로 뭘 해봤자, 그냥 동전 던지는 수준을 벗어나지 못하도록 하자는 것이다. 비슷하게, $L$ 비트 수열을 보고, 그 전에 어떤 수열이 나왔는지 복원이 불가능하도록 한다. "CSPRNG"를 참고하자.
엄밀하게 이야기를 하려면, (확률적) 튜링 기계 이야기가 나와야 하는 것 같다. 이 부분은 잘 모르므로 생략한다.
이 논문에서는 $1/P$ generator와 $x^2 \pmod N$ generator를 소개하는데, 두 번째 방식이 굉장히 좋다고 소개한다.
첫 번째 방식으로는 완전히 예측가능한 비트 수열이 제작되고, 비트 수열 일부분으로 수열 전체를 효율적으로 복원할 수 있다.
두 번째 방식은 우리가 원하는 안전성을 보장한다. 단, 몇 가지 정수론적 가정이 필요하다고 한다. 이는 뒤에서 서술한다.
두 방식 모두 써먹을 곳이 있다고 하는데, 우리가 원하는 암호론에 써먹을 수 있는 것은 $x^2 \pmod N$ generator다.
2. Notations & Definitions
일단 최대한 논문의 notation을 활용한다. 자연수 $N$에 대하여 $|N|_b = \lfloor 1 + \log_b N \rfloor$를 $N$의 $b$진법 전개 길이라고 하고, $|N| = |N|_2$라 하자. 또한, $\Sigma = \{ 0, 1, \cdots b-1 \}$에 대하여 $\Sigma^*$를 $\Sigma$의 원소로 이루어진 유한 수열의 집합, $\Sigma^\infty$를 $\Sigma$의 원소로 이루어진 무한 수열의 (한 방향으로) 집합이라 하자.
$x \in \Sigma^*$에 대하여 $|x|$는 $x$의 길이이고, $\Sigma^k$는 길이 $k$인 $\Sigma^*$의 수열의 집합이다.
$x \in \Sigma^\infty$에 대해 $x^k$는 $x$의 첫 $k$개 원소로 이루어진 부분 수열이고, $x_k$는 $x$의 $k$번째 원소다. 0-index 활용.
$\mathbb{N}$은 양의 정수로 이루어진 parameter 집합이다. 이제 각 $N \in \mathbb{N}$에 대하여, $X_N \subset \{0, 1\}^n$을 seed의 집합이라 하자.
여기서 $n = |N|$이다. 이제 $X = \{(N, x) : N \in \mathbb{N}, x \in X_N\}$을 seed domain이라 하자.
여기서 우리는 $X$를 $X_N$들의 disjoint union으로 생각할 수 있다. 앞으로도 계속 써먹을 접근법이다.
특히, $X^n = \{(N, x) : N \in \mathbb{N}, |N| = n , x \in X_N\}$을 길이 $n$인 seed의 집합이라 하자.
충분히 큰 자연수 $n$에 대하여, $\mu_n$을 $X^n$ 위에서의 확률분포라고 하자. 이제 $U = \{ \mu_n \}$이 $X$ 위에서의 accessible 확률분포라는 것은, 충분히 큰 자연수 $n$을 입력으로 받고, $X^n$의 원소 중 하나를 $n$에 대한 다항식 시간에 $\mu_n$과 비슷한 확률분포로 뽑아내는 확률적 알고리즘이 존재한다는 것이다.
여기서 "비슷한"의 정의를 엄밀하게 해야겠다. 알고리즘이 실제로 $X^n$의 원소를 뽑아내는 확률분포를 $\mu'_n$이라 하면, 임의의 $t > 0$을 고정했을 때 충분히 큰 $n$에 대하여 $\sum_{(N,x) \in X^n} | \mu_n ( N, x) - \mu'_n (N, x) | < \frac{1}{n^t}$가 성립해야 한다. 컴퓨터가 확률적으로 할 수 있는 일은 fair coin toss 뿐이라고 가정한다.
이제 $X$가 seed domain이고 $U$가 $X$ 위의 accessible 확률분포라면, $(X, U)$를 seed space라고 한다.
때에 따라서, $U$를 생략하고 그냥 $X$를 seed space라고 부를 수 있다.
이제 본격적으로 PRNG를 수학적으로 정의할 수 있다. $\Sigma = \{0 ,1, \cdots , b-1\}$이라 하자.
$b$진법 pseudo-random sequence generator $G$를 정의하려면, seed space $X$가 우선 필요하다.
$G$는 $X$의 원소 하나를 $\Sigma^\infty$로 보내는 함수이다. 그런데 효율적으로 수열을 생성하는 것이 목적이니, 조건을 하나 추가한다. 각 정수 $s \ge 0$에 대하여, 적당한 정수 $t \ge 0$이 있어 $\mu_n (N, x) \neq 0$을 만족하는 모든 $(N, x)$에 대하여 $G(N, x)$의 첫 $n^s$개의 원소가 $\mathcal{O}(n^t)$ 시간에 계산될 수 있어야 한다.
이제 $G(N, x)$를 seed $(N, x)$로 $G$에 의해 생성된 pseudo-random sequence라고 정의한다.
seed space $X$ 위에서의 transformation $T$란, 다항식 시간에 계산될 수 있는 함수 $T : X \rightarrow X$다.
단, 충분히 큰 $n$에 대하여 $T(X^n) \subset X^n$이어야 하고, $T$는 확률분포 $\mu_n$을 보존해야 한다.
즉, 각 $A \subset X^n$에 대하여 $\mu_n (A) = \mu_n (T^{-1}(A))$가 성립해야 한다.
이제 각 seed $x \in X^n$에 대하여, $x, Tx, T^2 x, \cdots$를 $x$의 orbit (under $T$)라 하자.
때에 따라서, $x_0 = x$, $x_k = T^k x$를 정의하기도 한다. 이 경우 $x_{k+1} = T(x_k)$가 성립한다.
seed space $X$를 states $\Sigma$로 보내는 다항식 시간에 계산될 수 있는 함수 $B$를 partition이라 한다.
이제 $\langle X, T, B \rangle$로 구성된 시스템을 하나 생각해보자. 여기서 $X$는 seed space, $T$는 transformation, $B$는 partition이다.
그러면 단순하게 $G(N,x)$의 $k$번째 원소를 $B(T^k x)$로 정의하여, pseudo-random sequence generator를 얻을 수 있을 것이다.
여기서 생각할 수 있는 것은, 만약 $T^{-1}$이 잘 정의되고 계산 가능하다면, 뒤쪽으로 수열을 생성하여 "양쪽으로 무한한" 수열을 만들 수 있다는 것이다.
마지막으로, 앞으로 자연수들을 비트 수열로 간주하고 (natural identification) 이를 다룰 것이다.
또한, $Z_n^{*}$를 $n$과 서로소인 $n$ 미만 자연수들로 이루어진 multiplicative group이라 하자.
3. The $1/P$ generator
$b$진법 $1/P$ generator를 정의해보자. 이를 위해서는 parameter 집합, seed domain, accessible한 확률분포, 그리고 $G$가 필요하다.
parameter 집합은 $\mathbb{N} = \{ P : P \in \mathbb{N}, P > 1 , \operatorname{gcd}(P, b) = 1 \}$이다.
seed domain $X$는 각 $\mathbb{N}$에 속하는 각 $P$에 대해서 $Z_P^{*}$를 disjoint union한 것이다. (자연수를 비트 수열로 본다)
$X$는 $\{r/P : P \in \mathbb{N}, r \in Z_P^{*} \}$와 identify할 수 있다. 이는 $[0, 1)$ 위에서 dense한 집합이다.
이제 accessible한 확률분포를 정의하자. $\mu_n(P, r) = u_n(P) \cdot v_P(r)$로 정의한다.
여기서 $u_n$은 $|P| = n$인 $P$에 대한 uniform distribution이다. $v_P$ 역시 $Z_P^{*}$ 위의 uniform distribution이다.
유한집합에서 하나의 원소를 uniform random하게 고르는 것은 어렵지 않으므로, $U = \{\mu_n\}$은 accessible하다.
이제 $G$를 정의하자. $G : X \rightarrow \Sigma^\infty$를 하나 만들어야 한다.
$X = (P, r)$이라 할 때, $G((P, r))$은 $r/P$를 $b$진법 전개한 수열이다. 이를 생성하는 것은 당연히 어렵지 않다.
그러니 $G$는 우리가 원하는 조건을 잘 만족하는 PRNG가 되겠다.
무언가 많고 복잡하게 썼지만, 결국 우리는 분모가 $b$와 서로소인 $0$과 $1$ 사이의 분수를 하나 적당하게 잡은 다음, 이를 $b$진법 전개하겠다는 것이다.
나쁘지 않은 접근이다. 이제 이 PRNG를 state와 transformation의 언어로도 서술할 수 있다.
여기서 $T$는 $X$에서 $X$로 가는 함수로, (여기서 $X$를 $[0, 1)$의 부분집합으로 identify) $T(x) = bx \pmod {1}$이 되겠다.
이제 partition $B$는 $B(x) = \lfloor bx \rfloor$로 생각할 수 있음 역시 자명하다.
결국 $T, B$는 우리가 생각하는 일반적인 $b$진법 전개 알고리즘을 그대로 보여주는 것들이다.
4. The generator $x^2 \pmod N$
비트 수열을 생성하는 $x^2 \pmod N$ generator를 정의해보자. 위에서 논의한 것처럼, 필요한 구조들을 하나씩 살펴보자.
parameter 집합은 서로 다르고, 같은 길이를 갖는 $3 \pmod {4}$ 형태의 소수 $P, Q$의 곱으로 나타낼 수 있는 모든 자연수다.
또한, seed domain $X$는 각 $\mathbb{N}$에 속하는 각 $N$에 대하여 $\pmod{N}$의 이차잉여의 집합을 disjoint union한 것이다.
이제 확률분포를 정의해야 한다. $\mu_n (N, x) = u_n(N) \cdot v_N(x)$라고 하자.
여기서 $u_n$은 $|N|=n$인 $N$에 대한 uniform distribution이고, $v_N$은 $\pmod{N}$의 이차잉여의 집합에 대한 uniform distribution이다.
이 확률분포 역시 accessible 하다. $|N|$의 길이를 고정한 상태에서 $N$ 하나를 uniform하게 뽑아보자.
$P, Q$의 길이가 자동으로 결정되니, $P, Q$를 uniform 랜덤하게 뽑은 다음 조건을 만족하는지 검토하는 것을 반복하면 된다.
여기서 가장 어려운 부분은 $P, Q$의 소수 여부를 결정하는 것과, $PQ$의 길이가 원하는 $|N|$과 같은지 검증하는 것이다.
소수 판별은 다항식 시간에 가능함을 안다. (리만 가설을 가정하면 Miller-Rabin으로도 되고, 지금은 리만 가설 없이도 안다)
$PQ$의 길이를 판별하는 것은 그냥 곱셈을 때리면 되니까 하면 된다.
또한, $4k+3$꼴 소수의 개수가 충분히 많으니, 랜덤하게 $P, Q$를 뽑아도 다항식 횟수번 이를 반복하면 $P, Q$가 소수인 경우가 나온다.
$4k+3$꼴 소수의 개수가 충분히 많음을 보이는 것은 Prime Number Theorem의 확장으로 가능하겠다.
$N$을 아는 상태에서 이차잉여 하나를 uniform하게 뽑아보자. 마찬가지로 랜덤한 값 하나를 뽑은 다음 이차잉여인지 판별하면 된다.
이차잉여의 개수는 당연히 충분히 많으니, 판별만 다항식 시간에 하면 된다. 오일러 판정 + 중국인의 나머지 정리로 쉽다.
여기서 $N$을 우리가 만드는 과정에서 $P, Q$를 이미 알고 있다는 점을 이용하였다. 제대로 이해한 건지 잘 모르겠다.
이제 transformation을 정의하자. $X$의 원소 $(N, x)$가 있다면, 이를 $(N, x^2 \pmod N)$으로 보내자.
즉, $N, x$를 seed로 받은 뒤 $N$을 고정하고, $x$를 $x^2 \pmod {N}$으로 계속 바꾸겠다는 것이다.
또한, partition $B$는 $X$의 원소 $(N, x)$가 있을 때, $B((N, x)) = x \pmod 2$로 정의하자.
$T, B$가 다항식 시간에 계산되는 값들임은 자명하다. 그러니 우리는 $(N, x)$를 seed로 하는 PRNG를 하나 만들었다.
5. The assumptions.
우리가 고안한 PRNG들의 성질을 확인하려면, 여러 정수론적 문제들의 난이도에 대한 가정이 필요하다.
Discrete Logarithm Problem과, Quadratic Residuosity Problem이 모두 풀기 어렵다는 가정이다.
DLP는 소수 $P$와 그의 원시근 $b$와 $x \in Z_P^*$가 있을 때, $b^y \equiv x \pmod{P}$인 $y$를 찾는 문제이다.
DLP가 어렵다는 것은, 직관적으로 말하면 모든 input에 대해서 다항식 시간에 DLP를 해결하는 확률적 알고리즘이 없다는 것이다.
논문의 용어를 그대로 가져오면, "any procedure for solving the DLP will be inefficient for a fraction of the input"이다.
엄밀한 정의가 논문에 있는데, 이는 필요할 때 뒤에서 후술하는 것으로 한다. (예쁘게 서술하는 방법을 모르겠다)
QRP는 서로 다른 두 홀수 소수의 곱 $N$이 있을 때, $x$가 주어졌을 때 $x$가 $\pmod N$으로 이차잉여인지 판별하는 문제다.
QRP가 어렵다는 것은, 다항식 시간의 확률적 알고리즘으로 이를 풀 경우 틀릴 확률이 있다는 것이다.
결론적으로는, 다항식 시간의 확률적 알고리즘은 단순히 동전을 던져서 "찍는" 것과 큰 차이가 없게 될 것이다.
논문의 용어를 그대로 가져오면, "any efficient procedure for guessing QRP will be incorrect for a fraction of the input"이다.
비슷하게, 엄밀한 정의가 논문에 있는데, 이는 필요할 때 뒤에서 후술하는 것으로 한다. (예쁘게 서술하는 방법을 모르겠다)
6. The $1/P$ generator is predictable.
먼저 정의 몇 가지를 추가적으로 하고 진행하자.
$P, b$는 서로소인 $2$ 이상 자연수이고, $r_0$는 $0 < r_0 < P$를 만족하는 자연수이다.
$r_0 / P = 0.q_1q_2q_3 \cdots $라 쓰자. 이는 $b$진법 전개이다. 자명하게 $q_i$들은 주기를 갖는다.
또한, $r_m = b^m r_0 \pmod P$라고 정의하자. 즉, $r_m / P = 0.q_{m+1}q_{m+2} \cdots$가 된다.
$P, b$가 임의의 자연수일 때, generalized de Bruijn sequence of period $P-1$, base $b$란 주기 $P-1$을 갖는 수열 $q_1q_2 \cdots$로, (단, $0 \le q_i < b$) $|P|_b-1$ 길이의 임의의 $b$-ary 문자열이 이 수열에 등장하고, $|P|_b$ 길이의 임의의 $b$-ary 문자열이 이 수열의 주기에 최대 한 번 등장하는 것이다.
그러니 $r_m = P \cdot (q_{m+1}q_{m+2} \cdots q_{m+|P_b|})/b^{|P_b|} + r_{m+|P_b|} / b^{|P|_b}$가 된다.
$0 < r_{m+|P_b|} < P < b^{|P|_b}$이므로, 뒤의 값은 $0$과 $1$ 사이의 값이다. 그러니 앞의 값에 ceil을 취하면 된다.
문제 3: 이제부터 $P$를 모르고 시작한다. $P$를 찾는 방법을 고안해보자.
일단 여기서는 $r_{m+1} - r_m b$가 $0$이 아닌 $P$의 배수이므로, 여기서 단서를 얻을 수 있겠다.
즉, $P$는 $\frac{r_mb-r_{m+1}}{1}$, $\frac{r_m b - r_{m+1}}{2}$, $\cdots$, $\frac{r_m b - r_{m+1}}{b-1}$ 중 하나다. (부등식 입장에서 보면 자명한 사실이다)
저 수열에서 $1, 2, \cdots b$ 전부와 서로소인 값은 유일함을 쉽게 증명할 수 있고, 그러니 그 값이 $P$가 된다.
$b$에 대한 다항식 시간으로 모든 연산을 할 수 있는데, 여기서 암묵적으로 $b$가 작은 값임을 가정한 것 같다 (확인 필요)
리만 가설을 가정하면 minimum primitive root가 $|P|$의 다항식에 의해 bound 된다고 하니, 괜찮은 것 같다. (확인 필요)
문제 4: $r_m/P = (q_{m+1}q_{m+2} \cdots q_{m+k})/b^k + \epsilon$가 (단, $0 \le \epsilon < 1/b^k$) 성립한다.
그런데 $\epsilon < 1/b^k \le 1/(2P^2) $이므로, $r_m/P$는 $(q_{m+1}q_{m+2} \cdots q_{m+k})/b^k$의 상당히 좋은 rational approximation이 된다.
실제로, $r_m/P$는 $(q_{m+1}q_{m+2} \cdots q_{m+k})/b^k$의 convergent가 됨을 어렵지 않게 보일 수 있다.
특히, $(q_{m+1}q_{m+2} \cdots q_{m+k})/b^k$의 convergent 중 $b$진법 전개를 했을 때 처음으로 $q_{m+1}q_{m+2} \cdots q_{m+k}$가 순서대로 등장하는 것이 $r_m/P$가 됨 역시 어렵지 않게 증명할 수 있다. convergent 전개를 할 때 분자/분모는 지수적 속도로 증가하므로, 이 모든 과정은 다항식 시간에 끝난다.
즉, $b$와 길이 $\lceil \log_b (2P^2) \rceil \le 2|P|_b+1$의 부분수열을 확보하면, 다항식 시간에 전/후 수열을 계산할 수 있다.
솔직히 $b$를 아는 것은 수열을 보면 모든 원소가 정확히 $\{0 ,1, \cdots b-1\}$에서 나오니, 어렵지 않을 것이다.
그러니 길이 $2|P|_b+1$의 부분수열만 확보하면, 이 generator의 모든 것을 파악하고 예측할 수 있다. 약하다.
이 문제를 풀면 접근이 쉬워진다. $dp[S][c]$를 집합 $S$와 그 부분집합들을 모두 색칠하되, $S$를 $c$로 색칠할 경우 최소 비용이라고 정의하자. $S$를 빨간색으로 칠한다면, [$S$의 부분집합 중 파란색으로 칠해진 가장 큰 집합 $V$]은 유일하게 결정된다. (존재하지 않는 경우 포함) 이제 $V$에 존재하지 않는 원소를 갖는 $S$의 부분집합은 전부 빨간색으로 칠해지게 된다. 이를 이용하여, $\mathcal{O}(3^n)$ 동적계획법을 설계할 수 있다. 이를 최적화하려면, SOS DP를 활용하면 된다.
그런디 넘버를 계산하면, 결국 $(a_1 \pmod {x+1}) \oplus (a_2 \pmod{x+1}) \cdots \oplus (a_n \pmod{x+1})$를 계산하는 문제가 된다.
$1, 2, \cdots , n$ 중 홀수번 등장하는 집합을 $S$라고 정의하자. $t(x+1) \le v < (t+1)(x+1)-1$인 $v \in S$에 대하여 $(v-t(x+1))$의 XOR 값을 로그 시간에 계산할 수 있으면, $\mathcal{O}(n \log^2 n)$에 문제를 해결할 수 있다. 이를 위해서, $\displaystyle f(i, 2^k) = \oplus_{i \le x < i+2^k, x \in S} (x-i)$라고 정의하자.
이 함수는 Sparse Table과 비슷한 방식으로 계산될 수 있고, 우리가 원하는 값들 역시 이를 이용하여 로그 시간에 계산할 수 있다.
계산하는 과정이 굉장히 절묘하다. XOR의 성질과 Sparse Table의 성질이 절묘하게 잘 맞아떨어지는 것 같다.
각 $k$에 대해서 $c_k$를 구하는 문제를 풀자. 이제 index가 $k$의 배수인 값들만 보면 된다.
이제 $\text{gcd}(i, j)=1$, $1 \le i, j \le \lfloor \frac{n}{k} \rfloor$인 경우 $|a_{ik}-b_{jk}|$의 최댓값을 보면 될 것이다.
그러니 $c_1$을 빠르게 구하는 방법을 고안하면, 이를 이용하여 $c_1, c_2, \cdots c_n$을 전부 구할 수 있다. $c_1$을 구하자.
답에 대한 이분탐색을 하자. $|a_i-b_j| \ge C$인 $\operatorname{gcd}(i, j)=1$이 존재함을 판별하면 된다.
이를 위해서는 $X = \displaystyle \sum_{1 \le i, j \le n, |a_i-b_j| \ge C} \sum_{d|\operatorname{gcd}(i,j)} \mu(d) > 0$임을 판별하면 된다. 이는 $\sum_{d|n} \mu(d) = [n=1]$을 이용한 것이다.
$i$를 고정하고, $a_i$가 $X$에 추가하는 값을 구하자. 그러면 $\sum_{d|i} \mu(d) \cdot \left( \sum_{j=1}^n [|a_i-b_j| \ge C] \cdot [d|j] \right)$가 $X$에 추가가 된다.
핵심 아이디어는 "처음으로 1번 그룹이 꽉차는 시점", "처음으로 2번 그룹이 꽉차는 시점"으로 경우를 나누는 것이다.
이걸 하면 간단한 조합론적 카운팅으로 식을 세울 수 있다. 문제는 이를 빠르게 계산하는 것이다.
식을 잘 세우면 결국 $\sum \frac{1}{2^k} \binom{k}{n-1}$와 주어진 사람의 수 $k_i$에 대하여 $\sum \frac{1}{2^k} \binom{k}{n-k_i-1}$을 주어진 $k$의 구간에 대하여 빠르게 계산해야 한다는 결론이 나온다.
이 식을 빠르게 계산하는 방법은 잘 모르겠고 (식을 잘 조작하면 $\sum_{i=l}^r \binom{n}{i}$를 빠르게 계산하는 것과 동치다) 이 문제에서는 가능한 $k_i$의 종류가 대충 800개 이하이므로 (합이 20만 이하니까) 이를 이용해서 $\mathcal{O}(n \sqrt{\sum k_i})$로 문제를 해결할 수 있다. 여러모로 재미없는 문제였다. 구현이 좀 힘들었다.
조건이 무섭게 생겼는데, 이를 해석하면 각 연결 컴포넌트의 크기가 6 이하란 것이다. 귀류법으로 크기 7 이상인 연결 컴포넌트가 있다면, $A$를 적당히 잡아서 임의의 $a, b \in A$에 대하여 $A$에 속한 정점만을 통해서 $a$에서 $b$로 가는 경로가 존재하도록 할 수 있다. 그러니 모순을 얻는다.
그러니 각 컴포넌트의 채색다항식을 "상태 압축" 백트래킹 + Lagrange Interpolation으로 얻을 수 있다. Project Euler 194, 544를 참고하면 좋을 것 같다. 이제 답을 구해야 하는데, 정점의 개수가 6 이하인 그래프 중 서로 non-isomorphic한 것의 개수가 200개 정도니 200개 이하의 서로 다른 채색다항식 $p$에 대하여 $p(1), p(2), \cdots p(n)$을 naive하게 계산하면 된다. Project Euler에서 배운 것을 많이 써먹을 수 있었던 문제였다.
이 경우, $a=0$, $b=0$인 경우를 제외하면 중요한 것은 $a, b$ 자체가 아니라 $a \cdot b^{-1} \pmod{p}$만이 중요하다.
그러니 $a=0$이나 $b=0$인 경우를 먼저 처리하고, 조건을 만족하는 $a \cdot b^{-1}$의 값을 모두 구하자.
여기까지는 (역원을 미리 전처리한다면) $\mathcal{O}(p)$에 가능하다. 이제 각 $t$에 대하여 $a \cdot b^{-1} \equiv t \pmod{p}$인 $a, b \in S$의 개수를 빠르게 구하는 방법을 구하자. 양변에 "로그"를 취하면 이는 FFT로 해결할 수 있는 문제의 형태임을 알 수 있다. $\pmod{p}$ 합동식의 입장에서 로그를 취하는 방법은 원시근 $g$를 잡는 것이다. 이제 모든 것을 적당히 정리해주면 $\mathcal{O}(p \log p)$에 문제를 해결할 수 있다. 문제가 더러워 보이는 것을 제외하면 재밌었다.
식 형태가 convolution이고, 여러모로 상황이 XOR, AND, OR-convolution과 비슷하다는 것을 알 수 있다.
FWHT의 근본은 결국 비트별로 변수를 쪼갠다음 각 변수마다 적당히 convolution을 해서 합치는 것이다.
여기서도 비슷하게 할 수 있다. 하지만 convolution 각을 재기가 까다로운데, 기존 FFT, FWHT처럼 "다항식에 값을 대입한다"라는 생각보다는 행렬변환 -> 단순 "pointwise" 곱셈 -> 행렬변환을 통해서 convolution을 해야겠다는 생각을 해야하기 때문이다. 게다가 단순히 $0, 1, 2$의 개수를 가지고 식을 세우려 하면 터지고, 식을 하나 추가해야 convolution을 할 수 있는 형태의 식이 나오게 된다. 여러모로 빡센 문제. 코드는 FWHT에 살짝 변형을 주면 된다.
그런데 FWHT처럼 구현했는데 맞는 이유는 솔직히 잘 모르겠다. 그냥 [각 "비트"별로 convolution을 하는 방법을 고안한 다음 FWHT처럼 짜면 되겠지]라고 생각해서 짰는데, 생각해보니까 FWHT는 multivariable polynomial처럼 생각하면 이해는 되는데 지금 하는 거는 그거랑은 또 달라서... 좀 생각해봐야 할 것 같다. 에디토리얼 찾아봐야 할 듯. Kronecker Product에 뭔가 큰 그림이 있는 것 같기도 하고 ㅋㅋ FWHT 구현 원리부터 다시 봐야겠다.
예전에 koosaga 블로그에서 키워드 Berlekamp-Massey를 봐서 빠르게 풀 수 있었다. 그때는 내가 이걸 진짜 풀 줄 몰랐지...
$p_k$을 $k$번째 시행에서 처음으로 $n$번 정점에 도착할 확률이라고 하자. "처음으로"라는 조건을 그래프로 모델하려면, $n$번 정점에 도착하면 무조건 가상의 $n+1$번 정점으로 가고, $n+1$번 정점에서는 $n+1$번 정점으로만 갈 수 있도록 하면 된다.
Random Walk하면 Markov Chain이고 결국에는 행렬이다. 그러니 $p_k$는 선형점화식을 따른다.
행렬의 크기가 $n$ 근처니 결국 점화식의 크기도 $n$ 근처다. 즉, 초기항 $2n$개 정도를 직접 $\mathcal{O}(nm) = \mathcal{O}(n^2)$ (planar graph에서 $|E| \le 3|V|-6$)에 구한 다음, Berlekamp-Massey를 돌려서 선형점화식을 구할 수 있다. 이제 우리의 목표는 $\sum_{k=0}^\infty kp_k$를 계산하는 것이다.
이는 생성함수를 이용하여 할 수 있다. $f(x) = \sum_{k=0}^\infty p_k x^k$라고 하자.
$p_k$의 점화식을 알고 있기 때문에, 이를 활용하여 $f(x) = \frac{P(x)}{Q(x)}$가 성립하는 다항식 $P, Q$를 구할 수 있다.
목표는 $f'(1)$과 같고, $P, Q$를 계산하고 미분하는 것은 어렵지 않게 $\mathcal{O}(n^2)$에 할 수 있다.
이를 이용하여 증명을 할 수 있다. $G$가 조건을 만족하려면 $G$의 최대 매칭의 크기는 $n-1$이어야 한다.
그러니 $|U|-\operatorname{odd}(G-U)+2n = 2n-2$인 정점의 집합 $U \subset V$가 존재한다.
즉, $\operatorname{odd}(G-U) = |U|+2$인 $U$가 있다. $G$에 임의의 $G$에 없는 간선을 추가한 뒤에는 이 $U$에 대해서도 $\operatorname{odd}(G-U) = |U|$가 성립해야 한다.
즉, $G$에 없는 간선은 전부 크기가 홀수인 컴포넌트 두 개를 잇는 간선이어야 한다. 이는 정말 강력한 조건이고, 여기서 정말 많은 정보를 얻어낼 수 있다.
우선 $G-U$의 각 컴포넌트는 전부 크기가 홀수여야 한다. 크기가 짝수인 컴포넌트가 있으면, "크기가 홀수인 컴포넌트 두 개를 잇는 간선"이 아니면서 $G$에 존재하지 않는 간선이 존재하게 되므로 모순이다. 비슷한 이유로, $G-U$의 각 컴포넌트는 전부 clique여야 한다. clique가 아니면, 컴포넌트 내부에서 그을 수 있는 간선이 있으므로 모순이다. 또한, 삭제한 정점의 집합 $U$에 속한 정점들은 차수가 $2n-1$이어야 한다. 차수가 $2n-1$이 아니면, 새로 그을 수 있는 간선이 존재하게 되기 때문이다. 이제 이를 종합하면, 원하는 그래프를 전부 classify 할 수 있다.
결론은 $G$가 차수 $2n-1$인 정점 $k$개와, 크기가 홀수이고 서로 "독립적인" clique $k+2$개로 분할된다는 것이다.
$k$를 고정하고 생각하면, 이때 $G$로 가능한 그래프의 개수는 홀수 $k+2$개의 합으로 $2n-k$를 만드는 경우의 수다.
이는 식을 잘 조작하면 $k+2$개의 자연수의 합으로 $n+1$을 만드는 경우의 수가 된다.
이를 각 $k \ge 0$에 대하여 더하면, $p(n+1)-1$이 답임을 알 수 있고, 증명이 끝난다.
$\prod_{d|n} \Phi_d(x) = x^n-1$이고 $\Phi_d(x)$ 각각이 irreducible polynomial이므로, 문제는 결국 $\Phi_d$를 구하라는 것이다.
첫 아이디어로 가능한 것은 $\Phi_n(x) = \frac{x^n-1}{\prod_{d|n, d \neq n} \Phi_d(x)}$를 써서 계산하는 것인데, 이 방법은 간단하지 않은 다항식 나눗셈을 많이해야 하므로 비효율적이다.
여기서는 뫼비우스 반전을 생각할 수 있다. 결국 양변에 로그를 취한 다음 뫼비우스 반전을 적용하면, $\Phi_n(x) = \prod_{d|n} (x^d-1)^{\mu(n/d)}$를 얻는다. $x^d-1$ 형태의 다항식은 곱하기도 나누기도 간단하니, 계산을 효율적으로 할 수 있다. 특히, $\mu(n/d) \neq 0$인 경우에만 연산을 하면 되므로 연산 횟수도 생각보다 적다. 계산을 할 때, 먼저 곱할 다항식을 다 곱한 후 나눌 다항식을 나눠주는 게 좋다. 출력 형식을 맞춰주는 것은 적당히 정렬 하면 된다.
문제를 적당히 해석한 뒤 Jimp Number가 정확히 어떤 자연수인지 classify 하는 것은 귀찮지만 어렵지는 않다.
결국 문제는 $n$ 이하 소수의 개수와, $n$ 이하 $4k+3$ 꼴 소수의 개수를 구하는 문제로 전환된다.
$n$ 이하 소수의 개수를 동적계획법으로 $\mathcal{O}(n^{3/4})$에 구하는 방법을 알고 있다면, 이를 간단하게 확장하여 $n$ 이하 $4k+3$ 꼴 소수의 개수를 구하는 $\mathcal{O}(n^{3/4})$ 알고리즘을 설계할 수 있다. 사실 앞에 $\phi(4)=2$라는 상수가 붙는다. 아무튼 이걸 짜면 아슬아슬하게 통과가 된다.
결국 Project Euler 611의 하위호환. 이 문제가 classify 난이도 및 케이스 분석 면을 봤을 때 훨씬 더 어려운 문제 같다.
사실 위에서 언급한 동적계획법은 top-down과 bottum-up 방식을 모두 활용한 뒤, offline query + fenwick tree를 이용하여 $\mathcal{O}(n^{2/3})$으로 최적화가 가능하다. 아니면 아예 Meissel-Lehmer Algorithm를 이용할 수도 있다. 확장이 잘 되는지는 모르겠다. 이런 방법들을 구현해야만 풀 수 있는 문제였다면 훨씬 더 어려운 문제가 되었을 것 같다. 정해는 offline query + fenwick tree로 최적화 하는 방법을 사용하는 것 같다. 이것도 한 번 짜보기는 해야될 듯.
다른 풀이로는 segmented sieve를 조져서 DB를 제작하는 풀이가 있었다고 한다. 엌ㅋㅋㅋㅋㅋㅋㅋㅋ
대충 생각하면, 가장 가까운 점이 삼각형 내부에 들어오지 못하도록 \(C'\)을 잡으려면 \(AC'\) 또는 \(C'B\)의 기울기가 굉장히 작은 interval 안에 들어가야 하고, Stern-Brocot Tree의 원리에서 그 interval 안에 들어가려면 \(AC'\) 또는 \(C'B\)의 길이가 \(AB\)보다 커진다는 것을 증명할 수 있다. 디테일은 생략.
지금 생각하는 건데, '가장 가까운 점'에 대한 추측을 하면 이분탐색 + 변 기준 CCW로도 해결할 수 있을 것 같다.
그런데 이걸 쉽게 하려면 (아마) __int128이 필요할 것이다. Atcoder에서 __int128을 지원하는지는 모르겠다.