rkm0959

하라는 공부는 안하고 단간론파 시리즈를 단간, 슈단, 뉴단 V3까지 정주행을 했다. 

몰입도 하고 느낀 것도 많고 재미도 있고 여운도 강하게 남아서 딱히 후회되지는 않는다.

빠르게 계절학기 잘 마무리하고 제대로 공부에 복귀해야겠다 ㅋㅋ

Matus Nemec, Marek Sys, Petr Svenda, Dusan Klinec, Vashek Matyas - 2017

1. Introduction

이 논문은 2017년의 논문으로, 제목처럼 많이 사용되는 RSA 공개키를 소인수분해하는 방법을 다룬다. 

앞선 논문 리딩에서 언급했듯이 RSA 공개키를 소인수분해하면 RSA 기반 암호는 깨진다. 이는 Textbook RSA든 RSA-OAEP든 마찬가지다.

그러니 이 논문은 당연하게도 많은 사람들에게 충격을 주었고, 실제로 이 논문 때문에 시스템을 교체한 곳도 많다고 한다.

논문의 제목처럼, 이 공격은 저번에도 언급된 Coppersmith's Attack과 관련이 깊다. 그러니 이에 대한 이해가 필수적이다.

이번 논문 리딩에서는 Lattice에 대한 기본적인 내용을 훑고, Coppersmith's Attack에 대한 내용을 증명과 함께 살펴본다.

그 후, 본격적으로 논문을 읽으면서 많이 사용되는 RSA 공개키들이 어떻게 생성되고, 이들이 어떠한 약점을 가지고 있는지 살펴본다. 

2. Brief Introduction to Lattices

사실 나도 잘 모르는 분야지만, 이 논문을 읽는데 필요한 지식들을 간단하게 나열해본다. 자세한 건 나도 빨리 배워야한다.

우리가 다룰 Lattice란, 쉽게 말해서 $\mathbb{R}^n$의 선형독립인 벡터 $v_1, v_2, \cdots, v_d$가 있을 때, $\{ \sum_{i=1}^d a_i v_i  | a_i \in \mathbb{Z} \}$에 해당한다. 

즉, $\mathbb{R}^n$의 subspace를 생각하되 가능한 계수를 $\mathbb{Z}$로 한정시켜서 생각하는 것이다.

이러한 Lattice가 주어졌을 때, 생각할 수 있는 어려운 문제들이 있다. 이들을 간단하게 소개한다.

Shortest Vector Problem: Lattice에 속하는 nonzero vector 중 가장 norm이 작은 것을 구한다.

Closest Vector Problem: Lattice에 속하는 vector 중 주어진 벡터에 가장 가까운 것을 구한다.

이 문제들은 상당히 어려운 것으로 알려져 있고, 이는 곧 Lattice가 암호학에 쓰이는 이유가 된다. (양자내성암호)

Shortest Vector Problem에 대해서 조금 더 논의를 해보자. 

Geometry of Numbers에서 가장 중요한 정리 중 하나인 Minkowski's Theorem을 생각해보자. 이를 활용하면, invertible한 $n \times n$ 행렬 $A$의 column으로 생성되는 Lattice에서 가장 짧은 nonzero vector의 norm이 최대 $\sqrt{n} \cdot \text{det}(A)^{1/n}$임을 어렵지 않게 증명할 수 있다.

그런데 이건 단순히 존재성의 여부이고, 실제로 계산하기에는 매우 어렵다. 

생각해보면, Lattice의 기저가 orthogonal인 경우에는 Shortest Vector Problem이 매우 쉽다는 것을 알 수 있다.

그러니 Lattice 자체는 그대로 유지하면서, 기저를 orthogonal하게 바꾸고 싶다는 전략이 나온다.

단순한 $\mathbb{R}^n$ 공간이었다면 Gram-Schmidt가 가능하지만, 여기서는 정수 계수를 유지해야 하므로 쉽지 않다.

이를 대신하는 알고리즘이 LLL 알고리즘이다. 자세한 디테일은 나도 모르므로 생략하지만, 다음 결과는 중요하다.

이 알고리즘을 통해서, 크기가 $2^{(n-1)/4} \cdot \text{det}(A)^{1/n}$ 이하인 nonzero vector를 찾을 수 있다는 것이다.

또한, LLL 알고리즘은 $n$에 대한 다항시간에 작동하므로, 효율적인 알고리즘이다.

3. Coppersmith's Attack

