Archive

페르마 인수분해는 홀수 $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)$가 성립한다.