Archive

사실 ctf를 참가하려 하면 막상 귀찮아 열심히 풀지 않는 경향이 있는데, 동아리 내부 퀄은 나름의 의무감을 핑계로 시간투자를 할 수 있어 공부하기에 괜찮은 시기인것 같다.

Crypto

baby_crypto

$q$가 $p$의 next prime이니, $N$을 fermat factorization하면 될 것 같다. 문제는 $N$이 주어져있지 않다. 따라서 $N$을 구해야 하는데, $c\equiv m^e\text{ }(mod\text{ }N)$이라는 점을 활용할 수 있다. 주어진 평문 2개와 그 암호문에 대해서, $m^e-c$는 $N$으로 나눈 나머지가 $0$이므로 $N$의 배수이다. 따라서 $\gcd(m_1^e-c_1,m_2^e-c_2)$는 $N$의 배수이며, 일반적으로 $N$을 얻는다. $N$을 구한 후에는 간단한 fermat factorization을 시행하면 $p,q$를 얻을 수 있고, $d$를 계산하여 플래그를 복구할 수 있다.

Monopoly

auth에서는 mod $(2^130-5)$에서, 입력을 16바이트단위로 끊어 $r$에 대한 다항식의 계수로 차용하고, 마지막엔 상수항으로 $s$를 더하여 그 suffix 128bit를 추출하여(mod $2^128$) 반환한다. 데이터에 패딩이 들어가긴 하나, 그 앞의 내용을 자유롭게 변형 가능하다는 점에서 문제를 쉽게 만든다. 마지막을 제외한 모든 블럭을 널바이트로 채우면 $r$에 대한 2차 이상의 항은 모두 소거되므로, $kr+s\mod (2^130-5)$의 suffix 128bit를 알 수 있다. 이때 잘린 비트는 고작해야 2개비트이므로, 많아야 4가지 경우의 수가 존재한다. 따라서 $k_1r+s=x_1\text{ }(mod\text{ }2^130-5)$과 $k_2r+s=x_2\text{ }(mod\text{ }2^130-5)$를 연립하여 $r,s$의 후보 최대 16개를 알 수 있으며 이를 모두 get flag에 시도하여 flag를 얻을 수 있다.

Penguin

뭔가 펭귄이 보여야할 것 같은 문제이다. 제목부터 ECB 취약점을 써야할 것 같은데, 우선 염두하고 첨부파일을 확인하면 타원곡선을 가장한 무언가가 보인다. chunkwise encryption이며, 각 청크는 청크의 값 $x$에 대해 $\left(g^x+f(i+a+b+gx+gy)+gy\right)\mod N$을 계산한다. 이때 $f$는 계수가 알려진 3차 다항함수이므로 아무 암호학적 기능을 하지 못한다. 따라서, 주어진 암호화에서 $x$는 구할 수 없으나, $g^x$까지는 구할 수 있다는 사실을 확인했다. 이때 $x$가 같으면 $g^x$도 같으므로, "펭귄이 보였던 것처럼" $g^x$로 작성된 bmp파일을 확인하면 flag를 읽을 수 있다.

Triple RSA

$d\mod (p-1)(q-1)$은 $\mod pq$에서의 $e$의 modular inverse이므로, $\mod pq$에서 $2^(e\times hint)$를 계산하면 $2^{p+\text{ironore15}}$이다. $\text{ironore15}$는 알려진 상수값이므로, 우리는 $2^p$의 값을 계산할 수 있다. $2^p$는 $\mod p$에서 2와 같으므로, $2^p-2$는 $p$의 배수이다. 따라서 $pqr$과 $2^p-2$의 gcd를 계산하면 $p$를 계산할 수 있다. 이번엔 $\mod N$에서 $2^(e\times hint)$를 계산하면 이 값은 $kpq+2^{p+\text{ironore15}}$과 같으므로, $2^(e\times hint)-2^{p+\text{ironore15}}$와 $N$의 gcd로 $pq$의 값을 구할 수 있다. 즉, $q,r$의 값을 계산하여 flag를 복구할 수 있다.

Circle Crypto

hyperbolic curve over finite field의 대표적 예시 중 하나인 circle curve를 제시하였다. 해당 집합에서의 additive DLP는 정수 유한체에서의 multiplicative DLP로 치환 가능하며, $p-1$이 smooth하기 때문에 쉽게 해결 가능하다.

수많은 양자컴퓨터에 관한 연구가 보고되고 있는 요즈음, 뉴스에서도 종종 양자컴퓨터에 대한 이야기를 들을 수 있다. 그러한 기사에서는 종종 "쇼어 알고리즘"을 언급하며 기존 보안체계 붕괴 등을 전망한다. 본 글에서는 양자컴퓨팅이란 무엇인지부터 시작하여 양자컴퓨팅에 대한 기반 지식이 없는 독자가 쇼어 알고리즘을 이해하는 것을 목표로 한다.

Part I. What is "Qubit"?

