준소수의 소인수분해 문제가 쉽게 풀리는 조건
정리 1
준소수의 소인수분해 문제 $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$ 다.
같이보기
소인수분해 문제의 어려움을 이용한 보안 알고리즘
소인수분해 문제에 대한 공격 알고리즘
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p133~139. ↩︎