📂정수론

준소수의 소인수분해 문제가 쉽게 풀리는 조건

정리 ¹

준소수의 소인수분해 문제 $N = pq$ 는 다음의 조건 하에서 비교적 쉽게 풀리게 된다.

• (i): $p$ 가 스무스한 소수다.
• (ii): $p \approx q$

설명

조건 (ii)의 의미는 $p$ 와 $q$ 의 차이가 적을 때 쉽게 풀린다는 것인데, 이에 대해서는 설명이 필요할 것이다:

• 언뜻 생각해보았을 때 $p,q \in \mathbb{N}$ 에 대해 $(p + q)$ 가 제한되어있다면 $N = pq$ 를 가장 크게 만드는 방법은 가능한 한 $p$ 와 $q$ 의 차가 크지 않게 하는 것이다. 가령 $p+q \le 12$ 이라면 $pq$ 는 $7 = p \approx q = 5$ 일 때 최대값 $35$ 를 갖는다.

거꾸로 ‘때려 맞히기’를 통한 풀이를 막기 위해서는 $p$, $q$ 는 둘 다 가능한 한 큰 게 좋다. 가령 $$N_{1}=3 \cdot 47=141 \\ N_{2}=11 \cdot 13=143$$ 이 있다고 치면 공개되었을 때는 $2$ 밖에 차이가 나지 않지만 $N_{1}$ 은 ‘노가다’를 시작하자마자 풀리게 된다.

• 그러나 이런 일차원적인 이유에서 크기가 비슷한 $p$, $q$ 을 쓴다면 이차원적인 생각을 하는 공격자에게 뚫릴 수 밖에 없다. 단순하게 생각해서 정말 $p \approx q$ 라면 공격자는 $N \approx p^2$ 이라 가정하고 $\sqrt{N}$ 의 근방으로 솔루션의 후보를 크게 줄일 수 있다. 이런 아이디어에서 수학적인 기교를 발휘하면 $N=pq$ 는 아주 쉬운 문제가 되어버린다.

증명

(i)

$p$ 가 스무스한 소수면 폴라드 $p-1$ 소인수분해 알고리즘을 사용할 수 있으므로 준소수의 소인수분해 문제가 비교적 쉽게 풀릴 수 있다.

■

(ii)

$p := a + b$, $q := a - b$ 이라고 두면 $p$, $q$ 는 $a$ 를 가운데로 $\pm b$ 만큼 떨어진 소수가 된다. 이를 $N$ 에 대해서 나타내보면 $$\begin{align*} N =& ( a + b)(a - b) \\ =& a^2 - b^2 \end{align*}$$ 즉 $N + b^2 = a^2$ 이다. 따라서 $N$ 에 $b$ 를 $1$ 씩 증가시켜가며 $\left( N + b^2 \right)$ 가 제곱수가 되면 $p = a + b$, $q = a - b$ 가 무엇인지 알 수 있어 준소수의 소인수분해 문제가 비교적 쉽게 풀릴 수 있다.

■

예시

예로써 $N = 25217$ 을 생각해보자. $N$ 을 곧이곧대로 소인수분해하는 것은 만만하지 않은 일이지만, $25217 + 8^2 = 159^2$ 임을 알고나면 $a = 159$, $b = 8$ 이므로 $$\begin{align*} p =& 159 + 8 = 167 \\ q =& 159-8 = 151 \end{align*}$$ 을 바로 구할 수 있다. 글의 맥락에 따라 말해보자면 $167 \approx 151$ 이기 때문에 쉽게 풀려버린 것이다.

한편 이 $b$ 를 찾는 걸 더 지혜롭게 해보자. 어떤 $k$ 에 대해서 $$k N = a^2 - b^2$$ 이라고 하면 $(a+b)$ 와 $(a-b)$ 는 $k$ 의 배수이므로 양변을 $k$ 로 나누기만 하면 $N$ 에 대한 식을 그대로 얻을 수 있다. 이렇게 번거로운 짓을 하는 이유는 이 식을 다음과 같이 나타낼 수 있기 때문이다. $$a^2 \equiv b^2 \pmod{N}$$ 이후는 다음과 같은 방법으로 $d = q$ 를 찾는다.

---

Step 1. $c_{i}$

계산약수가 적은 수 $c_{i}$ 들에 대해서 $c_{i} \equiv a_{i}^{2} \pmod{p}$ 를 만족시키도록 하는 $a_{1} , \cdots , a_{r}$ 들을 찾아두자.

---

Step 2. $b^2$ 계산

$$a_{i_{1}} \cdots a_{i_{s}} = a \\ c_{i_{1}} \cdots c_{i_{s}} = b^2$$ 를 만족하는 $c_{i_{1}} , \cdots , c_{i_{s}}$ 들을 찾는다.

---

Step 3. $d = \gcd \left( N , a-b \right)$

$$\begin{align*} a^2 & \equiv \left( a_{i_{1}} \cdots a_{i_{s}} \right)^{2} \\ & \equiv a_{i_{1}}^{2} \cdots a_{i_{s}}^{2} \\ & \equiv c_{i_{1}} \cdots c_{i_{s}} \\ & \equiv b^2 \end{align*}$$ 이렇게 구한 $a$, $b$ 를 통해 $d = \gcd \left( N , a-b \right)$ 를 계산하면 $d$ 는 $N$ 의 약수 $q$ 다.

같이보기

• 소인수분해

소인수분해 문제의 어려움을 이용한 보안 알고리즘

• RSA 공개 키 암호체계
• 골드바서-미칼리 확률 키 암호체계

소인수분해 문제에 대한 공격 알고리즘

• 폴라드 p-1 소인수분해 알고리즘
• 준소수의 소인수분해 문제가 쉽게 풀리는 조건