"비트(bit)"라는 말을 들어보았는가? 고전적인 컴퓨터(현재 사용되는 컴퓨터)에서 다루는 가장 기본적인 단위의 데이터이며, 0 또는 1의 값을 갖는 한 자리의 이진수이다. 고전 컴퓨터는 여러 비트를 조합하여 여러 자리의 이진수를 표현하고, 이를 이용하여 수많은 데이터를 표현한다. 예를 들자면, 이진수로 1011101로 표현되는 수 93은 7개 이상의 비트를 조합하여 표현할 수 있다. 고전적인 컴퓨터는 전류가 흐르거나 흐르지 않음으로 비트의 값을 표현한다. 일반적인 디지털 컴퓨터는 전류의 구체적 세기와는 무관하게 역치값 이상의 전류가 흐르느냐의 여부로 0과 1이 정확히 나뉘는 이산적인 체계를 갖고 있다. 이것이 "디지털" 컴퓨터라고 불리는 이유이기도 하다.
 
양자컴퓨터는 "큐비트(Qubit)"라는 단위로 정보를 저장한다. 고전적인 컴퓨터에서 비트에 대응되는 개념인데, 그 저장 방식이 처음 보면 다소 신기하다. 양자컴퓨터의 핵심은 "중첩"이라는 물리적 현상으로, 간단하게 이야기하자면 매우 작은 입자를 관측하지 않는다면 그 입자는 여러 상태가 동시에 존재하다가 관측할 경우 그 중 하나로 랜덤하게 상태가 확정되는 현상이다. 랜덤박스를 생각한다면 이해가 좀 더 쉬울 것이다. 열기 전까진(관측하기 전까진) 내용물을 알 수 없지만(여러 상태가 동시에 존재하지만) 상자를 열면(관측하면) 내용물이 무엇인지를 확실히 알 수 있다.(상태가 확정된다.) 다만 이러한 비유는 실제 물리적인 현상과는 차이가 있어 오개념이 생길 수 있으므로, 이해가 잘 되지 않는다면 단순히 관측하면 여러 값 중 하나가 랜덤으로 선택되어 보여진다고 생각하면 된다.

이제부터 약간의 수식들과 함께 설명하고자 한다. 수식 없이 쇼어 알고리즘을 설명하기란 불가능에 가깝기 때문에, 양해를 바란다.
하나의 큐비트는, 관측할 때 "0"과 "1"이라는 두 가지 상태 중 하나로 확정되는 중첩 상태에 놓여있다. 즉, 큐비트는 관측 시 각각의 상태가 될 확률을 표기하는 것으로 표현하는 것이 합리적일 것이다.

위 이미지에서 $a$와 $b$는 무엇을 의미하는 것일까? 자세한 물리적 내용은 생략하나 각각의 상태는 파동으로써 표현되어, 확률은 파동의 변위의 제곱으로 표현되므로 $a^2+b^2$이 확률의 총 합으로 1이 되어야 함을 알 수 있다. $a$와 $b$는 두 상태에 해당하는 파동의 scale factor라고 생각할 수 있다. (물리적인 디테일은 크게 중요하진 않으므로 이해가 가지 않는다면 생략해도 좋다.)
 
우리는 큐비트들을 벡터를 이용하여 표현한다. Bra-Ket Notation이라 하는 표기법을 이용하는데, 행벡터를 Bra, 열벡터를 Ket이라 부르고 다음과 같이 표기한다.
$$\vert x\rangle=\begin{bmatrix}a_1 \\a_2 \\\vdots\end{bmatrix}$$
$$\langle x\vert=\begin{bmatrix}a_1 a_2 \cdots\end{bmatrix}$$
양자컴퓨팅과 관련한 수식 전개에서 흔히 사용되는 곱셈은 주로 내적(inner product)이므로, 우리는 $\vert a\rangle$와 $\vert b\rangle$의 내적을 $\langle a\vert b\rangle$과 같이 적는다.
또한, 본 글에서 사용되는 모든 벡터는 복소수체 $\mathbb{C}$에서 정의되므로, transpose 대신 hermition을 취한다는 것을 염두하고 글을 읽도록 하자.
$$\langle x\vert = \vert x \rangle^H$$
 
임의의 큐비트의 상태는 $\vert x\rangle = A\vert 0\rangle+B\vert 1\rangle$과 같이 표현된다. 이때 아래의 사실을 기억하고 넘어가자.
$$\vert 0\rangle=\begin{bmatrix}1\\0\end{bmatrix},\vert 1\rangle=\begin{bmatrix}0\\1\end{bmatrix}$$
$$|A|^2+|B|^2=1$$
여기서 $A,B$는 복소수이므로 단순히 제곱하는 것이 아닌, norm의 제곱을 구하여야 한다.
복소수의 극형식을 이용하면 $\vert x\rangle=ae^{i\theta}\vert 0\rangle+be^{i\phi}\vert 1\rangle$와 같이 표현할 수 있고, 두 상태0과 1이 물리적으로는 파동으로 표현된다는 것을 생각하면 중요한 것은 진폭과 위상 차이뿐이며, 실제 위상의 값은 중요하지 않으므로 $e^{i\theta}$로 나누어 소거하면 $\vert x\rangle=a\vert 0\rangle+be^{i\phi}\vert 1\rangle$로 표현할 수 있다.
 
$a^2+b^2=1$이므로 $a=\cos{\frac{\theta}{2}},b=e^{i\phi}\sin{\frac{\theta}{2}}$로 표현해보자. 구면좌표계 $(\sin\theta \cos\phi,\sin\theta \sin\phi,\cos\theta)$를 이용하면 우리는 임의의 큐비트 상태를 어떤 구면 위에 표현할 수 있음을 알 수 있다. 이를 블로흐 구면(Bloch Sphere)라고 부른다. x,y,z축의 단위벡터는 각각의 $\theta,\phi$를 계산해보면 $\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}},\frac{\vert 0\rangle+i\vert 1\rangle}{\sqrt{2}},\vert 0\rangle$라는 사실을 발견할 수 있다. 흔히 $\frac{\vert 0\rangle+\vert 1\rangle}{\sqrt{2}}$를 $\vert+\rangle$로, $\frac{\vert 0\rangle-\vert 1\rangle}{\sqrt{2}}$를 $\vert-\rangle$로 쓴다.

