Archive

이번 포스트는 암호학을 배우면서 간단하게 접한 확률에 관한 몇 가지 지식을 소개하고자 한다.

1. Birthday Paradox

Birthday Paradox, 즉 생일의 역설은 이후 소개드릴 내용에 비해 잘 알려져 있는 사실이다. 이는 "23명이 모여있으면 그 중 생일이 같은 두 사람이 존재할 확률이 약 50%이다"라는 내용으로 흔히 소개되어 처음 접하면 "생각보다 많이 적네?" 싶은, 조금은 신기한 사실이다.

CTF에서는 몇 가지의 분류가 존재하는 값을 출력하는 확률적 알고리즘에 대해 같은 분류에 속하는 두 가지 출력을 얻고자 할 때 종종 사용된다. md5 해시의 값을 정수로 바꾸어 65537로 나눈 나머지가 같은 두 원본 텍스트 쌍을 찾는 경우 같은 예시가 존재한다.

물론 확률에 기반한 시행이므로 평균적으로 빨리 시행됨을 알려주는 것이므로 시행 시간에는 편차가 존재할 수 있다.

• Recommend to read : 위키백과 - 생일 공격

2. Frequency of Prime number

$x$ 이하의 소수의 개수를 의미하는 소수 계량 함수 $\pi(x)$에 대해 $\displaystyle\lim_{x\rightarrow\infty} \frac{\pi(x)}{x/\ln x}=1$이 성립한다.

이는 Big-Theta notation의 정의 $f(x)\in \Theta(g(x)) \Leftrightarrow 0<\displaystyle\lim_{x\rightarrow\infty} \frac{f(x)}{g(x)}<\infty$에 따라 $\pi(x)\in \Theta(x/\ln x)$라는 의미이기도 하며, $x$ 이하의 수를 랜덤하게 골랐을 때 그 수가 소수일 확률이 $\frac{\pi(x)}{x}\approx\frac{x/\ln x}{x}=\frac{1}{\ln x}$임을 의미하기도 한다.

CTF에서는 $n$-bit 정수를 랜덤하게 뽑을 때 소수일 확률이 $1/n$이며, 따라서 uniform하거나 그렇다고 추정되는 $n$-bit number generator을 반복 실행하여 소수를 얻을 실행 횟수의 기댓값이 $n$임을 알려주어 brute force 풀이의 근거가 된다.

대표적인 사용 예시로는 소수인 MD5 해시값을 찾는 경우가 있다. MD5는 32byte=256bit를 출력하는 해시 알고리즘이므로 평균적으로 $\ln{255}\approx177$개의 해시값을 구하면 소수인 MD5 해시값을 얻을 수 있다.

• Recommend to read : 위키백과 - 소수 계량 함수

3. Probablity of $\gcd(n,m)=1$

임의의 두 자연수 $n,m$에 대해 두 수가 서로소일 확률을 $P$라고 하자. 임의의 두 자연수의 최대공약수가 $d$일 확률을 $P(d)$라고 하자. 이때, 임의의 두 자연수는 자연수인 최대공약수를 가지므로 $\displaystyle\sum_{d=1}^{\infty} P(d) = 1$이 성립한다.

또한 어떤 두 자연수 $n,m$의 최대공약수가 $d$라 하면 $gcd(n/d,m/d)=1$이다. 바꿔말하자면 두 서로소인 자연수 $a,b$를 이용하여 $da,db$라는 최대공약수가 $d$인 두 자연수 쌍을 만들 수 있다. 임의의 자연수를 고를 때 $d$의 배수일 확률은 $1/d$이므로 $P(d)=P\times(1/d)\times(1/d)=P/d^2$이다.

즉, $\displaystyle\sum_{d=1}^{\infty} P(d) = \sum_{d=1}^{\infty} P/d^2 = P\times\sum_{d=1}^{\infty} 1/d^2 = \frac{\pi^2}{6}P = 1$이다. 따라서 $P=\displaystyle\frac{6}{\pi^2}$이다.

