Archive

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

1. Birthday Paradox

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

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

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

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

2. Frequency of Prime number

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

이는 Big-Theta notation의 정의 $f(x)\in \mathrm{\Theta }(g(x))\iff 0<{\displaystyle \underset{x\to \mathrm{\infty }}{lim}\frac{f(x)}{g(x)}<\mathrm{\infty }}$에 따라 $\pi (x)\in \mathrm{\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\approx 177$개의 해시값을 구하면 소수인 MD5 해시값을 얻을 수 있다.

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

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

임의의 두 자연수 $n,m$에 대해 두 수가 서로소일 확률을 $P$라고 하자. 임의의 두 자연수의 최대공약수가 $d$일 확률을 $P(d)$라고 하자. 이때, 임의의 두 자연수는 자연수인 최대공약수를 가지므로 ${\displaystyle \sum _{d=1}^{\mathrm{\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}^{\mathrm{\infty }}P(d)=\sum _{d=1}^{\mathrm{\infty }}P/d^2=P\times \sum _{d=1}^{\mathrm{\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{array}{rlr}N& =xy& \\ & =(\frac{x+y}{2}-\frac{y-x}{2})(\frac{x+y}{2}+\frac{y-x}{2})& \end{array}$$

$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$를 $\lceil \sqrt{N}\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=\mathrm{\Theta }(N)$은 익히 알려진 사실이므로, Fermat Factorization의 시간 복잡도는 Fermat Factorization을 통해 $N=xy$임을 찾을 때 $\frac{|y-x{|}^2}{\mathrm{\Theta }(N)}=\mathrm{\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$은 순환 행렬이다.
$$\mathrm{\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}_k{x}^k}$를 다음과 같은 벡터에 대응시켜보자.
$$v=\left[\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_n\end{array}\right]$$
다항식 $f,g$ 곱셈에서 $x^c$의 계수는 $a+b=c$를 만족하는 음이 아닌 가능한 모든 정수쌍 $a,b$에 대해 $f$의 $x^a$의 계수와 $g$의 $x^b$의 계수를 합한 값과 같으며, 두 $n$차 다항식을 곱하면 최대 $2n$차가 된다는 것은 익히 알려져 있다. 이를 고려할 때, '다항식 $f$를 곱한다'는 연산은 다음과 같은 $(2n+1)\times (n+1)$행렬로 표현할 수 있다.

$$\left[\begin{array}{cccc}{a}_0& 0& \cdots & 0\\ a_1& a_0& \cdots & 0\\ a_2& a_1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_n\end{array}\right]$$

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

페르마 소정리에 의하여 0이 아닌 $x\in \mathbb{Z}/p\mathbb{Z}$는 $x^{p-1}\equiv 1(\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$을 벡터가 아닌, 순환 행렬에 대응시키면 더 자연스러운 대응 관계를 관찰할 수 있다.

$$\left[\begin{array}{cccc}{a}_0& a_{p-2}& \cdots & a_1\\ a_1& a_0& \cdots & a_2\\ a_2& a_1& \cdots & a_3\\ ⋮& ⋮& \ddots & ⋮\\ a_{p-2}& a_{p-3}& \cdots & a_0\end{array}\right]$$

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}$ 상에서 근을 갖지 않는 임의의 다항식은 오일러 소정리에 의해 $(\varphi (n)-1)$차 이하의 다항식으로 표현된다. 행렬과의 대응관계 역시 똑같이 정의할 수 있으므로, 다음과 같은 관계가 $\mathbb{Z}/n\mathbb{Z}$ 상에서 정의되며 근을 갖지 않는 $(\varphi (n)-1)$차 다항식에 대응되는 $\varphi (n)\times \varphi (n)$순환행렬 $M$에 대하여 $M\equiv M^{\varphi (n)}(\text{mod }n)$가 성립한다.