Implicit Factoring with Shared MSBs & Middle Bits

* PC버전으로 보지 않으면 MathJax 플러그인이 실행되지 않아 expression이 표현되지 않습니다.

---

 

이 글은 PKC 2010 ; 13th International Conference on Practice and Theory in Public Key Cryptography 에서 발표된 Jean-Charles Faugère, Raphaël Marinier, Guénaël Renault 의 연구를 번역정리한 것이다.

 

RSA를 공략하기 위한 방법 중 하나는 $N$을 소인수분해하는 것이다.

일반적으로 큰 수를 소인수분해하기는 어렵지만, 특정 조건이 맞으면 짧은 시간 내에 소인수분해를 할 수 있다.

 

1. Factoring 2 RSA Moduli with Shared MSBs

다음과 같이 2개의 $n$-bit RSA moduli $N$이 있다고 가정하자. $q_i$는 $\alpha$-bit 소수이고, $p_i$는 $t$개의 MSB (최상위 비트) 를 공유한다.

$$\begin{array}{rl}{N}_1& =p_1{q}_1\\ N_2& =p_2{q}_2\end{array}$$

 

$t\ge 2\alpha +3$ 이면, $N_i$을 $O\left(n^2\right)$ 시간 내에 소인수분해할 수 있다.

 

Proof

Lemma 1에서 정의한 lattice $L$의 reduced basis를 구하는 데 $O\left(n^2\right)$의 시간이 걸리고, Lemma 2에서 $t\ge 2\alpha +3$ 이면 ${\mathbf{b}}_0=\pm {\mathbf{v}}_0$ 임을 증명하였다.

Lemma 1 아래의 설명을 따라 $N_i$의 인수를 구할 수 있다.

 

Lemma 1.

행렬 $M$을 아래와 같이 정의하고, $M$의 row vector를 각각 ${\mathbf{v}}_1$, ${\mathbf{v}}_2$ 라고 하자.

 

$$M=\left[\begin{array}{ccc}K& 0& N_2\\ 0& K& -N_1\end{array}\right],K=\lfloor 2^{n-t+\frac{1}{2}}\rfloor$$

 

행렬 $M$의 row vector의 span으로 구성되는 lattice $L$을 가정하고, $L$의 벡터 ${\mathbf{v}}_0$을 다음과 같이 정의한다.

 

$${\mathbf{v}}_0=q_1{\mathbf{v}}_1+q_2{\mathbf{v}}_2=⟨q_{1}K,q_{2}K,q_1{q}_2(p_2-p_1)⟩$$

---

$p_1$과 $p_2$는 $t$개의 최상위 비트를 공유하기 때문에 $p_2-p_1$ 은 대략 $n+\alpha -t$ bit의 정수가 된다. $t$가 충분히 크다면 ${\mathbf{v}}_0$은 $L$의 shortest vector가 될 수 있고, 이 경우 ${\mathbf{v}}_0$을 $K$로 나눠 $q_1$과 $q_2$를 다항 시간 ($O(n^2)$) 내에 구할 수 있다.

 

$L$의 Gramian matrix는 $M{M}^T=\left[\begin{array}{cc}{K}^2+N_2^2& -N_1{N}_2\\ -N_1{N}_2& K^2+N_1^2\end{array}\right]$ 이고, $L$의 volume은 Gramian matrix의 행렬식으로 $V=\det (M{M}^T)=K\sqrt{N_1^2+N_2^2+K^2}$ 이다. $K^2\approx 2^{2(n-t)}$ 은 $N_i^2\approx 2^{2n}$ 에 비해 상대적으로 작기 때문에, $V\approx 2^{2n-t}$ 으로 근사시킬 수 있다.

 

${\mathbf{v}}_0$이 $L$의 shortest vector라면, 이 vector의 norm $\Vert {\mathbf{v}}_0\Vert \approx 2^{n+\alpha -t}$는 $L$의 Minkowski's bound보다 작다. 따라서 아래 식이 성립한다.

 

$$2^{n+\alpha -t}\approx \Vert {\mathbf{v}}_0\Vert \le \sqrt{2}{V}^{\frac{1}{2}}\approx 2^{n-\frac{t}{2}}$$

 

위 식은 $t\ge 2\alpha$ 인 경우 성립한다.

---

 

Lemma 2.

Lagrange method를 통해 찾은 $L$의 basis를 $⟨{\mathbf{b}}_1,{\mathbf{b}}_2⟩$ 라고 하자. $\Vert {\mathbf{b}}_i\Vert ={\lambda }_i(L)$ 이며 Hadamard's inequality에 의해 $\det (L)\ge V$ 가 성립한다. 이 부등식을 풀어 아래의 두 관계를 얻을 수 있다.

 

$$\begin{array}{rl}\Vert {\mathbf{b}}_1\Vert & \le \Vert {\mathbf{v}}_0\Vert \\ \Vert {\mathbf{b}}_2\Vert & \ge \frac{V}{\Vert {\mathbf{v}}_0\Vert }\end{array}$$

 

만약 ${\mathbf{v}}_0<{\mathbf{b}}_2$ 라면, ${\mathbf{b}}_2$가 $L$의 local minimum이기 때문에 다음 식이 성립한다.

 

$${\mathbf{v}}_0=a{\mathbf{b}}_1=a(b{\mathbf{v}}_1+c{\mathbf{v}}_2)a,b,c\in \mathbb{Z}(ab=q_1,ac=q_2)$$

 