여기서는 Coppersmith's Attack이 무엇인지를 다룬다. 기본적으로 변수 1개인 경우를 다룬다.

다항식 $h(x) = \sum_{i=0}^n a_i x^i$에 대하여, $||h||^2 = \sum_{i=0}^n |a_i|^2$이라고 하자.

Theorem. (Coppersmith) $N$은 자연수고, $f \in \mathbb{Z}[x]$는 최고차항의 계수가 $1$인 $d$차 다항식이다. $\epsilon \ge 0$을 잡고, $X = N^{1/d - \epsilon}$이라 하자. $N, f$가 주어졌을 때, $|x_0| < X$와 $f(x_0) \equiv 0 \pmod{N}$을 만족하는 $x_0$를 모두 다항식 시간에 찾을 수 있다. 

이 정리를 증명하고, 실제로 $x_0$를 어떻게 찾는지까지 생각해보자.

그 전에 필요한 사전지식이 하나 더 있는데, 바로 다항식을 $\mathbb{Z}[x]$의 원소로 봤을 때 정수근을 찾는 것은 쉽다는 것이다.

이에 대한 내용을 알기 위해서는, 먼저 $\mathbb{F}_p$ 위에서 다항식의 인수분해가 쉽다는 것을 알아야 한다. 이 자료 참고.

그러니 (아마) 충분히 큰 $p$를 잡고 $\mathbb{F}_p$ 위에서의 다항식의 근을 찾은 다음 실제로 근이 되는지를 보면 될 것이다.

이제 본격적으로 Coppersmith's Theorem을 증명한다. 우선 핵심적인 Lemma를 소개한다.

Lemma. $h(x) \in \mathbb{Z}[x]$는 $d$차 다항식이고, $X$는 자연수다. 

$||h(xX)|| < N/\sqrt{d}$이며, $|x_0| < X$가 $h(x_0) \equiv 0 \pmod{N}$을 만족한다면, $h(x_0) = 0$이다.

Proof of Lemma. 접근의 방식 자체는 어렵지 않다. 목표는 $|h(x_0)|<N$을 보이는 것이다.

$|h(x_0)| = \left| \sum_{i=0}^d a_i x_0^i \right| = \left| \sum_{i=0}^d a_i X^i \left( \frac{x_0}{X} \right)^i \right| \le \sum_{i=0}^d \left| a_i X^i \left( \frac{x_0}{X} \right)^i \right| \le \sum_{i=0}^d |a_i X^i|$이다.

위 식의 우변은 Cauchy-Schwarz 부등식에의하여 $\sqrt{d} ||h(xX)||$ 이하가 되고, 다시 조건에 의하여 $N$ 미만이 된다. 증명 끝.

이제 새로운 전략이 나온다. $f(x) \equiv 0 \pmod{N}$의 근을 모두 찾고 싶다면, $f$의 배수인 다항식 중 norm이 작은 것을 하나 찾자.

만약 norm이 충분히 작은 다항식이 나온다면, 그 다항식의 정수근을 찾는 것으로 위 과정을 대체할 수 있다.

$\pmod{N}$을 생각하면서 근을 찾는 것보다 그냥 정수다항식의 정수근을 찾는 것이 훨씬 쉬우므로, 이는 괜찮은 전략이다.

이는 결국 $f(x), xf(x), x^2f(x), \cdots$를 잘 조합해서 작은 norm을 만드는 문제가 되고, Shortest Vector Problem의 냄새가 난다.

하지만 이렇게 단순한 방법으로는 좋은 다항식을 찾기 어렵다는 것을 알 수 있고, 약간의 트릭이 필요하다.

트릭은 $N$ 대신 $N$의 거듭제곱을 생각하는 것이다. $g_{u, v} (x) = N^{m-v} f(x)^v x^u$라는 다항식을 생각하자.

이때, $0 \le u \le d-1$이고 $0 \le v \le m$이다. $m$은 임의로 잡은 값이며 추후에 결정되는 자연수이다.

만약 $x_0$가 $f(x_0) \equiv 0 \pmod{N}$을 만족하면, $g_{u,v}(x)$는 자동으로 모두 $N^m$의 배수이다.

그러므로 바라보는 대상을 $g_{u,v}$로 바꾸고, norm에 대한 제약조건을 $N^m$에 대한 조건으로 바꿔주자.

이제 $n = d(m+1)$이라 하자. $g_{u, v}(xX)$의 차수는 $u + vd$이므로, 이는 $0$부터 $n-1$까지의 값을 순서대로 갖는다.