여러 수식을 이용하여 거창하게 설명했으나, 기억해야 할 점은 아직 단 하나의 큐비트에 대해서 설명했을 뿐이라는 사실이다. 당연하게도 실제로 유의미한 알고리즘을 작성하려면 여러 개의 큐비트를 동시에 사용해야 한다. 큐비트 $\vert x\rangle_0,\vert x\rangle_1,\vert x\rangle_2,\cdots$를 동시에 사용하면, 그 전체를 다루기 위한 벡터를 다음과 같이 표기할 수 있다.
$$\vert \psi\rangle=\vert x\rangle_0\otimes\vert x\rangle_1\otimes\vert x\rangle_2\otimes\cdots$$
여기서 $\otimes$는 tensor product로, $m\times n$ 행렬 $A$와 $p\times q$ 행렬 $B$의 tensor product는 다음과 같은 $mp\times nq$ 행렬로 정의된다. 또한 정의에서 알 수 있듯, tensor product는 결합 법칙이 성립한다.
$$A\otimes B = \begin{bmatrix}A_{11}B & A_{12}B & \cdots & A_{1n}B \\A_{21}B & A_{22}B & \cdots & A_{2n}B \\\vdots & \vdots & \ddots & \vdots \\A_{m1}B & A_{m2}B & \cdots &A_{mn}B\end{bmatrix}$$
우리는 여러 큐비트를 다룰 때 $2\times 1$ 행렬 $n$개의 tensor product를 이용하므로 이는 $2^n\times 1$ 행렬로써 표현된다. 이는 각각의 큐비트가 0 또는 1로 관측되는 $2^n$개의 모든 경우의 수를 표현하며, 해당 entry에 존재하는 값은 그 상태로 관측될 확률에 비례한다고 볼 수 있다. 따라서 우리는 $n$개의 큐비트를 사용할 때 $2^n$개의 기저가 필요하며, 이를 0부터 $2^n-1$까지의 수에 대응하여 다음과 같은 벡터로 표기한다.
$$\vert 0\rangle,\vert 1\rangle,\vert 2\rangle,\cdots,\vert 2^n-1\rangle$$
 

Part II. Control Qubits

고전적인 컴퓨터에서는 비트를 조작하는 방법으로 논리 게이트를 이용한다. 하나, 혹은 그 이상의 비트의 값을 받아 또 다른 값(혹은 값들)을 생성하는 것이 AND, OR, NOT, XOR과 같은 게이트들의 기능임을 알고 있을 것이다. 마찬가지로 양자컴퓨터에서는 큐비트를 조작하는 방법으로써 양자 논리 게이트를 이용한다.
 
논리 게이트는 여러 값을 받아서 하나의 값을 출력하거나 하나의 값을 받아 여러 값을 출력할 수도 있었으나, 이는 양자 논리 게이트에서는 불가능하다. 양자 논리 게이트에서는 정보의 소실이 발생할 수 없기 때문이다. 이러한 조건을 만족하는 연산을 unitary operation이라 하며 며 이에 해당하는 행렬 $U$는 unitary matrix이다.
$$UU^H=I, U^{-1}=U^H$$
 
다음은 몇가지 게이트의 예시이다.
$$\text{Pauli-X}=\begin{bmatrix}0&1\\1&0\end{bmatrix}$$
$$\text{Hadamard}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$$
$$\text{Controlled Not(CX)}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{bmatrix}$$
Pauli-X 게이트는 블로흐 구면에서 X축을 기준으로 180도 회전하는 연산이며, Hadamard 게이트는 Y축을 기준으로 반시계 방향 90도 회전하는 연산이다. $H(\vert 0\rangle) = \vert+\rangle, H(\vert 1\rangle)=\vert-\rangle$이며 $H(\vert +\rangle) = \vert 1\rangle, H(\vert -\rangle)=\vert0\rangle$이므로 초기 상태를 중첩상태로 만드는 등의 상황에서 자주 사용한다. Controlled Not 게이트는 입력 중 첫 비트를 Controlled bit로 사용하여, 해당 비트가 1일 때만 두 번째 비트에 Pauli-X 게이트를 적용한다.

Part III. Shor's Algortihm explained

드디어 글의 주제인 쇼어 알고리즘을 설명하고자 한다. 쇼어 알고리즘은 어떤 자연수 $N$의 비자명한 인수를 비트 수에 대한 다항시간복잡도에 해결하는 알고리즘이다. 고전적인 컴퓨터에서는 현재 $O(N^{1/4+\epsilon})$ 정도의 알고리즘이 알려져 있다는 사실을 생각하면 큰 수에 대해서는 가히 혁명적인 개선이다. 쇼어 알고리즘은 크게 다음과 같은 4개의 단계로 구분할 수 있다. 단계에 따라 살펴보자.

