이미지 출처 : https://history-computer.com/rsa-encryption/

RSA란?

---

RSA 암호 시스템은 공개키 암호 방식( PKC, Public-Key Cryptography )체계 중 하나이다.
1978년 Ron Rivest, Adi Shamir, Leonard Adleman 세 사람에 의해 이 체제가 개발되었다. 이 세 사람의 성을 따 RSA라는 이름이 붙게 된 암호 방식이다.

수학적으로 엄청나게 큰 숫자의 소인수 분해가 어렵다는 사실을 기반으로 두고 있다.

보안도가 매우 높은데다 후술할 계산과 간략화 알고리즘 덕분에 (고전적인 방법으로는) 해독할 수 없는 암호문이지만 미국 국가 표준 암호화 알고리즘인 AES 방식보다 계산 집약적이고 훨씬 느리다는 단점이 있다.

간단하게 RSA 암호의 동작을 알아봅시다.

• A가 B에게 메시지를 전달하려고 한다.

1. A는 B의 열린 자물쇠를 들고 와서 전달하고자 하는 메시지를 봉인(공개키 암호화 고정)한다.
2. A는 B에게 봉인한 메시지를 전달한다.
3. B는 해당 자물쇠의 열쇠(개인 키)로 A에게 받은 봉인된 메시지를 열어 확인한다.
   참고 : https://ko.wikipedia.org/wiki/RSA_%EC%95%94%ED%98%B8

PKC란?

---

PKC(Public-Key Cryptography, 공개 키 암호 방식)이란, 암호화( Public Key, 공개키 )와 복호화( Private Key, 비밀 키 )에 사용하는 키가 서로 다른 암호화 방식을 의미한다.
암호화와 복호화에 같은 키를 사용하는 대칭 키 암호화 방식( Symmetric-Key Algorithm )과 달리 키가 다른 비대칭 암호 방식( Asymmetric Cryptography )이라고도 불린다.

Mathematics

---

RSA 암호 시스템을 이해하기 위해, 수학을 베이스로 작동하기 때문에 몇 가지 수학적 이론들을 알고 있어야 한다. 정수론, 대수학을 공부하였다면 쉽게 이해할 수 있을 것이다.

기본적인 수학 기호 및 용어

$\mathbb{Z}$ : 정수의 집합

$gcd(a,b)$ : $a$, $b$의 최대공약수

$a ∣ b$ : $b$는 $a$로 나누어떨어진다.

$a ∤ b$ : $b$는 $a$로 나누어떨어지지 않는다.

$a ≡ b (mod m)$ : $a$를 $m$으로 나누었을 때의 나머지가 $b$와 같다.

기약잉여계 : 어떤 수 $a$에 대하여 1부터 $a$중 $a$와 서로소인 수들의 집합