페르마 인수분해는 홀수 $N$에 대해 $\sqrt{N}$에 근접한 두 인수가 존재할 때, 해당 두 인수를 빠르게 찾을 수 있는 방법이다. 실제 암호 분석에는 그 실용성이 떨어져 이용되기 어려우나, CTF에 한정하여서는 잘 알려져 있으며 종종 출제되는 기술이다.

CTF에서는 일반적으로 RSA의 공개키 $N=pq$에서 $p$와 $q$가 유사한 상황에 자주 사용되어 소인수분해로 사용하나, 실은 하나의 인수 쌍을 찾는 기술이므로 인수분해라 표현하는 것이 조금 더 정확할 것이다.

페르마 인수분해의 기본적인 아이디어는 다음과 같은, 여러분이 중학교 때 합차 공식이라는 이름으로 들어보았을 공식이다.

$$(a+b)(a-b)=a^2-b^2$$

좌변의 곱 꼴이 페르마 인수분해의 핵심이다. 좌변의 $a+b$, 그리고 $a-b$에 각각의 인수가 대응되게 하는 $a,b$를 찾으면 해당 수를 인수분해 했다고 할 수 있을 것이다.

어떤 홀수 $N$가 두 홀수 $x,y(x<y)$의 곱으로 표현된다고 생각해보자. 즉, $N=xy$이다. 이때, 다음의 식 전개를 살펴보자.

$$\begin{align}N&=xy&\\&=(\frac{x+y}{2}-\frac{y-x}{2})(\frac{x+y}{2}+\frac{y-x}{2})&\end{align}$$

$s=\frac{x+y}{2},d=\frac{y-x}{2}$라 하면 $N=(s+d)(s-d)=s^2-d^2$, 즉 $s^2-N=d^2$이다.

따라서 $N$ 이상인 제곱수 $s^2$에 대하여 $s$를 $\left\lceil\sqrt{N}\right\rceil$부터 시작하여 1씩 증가시키며 $N$을 빼고, 그 값이 제곱수가 된다면 $s$와 $d$의 값을 찾을 수 있으며 $s-d$와 $s+d$가 $N$의 인수가 된다는 사실을 알 수 있다.

요약하자면 다음 pseudo code를 산출할 수 있다.

위 알고리즘의 시간복잡도를 계산해보자. $s^2-N$이 $d^2$에 도달해야 하므로, $d^2$을 $N$ 근처에서의 제곱수 간 평균 간격으로 나누면 대략적인 반복문의 반복 횟수를 추정할 수 있다. $(N+1)^2-N^2=2N+1=\Theta(N)$은 익히 알려진 사실이므로, Fermat Factorization의 시간 복잡도는 Fermat Factorization을 통해 $N=xy$임을 찾을 때 $\frac{|y-x|^2}{\Theta(N)}=\Theta(\frac{|y-x|^2}{N})$임을 알 수 있다.

조금 응용을 해보자면, Fermat Factorization을 이용해 크기 비율을 대략적인 정수비로 아는 두 인수가 존재할 때, 그러한 두 인수를 찾을 수 있다. 만약 두 인수 $x,y$의 정수비에 가까운 정수비가 $a:b$라고 하면, $bx\approx ay$일 것이고, $N=xy$를 변형하여 $abN=abxy=(bx)(ay)$ 꼴로 고칠 수 있기 때문이다. 따라서 $abN$을 Fermat Factorization하고 구해진 두 인수를 $a, b$로 나눠보는 간단한 과정을 통해 $N$의 인수를 알 수 있다.

해당 글에서는 $\mathbb{Z}/p\mathbb{Z}$ 상의 순환 행렬에 대해 페르마 소정리가 성립함을 증명한다.

Theoretical Background

1. 페르마 소정리

소수 $p$와 정수 $a$에 대해 $a \equiv a^p (\text{mod }p)$가 성립한다.

2. 순환 행렬

$\mathbb{Z}/p\mathbb{Z}$ 상의 $n\times n$ 행렬 $M$이 다음과 같은 성질을 만족하면 $M$은 순환 행렬이다.
$$
\forall i,j,a,b\in \mathbb{Z}/p\mathbb{Z}\text{ which satisfies }i-j\equiv a-b (\text{mod }n), M_{ij}=M_{ab}
$$

Proof

1. Matrix Expression of polynomial multiplication