1. 임의의 정수 $1<a<N$을 선택한다. $\gcd(a,N)\neq 1$이라면 $\gcd(a,N)$은 $N$의 비자명 인수이므로 이를 반환한다. (classic)
2. 정의역이 $\{0,1,2,\cdots,Q-1\}$인 함수 $f(x)=a^x\mod N$의 주기 $r$을 구한다. (quantum)
3. $r$이 홀수이거나, $a^{r/2}\equiv -1\text{ }(\text{mod }N)$이라면 1.로 돌아간다. (classic)
4. $\gcd(a^{r/2}-1,N)$과 $\gcd(a^{r/2}+1,N)$을 반환한다. (classic)

Step 1.

gcd의 정의에 따라 $\gcd(a,N)$은 $N$의 약수이다. $1\le \gcd(a,N)\le a<N$이므로 $\gcd(a,N)\neq 1$이면 $1<\gcd(a,N)<N$, 즉 비자명 인수가 된다.
 

Step 2.

본 과정에서는 $N^2<Q=2^q<2N^2$인 $Q,q$에 대해 $q+n$개의 큐비트를 이용한다. 이중 $q$개의 큐비트는 함수 $f$의 값이 동일한 입력이 충분하도록 $\frac{Q}{r}>N$을 보장하기 위해서이며, $n$개의 큐비트는 함수값을 계산하는 과정에서 이용한다.
Step 2는 다음과 같이 세분화할 수 있다.
 

1. Hadamard 게이트를 이용하여 0부터 Q-1까지의 모든 수가 동등한 비율로 존재하는 중첩 상태를 만든다.
   $$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x\rangle = \left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_0\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_1\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_2\right)\otimes\cdots\otimes\left(\frac{1}{\sqrt{2}}\sum_{x=0}^{Q-1}\vert x\rangle_{q-1}\right)$$
2. 함수 $f$를 양자게이트로 구현한 연산 $U_f$를 적용한다. ($U_f(\vert x\rangle)=\vert a^x\mod N\rangle$)
   이는 지수인 $x$를 이진 전개하면 $a^x=a^{\sum x_i\times 2^i}=\prod a^{x_i\times2^i}$과 같이 식을 변형할 수 있으므로 $t$번째 비트(0-based)가 1인 $\vert x\rangle$을 $\vert a^t x \mod N\rangle$로 바꿔주는 conditional multiplication을 이용하여 구현할 수 있다.
   $$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,0^n\rangle\Rightarrow \frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,f(x)\rangle$$
3. Quantum Fourier Transform을 적용한다.
   $$w=e^{\frac{2\pi i}{Q}}$$
   $$QFT = \begin{bmatrix}1&1&1&\cdots&1\\1&w&w^2&\cdots&w^{Q-1}\\1&w^2&w^4&\cdots&w^{Q-2}\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&w^{Q-1}&w^{Q-2}&\cdots&w\end{bmatrix}$$
   $$\frac{1}{\sqrt{Q}}\sum_{x=0}^{Q-1}\vert x,f(x)\rangle\Rightarrow \frac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1} w^{xy}\vert y,f(x)\rangle$$
   이를 $f(x)$의 값을 기준으로 묶어 다시 쓰면
   $$\frac{1}{Q}\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1} w^{xy}\vert y,f(x)\rangle\Rightarrow \frac{1}{Q}\sum_{y=0}^{Q-1}\sum_{z=0}^{Q-1}\left(\sum_{f(x)=z}w^{xy}\right)\vert y,z\rangle$$
   집합 $\{x\vert f(x)=z\}$는 최솟값 $x_0$과 $x_0+kr$ ($k\in\mathbb{N}$)으로 구성된다. 즉, $\sum_{f(x)=z}w^{xy}$는 등비가 $w^{ry}$인 등비수열이다. $m=\left\lceil\frac{Q-x_0-1}{r}\right\rceil$로 정의하면 다음과 같이 $\vert y,z\rangle$이 관측될 확률을 계산할 수 있다.
   $$\begin{align}\Pr(\vert y,z\rangle) &= \frac{1}{Q}\left\vert\frac{w^{mry}-1}{w^{ry}-1}\right\vert^2 = \frac{1}{Q}\left\vert\frac{\cos\left(\frac{2\pi mry}{Q}\right)-1+i\sin\left(\frac{2\pi mry}{Q}\right)}{\cos\left(\frac{2\pi ry}{Q}\right)-1+i\sin\left(\frac{2\pi ry}{Q}\right)}\right\vert^2\\ &= \frac{1}{Q}\left\vert\frac{2-2\cos\left(\frac{2\pi mry}{Q}\right)}{2-2\cos\left(\frac{2\pi ry}{Q}\right)}\right\vert = \frac{1}{Q}\left\vert\frac{4\sin^2\left(\frac{\pi mry}{Q}\right)}{4\sin^2\left(\frac{\pi ry}{Q}\right)}\right\vert \\&=\frac{1}{Q}\left\vert\frac{\sin\left(\frac{\pi mry}{Q}\right)}{\sin\left(\frac{\pi ry}{Q}\right)}\right\vert^2 \end{align}$$
4. 위 확률은 $\frac{ry}{Q}$가 정수에 가까울 수록 다른 경우에 비해 극단적으로 값이 커지는 경향을 보인다. 따라서 우리는 그러한 $y$를 구할 수 있다. 이때 $\frac{ry}{Q}\approx c\in\mathbb{Z}$라 하자. $\frac{y}{Q}$는 알려진 값이며, $\frac{c}{r}$의 근사치이다. 따라서, $\frac{y}{Q}$를 연분수 전개(continued fraction expansion)하면 $\frac{c}{r}$의 좋은 근사값을 여럿 얻을 수 있으며, 높은 확률로 정확한 $r$의 값을 얻을 수 있다.
   
   