$g_{u,v}(xX)$의 계수들을 벡터로 보고 Lattice를 만든 후, 이를 행렬로 생각해보자. 이 행렬은 자명하게 triangular하다.

$g_{u,v}(xX)$의 최고차항의 계수가 $X^{u+dv} \cdot N^{m-v}$이므로, 이 행렬의 determinant는 이를 각 $u \in [0, d)$, $v \in [0, m]$에 대하여 곱한 값인 $X^{n(n-1)/2} \cdot N^{dm(m+1)/2}$가 된다. 이제 LLL 알고리즘을 돌려서 'Shortest Vector'를 찾자.

여기서 얻는 'Shortest Vector'의 길이는 최대 $2^{(n-1)/4} \left( X^{n(n-1)/2} \cdot N^{dm(m+1)/2} \right)^{1/n}$이다.

이는 정리하면 최대 $(\sqrt{2}X)^{(n-1)/2} \cdot N^{m/2}$가 되고, 우리의 목표는 이 값이 $N^m / \sqrt{n}$ 미만이 되는 것이다.

그런데 식을 정리해보면 $X = N^{1/d - \epsilon}$일 때 생각보다 잘 부등식이 정리가 되지 않음을 알 수 있다.

이를 해결하기 위해서, $X = \frac{1}{2} N^{1/d - \epsilon}$을 생각해서 우선 Coppersmith's Theorem의 약한 버전을 증명하자.

그 후, $X$의 상위 비트에 대해서 brute force를 진행하면서 각각의 경우에 대하여 위 정리를 반복해서 사용해주자.

그러면 $X$가 $N^{1/d - \epsilon}$인 경우에 대해서도 다항식 시간에 해를 모두 구할 수 있다는 것을 알 수 있고, 나아가 $\epsilon = 0$인 경우까지도 다룰 수 있다.

이 알고리즘은 변수가 두 개인 경우로 확장될 수 있으며, 이를 통해서 다음 결과도 얻을 수 있다.

Theorem. (Coppersmith) $N = pq$가 $n$-bit RSA modulus라 하자. 

이때, $p$의 $n/4$ least significant bits을 알거나 $p$의 $n/4$ most significant bits를 알면, $N$을 다항식 시간에 소인수분해 할 수 있다.

실제로 이 정리에 해당하는 공격을 수행하기 위해서, 변수가 하나인 형태의 Coppersmith's Attack을 사용할 수도 있다.

위 식에서 $N = pq$라고 하면, 우리는 $N$은 알지만 $p$는 모르는 상태다.

만약 충분히 큰 $r$에 대해서 $u = p \pmod{2^r}$을 알고 있다면, 결국 $2^r x + u$라는 일차식이 $\pmod{p}$에서 작은 근을 갖는다는 것을 알 수 있다.

이를 최고차항의 계수가 $1$이도록 바꿔주면 $x + u \cdot (2^{-r} \pmod{N})$이라는 일차식을 얻는다.

우리는 실제로 $p$를 모르지만, $p$의 배수 $N$을 알고 있으므로 Coppersmith's Attack의 모든 부분을 수행할 수 있다.

즉, norm이 $p^m / \sqrt{n}$ 이하인 다항식을 만들기 위해서 $N$을 사용하는 방식을 택할 수 있다.

위 방법을 그대로 사용하면 부등식 계산 부분에서 뭔가 잘 안된다는 것을 알 수 있다.

대신, $x^i f(x)^m$ 형태의 다항식을 몇 개 추가해주면 LLL 알고리즘이 잘 돌아갈 조건을 제공함을 알 수 있다. 이 구현 참고. 

직관적으로 생각해보면, $N$을 사용한 다항식은 계수가 지나치게 큰 것이므로 ($p$를 모르니 그 배수를 쓴 것이니) $x^i f(x)^m$ 형태의 다항식을 추가해서 이를 희석시킨 것이라고 생각해도 될 것 같다. 아무튼 하면 된다 :) 이제 본격적으로 논문을 읽어보자.

4. RSA Key Generation, and RSALib

RSA 키는 어떻게 만들까? 예를 들어 1024 비트 키를 만들고 싶다고 하자. 

그러면 512 비트 소수 $p, q$를 찾아서, $N=pq$를 잡고, $e = 2^{16}+1$이라 한 다음, $d$를 $ed \equiv 1 \pmod{\phi(N)}$이 성립하도록 잡으면 된다. 

안전성을 위해서는 $p, q$가 갖춰야 할 여러 조건들이 있고, 이에 대해서는 앞선 리딩에서 다뤘다.

