암호론 논문 리딩 #3: Twenty Years of Attacks on the RSA Cryptosystem

"Twenty Years of Attacks on the RSA Cryptosystem" - Dan Boneh

RSA에 대한 공격을 가장 자세하게 잘 다루는 review paper인 것 같다. 인용 횟수가 900번 근처다...

논문 리딩은 기본적으로 복습을 하면서 더 배우려고 하는 것이기 때문에, 내가 배운 내용도 조금씩 추가하면서 쓰겠다.

또한, Lattice를 제대로 알아야 (특히 LLL) 더욱 자세하게 글을 쓸 수 있을 것으로 보인다. 일단은 맛만 보는 걸로.

#1: Introduction

RSA는 카이사르 암호와 함께 가장 유명한 암호체계 중 하나일 것이다. 1977년 공개된 이 암호체계는 지금도 사용되고 있다. 

많이 사용되는 체계인만큼, 많은 암호학자들은 이 체계의 허점을 찾기 위해서 수많은 공격 방법들을 제시해왔다. 

공격 방법을 탐구하는 과정을 통해서, 암호학자들은 RSA를 안전하게 구현하고 활용하는 방법을 더욱 알아가게 되었다.

논문의 목적은 이러한 공격들을 돌아보면서, 공격을 위한 수학적 도구에는 어떤 것이 있으며, 이를 막는 방법을 알아보는 것이다.

먼저 Textbook RSA를 살펴보자. $p, q$를 크기가 비슷한 큰 소수라 하고, $N=pq$라 하자. 두 자연수 $e, d$는 $ed \equiv 1 \pmod {\phi(N)}$을 만족하는 자연수다. 여기서 $\phi(N) = (p-1)(q-1)$이다. 이때 $N$을 RSA modulus, $e$를 encryption exponent, $d$를 decryption exponent라고 부른다. $\langle N, e \rangle$은 모두 공개되어 있고 (공개키), 메세지를 암호화하는데 사용할 수 있다. 한편, $\langle N, d \rangle$은 비밀이며 (비밀키), 암호화된 메세지를 받는 사람만이 알고 있다. 메세지를 받는 사람은 비밀키를 이용하여 실제 메세지를 확인할 수 있다. 여기서 메세지란, $M \in \mathbb{Z}_N^{*}$을 말한다. $M$을 암호화하려면, $C \equiv M^e \pmod{N}$을 계산하면 된다.

이를 복호화하려면, $M \equiv C^d \pmod{N}$을 계산하면 된다. 여기서 $ed \equiv 1 \pmod{ \phi(N)}$과 오일러의 정리를 이용한다.

RSA 함수를 $x \rightarrow x^e \pmod{N}$으로 정의하자. $d$를 알면, 이 함수의 역을 쉽게 구할 수 있다.

슬슬 One-Way Function의 느낌이 나온다. 이러한 상황에서, 암호학자들은 $d$를 trapdoor라고 부른다.

trapdoor가 있는 one-way function은 전자서명 등에서 활용될 수 있다. 여기서 RSA의 유용함을 알 수 있다.

메세지 $M$을 내가 보냈다는 것을 인증하려면, 비밀키 $d$를 이용하여 $M^d \pmod{N}$을 사람들에게 주면 된다. 

그렇다면, 다른 사람들은 공개키 $e$를 이용하여 $M \equiv (M^d)^e \pmod{N}$, 즉 실제 메세지를 얻는다.

여기서는 $d$에 대한 정보가 없을 때, RSA 함수의 역함수를 계산하는 난이도에 대해서 다루도록 한다.

즉, $N, e, C$가 주어진 경우, $C$의 discrete $e$-th root modulo $N$을 구하는 난이도에 대해 다루는 것이다.

당연히 전수조사의 방법이 있으나, 이는 역시 당연하게도 매우 비효율적이다. 불가능하다고 보는 게 맞겠다.

우리가 관심이 있는 대상은 당연히 실제로 사용될 수 있는 공격들, 특히 다항식 시간을 필요로 하는 공격들이다.

실제 RSA를 이용한 암호체계는 단순한 RSA 함수 응용의 범주를 넘어간다. 안전한 암호가 되려면 빡빡한 기준을 통과해야 한다.

단순하게 RSA 함수를 이용하여 암호화를 하면, 메세지 $M$에 대한 non-trivial information을 손쉽게 얻을 수 있다.

대표적으로, $M$의 modulo $N$에 대한 Jacobi Symbol의 값을 매우 간단하게 얻을 수 있다.

또한, 단순하게 RSA 함수를 이용하여 암호화를 하면 adaptive chosen ciphertext attack에 아주 간단하게 당한다.

복호화를 하고 싶은 $C \equiv M^e \pmod{N}$이 있다고 하자. $2^eC$를 복호화하는 쿼리를 날려보자.

그러면 얻는 답은 $(2^eC)^d \equiv 2C^d \equiv 2M \pmod {N}$이다. 여기서 $M$을 복원하는 것은 쉬운 일이다.

그러니 실제로 RSA를 이용해서 암호화를 하려면, "랜덤함"으로 적당히 간을 쳐서 암호화를 할 필요가 있다. 여기서는 다루지 않는다.

RSA를 사용하기 위해서는, 먼저 큰 소수 $p, q$를 잡는다. 랜덤하게 큰 수를 잡고 적당한 소수 판정법을 쓰면 된다.

그 후 $N = pq$를 얻은 뒤, 적당한 $e$를 잡고 modulo inverse를 계산하는 알고리즘으로 $d$를 계산한다.

물론, 소수는 충분히 많기 때문에, 이러한 방법으로도 RSA key pair를 효율적으로 생성할 수 있다. 

RSA를 공격하는 가장 생각하기 쉬운 방법은 사실 그냥 $d$를 찾는 것이다. $d$를 어떻게 찾을 수 있을까?

가장 쉬운 접근은 역시 $\phi(N)$을 찾는 것이다. 그런데 이는 $N$을 소인수분해하는 것과 동치임을 쉽게 파악할 수 있다.

소인수분해가 얼마나 어려운 문제인지는 꽤 잘 알려져 있다. GNFS가 현재까지는 가장 빠르지만, 여전히 느리다.  

하지만, 쉽게 소인수분해가 가능한 수 역시 존재한다. 예를 들어보면, Pollard의 $p-1$ 알고리즘이 있다.

만약 $p-1$이 작은 소수들의 곱으로 표현이 된다면, 이 알고리즘을 통해서 $N=pq$를 인수분해 할 수 있다.

비슷한 접근으로, Williams의 $p+1$ 알고리즘도 존재한다. 이런 알고리즘으로 인수분해가 가능한 $N$은 사용하면 안된다. 

어쨌든, 인수분해가 가능하다면 RSA는 쉽게 깰 수 있다. 반대는 어떨까? 

즉, RSA를 효율적으로 깰 수 있으면 인수분해 역시 효율적으로 할 수 있을까? 이는 open problem이다.

만약 "가능하다"가 답이라면, chosen ciphertext attack으로 RSA를 깰 수 있다고 한다.

한편, $N$의 인수분해를 알면 우리는 $d$를 쉽게 계산할 수 있다. 반대는 어떨까?

즉, $d$를 안다면 $N$의 인수분해를 쉽게 계산할 수 있을까? 이는 "가능하다"가 답이다. 증명을 보자.