Step 3.

$r$이 홀수라면 Step 4를 진행할 수 없고, $a^{r/2}\equiv -1\text{ }(\text{mod }N)$이면 비자명 인수를 얻을 수 없으므로 알고리즘을 다시 실행한다. 그러할 확률은 크지 않아 알고리즘을 재실행하는 횟수는 일반적으로 0회, 매우 높은 확률로 수 회 내로 성공한다.

Step 4.

$b=a^{r/2}\mod N$은 $\text{mod }N$에서의 1의 비자명한 제곱근이다. 이는 $b^2\equiv 1\text{ }(\text{mod }N)$을 의미하며, $b^2=kN+1$을 만족하는 $k\in\mathbb{Z}$가 존재한다. 따라서 $(b-1)(b+1)=kN$이므로, $\gcd(b-1,N)$과 $\gcd(b+1,N)$은 $N$의 비자명한 인수이다.

Part IV. Essence of Shor's Algorithm

쇼어 알고리즘을 자연수 $N$의 비자명한 인수를 찾는 알고리즘이라고 소개했지만, 가장 중요한 부분은 양자컴퓨터를 이용해 계산한 Step 2이다. $f(x)=a^x\mod N$의 특수한 성질을 쓴 것이 아니라, 그저 주기함수이며 양자 게이트로 구현 가능하다는 사실이 중요했다. 이는 바꿔말하자면, 그러한 함수들은 양자컴퓨터를 이용하여 빠르게 그 주기를 계산할 수 있다는 뜻이다. 이러한 방식은 다양하게 응용될 수 있으며, 군 등의 순환 구조를 핵심으로 하여 위수의 기밀성이 중요한 (양자 내성이 없는) 현대 암호가 취약할 수 있음을 알 수 있다. 실제로 RSA는 물론이거니와, 타원곡선에 대한 공격 또한 연구된 바 있다. 아직은 실질적인 공격이 가능한 만큼의 큐비트를 이용할 수 없지만, 머지 않은 미래에 가능해질 수 있다.

본 글에서는 Church Encoding의 기본적 개념과 이를 특정한 함수로 구현할 때 발생할 수 있는 문제점을 다룬다.

1. Church Numeral이란

Church Numeral은 어떤 함수 $f$에 대해 자연수 $k$를 $f^k$로 표현하는 것이다.

2. Church Numeral의 사칙연산

Church Numeral은 페아노 공리계를 만족하며 자연수에 대한 사칙연산을 정의할 수 있다.

• successor: 함수 $g$가 자연수 $n$을 encode하면 $f\circ g$는 $f\circ f^n=f^{n+1}$이므로 $g$의 successor이다.
• 덧셈: 자연수 $n$과 $m$을 encode하는 함수 $g$, $h$에 대해 $g\circ h$는 $f^n \circ f^m=f^{n+m}$이므로 $n+m$을 encode한다. 즉, $g\circ h$는 $g$와 $h$의 합이다.
• 곱셈: 자연수 $n$과 $m$와 $n$을 encode하는 함수 $g$에 대해 $g^m$은 $(f^n)^m=f^{nm}$이므로 $nm$을 encode한다. 즉 $g^m$은 $g$에 자연수 $m$을 곱한 결과이다.
• predecessor: $f$의 역함수 $f^{-1}$와 2 이상의 자연수 $n$을 encode하는 함수 $g$에 대해 $f^{-1}\circ g=f^{-1}\circ f^n=f^{n-1}$이므로 $f^{-1}\circ g$은 $n-1$을 encode하며 $g$의 predecessor이다.
• 뺄셈: 자연수 $n,m(n>m)$을 encode하는 함수 $g$, $h$에 대해 $g\circ h^{-1}$은 $f^n\circ (f^m)^{-1}=f^{n-m}$이므로 $n-m$을 encode한다. 즉, $g\circ h^{-1}$은 $g$와 $h$의 차이다. 이를 통해 $0$과 음수의 encoding을 자연스럽게 정의할 수 있다.

3. 유한 집합과 Church Numeral

Church Numeral을 특정한 함수를 이용하여 구현할 때, 어떤 함수를 쓰는지와는 무관하게 같은 수는 같은 함수로 encode된다. 다만, 사용하는 함수에 따라 "다른 수는 항상 다른 함수로 encode된다"는 명제는 성립하지 않을 수 있다. 특히, 유한 집합 $S$에 대해 $f:S\Rightarrow S$는 $f^a= f^b$를 만족하는 서로 다른 자연수 $a,b$를 무한히 많이 갖는다. 이를 증명해보자.

Proof: $\exists a,b\in S : a\neq b \land f^a = f^b$ 

$S$의 각 원소를 정점으로 갖고, 간선 집합이 $\{x\rightarrow f(x) | x\in S\}$인 함수 $f:S\Rightarrow S$가 존재하는 그래프를 functional graph라고 한다. functional graph가 사이클을 갖지 않는다고 가정하면, 임의의 $x\in S$에 대해 집합 $\{x, f(x), f^2(x),\cdots,f^{n(S)}(x)\}$는 크기가 $n(S)+1$이며 $S$의 부분 집합이다. 이는 모순이므로 functional graph는 사이클을 적어도 하나 가진다. 또한 모든 정점의 outdegree는 정확히 1이므로 모든 사이클은 단순 사이클이라는 것도 확인할 수 있다.

