페르마 인수분해(Fermat Factorization)

페르마 인수분해는 홀수 $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를 산출할 수 있다.

pseudo code of Fermat's Factorization Method

위 알고리즘의 시간복잡도를 계산해보자. $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$의 인수를 알 수 있다.