$q_i$는 소수이기 때문에 $a=\pm 1$이 되고, 따라서 ${\mathbf{v}}_0=\pm {\mathbf{b}}_1$ 이다. 이를 다시 위의 부등호에 대입하면 아래의 결과가 나온다.

 

$$\begin{array}{}\text{(1)}& {\Vert {\mathbf{v}}_0\Vert }^2<V\end{array}$$

 

이제 $\Vert {\mathbf{v}}_0\Vert$의 upper bound와 $V$의 lower bound를 구해 $t$의 범위를 구할 것이다.

$|p_2-p_1|\le 2^{n-\alpha +1-t}$ 이므로, ${\mathbf{v}}_0$의 정의에 의해 ${\mathbf{v}}_0\le 2^{2(n-t)+1}(q_1^2+q_2^2)+q_1^2{q}_2^2{(p_1-p_2)}^2$ 이다. $p$와 $q$를 풀어주면 아래의 bound를 얻는다.

 

$$\begin{array}{}\text{(2)}& {\Vert {\mathbf{v}}_0\Vert }^2\le 2^{2(n+\alpha -t)+2}+2^{2(\alpha +n+1-t)}\le 2^{2(n+\alpha -t)+3}\end{array}$$

 

$V$는 $N_1,N_2\ge 2^{n-1}$ 과 $K^2\ge 2^{2(n-t)}$ 를 이용해서 아래의 boundary를 찾을 수 있다.

 

$$\begin{array}{}\text{(3)}& V^2=K^2(N_1^2+N_2^2+2^{2(n-t)})>2^{4n-2t-1}\end{array}$$

 

부등식 (2)와 (3)에서, (1)이 성립하기 위한 $t$의 범위는 다음과 같다.

 

$$\begin{array}{}\text{(4)}& t\ge 2\alpha +4\end{array}$$

 

한편 $\Vert {\mathbf{v}}_0\Vert$과 $V$의 범위를 더 tight하게 구해서 $t$의 범위를 확장시킬 수 있다.

$q_i$는 $\alpha$-bit 소수이므로 $q_i\le 2^{\alpha }-1$ 이다. $2^{\alpha }-1=2^{\alpha -{ϵ}_1}$ 로 ${ϵ}_1$을 정의한다. $q_i^2\le 2^{2\alpha -2{ϵ}_1}$ 이며, $K$의 정의를 사용해서 $K^2{q}_i^2$의 upper bound를 구할 수 있다.

 

$$\begin{array}{}\text{(5)}& K^2{q}_i^2\le 2^{2(n-t+\alpha )+1-2{ϵ}_1}\end{array}$$

 

$p_i$의 성질을 사용해 아래 부등식을 만들 수 있다.

 

$$\begin{array}{}\text{(6)}& q_1^2{q}_2^2{(p_2-p_1)}^2\le 2^{2(n-t+\alpha +1-2{ϵ}_1)}\end{array}$$

 

${\Vert {\mathbf{v}}_0\Vert }^2$을 $p$와 $q$로 풀어서 쓴 식에 (5), (6)의 부등식을 대입해서 다음과 같이 boundary를 설정할 수 있다.

 

$$\begin{array}{}\text{(7)}& {\Vert {\mathbf{v}}_0\Vert }^2\le 2^{2(n+\alpha -t)+2-2{ϵ}_1}+2^{2(n-t+\alpha +1-2{ϵ}_1)}\le 2^{2(n+\alpha -t)+3-{ϵ}_1}\end{array}$$

 

$2^{n-t+\frac{1}{2}}-1=2^{n-t+\frac{1}{2}-{ϵ}_2}$ 를 만족하는 ${ϵ}_2$를 정의한다. $K=\lfloor 2^{n-t+\frac{1}{2}}\rfloor \ge 2^{n-t+\frac{1}{2}-{ϵ}_2}$ 이고 $N_i^2\ge 2^{2n-2}$ 이므로 $V^2$의 lower bound는 다음과 같이 표현된다.

 

$$\begin{array}{}\text{(8)}& V^2=K^2(N_1^2+N_2^2+2^{2(n-t)})>K^2(N_1^2+N_2^2)\ge 2^{4n-2t-2{ϵ}_2}\end{array}$$

 

(7)과 (8)의 부등식으로 (1)이 성립하기 위한 $t$의 범위를 좁힐 수 있다. $2^{2(n+\alpha -t)+3-{ϵ}_1}\le 2^{2n-t-{ϵ}_2}$ 를 풀면 $t\ge 2\alpha +3+{ϵ}_2-{ϵ}_1$ 이 된다.

${ϵ}_1={\log }_2\left(\frac{1}{1-\frac{1}{2^{\alpha }}}\right)$ , ${ϵ}_2={\log }_2\left(\frac{1}{1-\frac{1}{2^{n-t+\frac{1}{2}}}}\right)$ 이고 $\alpha \le n-t$ 이므로, ${ϵ}_2\le {ϵ}_1$ 이고 $t\ge 2\alpha +3$ 이 된다.

 

Reference

https://hal.archives-ouvertes.fr/hal-01288914/document

https://en.wikipedia.org/wiki/Minkowski%27s_theorem

https://en.wikipedia.org/wiki/Minkowski%27s_bound

https://en.wikipedia.org/wiki/Hadamard%27s_inequality