즉 functional graph는 단순 사이클과 그 사이클의 정점을 루트로 하는 몇 개의 트리로 구성된 component를 하나 이상 가진다. 따라서 모든 사이클의 길이 $L_1, L_2,\cdots$의 최소공배수 $L$, 어떠한 자연수 $N$에 대해 $x\ge N$이면 $f^x=f^{x+L}$인 $N$이 존재하므로 위 명제는 참인 동시에 그러한 $a,b$는 무한히 많이 존재한다.

4. 무한 집합과 Church Numeral

그렇다면, 무한 집합에서 정의되는 함수는 이러한 문제에서 자유로운가? $f(x)=ix$와 이를 일반화한 $f(x)=e^{i\frac{2k\pi}{n}}x$는 무수히 많은 길이 $n$의 단순 사이클이 나타난다.

이외의 예시로는 $f(x)=\sqrt{1-x^2}$이 있다. 위의 예시와는 다르게, 2개의 수가 사이클을 이루고 나머지 2개의 수가 사이클에 붙어 있는 꼴이다.

두번째 예시인 $f(x)=\sqrt{1-x^2}$와 $f(x)=-\frac{1}{x}$ 등의 예시를 통해 길이가 2인 사이클을 구성하는 수들을 정의역으로 할 때 사용한 함수 $f$는 $y=x$에 대해 대칭임을 알 수 있다. 나아가, $f:\mathbb{R}\Rightarrow \mathbb{R}$의 모든 사이클의 길이가 2일 필요충분조건은 $f:S\Rightarrow S$가 $y=x$ 대칭이며 정의역 $T$에서 $f$와 동일한 $g:T\Rightarrow S$가 존재하는 만족하는 두 집합 $S$와 $T=\mathbb{R}\backslash S$가 존재한다는 것임을 확인할 수 있다.

드림핵에서 주최한 2022 Christmas CTF에 도롱뇽과학고등학교 2022 팀으로 참가하여 팀이 해결한 9문제 중 7문제를 해결하였고, 결과적으로 7위로 마무리하였다.

국내 ctf는 크립토 문제가 거의 출제되지 않거나 출제되어도 기초적인 수준인 경우가 많은데, 드림핵인 만큼 재밌게 풀만한 문제가 여럿 출제된듯 하다.

크립토 이외의 문제도 몇가지 해결하여 그 풀이도 기술할 예정이다.

Welcome - Misc

별다른 묘사 없이, flag를 읽는 파일의 존재와 ssh 접속 정보가 기술되어있다. ssh에 접속해보면 cd를 비롯하여 몇가지 제약사항이 있다는 것을 확인할 수 있다. 때문에 flag를 읽는 파일을 일반적으로 호출하기가 어려운데, 이를 find 명령어의 -exec 옵션을 이용하여 우회할 수 있다.

find a gift - Misc

리모트에 접속해보면, 현재 위치한 곳의 address와 갈 수 있는 address가 기술되어있다. 즉, 모종의 그래프 탐색을 요구하는 문제라고 볼 수 있다. 직접 몇 번 탐색을 해보니 완전이진그래프 꼴인 것 같았으나, ctf task로 출제한다면 노드의 수를 많게 해놓고 약간의 변형을 줄 수 있다 생각하여 일반적인 비재귀 DFS 알고리즘을 작성하여 문제를 해결하였다.

the present - Crypto

코드를 확인해보면 PRNG라는 class에서 유사난수를 생성하는 것을 확인할 수 있다. 그 생성 방식은 직전의 수를 거듭제곱하여 소수 P로 나눈 나머지를 취하는 것으로, 매우 취약한 방식이다. 직전의 수에만 의존하기 때문에 하나의 난수를 확보한다면 이후 난수를 전부 예측할 수 있기 때문이다. 다만 문제에서는 현재의 난수를 통해 직전의 seed를 계산해야 하기 때문에 문제의 난이도가 조금은 올라갔다고 볼 수 있다. 여기서 문제가 되는 것은 P를 4로 나눈 나머지가 3이므로 tonelli-shanks 알고리즘을 통해 이산 거듭제곱근을 계산하는 것이 매우 쉽다는 점이다. 따라서 단순히 거듭제곱근을 구하고, 가능한 두 거듭제곱근 중 flag 형식을 만족하는 수를 찾으면 된다.

Collatz_conjecture - Misc

콜라츠 추측은 수학계에서 매우 유명한 문제로, 단순한 문제 정의와는 상반되게  많은 수학자들의 노력에도 아직까지 해결되지 않은 난제이다. 컴퓨터를 이용하여 매우 큰 수까지도 콜라츠 추측이 성립함이 알려져 있으므로 실제 콜라츠 추측의 반례를 찾는 것은 의도된 풀이가 아닐 것이다. 문제에서 제시된 소스코드를 확인하여 보면 C언어로 작성되어, 입력을 unsigned int64에 저장하고 콜라츠 추측을 검증한다. 이때 콜라츠 추측은 입력보다 큰 수가 그 과정에서 등장할 수 있으며, 이는 오버플로우를 발생시켜 의도되지 않은 방향으로 프로그램을 진행시킬 수 있다. 체인의 길이가 긴 솔루션을 찾는 것은 다소 복잡하며 많은 시간을 요하므로 $3x+1=2^{64}$인 $x$를 찾아 $x$->0->0의 체인으로 문제를 해결하였다.