하지만 결론적으로 웬만하면 랜덤한 $p, q$를 잡으면 된다는 사실 역시 알고 있다.

소수 정리에 의해서 $x$ 근처의 자연수가 소수일 확률은 매우 대충보면 $1/\log x$ 정도다.

그러니까 랜덤한 자연수를 잡고, Miller-Rabin 등 소수 판별 알고리즘을 돌리는 것을 소수가 나오기 전까지 반복하면 소수를 얻을 수 있다.

그런데 RSA 키를 가능한 빠르게 생성하고 싶다고 가정하자. 어떻게 위 과정을 최적화할 수 있을까?

기본적으로 소수를 찾는 과정이 가장 느리므로, 이 과정을 더 빠르게하면 좋을 것 같다.

당장 랜덤한 자연수를 찍으면 2부터 100까지의 소수 중 하나의 배수가 될 확률이 상당히 높을텐데, 이거라도 미리 거르면 좋을 것 같다.

그래서 RSALib는 다음과 같은 방법을 채택했다. $n$이란 자연수를 먼저 설정하는데, 이는 RSA 키의 길이에 따라서 결정된다.

그 후, $M$을 첫 $n$개의 소수의 곱으로 설정한다. 이제 랜덤한 $k, a$를 잡아서 $k \cdot M + (65537^a \pmod{M})$을 소수 후보로 잡는다.

이렇게 하면 첫 $n$개의 소수는 약수로 갖지 않게 된다는 것이 자명해지고, 소수 판별을 반복하는 횟수가 줄어든다.

그런데 생각해보면, $M$은 여러 소수의 곱이니 원시근이 없고, $65537^a \pmod{M}$은 $M$과 서로소인 모든 나머지를 표현하지 못한다.

다르게 말하면 이는 이 새로운 방식이 생성할 수 없는 소수들이 있고, 실제로 이 방식은 랜덤하지 않다는 것이다.

또한, $p, q$가 이 방식으로 생성되었다면, $N \pmod{M}$ 역시 $65537$의 거듭제곱으로 표현할 수 있다.

$M$은 큰 값이지만 smooth 하므로, Pohlig-Hellman Algorithm으로 $N \equiv 65537^c \pmod{M}$인 $c$를 찾을 수 있다.

이는 생성된 키 $N$이 제대로 계산되었는지 (RSALib로 생성되었는지) 확인하는 방법이 될 수도 있다.

다시 강조하지만, $M$과 서로소인 나머지 중 $65537^a \pmod{M}$으로 표현될 수 있는 값의 비율은 매우 낮다.

이제 이 RSA 키의 특수한 형태를 극도로 활용하여, $N$을 아예 소인수분해하는 방법을 찾아보자.

5. The ROCA Vulnerability

생각보다 아이디어는 그렇게 어렵지 않다. $p = k \cdot M + (65537^a \pmod{M})$이라 하자.

만약 우리가 $a$를 안다면, $p$의 하위 비트를 아는 것이 되며 이는 Coppersmith's Attack을 사용할 환경을 제공한다.

$T$를 $\pmod{M}$에 대한 $65537$의 order라고 하자. $c$를 $N \equiv 65537^c \pmod{M}$인 값이라고 하자.

$T, c$는 모두 어렵지 않은 정수론 알고리즘을 (order-finding algorithm, Pohlig-Hellman) 사용하여 계산할 수 있다.

이제 $a$를 $c/2$부터 $c/2 + T/2$까지를 brute-force하면서 계산하면, $p$가 걸리던 $q$가 걸리던 뭔가 걸린다.

즉, Coppersmith 공격을 약 $T/2$번 반복하면, $N$을 소인수분해 할 수 있다. 여기서 $T$가 작으면 좋겠다는 생각을 할 수 있다.

이를 위해서 일종의 최적화를 한다. $M'|M$인 $M'$을 잡되, 다음 조건을 모두 만족하도록 하자.

조건 1: $\pmod{M'}$에 대한 $65537$의 order가 작은 편이다.

조건 2: $M'$이 충분히 커서, $p \pmod{M'}$을 고정하면 Coppersmith's Attack을 수행할 수 있다. 즉 $M' > N^{1/4}$.

$M'$을 최적화하는 과정은 휴리스틱, 그리디, 전탐색 등을 든든하게 섞어서 해시코드 식 접근을 했다고 한다.

