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 $|p-q|$

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

 

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

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

$$x^2-N=y^2,N=(x+y)(x-y)$$

 

2. Pollard's p-1 Algorithm

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

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

 

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

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

3. $g=\gcd (a^M-1,N)$ 을 계산한다.

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,V_1=A,V_i=A{V}_{i-1}-V_{i-2}(\mathrm{mod}N)$$

2. $p-\left(\frac{D}{p}\right)\mid M$ 이면 $p\mid \gcd (N,V_M-2)$ 이다. 여기서 $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)$ 을 만족하므로 $\gcd (x_0-1,N)$ 과 $\gcd (x_0+1,N)$ 은 $N$의 인수가 된다.

 

6. Common Modulus Attack

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

한 평문 $m$을 아래와 같이 두 공개키 ($e_1$, $N$), ($e_2$, $N$) 으로 각각 암호화한다고 가정한다.

$$\begin{array}{r}{c}_1=m^{e_1}(\mathrm{mod}N)\\ c_2=m^{e_2}(\mathrm{mod}N)\end{array}$$

$e_1$과 $e_2$가 서로소라면, $r{e}_1+s{e}_2=1$ 를 만족하는 $r$, $s$에 대해서 아래의 식이 성립한다.

$$c_1^r{c}_2^s\equiv m^{(r{e}_1+s{e}_2)}\equiv m(\mathrm{mod}N)$$

 

7. Small e (e=3 Representatively)

$N$이 충분히 크거나 $m$이 충분히 작다면, 적당히 작은 수 $k$에 대해 $m^3\le 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