베주 항등식 (Bézout's Identity)

---

두 정수와 그 최대공약수 사이의 관계를 보여주는 항등식이다.
적어도 둘 중 하나는 0이 아닌 정수 $a$, $b$ 가 있을 때, 두 정수 $x$ ,$y$ 에 대하여 다음 명제가 성립된다.

$ax+by = \gcd(a, b)$

위의 식을 만족하는 $x$, $y$ 가 반드시 존재하게 된다.

Proof

---

증명의 순서는 다음과 같다.
1. $ax + by$꼴로 표현할 수 있는 가장 작은 자연수가 존재함을 밝힌다. 그것을 $d$라 하자.
2. $d$는 $a$와 $b$의 공약수임을 밝힌다.
3. $d$가 $a$와 $b$의 최대공약수임을 밝힌다.

(i) $ax + by$꼴로 표현할 수 있는 가장 작은 자연수가 존재함을 밝힌다. 그것을 $d$라 하자.
먼저, 둘 중 적어도 하나는 0이 아닌 정수 $a$, $b$가 있을 때 다음과 같은 집합 $S$를 정의할 수 있다.

$S = \{ m ∣ m =ax + by > 0, x \isin \Z, y \isin \Z\}$

S ≠ ∅을 증명해보자.

$\left \{ \begin{array}{cc} a×1+b×0∈S\;\;\;\;\;\;\;\; if\;\; a > 0 \\ a×(-1)+b×0∈S \;\;if\;\; a < 0 \\ b \neq 0, |b| \isin S\;\;\;\;\;\;\;\;\;\;\;\;\;\;if\;\;a= 0 \end{array} \right.$

위와 같은 논리로 집합 $S$는 둘 중 적어도 하나는 0이 아닌 정수 $a$, $b$가 있을 때 집합 $S$의 정의에 따라 자연수의 부분집합이므로 $|a|$, $|b|$ 중 적어도 하나의 원소를 가지므로 $S$ ≠ ∅ 임을 알 수 있다.

$S$ ≠ ∅ 이므로 자연수의 정렬성에 의해 집합 $S$는 최소원소, 즉 $ax + by$ 꼴로 나타낼 수 있는 가장 작은 자연수가 존재한다. 그것을 $d$라 하자.

(ii) $d$는 $a$와 $b$의 공약수임을 밝힌다.

$S$의 정의로, $d$는 $S$의 원소이므로 $d$ = $ak + bl$를 만족하는 두 정수 $k$, $l$이 존재한다고 할 있다.
나머지 정리에 의해 $a$를 $d$로 나눈 몫 $q$와 나머지 $r$에 대해 다음과 같이 나타낼 수 있다.

$a = dq + r(q ∈ \Z, 0 \leq r < d) \\$

위 식을 나머지 $r$에 대해 정리하면 다음과 같이 나타낼 수 있다.

$r = a - dq = a -(ak + bl)q = (1 -kq)a+ (-lq)b ∈ S$

이 부분에서 $r$ > 0 일 때 집합 $S$의 정의에 의해 $r$ ∈ $S$가 되고, $r$ < $d$ 이기 때문에 $d$가 집합 $S$의 최소원소라는 가정에 모순이 발생한다.

따라서 $r = 0$이며, $a = dq$, 즉, $d | a$ 임을 알 수 있다. 이와 같은 방식으로 $d | b$ 임을 알 수 있다.
$d | a$ 이고 $d | b$이므로 $d$는 $a$와 $b$의 공약수이다.

(iii) $d$가 $a$와 $b$의 최대공약수임을 밝힌다.
$a$와 $b$의 공약수 $e$가 있다고 하면 다음과 같이 나타낼 수 있다.

$a = ea', b = eb'$

이를 $d = ak + bl$ 에 대입하면 다음과 같으므로 $e$는 $d$의 약수이다.

$d = ea'k + eb'l = e(a'k + b'l)$

결론적으로, $e | d$이고 $d|gcd(a, b)$ 이므로 $d=gcd(a,b)$이고,
$d=gcd(a,b)=ax+by$를 만족하는 두 정수 $x$, $y$가 존재함을 알 수 있다.

유클리드 호제법 (Euclidian Algorithm)

---

두 정수 $a$, $b$가 있고, $a$를 $b$로 나눈 나머지 $r(0 ≤ r < b)$에 대하여 다음식이 성립한다.

$gcd(a, b) = gcd(b, r)$

Proof

---

(i) $a$, $b$의 최대공약수, 즉, $gcd(a,b)$ 를 $G$ 라고 하고 서로소인 두 정수 $a'$, $b'$에 대해 $a = Ga'$, $b = Gb'$와 같이 나타낼 수 있다. 그리고 나머지 정리에 의해 $a$ 를 $b$로 나눈 몫 $q$, 나머지 $r$에 대해 다음과 같이 나타낼 수 있다.

$a = bq + r(0 \leq r < b) \\ r = a - bq = Ga' - Gb'q = G(a' - b'q)$

$r$에 대하여 정리하면 $r = G(a'- b'q)$, $G | r$임을 알 수 있다.

(ii) $gcd(b', a'- b'q) = G'$ 라고 하면, 서로소인 두 정수 $k$, $l$에 대해 다음과 같이 나타낼 수 있다.

$b' = G'k \\ a'-b'q = G'l \\ a' = G'l + b'q = G'l + G'kq = G'(l+kq)$

$a'$에 대하여 정리하면, $G'$은 $a'$, $b'$의 공약수인데 $a'$, $b'$은 서로소이므로 $gcd(a',b') = 1$이다.
따라서, 항상 $G' = 1$, 즉, $b'$와 $a' - b'q$는 서로소라는 것을 알 수 있다.

$b=Gb', r=G(a'-b'q) \\ gcd(b', a'-b'q) = 1 \\ gcd(b,r) = G = gcd(a,b)$

결론적으로 $gcd(a, b) = gcd(b, r)$ 라는 것을 알 수 있다.

확장 유클리드 알고리즘 (Extended Euclidian Algorithm)

---

두 정수 $a$, $b$에 대하여 베주 항등식인 $ax + by = gcd(a, b)$를 만족하는 정수 $x$, $y$의 값을 구하는 방법이다.

Proof

---

증명 순서는 다음과 같다.
1. 점화식을 도출한다.
2. 언제 $ax + by = gcd(a, b)$를 만족하는 $x$, $y$값이 되는지 확인한다.

(i) 유클리드 호제법에 의해, 두 정수 $a$, $b$의 최대공약수 $gcd(a, b)$에 대해서 다음과 같이 나타낼 수 있다.

$gcd(a, b) = gcd(b, r_{1}) = gcd(r_{1}, r_{2}) = ... = gcd(r_{i-1}, r_{i}) = ...$

이를 풀어 정리하면 아래와 같이 나타낼 수 있다.

$a = bq_{0} + r_{1}(0 < r_{1} < b) \\ b = r_{1}q_{1} + r_{2}(0 < r_{2} < r_{1}) \\ c = r_{2}q_{2} + r_{3}(0 < r_{3} < r_{2}) \\ . \\ . \\ r_{i-1}=r_{i}q_{i} + r_{i+1}(0 < r_{i+1} < r_{i}) \\ . \\ . \\ .$

이를 통해 다음과 같은 점화식을 도출할 수 있다.

$r_{i+1}=r_{i-1} - r_{i}q_{i} \\ r_{i} = ax_{i} + by_{i}$

두 번째 식을 위 점화식에 대입하여 정리하면 다음과 같이 나타낼 수 있다.

$r_{i-1} = ax_{i-1} + by_{i-1} \\ r_{i+1} = ax_{i+1} + by_{i+1} \\ =ax_{i-1} + by_{i-1} - (ax_{i} + by_{i})q_{i}\\ =a(x_{i-1} + x_{i}q_{i}) + b(y_{i-1}-y_{i}q_{i})$

따라서, $ax_{i+1} = x_{i-1} - x_{i}q_{i}$, $by_{i+1} = y_{i-1} - y_{i}q_{i}$라는 점화식을 도출할 수 있다.

그러면 이 부분에서 다음과 같이 $x$, $y$의 초기조건을 이끌어낼 수 있다.

$r_{0} = a = ax_{0}+by_{0}(x_{0} = 1, y_{0} = 0) \\ r_{1} = b = ax_{1}+by_{1}(x_{1} = 0, y_{1} = 1)$

위에서 구한 점화식으로 $r_i$가 0이 될 때까지 반복하면, 그때의 $x_i$, $y_i$의 값이 각각 $ax + by = gcd(a, b)$를 만족하는 $x$, $y$값이 되는 것이다.

페르마의 소정리 (Fermat's little Theorem)

---

소수 $p$와 $p$와 서로소인 정수 $a$에 대해 다음과 같은 식이 성립한다.

$a^{p-1} \equiv 1(mod\;p)$

따름정리 : 소수 $p$에 대하여 다음 식이 성립힌다.

$a^{p} \equiv a(mod\; p)$

Proof

---

페르마의 소정리는 다양한 방법으로 증명을 할 수 있다.
다양한 방법 중 기약잉여계를 사용해 페르마의 소정리를 증명할 것 이다.

먼저, $a$와 $p$가 서로소라고 하자.
이때, $\{1a, 2a, ..., (p-1)a\}$는 $mod\;p$에 대해 서로 합동이 아니다.
또한 이중에서 $p$의 배수인 것은 없으므로, 이 집합을 p로 나눈 나머지들의 집합은 $\{1,2, ...,p-1\}$와 같다. 이때 다음과 같은 식이 성립한다.

$1a\cdot2a\cdot....\cdot(p-1)a \equiv \{1\cdot2\cdot...\cdot(p-1)\}a^{p-1} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\equiv\{1\cdot2\cdot...(p-1)\}(mod\;p)$

위 합동식에서 소수 $p$에 대해 역원이 존재하기 때문에 $1\cdot2\cdot...\cdot(p-1)$을 약분할 수 있다.
결론적으로, $a^{p-1} \equiv 1(mod\;p)$ 라는 것을 증명할 수 있다.

오일러 정리 (Euler's Theorem)

---

서로소인 두 정수 $a$와 $n$에 대하여 다음 식이 성립한다.

$a^{\varphi(n)} \equiv 1(mod\; n)$

Proof

---

정수 $n$의 기약잉여계 $S$는 다음과 같다.

$S = \{b_{1}, b_{2}, b_{3},...,b_{\varphi(n)}\}$

$S$의 각 원소에 $n$과 서로소인 $a$를 곱한 집합을 $aS$ 하면 다음과 같다.

$aS=\{ab_{1}, ab_{2}, ab_{3},...,ab_{\varphi(n)}\}$

이때, $aS$의 모든 원소는 $n$과 서로소인 수들끼리 곱한 수들이므로 그 원소들 역시 $n$과 서로소이다.

또한, $aS$의 모든 원소를 $n$로 나눈 나머지는 모두 서로 다르다.

만일, $ab_{i} \equiv ab_{j}(mod\;n), 1\leq i, j \leq \varphi(n)$가 존재한다고 가정해보자.

그럼 $n|ab_{i} - ab_{j} = a(b_{i}-b_{j})$ 이고 $n$와 $a$가 서로소이므로 $n|b_{i}-b_{j}$ 라는 것을 알 수 있다.
$n|b_{i}-b_{j}$라는 것은 $b_{i}-b_{j}$가 $n$의 배수이다.
이때, $b_{i}$와 $b_{j}$는 둘 다 1이상 $n$이하의 수들이므로 다음 부등식이 성립해야 한다.

$|b_{i}-b_{j}| \leq (n-1)$

하지만, 부등식을 만족하고 $n$의 배수인 것은 0뿐이므로 $b_{i}-b_{j}=0$, 즉 $b_{i}=b_{j}$이므로 모순이 발생한다.

결국, 집합 $aS$의 각 원소를 $n$으로 나눈 나머지들의 집합은 모두 $n$과 서로소이며, 서로 다른 자연수이므로 $n$의 기약잉여계인 $S$와 같다고 볼 수 있다.

따라서, 다음과 같은 식으로 나타낼 수 있다.

$ab_{1}\cdot ab_{2}\cdot ab_{3}\cdot...\cdot ab_{\varphi(n)} \equiv (b_{1} b_{2}b_{3}\cdot\cdot\cdot b_{\varphi(n)})a^{\varphi(n)} \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\equiv(b_{1} b_{2}b_{3}\cdot\cdot\cdot b_{\varphi(n)})(mod\;n)$

위 합동식에서 $n$과 서로소인 $(b_{1} b_{2}b_{3}\cdot\cdot\cdot b_{\varphi(n)})$은 역원이 존재하므로 약분할 수 있다.
결론적으로, $a^{\varphi(n)} \equiv 1(mod\; n)$라는 것을 증명 할 수 있다.

RSA Mechanism

---

Key Generation

---

키 생성 과정
1. 두 소수 $p$, $q$를 준비한다.
2. $N = pq$를 계산한다.
3. $\varphi(n)$, 즉, $(p-1)(q-1)$과 각각 서로소인 정수 $e$를 준비한다.
4. $ed \equiv 1(mod\;\varphi(N))$를 만족하는 정수 $d$를 찾는다. (확장 유클리드 알고리즘 사용)
5. $p$, $q$는 더 이상 필요 없으며, 보안상의 문제가 될 수 있으니, 파기한다.

4번에서 확장된 유클리드 호제법을 이용하면 정수 $d$를 빠르게 구할 수 있다.
또 이 부분에서 $e$를 준비한 이유가 나타난다. $e$가 $(p-1)(q-1)$와 서로소가 아니라면 이를 만족하는 $d$는 존재하지 않기 때문에 3번 과정이 필요하다.

Encryption

---

공개키 $N$과 $e$, 전달하고자 하는 메시지 $m (m<N)$에 대하여 다음과 같이 암호화한다.

$c=m^{e}\;mod\;N$

c는 암호문이다.

Decryption

---

공개키 $N$, 비밀키 $d$, 암호화된 메시지 $c$에 대하여 다음과 같이 복호화한다.

$m=c^{d}\;mod\;N$

m은 복호화된 메시지이다.

Proof

---

우선, 복호화 식을 정리해보자.

$m = c^{d}\;mod\;N\\ \;\;\;\;=(m^{e}\;mod\;N)^{d}\;mod\;N \\ \;\;\;\;=m^{ed}\;mod\;N$

따라서 RSA 암호 시스템을 증명하기 위해선 $m^{ed}\equiv m(mod\;N)$을 증명하면 된다.
$N=p\times q$이므로 위 합동식이 $mod\;p$, $mod\;q$, $mod\;N$일 때 모두 성립한다.
또, $ed\equiv1(mod\;\varphi(N))$이므로, 적당한 수 k에 대하여 $ed=k\varphi(N)+1=k(p-1)(q-1)+1$이란 것을 알 수 있다.

먼저, $mod\;N$ 대신 $mod\;p$을 사용하여 위 합동식에 대입하여 정리하면 다음과 같다.

$m^{ed}\equiv m(mod\;N) \equiv m(mod\;p) \\ m^{k(p-1)(q-1)+1} = m^{k(p-1)(q-1)}\times m\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;=(m^{p-1})^{k(q-1)} \times m\\ (m^{p-1})^{k(q-1)} \equiv m(mod\;p)$

여기서 두 가지 경우로 나뉘는데,
첫 번째 경우는 $m$이 $p$의 배수 일때이다.
$m$이 $p$의 배수이면 위 합동식의 양변이 모두 $p$로 나누어떨어져서 0이 되므로, 합동식이 성립한다.

두 번째 경우는 $m$이 $p$의 배수가 아닐 때이다.
$m$이 $p$의 배수가 아니면 $p$가 소수이기 때문에 페르마의 소정리에 의해 $m^{p-1} \equiv 1(mod\;p)$이고, 이 식을 위 식에 대입해보면 다음과 같이 합동식이 성립하게 된다.

$(m^{p-1})^{k(q-1)} \times m \equiv m(mod\;p) \\ 1^{k(q-1)} \times m \equiv m(mod\;p) \\ m \equiv m(mod\;p)$