Red-Black Christmas Tree - Crypto

red-black tree는 많은 곳에서 사용되는 self-balancing binary search tree이므로 해당 문제에서 이와 관련된 것을 다룰까 하여 기대했으나, 아쉽게도 그렇지는 않았다. 아직까지 문제 제목이 왜 이런지는 의문이다만, 크립토 문제 중에서는 난이도가 있어 솔브수가 적은 문제였다.

문제 난이도 때문에 끝까지 단독 솔브를 기대했으나, 또다른 팀이 풀어 2솔브로 마무리된 문제이다.

문제에서 제시된 코드를 확인해보면, $O(N^2)$ 곱셈을 구현한 듯한 함수와 분할정복을 이용한 거듭제곱을 구현한 듯한 함수를 확인할 수 있다. 다만 눈에 띄는 점은, 덧셈과 뺄셈이 있어야 할 자리에 XOR이 있다는 점이다. 여기서 생각할 수 있는 것은 대부분의 ctf task에서 단 하나뿐이다. 비트별로 별도의 수를 의미하는, $\mathbb{F}_2$ 상의 연산이라는 것이다. 즉, 해당 문제에서 각각의 정수는 $\mathbb{F}_2/n$의 원소인 다항식을 의미한다. 이때 $n$은 제시된 정수 $n$을 다항식으로써 해석한 것이다. 조금 다르게 말하자면 2진법에서 각 자리수는 0 또는 1이라는 규칙은 남긴채로 진수만 2에서 $X$로 변경한 것이다. 따라서 본 문제의 풀이는 $\mathbb{F}_2/n$에서의 RSA이며, RSA의 암호학적 안전성은 order의 비밀성에서 기인한다는 점을 생각할 때 $\mathbb{F}_2/n$의 order를 계산하면 문제를 해결할 수 있으므로 이를 계산하여 0x10001제곱하는 연산의 역연산을 구하여 계산하면 flag를 복구할 수 있다.

where's the box - Crypto

정수 $m$을 임의의 난수 $r$에 대해 $g^mr^n\mod n$으로 암호화하는 암호 시스템의 encrypt oracle, decrypt oracle, encrypt flag oracle이 제공된다. 이때 임의의 두 정수가 서로소일 확률은 $\frac{6}{\pi^2}$이므로 flag를 3회 정도 encrypt한 후 gcd를 취하면 $g^{flag}$를 어렵지 않게 구할 수 있다. 이때 decrypt oracle에서는 복호화 결과가 flag의 배수이면 결과를 보여주지 않는데, 이는 $g^{flag}$를 거듭제곱한 값의 복호화를 방지한다. 그럼에도 $g^{flag+1}$의 복호화 결과는 보여주므로 이를 계산하여 복호화하면 flag를 얻을 수 있다.

santa's sack - Crypto

flag를 내가 습득하진 않았지만, 풀이를 도우며 도출한 풀이를 작성한다. b[0]의 값이 될 수 있는 후보는 1226~2450의 1225개의 정수이다. 이에 대응되는 b[1]의 개수까지 고려하면 (b[0],b[1])의 개수는 대략 몇백만개 정도로 bound된다. 각각의 후보에 대해, $x\times b[0]+y\times b[1]=\gcd(b[0],b[1])$의 확장 유클리드 호제법을 해결하면 $r\times \gcd(b[0],b[1])+kq$의 값을 얻을 수 있다. $\gcd(b[0],b[1])$이 1일 확률은 다소 높으므로 그럴 것이라 가정하고 수식을 전개하면 $q$ 값 역시 복구할 수 있으며, 이렇게 얻은 $r$과 $q$가 올바른 값임은 b 배열을 모두 복구하여 superincreasing sequence임을 확인하여 알 수 있다. b 배열을 복구한 후에는 암호문에 적절한 연산을 취한 후 복구한 b 배열의 knapsack 문제로 변환되므로 이를 CJLOSS 알고리즘을 이용하여 해결하면 flag를 얻을 수 있다.

Windows Search - Forensic

.edb 파일이 제공되어, https://moaistory.blogspot.com/2018/10/winsearchdbanalyzer.html에서 WinSearchDBAnalyzer 다운로드 후 flag.txt를 찾으면 된다.

Black Body Radiation

• Stephen-Boltzman Law: $P_{blackbody} = \sigma AT^4$
• Wien's Law: $\lambda_{peak}T=\text{Const.}$
• Rayleigh-Jeans Law: $R(\lambda,T)=\frac{2\pi ckT}{\lambda^4}$
• Plank's Law: $R(\lambda,T)=\frac{2\pi hc^2}{\lambda^5 (e^{hc/\lambda kT}-1)}$

Compton Effect: $\Delta\lambda = \frac{h}{m_0c}(1-\cos\theta)$

Bohr의 가정(각운동량 양자화): $L=mvr=n\hbar$

수소 원자

• $r_n = \frac{\epsilon_0n^2h^2}{\pi me^2}$
• $v_n = \frac{e^2}{2\epsilon_0 nh}$
• Bohr Radius $a_0=\frac{\epsilon_0h^2}{\pi me^2}$
• $r_n = a_0n^2$
• $K = \frac{me^4}{8\epsilon_0^2n^2h^2}$
• $U = -\frac{me^4}{4\epsilon_0^2n^2h^2}$
• $E=U+K = -\frac{me^4}{8\epsilon_0^2n^2h^2}$
• $R_H=\frac{me^4}{8c\epsilon_0^2h^3}$
• $\frac{1}{\lambda}=R_H\left(\frac{1}{{n_1}^2}-\frac{1}{{n_2}^2}\right)$

