* 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{align}N_{1}&=p_{1}q_{1} \\ N_{2}&=p_{2}q_{2}\end{align}\]
\(t\geq 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\geq 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=\begin{bmatrix}K & 0 & N_{2} \\ 0 & K & -N_{1}\end{bmatrix},\quad K=\lfloor2^{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}=\langle q_{1}K, q_{2}K, q_{1}q_{2}(p_{2}-p_{1})\rangle\]
\(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는 \(MM^{T}=\begin{bmatrix}K^{2}+N_{2}^{2} & -N_{1}N_{2} \\ -N_{1}N_{2} & K^{2}+N_{1}^{2}\end{bmatrix}\) 이고, \(L\)의 volume은 Gramian matrix의 행렬식으로 \(V=\mathrm{det}(MM^{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 \(\left\lVert\mathbf{v}_{0}\right\rVert\approx 2^{n+\alpha-t}\)는 \(L\)의 Minkowski's bound보다 작다. 따라서 아래 식이 성립한다.
\[2^{n+\alpha-t}\approx\left\lVert\mathbf{v}_{0}\right\rVert\leq\sqrt{2}V^{\frac{1}{2}}\approx 2^{n-\frac{t}{2}}\]
위 식은 \(t\geq2\alpha\) 인 경우 성립한다.
Lemma 2.
Lagrange method를 통해 찾은 \(L\)의 basis를 \(\langle\mathbf{b}_{1},\mathbf{b}_{2}\rangle\) 라고 하자. \(\left\lVert\mathbf{b}_{i}\right\rVert=\lambda_{i}(L)\) 이며 Hadamard's inequality에 의해 \(\mathrm{det}(L)\geq V\) 가 성립한다. 이 부등식을 풀어 아래의 두 관계를 얻을 수 있다.
\[\begin{align}\left\lVert\mathbf{b}_{1}\right\rVert&\leq\left\lVert\mathbf{v}_{0}\right\rVert \\ \left\lVert\mathbf{b}_{2}\right\rVert&\geq\frac{V}{\left\lVert\mathbf{v}_{0}\right\rVert}\end{align}\]
만약 \(\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})\qquad a,b,c\in\mathbb{Z}\quad(ab=q_{1},ac=q_{2})\]
\(q_{i}\)는 소수이기 때문에 \(a=\pm 1\)이 되고, 따라서 \(\mathbf{v}_{0}=\pm\mathbf{b}_{1}\) 이다. 이를 다시 위의 부등호에 대입하면 아래의 결과가 나온다.
\[\left\lVert\mathbf{v}_{0}\right\rVert^{2}<V\tag{1}\]
이제 \(\left\lVert\mathbf{v}_{0}\right\rVert\)의 upper bound와 \(V\)의 lower bound를 구해 \(t\)의 범위를 구할 것이다.
\(|p_{2}-p_{1}|\leq2^{n-\alpha+1-t}\) 이므로, \(\mathbf{v}_{0}\)의 정의에 의해 \(\mathbf{v}_{0}\leq2^{2(n-t)+1}\left(q_{1}^{2}+q_{2}^{2}\right)+q_{1}^{2}q_{2}^{2}\left(p_{1}-p_{2}\right)^{2}\) 이다. \(p\)와 \(q\)를 풀어주면 아래의 bound를 얻는다.
\[\left\lVert\mathbf{v}_{0}\right\rVert^{2}\leq2^{2(n+\alpha-t)+2}+2^{2(\alpha+n+1-t)}\leq 2^{2(n+\alpha-t)+3}\tag{2}\]
\(V\)는 \(N_{1}, N_{2}\geq 2^{n-1}\) 과 \(K^{2}\geq 2^{2(n-t)}\) 를 이용해서 아래의 boundary를 찾을 수 있다.
\[V^{2}=K^{2}\left(N_{1}^{2}+N_{2}^{2}+2^{2(n-t)}\right)>2^{4n-2t-1}\tag{3}\]
부등식 (2)와 (3)에서, (1)이 성립하기 위한 \(t\)의 범위는 다음과 같다.
\[t\geq 2\alpha+4\tag{4}\]
한편 \(\left\lVert\mathbf{v}_{0}\right\rVert\)과 \(V\)의 범위를 더 tight하게 구해서 \(t\)의 범위를 확장시킬 수 있다.
\(q_{i}\)는 \(\alpha\)-bit 소수이므로 \(q_{i}\leq2^{\alpha}-1\) 이다. \(2^{\alpha}-1=2^{\alpha-\epsilon_{1}}\) 로 \(\epsilon_{1}\)을 정의한다. \(q_{i}^{2}\leq 2^{2\alpha -2\epsilon_{1}}\) 이며, \(K\)의 정의를 사용해서 \(K^{2}q_{i}^{2}\)의 upper bound를 구할 수 있다.
\[K^{2}q_{i}^{2}\leq 2^{2(n-t+\alpha)+1-2\epsilon_{1}}\tag{5}\]
\(p_{i}\)의 성질을 사용해 아래 부등식을 만들 수 있다.
\[q_{1}^{2}q_{2}^{2}\left(p_{2}-p_{1}\right)^{2}\leq 2^{2(n-t+\alpha+1-2\epsilon_{1})}\tag{6}\]
\(\left\lVert\mathbf{v}_{0}\right\rVert^{2}\)을 \(p\)와 \(q\)로 풀어서 쓴 식에 (5), (6)의 부등식을 대입해서 다음과 같이 boundary를 설정할 수 있다.
\[\left\lVert\mathbf{v}_{0}\right\rVert^{2}\leq 2^{2(n+\alpha-t)+2-2\epsilon_{1}}+2^{2(n-t+\alpha+1-2\epsilon_{1})}\leq 2^{2(n+\alpha-t)+3-\epsilon_{1}}\tag{7}\]
\(2^{n-t+\frac{1}{2}}-1=2^{n-t+\frac{1}{2}-\epsilon_{2}}\) 를 만족하는 \(\epsilon_{2}\)를 정의한다. \(K=\lfloor2^{n-t+\frac{1}{2}}\rfloor\geq 2^{n-t+\frac{1}{2}-\epsilon_{2}}\) 이고 \(N_{i}^{2}\geq 2^{2n-2}\) 이므로 \(V^{2}\)의 lower bound는 다음과 같이 표현된다.
\[V^{2}=K^{2}\left(N_{1}^{2}+N_{2}^{2}+2^{2(n-t)}\right)>K^{2}\left(N_{1}^{2}+N_{2}^{2}\right)\geq 2^{4n-2t-2\epsilon_{2}}\tag{8}\]
(7)과 (8)의 부등식으로 (1)이 성립하기 위한 \(t\)의 범위를 좁힐 수 있다. \(2^{2(n+\alpha-t)+3-\epsilon_{1}}\leq 2^{2n-t-\epsilon_{2}}\) 를 풀면 \(t\geq 2\alpha+3+\epsilon_{2}-\epsilon_{1}\) 이 된다.
\(\epsilon_{1}=\log_{2}\left(\frac{1}{1-\frac{1}{2^{\alpha}}}\right)\) , \(\epsilon_{2}=\log_{2}\left(\frac{1}{1-\frac{1}{2^{n-t+\frac{1}{2}}}}\right)\) 이고 \(\alpha\leq n-t\) 이므로, \(\epsilon_{2}\leq\epsilon_{1}\) 이고 \(t\geq 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
'Cryptography > Techniques' 카테고리의 다른 글
| RSA Exploit (0) | 2020.01.28 |
|---|