이제 이 과정을 모두 합치면 $N$을 소인수분해 할 수 있다. 대표적인 구현은 이 코드를 참고하자.

최근에는 학교 시험을 많이 쳐서 블로그에 글을 올리지 못했다. 여름방학 목표 글에서도 썼지만 이번 학기는 배운 게 정말 많은 학기였다. 

어떤 과목을 들었고, 어떤 것을 배웠는지, 어떤 것을 느꼈는지를 전공 위주로 간단하게 정리해보려고 한다.

현대대수학 1

• 수학으로 뭘 하려면 근본이 중요한 것 같고, 그런 면에서 더욱 중요했던 과목
• 아는 내용이 많아서, 특히 군론은 선형대수학 2와 겹치는 부분이 많아서 새로 배운 것은 적었음
• Burnside's Lemma를 쓰는 문제가 나왔는데, 어이없는 실수를 해서 틀렸다. 솔직히 매우 부끄럽다 ㅋㅋ
• 현대대수학 2에서는 진짜 많은 것을 배울 수 있을 것 같아서 기대를 하고 있다

수치선형대수

• 처음에는 '수치'란 이름이 붙어서 오차분석에 더 비중을 둔 과목일 줄 알았다
• 실제로는 선형대수학 알고리즘을 다루는 과목이었다. 어쨌든 재미는 있었음
• 배우는 건 정말 많은데, 나름 최근에 나온 이론도 많아서 그런지 100% 이해를 한 이론은 적다
• 아쉬운 면도 있지만 학부 3학년 과목에서 모든 내용을 다루기엔 무리가 있으니 이해가 된다
• Gaussian Elimination, LU Decomposition, Cholesky Decomposition, QR Decomposition, Singular Value Decomposition
• Least-Square Approximation과 그 계산 방법
• Givens Rotation과 Householder Reflection을 활용한 QR Decomposition의 계산
• 행렬의 Eigenvalue를 계산하는 알고리즘들 (QR Iteration, Single/Double Shift Francis Algorithm 등)
• Symmetric 행렬의 Eigenvalue를 계산하는 알고리즘들
• Iterative Methods for solving $Ax = b$ (Jacobi, Gauss-Seidel, SOR, Steepest Descent, Conjugate Gradient)
• Arnoldi Decomposition과 이를 활용한 다양한 알고리즘
• 이 글을 작성하는데 많은 도움을 준 과목이다
• 과제가 많았는데 그래도 나름 유익했고, 시험은 거의 선형대수학으로 나와서 아쉬웠다

암호론

• 정수론을 매우 좋아하는 만큼 정수론을 써먹는 방법을 알고 싶어서 들어왔다
• 근데 정작 요즘 메타는 정수론에서 벗어난 것 같다. 하지만 여전히 엄청 재밌는 수학이 많이 쓰이는 것 같다
• 학문 자체가 진짜 재밌어서 (여름방학 계획에서 말했듯이) 더욱 깊은 공부를 하려고 한다
• 그래서 암호학 분야 CTF도 시작했고, 논문도 몇 개 읽으려고 한다. 이에 대해서는 아래에서 더 말한다
• 수업에서는 암호론 분야 전반을 다뤘다. 블록암호, RSA, 전자서명, 비밀공유, 양자내성, 동형암호 및 최신동향을 다 다룬다
• 내용을 배우고 찾아보면서 진짜 신기한 것들을 많이 배웠는데, 이런 것들은 한 번 블로그에 정리를 할 것 같다
• 3학년 1학기가 되면 가능하면 암호론 랩에 가고 싶다는 게 지금 생각. 웬만하면 안 바뀔 것 같다

해석개론 및 연습 1

• 수학 근본을 챙기기 위한 과목이다
• 교수님이 수업을 굉장히 열정적으로 하셔서 재밌게 들을 수 있었다
• 해석개론 및 연습 2를 가면 더욱 깊이있는 내용을 배울 수 있을 것 같아서 기대가 된다

양자 컴퓨팅 및 정보의 기초

• 생각보다 암호론과의 시너지가 잘 맞는 과목이었다. 함께 들을 수 있어서 좋았다
• 암호론에서 '양자컴이 나오면 RSA가 깨진다, 블록암호 길이도 2배 늘려야 한다'라는 내용을 배웠다
• 그 이유를 이 수업에서 전부 배울 수 있었다 (Shor Algorithm, Grover Algorithm)
• 물리 근본이 없어서 걱정을 많이 했는데, 좋은 친구들이 도와줘서 어떻게 어떻게 잘 된 것 같다