Theorem. RSA의 기본 조건을 만족하는 $e, d, N$을 아는 경우 $N$을 소인수분해 할 수 있다.

현재 우리가 아는 것은 $N, e, d$이고, 목표는 $N$의 인수분해이다. 

이제 $k = ed-1$을 계산하면, 이 값은 $\phi(N)$의 배수가 된다. 특히, $\phi(N)$이 짝수이므로 $k$도 짝수다.

이제 $k = 2^t r$이라 쓰자. (단, $r$은 홀수, $t \ge 1$) 이제 다음을 반복한다. 

1. $N$의 배수가 아닌 $g$를 랜덤하게 하나 잡자. 만약 $\text{gcd}(g, N) \neq 1$이면 소인수분해 끝.

2. $0 \le i \le t$에 대하여 $s_i = g^{k/2^i} \pmod{N}$라 하자. $s_{i-1} \equiv s^2_i \equiv 1 \pmod {N}$이고, $s_i \not\equiv \pm 1 \pmod{N}$인 $i$를 찾자.

3. 이때, $\text{gcd}(s_i - 1, N)$은 $N$의 non-trivial한 factor가 된다. 만약 $i$를 찾는데 실패했다면 다시 처음부터 반복.

우선 $t$의 값은 크지 않으며, 거듭제곱과 modulo 연산 역시 빠른 시간에 할 수 있다. GCD 역시 빠른 시간에 할 수 있다.

그러므로 위 알고리즘에서 한 iteration을 하는데 걸리는 시간은 다항식 시간임을 알 수 있다. 

그러니, 우리가 검증해야 하는 것은 위 알고리즘이 성공할 시 정당한 답을 낸다는 것과, 위 알고리즘이 무시하지 못할 확률로 성공한다는 것이다.

먼저 성공할 시 정당한 답을 낸다는 것을 보이자. 만약 $x^2 \equiv 1 \pmod {N}$인데 $x \not\equiv \pm 1 \pmod{N}$이라 하자.

이는 중국인의 나머지 정리에서, $x \equiv 1 \pmod {p}$이고 $x \equiv -1 \pmod{q}$이거나, $x \equiv -1 \pmod{p}$이고 $x \equiv 1 \pmod {q}$라는 것이다. 

당연히 $p=2$나 $q=2$와 같은 경우를 무시해주면, 이것은 결국 $\text{gcd}(x-1, N)$이 $p$ 또는 $q$라는 뜻이다. 

즉, 2번에서 적당한 $i$를 찾았다면, $\text{gcd}(s_i - 1, N)$은 $N$의 non-trivial factor $p$ 또는 $q$가 된다. ok.

이제 위 알고리즘이 무시하지 못할 확률로 성공함을 설명하자. 50% 정도 이상의 확률로 성공함을 보일 수 있다.

$p-1 = 2^A u$, $q-1 = 2^B v$라 쓰고, (단, $u, v$는 홀수) 일반성을 잃지 않고 $A \ge B$라고 가정하자. 

또한, $k = ed-1$은 $\phi(N) = 2^{A+B}uv$의 배수이므로, $2^{A+B+C} uvw$라고 쓰자. (단, $w$는 홀수) 두 가지 케이스를 나누자.

Note: 이 방식으로 케이스를 분류하는 것은 Miller-Rabin Primality Test를 소개한 논문에서도 사용되는 방식이다. 근본 넘친다.

Case 1. $A > B$가 성립한다.

만약 $g$가 $p$에 대한 비이차잉여라면, 성공함을 보인다.

$g^{2^{A-1}u} \equiv -1 \pmod {p}$이므로, $g^{2^{A-1}uvw} \equiv -1 \pmod{p}$이다. 

또한, $g^{2^Bv} \equiv 1 \pmod{q}$이므로, $g^{2^{A-1}uvw} \equiv 1 \pmod{q}$이다. 

여기서 우리는 $g^{2^A uvw} \equiv 1 \pmod {N}$이고, $g^{2^{A-1}uvw}$는 우리가 원하는 형태를 갖춤을 알 수 있다.

$k = 2^{A+B+C} uvw$이니, 위 알고리즘을 사용하면 우리가 원하는 $g^{2^{A-1}uvw}$를 마주치고 소인수분해에 성공한다.

Case 2. $A = B = K$가 성립한다.

만약 $g$의 $N$에 대한 Jacobi Symbol의 값이 $-1$이라면, 성공함을 보인다.

잠시 $g$가 $p$에 대한 비이차잉여이고, $q$에 대한 이차잉여라고 가정하자. 반대인 경우에도 마찬가지이다.

$g^{2^{K-1}u} \equiv -1 \pmod{p}$이고 $g^{2^{K-1}v} \equiv 1 \pmod{q}$이다. 

그러니 $g^{2^{K-1}uvw} \equiv -1 \pmod{p}$이고 $g^{2^{K-1}uvw} \equiv 1 \pmod {q}$가 성립한다. 

여기서 우리는 $g^{2^K uvw} \equiv 1 \pmod {N}$이고, $g^{2^{K-1}uvw}$는 우리가 원하는 형태를 갖춤을 알 수 있다.

$k = 2^{2K+C} uvw$이니, 위 알고리즘을 사용하면 우리가 원하는 $g^{2^{K-1}uvw}$를 마주치고 소인수분해에 성공한다.

두 경우 모두에서, 성공 확률이 50% 이상임을 쉽게 파악할 수 있다. 그러니 이를 충분히 반복하면 인수분해에 성공한다.

#2: Elementary Attacks

첫 번째로 살펴볼 것은 메세지 자체가 크기가 작은 경우이다. 만약 $M$이 크기가 작고, 크기가 비슷한 두 자연수의 곱으로 표현될 수 있다고 하자. 이 경우, 간단한 meet-in-the-middle attack을 통해서 메세지를 복원할 수 있다. Key의 크기가 커도 메세지의 크기가 작으면 소용없다는 점을 간과한 경우 발생하는 문제다. 

이와 같이 RSA를 잘못 활용한 경우 이를 공격하는 방법을 여기서 더 소개한다.

두 번째로 살펴볼 것은, 모든 사람들에게 공통된 $N$을 사용하게 하는 경우 발생하는 문제점이다. 

각 사람들마다 서로 같은 $N$을 주는 대신, 각 사람들에게 $e_i, d_i$를 부여하면 어떻게 될까? (물론, $p, q$는 알려주지 않는다)

다른 사람의 공개키 $e_i$를 봐서 $d_i$를 계산할 수 없으므로 ($p, q$는 모르니까) 이 방법은 잘 먹힐 것처럼 생겼다.

하지만 앞에서 보았듯이, $e_i, d_i, N$을 알면 효율적으로 $N$을 소인수분해 할 수 있다. 그러니 이렇게 하면 나라 망한다.

즉, 모든 사람들이 서로 다른 $N$을 갖도록 해야 안전한 암호체계를 만들 수 있다.

세 번째로 살펴볼 것은, "blinding"이란 것이다. Eve가 Alice에게 메세지 $M \in \mathbb{Z}_N^{*}$에 대한 전자서명을 원한다고 하자.