다항식 $f(x)=\displaystyle\sum_{k=0}^{n}a_kx^k$를 다음과 같은 벡터에 대응시켜보자.
$$
v=\begin{bmatrix}
a_0 \\
a_1 \\
\vdots \\
a_n
\end{bmatrix}$$
다항식 $f,g$ 곱셈에서 $x^c$의 계수는 $a+b=c$를 만족하는 음이 아닌 가능한 모든 정수쌍 $a,b$에 대해 $f$의 $x^a$의 계수와 $g$의 $x^b$의 계수를 합한 값과 같으며, 두 $n$차 다항식을 곱하면 최대 $2n$차가 된다는 것은 익히 알려져 있다. 이를 고려할 때, '다항식 $f$를 곱한다'는 연산은 다음과 같은 $(2n+1) \times (n+1)$행렬로 표현할 수 있다.

$$ \begin{bmatrix} a_0 & 0 & \cdots & 0 \\ a_1 & a_0 & \cdots & 0 \\ a_2 & a_1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & a_n \end{bmatrix} $$

2. Polynomial multiplication over $\mathbb{Z}/p\mathbb{Z}$

페르마 소정리에 의하여 0이 아닌 $x\in\mathbb{Z}/p\mathbb{Z}$는 $x^{p-1}\equiv1(\text{mod }p)$를 만족하므로, $\mathbb{Z}/p\mathbb{Z}$에서 정의되며 근을 갖지 않는 다항식 $f$를 다음과 같은 $(p-1)\times(p-1)$ 순환 행렬에 대응시키면, 다항식 $f,g$와 이에 대응하는 행렬 $M_f,M_g$에 대해서 $f\times g$가 $M_f\times M_g$에 대응된다는 성질을 확인할 수 있다. 따라서 다항식을 $f$을 벡터가 아닌, 순환 행렬에 대응시키면 더 자연스러운 대응 관계를 관찰할 수 있다.

$$\begin{bmatrix}
a_0 & a_{p-2} & \cdots & a_1 \\
a_1 & a_0 & \cdots & a_2 \\
a_2 & a_1 & \cdots & a_3 \\
\vdots & \vdots & \ddots & \vdots \\
a_{p-2} & a_{p-3} & \cdots & a_0
\end{bmatrix}$$

3. Fermat's Little Theorem of Circulant Matrix

(2.)에서의 관찰을 귀납적으로 적용하면, $\mathbb{Z}/p\mathbb{Z}$ 상에서 정의되고 근을 갖지 않는 $(p-2)$차 다항식 $f$에 대응되는 $(p-1)\times(p-1)$ 순환 행렬 $M$에 대해 $M^p$가 $\{f(x)\}^p$에 대응된다. 페르마 소정리에 따라 $f(x)\equiv\{f(x)\}^p(\text{mod }p)$이므로 $\{f(x)\}^p$에 대응되는 $M^p$는 $f(x)$에 대응되는 $M$과 동일하여, $M\equiv M^p(\text{mod }p)$임을 알 수 있다.

4. Extension (Euler's Theroem of Circulant Matrix)

$\mathbb{Z}/n\mathbb{Z}$에서 위와 같은 과정을 진행할 수 있는지 확인해보자. 핵심 아이디어는 $\mathbb{Z}/p\mathbb{Z}$상에서 근을 갖지 않는 모든 다항식은 $p-2$차 이하로 나타나며, 다항식 곱셈을 행렬의 곱셈으로 표현할 수 있다는 것이었다. 마찬가지로 $\mathbb{Z}/n\mathbb{Z}$ 상에서 근을 갖지 않는 임의의 다항식은 오일러 소정리에 의해 $(\phi(n)-1)$차 이하의 다항식으로 표현된다. 행렬과의 대응관계 역시 똑같이 정의할 수 있으므로, 다음과 같은 관계가 $\mathbb{Z}/n\mathbb{Z}$ 상에서 정의되며 근을 갖지 않는 $(\phi(n)-1)$차 다항식에 대응되는 $\phi(n)\times\phi(n)$순환행렬 $M$에 대하여 $M\equiv M^{\phi(n)}(\text{mod }n)$가 성립한다.