종강 이후로는 바킹독님의 추천을 받아서 CryptoHack이라는 사이트를 많이 풀었고, 비슷한 사이트인 id0-rsa.pub도 풀고 있다.

문제를 풀다가 내 블록암호에 대한 지식이 어마어마하게 얕다는 것을 많이 느껴서, 이쪽으로 공부를 잠깐 할 생각이다.

읽을 논문도 결정했는데, 우선 ROCA Vulnerability와 Bleichenbacher 공격에 대해서 제대로 읽어보려고 한다.

저번에 Lattice에 대한 지식이 전무해서 읽지 못했던 RSA에 대한 Survey Paper의 일부분도 읽고 정리할 것 같다.

암호론 시험공부를 하면서 동형암호 HEAAN에 대한 논문/자료도 열심히 읽었는데, 이것도 제대로 읽으려고 한다.

가능할지는 모르겠는데, 예전 노트북에 Linux를 깔아서 HEAAN은 직접 프로그래밍을 하면서 익숙해지려고 한다. 

그리고 최근에 올렸던 특성다항식의 빠른 계산을 백준 문제로 만들어서 올릴 계획을 세우고 있다.

마지막으로 2학기에 듣고 싶은 과목을 소개한다. 이대로 들을 수 있으면 진짜 좋겠다 ㅋㅋ

해석개론 및 연습 2, 현대대수학 2 : 수학 근본 챙기는 과목, 못 들을 이유가 없다

수치해석개론, 최적화의 수학적 이론 및 계산, 대수적 코딩이론 (택 2) : 수학 응용 챙기는 과목

컴퓨터 프로그래밍, 자료구조, 알고리즘 (택 2) : 컴공 전공 챙기는 과목, 복수전공하니까 이제 들을 수 있을거라 믿는다

계산수론 (청강) : 이미 좋아하는 분야인만큼, 꼭 들어보고 싶다. 랩을 가는 것에도 도움이 되지 않을까?

저렇게 들으면 21학점이 나온다. 근데 1학기 학점은 잘 나올까? ㅋㅋ

UPD: 1학기 학점은 잘 나왔고, 암호학 리딩은 많이 못했다. 방학 때 너무 놀았음 ㅋㅅㅋ

정말 많은 것을 배운 한학기였다.

해석개론 및 연습 2 내용 미리 가볍게만 예습

정보처리기능사 실기 따기

양자컴퓨팅 강의 못 본 것들 다시보기

암호론 CTF 입문 : CryptoHack, id0-rsa.pub 가능한만큼 풀기

Matroid 관련 내용 공부하기 (알고리즘 구현까지)

이인석 교수님의 "대수학" 초반부분 공부하기 (대수적코딩이론 듣는 경우 -> 안 들을 가능성 높음)

Problem Solving (적당히 하고, SCPC 준비 위주로)

Project Euler 푸는 것 계속하기 (근데 정작 PE가 여름방학이라서, 이거는 많이 못할듯)

계절학기 과하게 하지말고 적당히 듣기

Hackenbush에 대한 간단한 튜토리얼을 쓰려고 하는데, 내가 이걸 잘 아는 거는 아니라서 (...) 증명 및 깊이 있는 이론들은 (ordinal 등장 등) 대부분 생략하고 알고리즘 문제 풀이에 써먹을 수 있는 부분들만 간략히 추려서 쓰려고 한다. 자세한 증명은 구글에 검색하면 자료가 매우 많으니 찾아보는 것을 추천한다 :)

Hackenbush 게임은 두 명이서 하는 게임으로, 여러 가지 버전들이 존재하지만 근본적인 목표는 똑같다.

위 그림과 같이, 일종의 그래프가 지면에 연결되어 있는 상태에서 게임이 시작된다. 

각 플레이어는 순서대로 간선 하나를 제거하는데, 이때 더 이상 지면에 연결되지 않게 되는 간선들은 모두 삭제된다.

일반적인 룰에서는 (normal play convention) 간선을 제거하지 못하게 되는 플레이어가 패배한다.

간선이 무한히 많은 경우도 존재하지만, 여기에서는 유한한 개수의 간선이 존재한다고 가정한다.

그러면 게임이 확실하게 Sprague-Grundy 방식으로 분석이 가능해진다. 이를 위해서 다음 Principle을 활용한다.

