8. RSA 암호화 (RSA Encryption Algorithm)

RSA 암호화는 대표적인 공개키 방식 암호화 알고리즘으로, 개발자 세 명의 이름을 따서 만들어졌다. (즉, Really Secure Algorithm 따위의 멋있는 약자가 아니라, 김이박 암호화 같은 이름이다.)

RSA 암호화는 공개 키 $e, n$과, 비공개 키 $d$을 사용한다.

$e$는 암호화^Encryption, $d$는 복호화^Decryption의 약자이다. 복호화하고자 하는 이만 비공개 키를 알고 있어도 되는 특성 때문에, $d$는 개인 키라고도 불린다.

키 만들기

1. 먼저, 두 개의 큰 소수 $p, q$를 준비한다. 이때, 암호화할 메시지 $m$보다 $p$가 커야 한다.
   (보통 큰 홀수를 하나 만들어서, 2씩 더해가면서 소수를 찾는다.)
2. $(p-1), (q-1)$과 각각 서로소인 정수 $e$를 얻는다. (보통 소수인 3(0x11)이나 65537(0x10001)을 사용한다.)
3. $ed \mod (p-1)(q-1) = 1$인 $d$를 찾는다. 즉, $d$는 $e (\mod (p-1)(q-1))$의 곱의 역원이다.
4. $n=p\cdot q$를 구한다. 보통 RSA 암호화에서 키의 크기를 논하면 $n$의 크기를 말한다.
5. 이제 $e,n$은 공개하고, $p,q$는 파기한다.

$e$는 암호화 $d$는 복호화에 사용되며, 두 과정 모두 $n$역시 필요로 한다. $p,q$는 키 생성 과정에서만 사용되고 이후에는 쓸모가 없으므로 키 생성 후 파기한다.

암호화/복호화

$$m' = \text{rem}(m^e, n)$$

$$m = \text{rem}((m')^d, n)$$

증명

암호화한 메세지 $m'$과 원래 메세지 $m$이 어떻게 똑같은지 증명해보자.

페르마의 소정리에 의해, 어떤 소수 $p$의 오일러 피 함수 $\phi(p)$는 $p-1$이다. 즉, $n = pq$이므로, $\phi(n) = (p-1)(q-1)$이다.

$ed=r(p-1)(q-1)+1 = r\phi(n)+1$이다. ($r$은 어떤 정수)

$mr \mod n = (m\mod n)(r\mod n) \mod n$, $m^r \mod n = (m \mod n)^r mod n$이다.

그러므로,

$$\begin{align*}m' &= m^d \mod n = (m^e \mod n)^d \mod n \\ &= (m^e)^d \mod n = m^{ed} \mod n\\ &= m^{r\phi(n)+1} \mod n = (m^{\phi(n)} \mod n)^r \cdot m \mod n\\ &= 1^r\cdot m \mod n = m\end{align*}$$

예제

$m = 11$을 RSA 암호화 해보자.

$p = 7, q = 13, e = 5$으로 정하자. $n = pq = 91$이 된다.

$5\cdot d \mod (6\cdot 12) = 1$인 $d$를 확장된 유클리드 호제법으로 구해보자.

$5, 72$의 최대공약수를 구하면 된다.

$i$	$x$	$y$	$r$	$q$
0	1	0	72
1	0	1	5	14
2	1	-14	2	2
3	-2	29	1	2
			0

$5,72$의 최대 공약수는 $-2\cdot 72 + 29\cdot 5 = 1$이다.

즉, $d=29$이다.

이제 $e, n$을 활용한 암호화다.

$$\begin{align*}m' &= m^e \mod n\\ &=11^5 \mod 91\\ &=161051 \mod 91 = 72 \end{align*}$$

이제 $p,q$는 파기하고, $e=5, n=91$을 공개한다. 그리고 복호화를 할 사람에게만 개인키인 $d=29$를 제공한다.

복호화를 해보자.

$$\begin{align*} m &= (m')^d \mod n\\ &= 72^29 \mod 91\end{align*}$$

$72^29$는 컴퓨터로 계산하기엔 엄청나게 큰 수다. 이를 간단히 계산하는 방법이 있으나 본 글에서는 다루지 않겠다.

알아보고 싶다면, 이 글의 2문단 아래쪽을 참고하면 된다.

계산 결과는 11이 된다.