즉, $M^d \pmod{N}$을 원하는 것이다. 물론 호구가 아닌 이상 Alice가 Eve의 말을 듣고 전자서명을 하지는 않는다.

하지만, Eve가 적당한 $r \in \mathbb{Z}_N^{*}$를 랜덤하게 잡고, $M' \equiv r^eM \pmod{N}$을 계산했다고 하자.

이제 Eve는 Alice에게 $M'$에 대한 전자서명을 부탁한다. Alice는 $r$의 존재도 모르고 그러니 $M$도 모른다.

이제 Alice는 큰 문제가 없게 생긴 $M'$에 대한 전자서명을 줄 수도 있다. 이때, 그 전자서명의 값은 $rM^d \pmod{N}$이 된다.

결국 Eve는 $r$의 modulo inverse를 취해줘서 $M^d \pmod{N}$의 값을 얻게 된다. 전자서명이 뚫린 것이다.

물론, 실제 RSA를 이용한 전자서명이 이렇게 간단하지는 않으므로, 걱정은 하지 않아도 된다. 

또한, 논문에 의하면 blinding이 가능하다는 점을 이용하여 "anonymous digital cash"를 구현할 수 있다고 한다. 

#3: Low Private Exponent

애초에 작은 $d$ 값을 왜 사용하고 싶어하는 걸까? 이유는 시간에 있다. $d$가 작을수록 decryption에 필요한 시간이 줄어들기 때문이다. 

적은 계산 시간은 솔깃하지만, 작은 $d$ 값은 보안성 입장에서 볼 때 매우 위험하다. 다음 공격을 소개한다. 