Colon Principle: 그래프 $G, H, K$가 있다. $H, K$의 Grundy 값이 같다면, $G$의 정점 $x$에 $H$를 붙인 그래프와 $x$에 $K$를 붙인 그래프의 Grundy 값이 동일하다. 그러므로, 한 점에서 '가지치기'가 되는 그래프가 있다면, 각 가지들의 Grundy 값의 XOR에 해당하는 길이의 일직선을 붙이는 것으로 가지들을 대체할 수 있다. 이를 통해서 트리 그래프에 대한 분석을 끝낼 수 있다. DFS를 돌면서 서브트리의 Grundy 값을 순서대로 계산하면 된다.

Fusion Principle: 두 정점이 한 사이클 위에 놓인다면 (지면을 하나의 노드로 본다) 두 점을 하나로 합쳐도 Grundy 값이 변하지 않는다. 

이때 두 점을 잇는 간선들은 self-loop가 된다. 이 성질을 이용하면, 임의의 그래프에 대한 Grundy 값을 구할 수 있다.

실제로 이를 활용하는 문제는 본 적이 없지만, 아무튼 이를 이용하면 기본 Hackenbush에 대한 분석은 끝이다.

연습문제: Project Euler 400 Fibonacci Tree Game, BOJ 13893 Dictionary Game

두 문제 다 Hackenbush에 대한 이해와 적당한 구현을 (DP/Trie 등) 통해서 해결할 수 있다. Fusion Principle은 필요 없다.

Blue-Red Hackenbush는 조금 색다르다. 이제는 각 간선마다 누가 자를 수 있는지가 둘 중 한 명으로 정해져 있다.

각 플레이어를 Blue/Red라고 하고, Blue 간선은 Blue만, Red 간선은 Red만 자를 수 있도록 한다.

이때는 각 연결 컴포넌트 $G$에 대하여, 그 컴포넌트의 값 $v(G)$를 다음과 같이 재귀적으로 정할 수 있다.

아무것도 없는 그래프의 경우 값은 자명하게 $0$이다. $G$가 nonempty라고 가정하자.

$b$를 Blue가 만들 수 있는 상태 $G'$ 중 $v(G')$의 최댓값이라 하자. 불가능한 경우 $-\infty$.

$r$을 Red가 만들 수 있는 상태 $G'$ 중 $v(G')$의 최솟값이라 하자. 불가능한 경우 $\infty$.

만약 $b < n < r$인 정수 $n$이 존재한다면, $v(G)$는 해당하는 정수 $n$ 중 $0$에 가장 가까운 것이다. 

그렇지 않다면, $v(G)$는 $b < x < r$을 만족하는 유리수 $x$ 중 분모가 $2$의 거듭제곱인 것 중에서 분모가 최소인 것이다. 

또한, 독립적인 그래프 $G, H$에 대하여 $v(G+H) = v(G) + v(H)$가 성립한다.

만약 $v(G) > 0$이라면 Blue가 승리, $v(G) < 0$이라면 Red가 승리, $v(G)= 0$이라면 후공 승리가 된다.

이 게임에 대한 직관적인 이해를 원한다면 stonejjun의 블로그를 찾아보는 것을 추천한다.

이걸 모두 짬뽕한 Blue-Red-Green Hackenbush도 있는데, 이건 진짜 무서워 보인다 ㅋㅋ

연습문제: BOJ 13409 Black and White Boxes, BOJ 18945 조직된 ㄱ폭탄 게임

13409는 Hackenbush 값을 계산한 다음 Meet In The Middle을 하면 간단하게 해결할 수 있다.

18945는 몇 가지 관찰을 한 다음, 문제를 Blue-Red Hackenbush로 변형하여 해결할 수 있다.

이 글의 진짜 목적 중 하나가 18945의 풀이를 적는 것이니, 여기에 소개한다.

각 게임을 독립적인 Blue-Red Hackenbush 게임으로 보고, 그에 대응하는 값을 계산하자. 

그러면 남은 쿼리들은 전부 단순한 point update range query 문제가 되므로, 펜윅/세그먼트 트리를 이용하여 계산할 수 있다. 

그러니 문제 난이도의 99%는 각 게임을 Blue-Red Hackenbush 게임으로 변환하는 것에서 나온다. 

일반성을 잃지 않고 A 폭탄이 하나 존재한다고 가정하자. 그러면 B 폭탄을 3가지 종류로 나눌 수 있다.

종류 1: A 폭탄이 터지면 강제로 제거되는 B 폭탄들

종류 2: 터뜨리면 A 폭탄이 터지게 되는 B 폭탄들

