Attacks on RSA

 

[1] Common Modulus Attack

RSA 시스템 관리자가 편의를 위해 동일한 모듈러스 $N$을 여러 사용자에게 발급하고, 공개키 $e$와 개인키 $d$만 다르게 설정했을 때 발생한다.

 

 

시나리오

• 상황 : Alice가 동일한 메세지 $M$을 Bob과 Charlie에게 보내는 상황
• 취약점 : Bob과 Charlie는 같은 회사 사람이라 동일한 모듈러스 $N$을 가지고 있다.
  • Bob의 공개키 : ($N, e_1$)
  • Charlie의 공개키 : ($N, e_2$)
• 공격 조건 : 두 공개 지수 $e_1$과 $e_2$가 서로소($\text{gcd}(e_1, e_2)$)여야 한다.

 

공격 원리

공격자는 도청을 통해서 두 개의 암호문을 얻는다.

1. $C_1 \equiv M^{e_1} \pmod{N}$
2. $C_2 \equiv M^{e_2} \pmod{N}$

공격자는 $N, e_1, e_2, C_1, C_2$를 모두 알고 있다. 여기서 Extended Euclidean Algorithm을 사용한다. $e_1과 e_2$가 서로소 이므로, Bézout's identity에 의해 다음을 만족하는 정수 $a,b$가 존재한다.

 

$a \cdot e_1 + b \cdot e_2 = 1$

 

따라서 공격자는 이를 이용해 $(a,b)$ 쌍을 구할 수 있다.

Bézout's Identity
GCB(최대공약수)는 두 수의 Linear Combination으로 표현할 수 있다.
0이 아닌 정수 $a,b$가 있을 때, 그들의 최대 공약수를 $d=\text{gcd}(a,b)$라고 하면 다음 식을 만족하는 정수 $x,y$가 반드시 존재한다.

                                                                                   $ax+by = d$

Extended Euclidean Algorithm
Bézout's Identity의 해 $(x,y)$를 실제로 찾아내는 방법

 

이제 공격자는 다음 식을 계산해서 평문 $M$을 구할 수 있다.

 

$C_1^a \cdot C_2^b \equiv M^{e_1\cdot a} \cdot M^{e_1\cdot b} \equiv M^{ae_1+be_2} \equiv M \pmod{N}$

 

즉, 개인키 $d$가 없어도 공격자가 평문 $M$을 구할 수 있게 된다.

 

💡$a,b$ 둘 중 하는 반드시 음수가 된다. 모듈러 연산에서 음수 지수는 Modular Inverse를 구해서 계산하면 된다.

 

 

---

[2] Low Public Exponent Attack

사용자가 암호화 속도를 높이기 위해서 공개 지수 $e$를 너무 작게 설정했을 때 발생하는 문제이다.

작은 크기의 평문 $M$을 작은 공개 지수 $e$를 사용해 암호화하는 경우, $M^e < N$인 경우가 발생하면 취약점이 생긴다.

 

 

시나리오

• 설정 : 공개키 $e = 3$을 사용하고, 모듈러스 N은 매우 큼.
• 취약점 : 보내려는 메시지 $M$이 너무 짧거나 작아서, $e$번 제곱해서 N을 넘지 않는다.
• 조건 : $M^e < N$

 

공격 원리

RSA의 암호화 식은 다음과 같다.

$C \equiv M^e \pmod{N}$

 

하지만 만약 $M^3$이 $N$보다 작다면, 모듈러 연산 $\pmod{N}$이 실제로 아무런 효력을 발휘하지 못한다. 즉, 그냥 실수 연산과 같아진다

 

$C = M^3$

 

공격자는 복잡한 소인수분해 없이 단순히 암호문 C의 실수 세제곱을 구하면 된다.

 

$M =  \sqrt[3]{C}$

---

[3] Håstad's Broadcast Attack

Low Public Component Attack의 확장판이라고 할 수 있다. 한 명에게 보내는 것은 안전할지 몰라도, 동일한 메시지를 여러 사람에게 Broadcast할 때 취약점이 발생한다.

 

 

시나리오

• 상황 : Alice가 같은 메세지 $M$을 $k$명의 수신자에게 보낸다.
• 설정:
  • 모든 수신자는 서로 다른 모듈러스 $N_1, N_2, \ldots, N_k$를 사용한다.
  • 하지만 모두 같은 작은 공개 지수 $e$를 사용한다.
• 공격 조건 : $k \geq e$

 

공격 원리

공격자는 다음과 같은 $e$개의 암호문을 수집한다. 여기서는 $e=3$이라고 가정한다.

1.  $C_1 \equiv M^3 \pmod{N_1}$
2.  $C_2 \equiv M^3 \pmod{N_2}$
3.  $C_3 \equiv M^3 \pmod{N_3}$

여기서 $N_1, N_2,  N_3는 서로 서로소이다.

 

CRT에 따르면, 이 연립 합동식을 만족하는 유일한 해 $C$가 0과 $N_1N_2N_3$사이 어딘가에 존재한다.

 

$C \equiv M^3 \pmod{N_1N_2N_3}$