Theorem. (Wiener's Attack) $N = pq$고, $q < p < 2q$라 하자. $d < \frac{1}{3} N^{1/4}$라 하자.

$ed \equiv 1 \pmod{\phi(N)}$인 $N$과 $e < \phi(N)$이 주어졌을 때, $d$를 효율적으로 복원할 수 있다.

앞선 논문 리딩에서도 사용된 연분수를 이용한 rational approximation이 다시 등장한다.

$ed \equiv 1 \pmod{\phi(N)}$이므로, 적당한 $k$가 있어 $ed - k \phi(N) = 1$이다. 그러니, 이를 다시 쓰면 $\displaystyle \left| \frac{e}{\phi(N)} - \frac{k}{d} \right| = \frac{1}{d\phi(N)}$이다.

즉, $\displaystyle \frac{k}{d}$는 $\displaystyle \frac{e}{\phi(N)}$의 근사가 된다. 그런데 $\phi(N)$은 몰라도, $N$은 이미 알고 있다.

또한, $\phi(N) = N -p - q + 1$이고 $p+q-1 < 3 \sqrt{N}$이므로, $|N - \phi(N)| < 3\sqrt{N}$이다.

즉, $\phi(N)$ 대신 $N$을 사용해도 꽤 강력한 근사가 나올 것임을 추측할 수 있다. 

실제로, $\displaystyle \left| \frac{e}{N} - \frac{k}{d} \right| = \left| \frac{ed-k\phi(N) - kN + k \phi(N)}{Nd} \right| = \left| \frac{1-k(N-\phi(N))}{Nd} \right| \le \frac{3k\sqrt{N}}{Nd} = \frac{3k}{d\sqrt{N}}$을 얻는다.

그런데 $k \phi(N) = ed-1 < ed$이고 $e < \phi(N)$이므로 $k < d < \frac{1}{3} N^{1/4}$를 얻는다.

그러므로, $\displaystyle \left| \frac{e}{N} - \frac{k}{d} \right| \le \frac{3k}{d\sqrt{N}} < \frac{1}{dN^{1/4}} < \frac{1}{2d^2}$을 얻는다. 원하는 식이 나왔다. 연분수를 강제하는 형태의 부등식이다.

잘 알려진 연분수 및 근사에 대한 정리에서, $\displaystyle \frac{k}{d}$는 $\displaystyle \frac{e}{N}$의 연분수 표현에서의 근사분수 중 하나다.

또한, 근사분수의 분모의 크기는 지수적으로 증가하며, $\text{gcd}(k, d) =1$이므로 기약분수 여부는 걱정할 필요가 없다.

즉, 실제로 고려해야 할 근사분수의 개수, 즉 $d$의 후보는 다항식 개수만큼 있다. 이를 전부 시도해보면 된다.

후보를 하나 고정하면, $N, e, d, k$를 전부 알 수 있으므로 $\phi(N)$을 계산하는 시도를 할 수 있다.

이제 $\phi(N)$의 값에 대한 후보가 있을 때, 이 값이 $\phi(N)$이 맞는지 판별하는 것은 어렵지 않으므로, (이차방정식 이용) 증명 끝.

이 attack을 회피하면서 빠르게 decryption을 할 수 있는 방법은 없을까? Wiener는 이런 방법을 2개 제시했다.

이 방법들은 안전성이 증명된 것은 아니나, 최소한 Wiener's Attack은 회피할 수 있다. 

첫 번째 방법은 $e$를 키우는 것이다. 위 증명을 살펴보면, $e < \phi(N)$을 사용하였다.

이를 대신하여, 큰 자연수 $t$를 잡고 $e' = e + t \cdot \phi(N)$을 이용하자. 당연히 $d$의 값에는 변화는 없다.

위 증명과 같은 방식으로 계산을 하면, $e' > N^{1.5}$일 경우 $d$가 아무리 작아도 이 방법으로 공격을 할 수는 없음을 확인할 수 있다.

물론, encryption exponent를 키우면 encryption에 소모되는 시간이 매우 커진다. 일종의 trade-off라고 봐야겠다.

두 번째 방법은 CRT를 이용하는 것이다. 복호화 과정의 결과값을 $\pmod{p}$와 $\pmod{q}$에 대해 따로 계산하자는 것이다.

만약 $d_p \equiv d \pmod{p-1}$과 $d_q \equiv d \pmod{q-1}$이 둘 다 작다면, 이는 효율적으로 계산할 수 있다.

물론, 실제 결과값을 얻고 싶다면 CRT를 이용해주면 된다. 핵심 아이디어는, $d_p, d_q$가 작더라도 $d$가 클 수 있다는 것이다. 그런데 다음이 성립한다.

Theorem. 위 방법을 사용할 때, adversary는 $\mathcal{O}(\operatorname{min}(\sqrt{d_p}, \sqrt{d_q}))$ 시간에 $N$을 소인수분해 할 수 있다.

문헌을 뒤져보니, 결과적으로 증명 도중에 가정을 꽤 많이 추가해야 하는 것 같다.

별로 중요하지 않아보이나 매우 중요한 사실을 하나 짚고 넘어가자. $d_p \neq d_q$가 성립한다. 

이유는 간단한데, $d_p = d_q$가 성립하면 $\lambda(N) = \text{lcm}(p-1, q-1)$이라 할 때 $d \pmod{\lambda(N)} = d_p = d_q$가 작게 된다.

Wiener's Attack을 간단하게 확장하면, $\phi(N)$ 대신 $\lambda(N)$을 이용하더라도 비슷하게 공격을 할 수 있다. 

물론, $d_p = d_q$가 크면 애초에 이 최적화 방법을 사용할 이유가 없다. 이 정도면 $d_p \neq d_q$를 가정할 근거가 된다.

또한, 아래에서는 $d_p$와 $d_q$가 "정말 다르다"라는 가정을 사용하게 된다. 이 역시 인정하고 넘어가도록 하자.

핵심 아이디어를 소개하기 위해서, $\mathcal{O}(\operatorname{min}(d_p, d_q))$ 시간에 $N$을 소인수분해하는 방법을 제시한다.

0. $\operatorname{min}(d_p, d_q) < B$가 성립한다고 가정하자. adversary는 공격을 시도하기 위해 $B$의 값을 적당히 잡을 수 있다.

1. 랜덤한 자연수 $m$을 하나 잡는다. $m$이 $N$의 배수가 아니도록 한다. $\text{gcd}(m, N) \neq 1$이면 끝.

2. 각 $1 \le i \le B$에 대하여, $\text{gcd}(m^{ei}-m, N)$을 계산하고, non-trivial factor가 나오는지 확인한다.

3. 성공하면 끝이고, 아니면 다시 1번으로 돌아가서 이 과정을 반복한다.  

이 알고리즘이 효율적으로 작동함은 자명하다. 성공 확률이 무시하지 못할 정도임을 증명하면 충분하다.

일반성을 잃지 않고, $d_p < B$가 성립한다고 가정하자. 또한, 운이 좋게 $m$이 $q$의 원시근이 되었다고 가정하자.

그러면 $m^{ed_p} \equiv m \pmod{p}$이고, $m^{ed_p} \not\equiv m \pmod{q}$가 성립하게 된다. 여기서 $ed_p \not\equiv ed_q \equiv 1 \pmod{q-1}$을 이용하였다. 

그러니 $\text{gcd}(m^{ed_p}-m, N)$은 우리가 원하는 non-trivial factor가 되고, $d_p < B$니 이는 알고리즘 중간에 계산이 된다.

또한, 원시근의 개수는 충분히 많다는 것이 잘 알려져 있으므로, $m$이 $q$의 원시근임을 충분히 기대할 수 있다.

물론, 실제로는 $m$이 $q$의 원시근인 조건이 필요조건이 아니므로, 성공할 확률이 더욱 높다고 볼 수 있다.

이제 이를 최적화해보자. Baby-Step-Giant-Step의 변형이 필요해보인다. 그림을 그려보면, 다음과 같다.

0. $\operatorname{min}(d_p, d_q) < B$가 성립한다고 가정하자. $M = \lfloor \sqrt{B} \rfloor$라고 하자. 

1. 랜덤한 자연수 $m$을 하나 잡는다. $m$이 $N$의 배수가 아니도록 한다. $\text{gcd}(m, N) \neq 1$이면 끝.

2. 각 $0 \le i < M$, $0 \le j \le M+1$에 대하여, $\text{gcd}(m^{e(i+jM)}-m, N)$을 계산하고, non-trivial factor가 나오는지 확인한다.

3. 성공하면 끝이고, 아니면 다시 1번으로 돌아가서 이 과정을 반복한다.

물론, 이 알고리즘은 정당하지만 앞서 살펴본 알고리즘과 시간복잡도가 동일하다. 더욱 최적화가 필요하다.

아이디어는, $i$를 고정한 뒤 각 $j$에 대한 확인을 빠르게 하자는 것이다. 이게 가능할까? 가능하다.

0. $\operatorname{min}(d_p, d_q) < B$가 성립한다고 가정하자. $M = \lfloor \sqrt{B} \rfloor$라고 하자. 

1. 랜덤한 자연수 $m$을 하나 잡는다. $m$이 $N$의 배수가 아니도록 한다. $\text{gcd}(m, N) \neq 1$이면 끝.

2. $G(x) = \prod_{j=0}^{M+1} \left( m^{eMj}x - m \right) \pmod{N}$이라 하자. 이는 다항식이다.

3. $G(m^0), G(m^e), \cdots , G(m^{e(M-1)})$을 전부 계산한 다음, 각 값과 $N$ 사이의 GCD를 계산한다. 

4. non-trivial factor를 얻으면 끝이고, 아니면 다시 1번으로 돌아가서 이 과정을 반복한다.

분석을 위해서, 다시 $d_p < B$를 가정하자. 또한, $d_p = d_1 + M d_2$, $0 \le d_1 < M$, $0 \le d_2 \le M+1$이라 하자. $m$이 $q$의 원시근이라고 가정하자.

자명하게, $G(m^{ed_1})$은 $p$의 배수가 된다. 게다가, $d_q$가 $d_1, d_1+M, \cdots , d_1+M(M+1)$과 전부 다르다면, $G(m^{ed_1})$는 $q$의 배수가 되지 않는다. 

그러니 $G(m^{ed_1})$은 $N$과 non-trivial factor를 갖는다. 그러니 위 가정이 전부 성립하면, 알고리즘은 성공한다.

$m$이 $q$의 원시근이 된다는 가정은 앞서 언급했듯이, 원시근의 개수가 많다는 사실에서 기대할만 하다. 

$d_q$가 $d_1, d_1+M, \cdots, d_1+M(M+1)$과 다르다는 가정은 앞서 말한 $d_p$와 $d_q$가 "많이 다르다"는 가정이다.

이는 조금 위험해보이는 가정이지만, 이 정리의 문맥에서는 (즉, CRT를 사용한 RSA의 최적화) 성립하는 가정이라고 한다. 

개인적인 (짧은) 생각으로는 $M$의 값을 적당히 바꿔가면서 알고리즘을 돌려주면 이 가정은 필요가 없을 것 같다. 

그러니 이 알고리즘은 성공할 가능성이 무시하지 못할 정도이다. 그런데 궁금증이 하나 생긴다.

다항식 $G(x)$는 어떻게 효율적으로 계산할 수 있을까? $G(x)$의 값을 $x = m^0 , m^e, \cdots m^{e(M-1)}$에서 어떻게 빠르게 계산할 수 있을까?

이건 PS에서도 보이는 내용이다. FFT + Multipoint Evaluation을 하면 된다. 이는 굳이 여기서 다룰 필요가 없는 내용으로 보인다.

이제 모든 과정을 정리하면, 시간복잡도가 정말 $\mathcal{O}(\operatorname{min}(\sqrt{d_p}, \sqrt{d_q}))$임을 알 수 있다. 증명 끝.

그러니 결론은 위 최적화를 사용하더라도 적당히 사용해야 한다는 것이다. $d_p , d_q$ 역시 보안을 위해서는 잘 잡아야 한다는 것이다.

Wiener's Attack의 $d$에 대한 bound는 이후 더욱 개선되었다. $d < N^{0.292}$면 $N, e$를 통해 $d$를 복원할 수 있다는 것을 Boneh와 Durfee가 증명하였다. 

또한, $d < N^{0.5}$라면 $N, e$를 통해 $d$를 복원할 수 있다는 것이 강력한 추측이다. 이는 open problem이다.

#4: Low Public Exponent

이제는 $e$가 작은 경우를 다룬다. 작은 $e$가 매력적인 이유는 encryption에 드는 시간이 줄어들기 때문이다.

하지만 앞서 $d$에 대해서 살펴본 내용들과 마찬가지로, 작은 $e$를 사용하면 다양한 공격의 표적이 될 수 있다.

$e$로 사용할 수 있는 가장 작은 값은 $3$이지만, 아래에 제시된 공격들을 막기 위해 $e=2^{16}+1$이 자주 사용된다.

아래에서 다룰 공격들의 중심에는 Coppersmith의 정리가 있다. 이를 완전히 이해하려면 Lattice에 대한 이해가 필수적이다.

아직은 내가 Lattice를 배우지 않았으니, 지금은 단순히 statement를 적고 넘어간다. 나중에 더 깊은 내용을 추가하는 것이 목표다.

Theorem. (Coppersmith) $N$은 자연수고, $f \in \mathbb{Z}[x]$는 최고차항의 계수가 $1$인 $d$차 다항식이다. $\epsilon \ge 0$을 잡고, $X = N^{1/d - \epsilon}$이라 하자. $N, f$가 주어졌을 때, $|x_0| < X$와 $f(x_0) \equiv 0 \pmod{N}$을 만족하는 $x_0$를 모두 다항식 시간에 찾을 수 있다. 

이 정리의 첫 번째 활용 사례로, Hastad's Broadcast Attack을 알아보자. 

만약 Alice가 메세지 $M$을 여러 사람들에게 전송하고 싶다고 하자. 각 사람들은 $N_i , e_i$를 공개키로 가지고 있다.

그러면 Alice는 $M^{e_i} \pmod{N_i}$를 각각 계산한 다음 이를 각 사람들에게 전송한다. Eve가 이 값들을 전부 확보했다고 가정하자.

가장 간단한 예시로, $e_i$의 값들이 전부 $3$인 경우를 생각해보자. 그러면 값을 $3$개만 확보해도 Eve는 $M$을 복원할 수 있다.

Eve가 $C_1 \equiv M^3 \pmod{N_1}$, $C_2 \equiv M^3 \pmod{N_2}$, $C_3 \equiv M^3 \pmod{N_3}$을 안다고 가정하자. 

그러면 $N_1 , N_2, N_3$가 전부 서로소라고 가정하자. (아니라면, 소인수분해가 간단하게 될 것이다)

이제 중국인의 나머지 정리에서, $M^3 \pmod{N_1N_2N_3}$를 얻을 수 있다. 그런데 $M^3 < N_1N_2N_3$이니, $M$을 얻는다.

이 공격에 대한 간단한 방어를 생각할 수 있다. 각 사람들에게 메세지의 아주 일부를 바꿔서 보내는 것이다.

즉, $i$번째 사람에게 $M^{e_i} \pmod{N_i}$ 대신 $(M+i \cdot 2^m)^{e_i} \pmod{N_i}$를 (물론 $i$와 함께) 보내는 것이다.

여기서 $m$은 $M$의 비트 개수이다. 이 방법은 매우 간단하지만, 위 공격을 막을 수 있을 것으로 보인다.

더욱 일반적으로, 메세지를 전달하고 싶은 사람 $P_1, P_2, \cdots, P_k$가 있을 때, $i$번째 사람에게 $M$을 직접 암호화하는 대신, $f_i \in \mathbb{Z}_{N_i} [x]$를 하나 잡은다음 $f_i(M)$을 암호화하여 (물론, $f_i$와 함께) 보내는 방법을 생각할 수 있다. 이제, Eve가 얻을 수 있는 정보는 다항식 $f_i$와 $e_i, N_i$, $C_i \equiv f_i(M)^{e_i} \pmod{N_i}$이다.  

이 상태에서 Eve가 $M$을 도출하는 것은 매우 어려워보인다. 하지만 충분히 많은 정보를 확보하면 가능하다. Coppersmith's Theorem의 위력을 확인해보자.

Theorem. (Hastad's Attack) $N_1, N_2, \cdots , N_k$는 서로소인 자연수이다. $N_{min} = \operatorname{min}(N_1, N_2, \cdots, N_k)$라 하자. 각 $1 \le i \le k$에 대하여, $g_i \in \mathbb{Z}_{N_i}[x]$는 차수가 $d$ 이하인 다항식이라 하자. $g_i(M) \equiv 0 \pmod{N_i}$이 각 $1 \le i \le k$에 대해서 성립하는 $M < N_{min}$이 유일하고, $k>d$가 성립한다고 가정하자. 이때, $1 \le i \le k$에 대하여 $N_i , g_i$를 전부 알 경우 $M$을 다항식 시간에 찾을 수 있다.

먼저, 각 $g_i$가 전부 최고차항의 계수가 $1$임을 가정할 수 있다. $g_i$의 최고차항의 계수가 $N_i$와 서로소가 아니라면, $N_i$를 소인수분해 할 수 있다. 

이는 RSA를 다루는 우리의 문맥에서 맞지 않다. 이제 $g_i$의 최고차항의 계수의 modulo inverse를 구해서, $g_i$의 최고차항의 계수를 $1$로 바꿀 수 있다.

또한, $M$이 $N_i$들과 서로소가 아닌 경우 역시 RSA를 다루는 우리의 문맥에 맞지 않다. 

그러니, $M$이 $N_i$들과 서로소라고 가정하자. 이러면, $g_i$들에 $x$의 거듭제곱을 적당히 곱해서 모두 차수가 $d$이도록 할 수 있다.

$T_i \equiv \delta_{i, j} \pmod{N_j}$를 만족하는 $T_i$를 CRT로 찾고, $g(x) \equiv \sum_{i=1}^k T_i g_i(x)$를 잡자. $\overline{N} = N_1N_2 \cdots N_k$라 하고, $g(x)$를 $\mathbb{Z}_{\overline{N}}[x]$의 원소로 보자.

$g(x)$의 최고차항의 계수를 각 $i$에 대하여 $\pmod{N_i}$로 보면 $1$임을 확인할 수 있고, 그러니 $g(x)$는 최고차항의 계수가 $1$이다.

또한, $g(x)$의 차수는 $d$이다. 우리가 원하는 $M$은 $g$의 근이며, $M < N_{min} \le \overline{N}^{1/k} < \overline{N}^{1/d}$다.

그러니, $g(x)$와 $\overline{N}$에 대한 Coppersmith's Theorem을 이용하면 $M$을 찾을 수 있다.

그러니 Eve는 $g_i = f_i^{e_i} - C_i$를 잡은 다음, Hastad's Attack을 활용하여 $M$을 복원할 수 있다.

위 정리의 statement를 다시 읽어보면, 이 공격은 $e_i$의 값들이 작을 때 더욱 강력함도 알 수 있다.

실제로 Broadcast Attack에 대한 방어를 하고 싶다면, "랜덤함"으로 적당히 간을 쳐주면 된다고 한다. 

두 번째 공격은 Franklin-Reiter Related Message Attack이다. $N, e$가 Alice의 공개키라고 하자. 

이제 Bob이 $M_1, M_2 \in \mathbb{Z}_{N}^{*}$를 Alice에게 보내려고 한다.

그런데, 알려진 다항식 $f \in \mathbb{Z}_N [x]$가 있어 $M_1 \equiv f(M_2) \pmod{N}$이 성립한다고 하자.

Bob이 단순하게 $C_1 \equiv M_1^e \pmod{N}$과 $C_2 \equiv M_2^e \pmod{N}$을 계산했다고 하자.

이제, $C_1, C_2$가 주어졌을 때 Eve가 $M_1, M_2$를 복원할 수 있음을 보일 수 있다.

이 공격은 일반적으로 $\mathcal{O}(e^2)$ 정도의 시간을 필요로 한다고 한다. 

일반적인 경우의 증명은 빡센 대수학을 필요로 한다고 하므로, 여기서는 $e=3$이고 $f$가 일차식인 경우를 보인다.

Lemma. $e=3$이라 하고, $N, e$가 RSA를 위한 공개키라고 하자. $M_1 \neq M_2 \in \mathbb{Z}_N^{*}$가 적당한 $f = ax+b \in \mathbb{Z}_N [x]$에 대하여 $M_1 \equiv f(M_2) \pmod{N}$을 만족한다고 하자. 단, $b \neq 0$이다. 이때, $N, e, C_1, C_2, f$를 알면 $M_1, M_2$를 $\mathcal{O}(\log^2 N)$ 시간에 구할 수 있다. 

아주 특수한 경우를 다루는 만큼, 증명 역시 크게 어렵지 않다. 먼저 $e$와 관련이 없는 큰 그림을 그려보자.

$M_1 \equiv f(M_2) \pmod{N}$을 알고 있으므로, $M_2$는 $g_1(x) = f(x)^e - C_1 \in \mathbb{Z}_N [x]$의 근이다.

또한, $M_2$는 $g_2(x) = x^e - C_2 \in \mathbb{Z}_N [x]$의 근이기도 하다. 즉, $(x-M_2)$는 $g_1(x), g_2(x)$의 공통 약수다.

그러므로, 유클리드 호제법을 이용하여 $g_1(x), g_2(x)$의 최대공약수를 구한 다음, 그 결과가 일차식이라면 $M_2$를 얻을 수 있다.

Note: 조금 생각을 해보면 유클리드 호제법을 하다가 "문제"가 생기면 $N$의 소인수분해를 얻을 수 있다. 이 점 참고.

특히, $e=3$인 경우에는, 최대공약수가 무조건 일차식이 된다. $g_2(x) = x^3 - C_2$를 생각해보자. 

$\text{gcd}(3, \phi(N))=1$이므로, $N=pq$라 할 때 $p, q$는 전부 $2 \pmod{3}$ 형태의 소수이다. 이 경우, $x \rightarrow x^3$은 전단사함수가 된다.

그러므로, $g_2(x) = x^3 - C_2$의 근은 유일하게 존재한다. 즉, $g_2$는 일차식 하나와 irreducible 이차식 하나로 분해된다.

여기서 일차식은 $g_1(x)$와 무조건 공유가 되어야 한다. 공통근이 존재해야 하기 때문이다.

또한, $g_1$과 $g_2$는 서로 나눌 수 없으므로, $g_1$과 $g_2$의 최대공약수는 일차식이 될 수 밖에 없다. 증명 끝.

$e>3$인 경우에는, 최대공약수가 거의 항상 일차식이 되지만, 아닌 경우도 존재한다. 이 경우, 공격은 실패한다.

위 공격을 더욱 강화한 것이 Coppersmith's Short Pad Attack이다. 메세지 $M$에 "랜덤함"으로 간을 해서 암호화를 해야 안전하다고 이미 언급했다.

"랜덤함"으로 간을 하는 가장 간단한 방법은, $M$의 끝에 몇 개의 random bit를 추가하는 것이다. 

하지만 이렇게 간을 대충하면 위험하고, 이를 보여주는 것이 Coppersmith's Short Pad Attack이다.

시나리오는 대강 이런 느낌이다. Alice가 Bob에게 메시지 $M$을 전달하려고 한다. 

이때 Alice는 $M$의 끝에 몇 개의 random bit를 추가하여 암호화한 다음 Bob에게 전송한다. 이를 Eve가 중간에 연결망을 끊어 Bob이 이를 받지 못하게 한다.

그러면 Alice는 $M$의 끝에 몇 개의 random bit를 다시 추가하여 암호화한 다음 Bob에게 다시 전송하게 될 것이다.

이렇게 되면 Eve는 중간에서 같은 메시지의 (물론, 다른 random bit를 갖는) 암호문을 두 개 확보한다. 이제 Eve는 $M$을 복원할 수 있다.

Theorem. (Coppersmith's Short Pad Attack) $N, e$는 RSA 공개키이고, $N$은 $n$-bit이다. $m=\lfloor n/e^2 \rfloor$라 하자. $M \in \mathbb{Z}_N^{*}$는 길이가 $n-m$ 이하인 메시지이고, $M_1 = 2^m M +r_1$, $M_2 = 2^m M+r_2$라 하자. 이때, $r_1, r_2$는 $0 \le r_1, r_2 < 2^m$을 만족하는 서로 다른 정수다. $N, e$와 $C_1, C_2 \equiv M_1^e, M_2^e \pmod{N}$을 알 때, $M$을 다항식 시간에 얻을 수 있다. 

$g_1(x,y) = x^e - C_1$, $g_2(x, y) = (x+y)^e - C_2$라고 하자. 만약 $y = r_2 - r_1$이라면, 두 다항식은 공통근 $M_1$을 갖는다.

변수가 두 개인 다항식의 공통근이 나왔으므로, Resultant를 생각할 수 있다.

즉, $h(y) = \text{res}_{x} ( g_1, g_2) \in \mathbb{Z}_N [y]$를 계산하면, 이는 $r_2 - r_1$을 근으로 갖는다.

한편, $h$의 차수는 최대 $e^2$이며, $|r_2 - r_1| < 2^m < N^{1/e^2}$이다. 그러니, Coppersmith's Theorem으로 $r_2-r_1$의 값을 구할 수 있다.

이제 $r_2-r_1$의 값을 알면, 남은 문제는 앞서 했던 Franklin-Reiter Related Message Attack으로 해결된다. 증명 끝.

여기서 $e=3$인 경우, 추가되어야 하는 random bit의 길이가 전체 메시지의 $1/9$ 이상은 되어야 함을 알 수 있다.

물론, $e=2^{16}+1 = 65537$을 사용하면, 이 공격에 당할 염려는 사실상 없다고 봐도 무방하다.

마지막으로 살펴볼 내용은 Partial Key Exposure Attack이다. Eve가 열심히 뚫어서 $d$의 일부를 얻은 시나리오를 생각해보자.

이 정보를 가지고 $d$ 전체를 확보할 수 있을까? 답은, $e$가 작으면 충분히 가능하다라는 것이다.

$e < \sqrt{N}$인 경우 $d$의 일부를 이용하여 $d$ 전체를 복원하는 것이 가능하다는 결과도 있다고 한다.

이런 결과가 있는 만큼, 웬만하면 $d$ 전체를 안전하게 보관하는 것이 좋다는 결론을 얻을 수 있다.

계속 등장하고 계신 Coppersmith 선생님의 멋지고 중요한 결과를 하나 더 소개한다. 

Theorem. (Coppersmith) $N = pq$가 $n$-bit RSA modulus라 하자. 

이때, $p$의 $n/4$ least significant bits을 알거나 $p$의 $n/4$ most significant bits를 알면, $N$을 다항식 시간에 소인수분해 할 수 있다.

이를 이용하여, Partial Key Exposure Attack이 실제로 가능함을 어렵지 않게 증명할 수 있다.

Theorem. (Boneh, Durfee, Frank's Partial Key Exposure Attack) $N, d$는 RSA 비밀키이고, $N$은 $n$-bit다. 

$d$의 $\lceil n/4 \rceil$ least significant bits를 알면, $d$ 전체를 $e \log_2 e$에 비례하는 시간에 복원할 수 있다.

$e, d$의 정의에서, 적당한 자연수 $k$가 있어 $ed-k(N-p-q+1) = 1$이 성립해야 한다.

$d < \phi(N) = N-p-q+1$이 성립하므로, $0< k \le e$가 성립해야 한다. 이제 $q = N/p$라 쓰고 주어진 식을 $\pmod{2^{n/4}}$로 본다.

이제 $edp - kp(N-p+1) + kN \equiv p \pmod{2^{n/4}}$를 얻는다. $e$는 공개되어 있고, $d \pmod{2^{n/4}}$는 이미 알고 있다.

그러니, $ed \pmod{2^{n/4}}$의 값을 이미 알고 있다. 이렇게 되면 위 식은 $k, p$에 대한 합동식이 된다.

특히, 이 식은 $k$를 고정하고 보면 $p$에 대한 이차합동식이 된다. 가능한 $k$의 후보는 $e$개이므로, 각각에 대해서 $p$에 대한 이차합동식을 풀어주자.

이제 $p \pmod{2^{n/4}}$로 가능한 후보를 몇 가지 얻을 수 있고, 각각에 대하여 위 Theorem의 알고리즘을 돌려주면 된다.

이차합동식에 대한 사실들을 잘 조합하면, 가능한 $p$의 후보가 $\mathcal{O}(e \log_2 e)$ 이하임을 알 수 있다고 한다.

그러니, $\mathcal{O}(e \log_2 e)$번의 시도를 하면 $N$의 소인수분해를 얻고 즉 $d$를 계산할 수 있을 것이다.

추가적으로, $e$가 작은 경우에는 $d$의 most significant bits를 쉽게 얻을 수 있음도 알 수 있다.

$ed - k(N-p-q+1)=1$인 $0 < k \le e$가 있다. $k$를 고정하고 생각하면, $\lfloor \frac{kN+1}{e} \rfloor$가 $d$의 좋은 근사가 됨을 알 수 있다.

정확하게 계산을 해보면 (Wiener's Attack에서 했던 계산이다) 실제 차이가 $3 \sqrt{N}$ 이하임을 알 수 있다.

즉, $e$가 작은 경우에는 $d$의 앞쪽 절반 정도의 most significant bits에 해당하는 후보군을 간단하게 얻을 수 있다.

특히, $e=3$인 경우에는 $k=2$가 강제되고 ($\pmod{3}$을 관찰하면 된다) 그러니 $d$의 앞쪽 절반을 전부 알 수 있다.

놀랍게도 #4에서 증명을 생략한 Coppersmith의 정리들은 전부 Lattice를 활용하는 것으로 알고 있다. Lattice가 많이 사기인듯. 

 

#5: Implementation Attacks

Implementation Attack은 RSA 함수의 성질 자체를 이용하여 공격을 하는 것이 아니라, RSA 구현체의 성질을 이용하여 공격을 한다.

가장 대표적으로 알려진 것은 Timing Attack이다. decryption을 위해서는, $M \equiv C^d \pmod{N}$을 계산해야 한다.

이 과정은 일반적인 binary exponentiation으로 구현되어 있을 가능성이 높다. 이는 다음과 같은 알고리즘이다.

$d=d_nd_{n-1} \cdots d_0$라고 하자. $C=1$, $z=M$이라고 하자. 각 $i=0, 1, \cdots n$에 대하여, 다음을 반복한다.

만약 $d_i=1$이라면, $C$를 $C \cdot z \pmod{N}$으로 바꾼다. 그 후, $z$를 $z^2 \pmod{N}$으로 바꾼다.

Eve가 적당한 $M_1, M_2, \cdots , M_k \in \mathbb{Z}_N^{*}$에 대해서 $M_i^d$를 계산하는데 걸리는 시간 $T_i$를 측정했다고 하자.

$d$가 홀수임은 자명하므로, $d_0=1$이고 첫 번째 스텝이 끝난 시점에 $C = M$, $z = M^2 \pmod{N}$임을 안다. 

이제부터 본격적으로 경우가 나뉘기 시작한다. 만약 $d_1=1$이라면, 기계는 $C \cdot z = M^3 \pmod{N}$을 계산한다.

$d_1 = 0$이라면, 이를 계산할 필요가 없다. $t_i$를 기계가 $M_i \cdot M_i^2 \pmod{N}$을 계산하는데 걸리는 시간이라고 하자.

이때, $t_i$의 값은 기계에 대한 정보를 충분히 얻으면 (Eve는 컴잘알이다) 사전에 얻을 수 있다고 가정한다. 

핵심적인 관찰은, $d_1 = 1$인 경우 $t_i$와 $T_i$ 사이의 correlation이 존재한다는 것이다. 

하지만 $d_1=0$이라면, $t_i$와 $T_i$는 independent한 것으로 보인다. 그러니 correlation을 기반으로 $d_1$의 값을 찾을 수 있다.

이 순서대로 계속하면, $d_2, d_3, \cdots , d_n$을 전부 복구하여 $d$를 계산할 수 있고 암호를 깰 수 있다.

더욱 자세한 내용과, 이 공격을 구현하는 방법을 알고자 한다면 NEERC 2017의 Editorial을 읽는 것을 추천한다. (나는 아직 안 읽었다)

놀랍게도, 이 대회의 H번이 정확히 이 구현을 요구하는 문제였다. 심지어 이 대회의 K번은 Knapsack Cryptosystem의 특수한 경우를 깨는 문제였다. 

위 공격과 비슷한 맥락으로, 기계가 사용한 전력을 이용하여 공격을 하는 방법 역시 있다고 한다. 

이를 방어하는 방법에는 크게 두 가지가 있다. 첫 번째 방법은, 계산 시간의 측정을 무의미하게 만드는 것이다. 

즉, 계산을 하는 도중에 적당한 딜레이를 추가하여, 위 공격에 필요한 사실들을 전부 거짓으로 만들어주면 된다.

두 번째 방법은, 앞서 언급한 "blinding"을 활용하는 것이다. 기계가 $M^d$를 계산해야 한다고 하자.

그러면 기계는 단순하게 $M^d$를 계산하는 대신, 랜덤한 $r \in \mathbb{Z}_N^{*}$를 잡고 $M' = M \cdot r^e \pmod{N}$을 계산한다.

그 후, $M'^d \equiv r \cdot M^d \pmod{N}$을 binary exponentiation으로 계산하고 modulo inverse를 이용해 $M^d \pmod{N}$을 얻는다.

이렇게 되면 핵심적인 부분인 거듭제곱을 랜덤하고 Eve가 값을 모르는 $M'$에 적용하므로, Eve는 위 공격을 활용할 수 없다.

두 번째로 볼 것은 Random Fault를 활용한 공격이다. 앞서 다루었듯이, CRT를 활용하여 $M^d \pmod{N}$을 빠르게 계산하는 방법이 존재한다.

$d$가 있다면, $d_p \equiv d \pmod{p-1}$과 $d_q \equiv d \pmod{q-1}$을 얻은 뒤 $C_p \equiv M^{d_p} \pmod{p}$, $C_q \equiv M^{d_q} \pmod{q}$를 계산한다.

이제, CRT를 활용하여 $C \equiv M^d \pmod{N}$을 빠르게 계산할 수 있다.

계산을 조금 해보면, (FFT를 활용하지 않는 단순 곱셈을 가정할 때) 이 방법으로 약 $4$배 정도의 속도 개선이 가능함을 알 수 있다.

그러니 이런 계산 방법은 상당히 매력적인 방법이고, 실제로 많은 구현체에서 활용된다고 한다.

기계에서 버그가 발생하여, 잘못된 값을 계산했다고 하자. 특히, $C_p$와 $C_q$ 중 정확히 한 값이 틀리게 계산되었다고 하자.

일반성을 잃지 않고, $C_p$는 제대로 계산되었으나 $C_q$는 잘못 계산되었다고 하고, 잘못 계산된 값을 $\hat{C_q}$라 하자.

그렇다면 CRT를 통해서 얻어진 $C$의 값은 잘못 계산될 것이며, 이 값을 $\hat{C}$라 하자.

Eve가 $M$을 가지고 와서 기계에게 $M^d \pmod{N}$을 계산해달라고 했는데, 위 오류가 발생했다고 하자.

$\hat{C}^e \not\equiv M \pmod{N}$이 성립하므로, Eve는 오류가 발생했음을 확인할 수 있다.

그런데 $\hat{C}^e \equiv M \pmod{p}$이고, $\hat{C}^e \not\equiv M \pmod{q}$이므로, $\text{gcd}(\hat{C}^e - M, N)$을 계산하면 $N$의 소인수분해를 얻을 수 있다.

공격이 성공하려면 $M$에 대한 정보를 Eve가 들고 있어야 하며, 계산 과정에서 $M$을 바꾸는 일이 없어야 한다.

즉, $M^d \pmod{N}$을 계산하기 전에 $M$에 random bit를 추가하는 등의 방식으로 "랜덤함" 한 스푼을 추가하면 이 공격을 막을 수 있다.

훨씬 간단한 방법으로는, 기계가 값을 출력하기 전에 제대로 계산을 했는지 확인하는 것이 있다. 실수를 했다면, 다시 계산하면 된다.

다양한 암호 체계가 이처럼 기계의 오류를 통해서 깨질 수 있다는 것이 밝혀졌다고 한다. 

마지막으로, Bleichenbacher's Attack on PKCS 1을 살펴본다. 암호학자들이 암호에 대한 빡빡한 기준을 갖는 이유를 알게 해주는 공격이다.

$N$은 $n$-bit RSA modulus고, $M$은 $m$-bit 메시지이며 $m<n$이라 가정하자. 

RSA 암호화를 진행하기 전에, $M$에 random bits를 추가하여 $n$-bit로 만드는 것은 나쁘지 않은 아이디어다.

"랜덤함"으로 간을 쳐주는 나쁘지 않은 방법이 되기 때문이다. 이는 실제로 공개키 암호 표준이었던 PKCS 1에서 사용된 접근이다.

"랜덤함" 간을 친 후, 메시지는 0x00 0x02 [random bits] 0x00 [메시지] 형태를 갖추게 된다. 

앞에 있는 16개의 bit는 랜덤함으로 간을 쳤다는 것을 알리기 위한 신호의 의미를 갖는다. 뒤의 0x00은 여기서부터 진짜 메시지라는 것을 알려주는 신호다.

암호화된 메세지를 Alice의 기계가 받으면, 기계는 이를 decrypt하고 첫 16개의 bit를 확인한다. 그 후, random bits를 전부 제거하여 메시지를 얻는다. 

그런데, 어떤 기계는 첫 16개의 bit가 0x00 0x02가 아닐 때 "invalid ciphertext"라는 에러 메시지를 보내줄 수도 있다.

이 점을 정말 제대로 활용한 것이 Bleichenbacher's Attack이다. 이 에러 메시지로 할 수 있는 게 생각보다 많다.

Eve는 ciphertext $C$가 있고, 이를 복호화하고자 한다. 이를 위해서, Eve는 랜덤한 $r \in \mathbb{Z}_N^{*}$를 하나 잡는다.

그 후, $C' \equiv r^eC \pmod{N}$을 계산하고, $C'$을 Alice의 기계에 보내준다. 

이제 Eve는 에러 메시지의 여부를 통해서 $C'^d \pmod{N}$의 첫 16개의 bit가 0x00 0x02인지 확인할 수 있다.

그러니, 에러 메시지의 존재는 Eve의 입장에서는 일종의 oracle이 된다. 

참 도움이 안 될 것 같은 정보지만, Eve는 이를 활용하여 효율적으로 $C$를 복호화할 수 있음을 보였다. 

Bleichenbacher의 당시 논문에 의하면, 대략 $2^{20}$번의 시행으로 $C$를 복호화할 수 있다고 한다.

이는 adaptive chosen ciphertext attack이 실제로 가능하다는 것을 보여준 대표적인 사례이다. 

즉, 암호학자들이 ACCA까지 보는 게 쓸데없는 일이 아니라는 것이다. (이는 예전에 내가 가졌던 의문에 대한 답이 된다)

#6: Conclusion - Selection of Parameters

앞에서 다룬 공격 외에도, 타원곡선을 이용한 공격, Cycling Attack 등 수많은 공격들이 존재한다. 

위에서 다룬 내용들과, 다루지 않은 공격들을 통하여 우리는 어떤 parameter가 공격에 취약한지 알 수 있었다.

이는 다르게 말하면, 위 내용을 통해서 RSA를 안전하게 사용하기 위해서는 어떻게 parameter를 설정해야 하는지도 알 수 있다는 것이다.

• $N$의 크기는 2048-bit 정도로 큰 것을 사용해야 한다. $N$의 소인수분해가 어려워야 하기 때문이다.
• $p$와 $q$의 크기는 비슷해야 한다. 타원곡선을 이용한 공격을 막아야 하기 때문이다.
• $q-p$는 충분히 커야 한다. $\sqrt{N}$ 근처의 수를 탐색하여 소인수분해하는 것을 막아야 하기 때문이다.
• $p-1$은 큰 소인수를 가져야 한다. Pollard의 $p-1$ 알고리즘을 막아야 하기 때문이다.
• $p+1$은 큰 소인수를 가져야 한다. Williams의 $p+1$ 알고리즘을 막아야 하기 때문이다.
• $r$이 $p-1$의 최대 소인수일 때, $r-1$이 큰 소인수를 가져야 한다. Cycling Attack을 막아야 하기 때문이다.
• $d$는 작으면 안된다. Low Private Exponent에 해당하는 공격을 막아야 하기 때문이다.
• $e$는 작으면 안된다. Low Public Exponent에 해당하는 공격을 막아야 하기 때문이다.
• 일반적으로 사용되는 $e$의 값은 $e = 2^{16} + 1$이다.
• 랜덤한 소수 $p, q$는 높은 확률로 암호학적으로 안전한 소수가 된다고 한다.

다음으로 읽을 논문을 찾아야 하는데, 뭘 읽어야 할지 잘 모르겠다. 일단 수업 내용부터 제대로 따라가야 할 것으로 보인다.