종류 3: A 폭탄과 서로 interact 할 수 없는 (즉, 하나가 터져도 다른 하나가 터지지 않음) B 폭탄들

이 게임판에서 A가 할 수 있는 행동은 단순히 A 폭탄 하나를 터뜨리는 것 뿐이다. 

B가 할 수 있는 행동은 다양한데, 실제로 고려해야 하는 것은 몇 가지 없음을 알 수 있다.

우선 종류 3의 폭탄과 같은 경우에는 애초에 A 폭탄이 터지던 말던 상관이 없기 때문에, 최대한 마지막에 터뜨리는 것이 좋다. 

물론, 자신이 터뜨린 폭탄에 의해 자신의 다른 B 폭탄이 쓸데없이 터지지 않도록 순서를 잘 정해서 터뜨려야 한다.

종류 2의 폭탄은 터뜨린다면 강제적으로 종류 1의 폭탄 중 남아있는 것은 무조건 터지게되며, 경우에 따라서 종류 3의 폭탄 역시 터질 수 있다. 

그러니 A 폭탄을 제거할 목적으로 종류 2의 폭탄을 터뜨린다면 종류 3의 폭탄을 최소한으로 터뜨리도록 하는 폭탄을 하나 찾아서 그걸 터뜨려야 한다.  

종류 1의 폭탄은 터뜨린다면, 다른 종류 1의 폭탄을 터뜨리지 않도록 행/열 순서를 잘 잡아서 순서대로 터뜨려야 한다.

이를 종합하면, 다음과 같은 Blue-Red Hackenbush 그림을 그릴 수 있다. A가 Red, B가 Blue라고 하자.

그래프가 특수한 형태를 가진다. 그러니, 이와 같은 경우에서 Hackenbush 값은 아예 closed form 식을 통해서도 구할 수 있다.

나는 DP를 이용하여 위에서 설명한 규칙을 직접 적용하는 방식으로 구현했다. 분수를 다루기 귀찮으니, 적당히 큰 2의 거듭제곱을 곱해줘서 다루면 편하다. 

바쁘기보다는 게을러서 PS를 안했다. 또 수학 PS 연습을 팠는데, 슬슬 머리가 터질 것 같고 진짜 PS가 하고 싶어졌다.

2주간 진행한 연습에서 6/12문제를 해결하였다. 그 중 단순한 사전지식 문제도 꽤 포함되어 있다.

아래에 소개한 내용 외에도 5월에는 Project Euler 715를 풀었는데, 5등을 기록했고 만족하고 있다. 

Thread에도 꽤 유의미한 내용을 두 개 제공해서 kudos도 많이 받고 기쁘다. 이 기회에 Eulerian 랭킹 상위권을 시도하려고 한다.

GCJ Round 2도 쳤고 작년보다는 등수가 많이 떨어졌고 뇌절도 많이했지만 아무튼 티셔츠는 받아서 다행이다.

감이 엄청 떨어진 것 같으니 시간나면 플레티넘 문제부터 다시 차근차근 푸는 연습을 해야겠다.

또한, 지금 진행되고 있는 대회인 Semi-Game Cup의 검수를 맡아서 몇 문제 풀었다. :)

BOJ 18465 Horrible Cycles (K, Ruby V)

BOJ 18630 Lati@s (J, Ruby IV)

BOJ 18461 Disjoint LIS (I, Ruby IV)

BOJ 10057 Pachinko (L, Ruby V)

BOJ 18622 Dedenne (H, Ruby IV)

BOJ 17160 Traffic Blights (G, Ruby IV)

연습을 계속하고 있다. 21/26 문제를 해결하는 것으로 일단 종료. 4월에 시작한 연습이니까 4월 카테고리에 넣는다.

남은 문제들은 다 너무 어려워서 못 풀겠다. 일단 수학 PS는 질리도록 했으니 다른 것부터 하는 게 좋을 듯.

4월 30일

BOJ 5627 박테리아 (T, Diamond III)

BOJ 12735 Boat (R, Diamond III)

BOJ 18480 Four Elements (H, Ruby V)

5월 1일

BOJ 18297 Pixels (O, Diamond III) 

5월 2일

BOJ 14639 Replicate Replicate Rfplicbte (N, Diamond II)

BOJ 18527 All Kill (I, Ruby IV)

BOJ 18574 Fractional XOR Maximization (E, Ruby V)

5월 4일

BOJ 18791 N의 배수 (2) (Y, Diamond III)

BOJ 18792 N의 배수 (3) (Z, Diamond I)