RSA Exploit

c ≡ m^e mod N, m ≡ c^d mod N

N = pq (p, q are prime numbers)  /  d ≡ e⁻¹ (mod λ(n))

e, N: Public Key, d: Private Key

 

1-1. Improper Selection of p, q - Large \(\left| p-q \right|\)

\(p\)와 \(q\)의 차이가 매우 크다면 Brute-Force로 비교적 짧은 시간 내에 소인수분해를 할 수 있다.

 

1-2. Improper Selection of p, q - Small \(\left| p-q \right|\) (Fermat Factorization)

\(p\)와 \(q\)의 차이가 작다면 두 수는 \(\sqrt{N}\) 에 인접한 위치에 있다. \(\sqrt{N}\) 보다 큰 \(x\) 에 대해서, \(x^{2}-N\) 이 제곱수가 되는 경우 \(N\)을 분해할 수 있다.

\[x^{2}-N=y^{2}, \quad N=(x+y)(x-y) \]

 

2. Pollard's p-1 Algorithm

\(p-1\)이 적당히 작은 수 \(B\)에 대해서 \(B\)-powersmooth number일 때 \(N\) 의 소인수를 구할 수 있는 알고리즘이다.

다음과 같은 수 \(M=\displaystyle \prod_{primes\ q \leq B} q^{\lfloor{log_{q}B}\rfloor}\) 이 있다고 가정한다. \(M\)은 \(p-1\)의 배수이므로, FLT에 의해 \(p\)와 서로소인 \(a\)에 대해서 \(a^{M}-1=a^{K(p-1)}-1 \equiv 0 \pmod{p}\) 가 성립한다. \(a^{M}-1\) 과 \(N\)의 공약수를 구하면 \(N\)의 소인수를 찾을 수도 있다.

 

1. Smoothness bound \(B\)를 정하고, \(M\)을 계산한다.

2. \(N\)과 서로소인 수 \(a\)를 임의로 정한다.

3. \(g=\mathrm{gcd}\left(a^{M}-1, N\right)\) 을 계산한다.

4-1. \(g=1\) 인 경우, \(B\)를 증가시킨 뒤 다시 시도한다.

4-2. \(g=N\) 인 경우, \(B\)를 감소시킨 뒤 다시 시도한다.

4-3. \(1<g<N\) 인 경우, \(g\)는 \(N\)의 인수이다.

 

3. Williams' p+1 Algorithm

Pollard's p-1 Algorithm의 변형 알고리즘이며, \(p+1\)이 \(B\)-powersmooth number일 때 \(N\)의 소인수를 구할 수 있는 알고리즘이다.

 

1. 2보다 큰 자연수 A로 아래와 같은 Lucas sequence를 정의한다.

\[V_{0}=2,\quad V_{1}=A,\quad V_{i}=AV_{i-1}-V_{i-2}\ (\mathrm{mod}\ N)\]

2. \(p-\left(\frac{D}{p}\right)\mid M\) 이면 \(p\mid \mathrm{gcd}\left(N, V_{M}-2\right)\) 이다. 여기서 \(D=A^{2}-4\) 이고, \(\left(\frac{D}{p}\right)\) 는 Jacobi 기호다. 여기에 사용되는 \(M\)은 \(k!\) 형태로 나타내어지며, \(V_{M}\)은 \(V_{M-1}\) 로 구성되는 Lucas sequence의 \(M\)번째 원소다.

 

t로 구성되는 수열의 \(M\)번째 원소는 아래 방법으로 구한다. (Python, SageMath)

 

from sage.all import *
 
p = random_prime(512, proof=False)
q = random_prime(512, proof=False)
N = p*q
A = 5
 
x = A
y = (A^2-2)%N
M = factorial(7)
 
for b in M.bits()[-2::-1] :
    if b == 1 :
        x = (x*y-A)%N
        y = (y^2-2)%N
    else :
        y = (x*y-A)%N
        x = (x^2-2)%N
 
V = x

 

4. Common Factors in Public Keys

여러 개의 공개키가 주어질 때, 공개키들 사이에 1이 아닌 공약수가 있다면 \(N\)을 빠르게 분해할 수 있다.

 

5. Miller-Rabin Primality Test

이 알고리즘은 어떤 수가 소수인지 판별하기 위한 알고리즘이지만, \(N\)이 유사 소수일 경우, 소인수를 구할 수 있다.

\(N=d\cdot 2^{n}+1\) 이 pseudoprime to base \(a\)일 때, 아래와 같은 수열 \(x_{n}\)을 가정한다.

\[x_{n}=a^{d\cdot 2^{n}}\]

어떤 수 \(i\)에 대해서 \(x_{i}\)는 아래 식을 만족한다.

\[x_{i}=a^{d\cdot 2^{i}}\equiv 1\ (\mathrm{mod}\ N)\]

이 때 \(x_{0}:=x_{i-1}\)은 \(x_{0}^{2}\equiv 1\ (\mathrm{mod}\ N)\) 과 \(x_{0}\not\equiv\pm 1\ (\mathrm{mod}\ N)\) 을 만족하므로 \(\mathrm{gcd}(x_{0}-1, N)\) 과 \(\mathrm{gcd}(x_{0}+1, N)\) 은 \(N\)의 인수가 된다.

 

6. Common Modulus Attack

Modulus 값이 같은 두 공개키로 두 평문을 암호화하면 원문을 복구할 수도 있다.

한 평문 \(m\)을 아래와 같이 두 공개키 (\(e_{1}\), \(N\)), (\(e_{2}\), \(N\)) 으로 각각 암호화한다고 가정한다.

$$ \begin{align} c_{1}=m^{e_{1}}\ (\mathrm{mod}\ N) \\ c_{2}=m^{e_{2}}\ (\mathrm{mod}\ N) \end{align} $$

\(e_{1}\)과 \(e_{2}\)가 서로소라면, \(re_{1}+se_{2}=1\) 를 만족하는 \(r\), \(s\)에 대해서 아래의 식이 성립한다.

$$ c_{1}^{r}c_{2}^{s} \equiv m^{\left(re_{1}+se_{2}\right)}\equiv m\ (\mathrm{mod}\ N) $$

 

7. Small e (e=3 Representatively)

\(N\)이 충분히 크거나 \(m\)이 충분히 작다면, 적당히 작은 수 \(k\)에 대해 \(m^{3}\leq kN\) 을 만족해 Brute-Force로 \(k\)를 증가시키면서 \(\sqrt[3]{c+kN}\) 이 정수일 때 값을 취해 평문을 복구할 수 있다.

 

8. Wiener's Attack

\(d<\frac{1}{3}N^{\frac{1}{4}}\) 인 경우 \(d\)를 복구할 수 있다.

증명과 알고리즘은 나중에 추가예정

 

9. 

 

Reference

ctf-wiki

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_module_attack-zh/

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_e_attack-zh/

https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_d_attack-zh/

Wikipedia

https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm

https://en.wikipedia.org/wiki/Williams%27s_p_%2B_1_algorithm

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test