• 각 $N_i$는 $M$보다 크다. (당연히 모듈러스가 메시지보다 커야 암호화가 되니까.)
• 그렇다면 $N_1N_2N_3$은 $M^3$보다 훨씬 크다. ($M < N_i \implies M^3 < N_1 N_2 N_3$)

결국 $C$는 $N_1N_2N_3$로 나눈 나머지가 아니라, 그냥 정수 $M^3$ 그 자체가 된다.

 

$C = M^3$

 

공격자는 CRT로 구한 $C$에 단순히 실수 세제곱근을 취해서 $M$을 복구할 수 있다.

 

$M = \sqrt{3}{C}$

---

[4] 개인키 유출

RSA 개인키의 일부 요소($p, q, \phi(n), d$) 중 하나만 유출되어도, 수학적 관계를 통해 나머지 모든 비밀 정보를 복구할 수 있다.

 

전제 : 공격자는 공개키 $(N, e)$를 알고 잇다.

 

1. $p$ (또는 $q$)가 유출된 경우

• 복구 방법
  1. $N= p \times q$이므로, $q = N / p$로 $q$를 구한다.
  2. $\phi(n) = (p-1)(q-1)$ 을 계산한다.
  3. Extended Euclidean Algorithm으로 $ed \equiv 1 \pmod{\phi(n)}$인 $d$를 계산한다.

 

2. $\phi(n)$이 유출된 경우

• 알고 있는 것 :
  1. $N = pq$
  2. $\phi(n) = (p-1)(q-1) = pq - (p+q) + 1 = N - (p+q) + 1$
• 복구 방법
  1. $p+q$를 구한다. $p+q = N - \phi(n) + 1$
  2. 합($p+q$)과 곱($pq=N$)을 알고 있으므로, $p$와 $q$는 $x^2 - (N - \phi(n) + 1)x + N = 0$의 두 근
  3. $p, q = \frac{(N - \phi(n) + 1) \pm \sqrt{(N - \phi(n) + 1)^2 - 4N}}{2}$

 

3. 개인키 $d$가 유출된 경우

• 방법A :
  • $r=de -1$이라고 가정. (r은 짝수.)
  • 적당한 홀수 $m$에 대해서 $r = 2^km$으로 나타낼 수 있다.
  • 적당한 $a$에 대해서 $b_0\equiv a^m \pmod{n}$이라고 가정.
  • $b_0$을 연속 제곱해서 $b_{u+1} \equiv b_u^2 \pmod{n}$을 1이 나올 때까지 구한다.
  • $ed - 1 = k\phi(n)$ 이며, $k\phi(n)$은 짝수입니다. $x^2 \equiv 1 \pmod N$ 이지만 $x \not\equiv \pm 1 \pmod N$ 인 비자명한 1의 제곱근(Non-trivial square root of unity) 을 찾으면, $\text{gcd}(x-1, N)$ 은 $N$의 인수($p$ 또는 $q$)가 된다.
• 방법B :
  • $e \times d = 1 + k\phi(n)$ => $k = \frac{ed - 1}{\phi(n)}$
  • 여기서 $N$이 매우 클 때, $\phi(n) \approx N$ 이라는 점을 이용한다. ($p, q$가 크면 $p+q$는 $N$에 비해 무시할 만큼 작으므로)
  • $k \approx \frac{ed}{N}$
  • $k$의 근사값을 구한 뒤, 반올림하여 정수 $k$를 확정하고, 이를 통해 $\phi(n)$을 역산한다.

---

안전한 RSA 구현

1. 소수 $p, q$ 생성 단계

- RSA의 근간이 되는 소수 $p,q$는 단순히 랜덤한 소수여서는 안된다.

• Strong Prime 사용
  • $p-1$과 $q-1$이 큰 소인수를 가져야한다.
  • $p+1$과 $q+1$도 큰 소인수를 가지면 좋다.
• $p$와 $q$의 값이 너무 비슷하면 안된다.
• Quadratic Residue 안전성
  • 공격자가 암호문이 $N$에 대해 이차 잉여인지 아닌지를 구별할 수 없도록 해야한다.
• Pseudo-prime 검증
  • 실제로는 소수가 아닌 합성수를 걸러내야한다.

 

2. $N, e, d$ 설정 단계

• 개인키 $d$의 크기 확보
  • $d$가 $N$에 비해 너무 작으면($d < \frac{1}{3}N^{\frac{1}{4}}$) 안된다.
• 공개키 $e$의 적절한 크기
  • 보통 $e = 65537 (2^{16}+1)$을 표준으로 사용한다.
• 다른 사용자와 동일한 모듈러스 $N$을 공유하면 안된다.

 

3. 운영 및 관리 단계

• 키 생성이 끝난 직후 $p, q, \phi(n)$ 등 중간 계산 값은 메모리에서 즉시 덮어쓰기(Wipe) 후 삭제해야한다.
• 키 생성 시 사용하는 난수 생성기(RNG)가 예측 불가능해야한다.
• 부채널 공격(Side-channel) 방어

 

여기서 소개한 공격 이외에도 다양한 공격을 할 수 있다.

이런 것들을 지키지 않는 취약점을 발견하면 RSA를 다양한 방법으로 공격할 수 있다는 말이다.