De Broglie wave length: $\lambda = \frac{h}{p}$

불확정성 원리: $\Delta x\Delta p\ge \hbar$, $\Delta E\Delta t\ge \hbar$

Schrodinger Equation(Time Independent)

• Hamiltonian: $H=\frac{P^2}{2m}+U$
• $P=\frac{\hbar}{i}\nabla=-\hbar^2\nabla^2=-\hbar^2\left(\frac{\partial^2}{\partial x^2}+\frac{\partial^2}{\partial y^2}+\frac{\partial^2}{\partial z^2}\right)$
• Schrodinger Equation: $H\psi = E\psi$
• Probability Density function: $P(x)=\psi^2(x)$
• normalization condition: $\int_{-\infty}^\infty\psi^2dx=1$

Bohr's correspondence principle: 양자적 현상의 scale을 키우면 고전역학적 분석에 수렴한다.

Inifinite Potential Well (1D)

• $-\frac{\hbar^2}{2m}\frac{d^2\psi}{dx^2}=E\psi$
• Boundary condition: $\psi=0$ at $x=0,L$
• $E=\frac{\hbar}{2m}\frac{n^2\pi}{L^2}=\frac{n^2h^2}{8mL^2}$
• $\psi_n=\sqrt{\frac{2}{L}}\sin\left(\frac{n\pi x}{L}\right)$

Infinite Potential Square Well (3D)

• $\psi(x)=A\sin\frac{n_x\pi x}{L}\sin{n_y\pi y}{L}\sin{n_z\pi z}{L}$
• $E = \frac{h^2}{8mL^2}({n_x}^2+{n_y}^2+{n_z}^2)$

Harmonic Oscillator

• $-\frac{\hbar^2}{2m}\frac{\partial^2 \psi}{\partial x^2}+\frac{1}{2}mw^2x^2\psi=E\psi$
• $-\frac{\hbar^2}{2m}\frac{\partial^2\psi}{\partial x^2}+\frac{1}{2}mw^2x^2\psi=E\psi$
• $E_n=\left(n+\frac{1}{2}\right)\hbar w$

Tunneling Effect: finite potential well의 경우 벽 너머서도 $\psi$가 nonzero -> 벽을 뚫고 외부로 나갈 확률 존재

Michaelson-Morley Experiment: 방향에 따른 빛의 속력의 차이가 관찰되지 않음 -> 매질 에테르가 존재한다는 가정에 모순

Galilean Transform (classical dynamics)

$$\begin{align}x&=x^\prime+ut \newline y&=y^\prime \newline z&=z^\prime \newline t&=t^\prime \newline v&=v^\prime+u\end{align}$$

Lorenz Transform (modern dynamics)

$$\begin{align}\gamma &= \frac{1}{\sqrt{1-u^2/c^2}}\newline x^\prime&=\gamma(x-ut)\newline t^\prime&=\lambda(t-\frac{ux}{c^2})\newline v_x^\prime&=\frac{dx-udt}{dt-udx/c^2}=\frac{v_x-u}{1-uv_x/c^2}\newline \vec{p}&=\frac{m\vec{u}}{\sqrt{1-u^2/c^2}}=\gamma m\vec{u}\newline \vec{F}&=\frac{d\vec{p}}{dt}=\frac{m(du/dt)}{(1-u^2/c^2)^{3/2}}\newline K&=\int\frac{dp}{dt}udt=\gamma mc^2-mc^2\newline E&=K+mc^2\newline \left(\frac{E}{mc^2}\right)^2&=\frac{1}{1-v^2/c^2}\left(\frac{P}{mc}\right)^2\newline E^2&=(mc^2)^2+(pc)^2\end{align}$$

Space-Time Coordinate : $(ict,x,y,z)$

Momentum

$$\begin{align}P_\mu &= (E/c,P_x,P_y,P_z)\newline\begin{bmatrix}P_0^\prime\newline P_1^\prime\newline P_2^\prime\newline P_3^\prime \end{bmatrix} &= \begin{bmatrix} \gamma & -i\gamma\beta & 0 & 0 \newline i\gamma\beta & \gamma 0 & 0 \newline 0 & 0 & 1 & 0 \newline 0 & 0 & 0 & 1\end{bmatrix}\begin{bmatrix}P_0\newline P_1\newline P_2\newline P_3 \end{bmatrix}\end{align}$$

Field Strength Tensor

$$F_{\mu\nu}=\begin{bmatrix}0 & B_3 & -B_2 & -iE_1 \newline-B_3 & 0 & B_1 & -iE_2 \newline B_2 & -B_1 & 0 & -iE_3 \newline iE_1 & iE_2 & iE_3 & 0\newline\end{bmatrix} $$

Einstein's Convention : repeated index variable with $\sum$ -> skip $\sum$ symbol

Let $A_{\mu\nu}$ be the matrix of Lorenz Transform.

Then $x_{\mu}=A_{\mu\nu}x_{\nu}$, $F_{\mu\nu}=A_{\mu\lambda}A_{\nu\delta}F_{\lambda\delta}$