정수론 (8) - RSA 암호

저번에 오일러 공식에 대해 알아보았습니다. 이번에는 오일러 공식의 가장 유용한 응용인 RSA 암호에 대해서 알아보도록 하겠습니다.

 

RSA 암호의 개요

다음과 같은 시나리오를 생각해봅시다. 두 명의 사람 A, B가 있습니다. A는 B에게 보석을 배달받아야 합니다. 그런데 A, B 사이에는 보석을 노리는 사람들이 너무 많습니다. 어떻게 하면 중간에 보석을 뺏길 일 없이 안전하게 배달을 완료할 수 있을까요?

한 가지 훌륭한 방법은 다음과 같습니다

1. 먼저 A는 집에 있는 자물쇠와 상자를 B에게 보냅니다. (A는 자물쇠의 열쇠도 가지고 있습니다)
2. B는 보석을 상자 안에 넣고 자물쇠로 잠군 뒤, A에게 보냅니다.
3. A는 자물쇠를 풀고 보석을 얻습니다.

이 방식은, 자물쇠는 누구나 잠굴 수 있으나 푸는 것은 열쇠가 있는 사람만이 가능하다 라는 원리에 기반합니다. RSA 암호는 이 아이디어를 이용합니다.

RSA 암호: 준비

지금부터 구체적으로 RSA 암호의 작동 방식에 대해 알아보겠습니다. 먼저 RSA 암호를 준비하는 단계는 다음과 같습니다.

1. 매우 큰 소수 $p, q$를 고릅니다(150~600 자리 정도)
2. 두 소수를 곱해 $n = pq$를 얻습니다. 여기서 $n$ 은 첫번째 공개키 입니다. (자물쇠의 역할 1)
3. $\varphi(n)$을 구합니다. 여기서 $\varphi$는 오일러 파이 함수로, 파이 함수의 성질에 의해 $\varphi(n) = (p-1)(q-1)$입니다.
4. $\varphi(n)$과 서로소인 수 $e$를 고릅니다. 단, $1<e<\varphi(n)$입니다. $e$는 두번째 공개키입니다. (자물쇠의 역할 2)
5. $de \equiv 1 \mod \varphi(n)$이 되는 $d$를 고릅니다. $d$는 비밀키입니다. (열쇠의 역할)

여기서 $e$ 는 보통 $65537(=2^{16}+1)$ 이라는 소수를 사용하는 것이 관습이지만, 사실 어떤 소수를 쓰든 큰 상관이 없습니다. 한편 $d$ 는 확장 유클리드 알고리즘을 활용하면 쉽게 계산할 수 있습니다. 확장 유클리드 알고리즘은 저번 시간에 다뤘는데요, 요약하자면 $ax + by = \text{gcd}(a, b)$ 가 되도록 하는 정수 $x, y$ 를 구하는 알고리즘입니다. 여기서 $a=e, b=\varphi (n)$ 이라고 두면

$$ex + \varphi(n) y = 1$$
이 되며, 이 식을 법 $\varphi(n)$ 에 대한 합동식으로 바꾸면,

$$ex \equiv 1 \mod \varphi(n)$$
이 됩니다. 즉, $x$가 바로 우리가 찾고자 하는 비밀키 $d$ 가 되는 것이죠. 이후 확장 유클리드 알고리즘의 과정은 저번 글에서 다뤘으므로 이만 생략하겠습니다.

공개키 $n, e$ 는 말 그대로 공개키이기 때문에 누구나 알 수 있습니다. 하지만 비밀키 $d$ 는 오직 수신자만 가지고 있어야 합니다.

 

RSA 암호: 암호화

이제 $e, d$ 를 이용해 메세지를 암호화하는 방법을 알아보겠습니다.

1. 발신자는 먼저 자신의 메세지를 미리 합의된 방법(ASCII, UTF-8 등)을 이용하여 숫자 $m$ 으로 바꿉니다. 여기서 $m<n$ 이어야 합니다. 아니면, 다음 단계에서 법 $n$ 을 취할 때 정보가 손실됩니다.
2. 그 다음 $c \equiv m^e \mod n$ 을 구합니다. 여기서 $c$ 가 암호화된 메세지입니다. 공개키 $n, e$ 를 활용해서 암호화가 됐습니다.

RSA 암호: 복호화

복호화에서 오일러 공식이 활약합니다.

1. $c^d$ 를 $n$ 으로 나눈 나머지를 구합니다. 이가 바로 $m$ 입니다!
2. $m$ 을 다시 알파벳으로 바꾸면 성공적으로 메세지 전달이 완료되었습니다.

이제 1번이 왜 성립하는지 알아보겠습니다. $c \equiv m^e \mod n$ 이므로, $c^d \equiv m^{de} \mod n$ 입니다. 그런데 앞서 $de \equiv 1 \mod \varphi(n)$ 이 되도록 설정했습니다. 따라서 다음이 성립합니다.

$$c^d = m^{de} = m^{k\varphi (n) + 1} \equiv m^{k \varphi(n)} \times m \equiv 1^k \times m \equiv m \mod n$$
세 번째 등호에서 오일러 공식 $m^{\varphi(n)} \equiv 1 \mod n$ 이 쓰였습니다.

 

RSA 암호의 예시

대학생 디멘이가 다른 학생들에게 자신의 성적이 알려지는 것을 원치 않아, 교수님에게 학점을 ASCII를 이용해 숫자로 변환한 뒤 RSA 암호로 보내줄 것을 요청했다고 합시다. 먼저 디멘이는 공개키와 비밀키를 생성해야 합니다.

1. 디멘이는 소수 $p = 11, q = 17$ 을 이용하기로 했습니다.
2. 첫번째 공개키는 $n = pq = 187$ 입니다. $\varphi(n) = 10\times 16 = 160$ 입니다.
3. 두번째 공개키는 $e = 3$ 으로 정했습니다.
4. 확장된 유클리드 알고리즘을 활용하여 $3d \equiv 1 \mod 160$ 이 되는 $d$ 는 $107$ 임을 구했습니다. 이가 비밀키입니다.

이제 디멘이는 자신의 카카오톡 상태메세지 등 공개적인 장소에 공개키 $n = 187, e = 3$ 을 공개합니다. 그러면 교수님은 이걸 보고 디멘이의 학점인 D(눈물...)을 암호화해야 합니다.

1. 먼저 D는 ASCII에서 68입니다. 따라서 $m = 68$ 입니다.
2. $m^e = 68^3 \equiv 85 \mod 187$ 이므로, $c = 85$ 입니다. 교수님은 이 사실을 자신의 상태메세지에 공개합니다.
3. 디멘이는 $c = 85$ 에 $d = 107$ 제곱을 한 뒤 $n=187$ 로 나눕니다. $85^{107} \equiv 68 \mod 187$ 이고, 68은 ASCII에서 D이므로, 이렇게 디멘이는 자신의 학점이 D라는 사실을 알게 되었습니다.

이 과정에서 디멘이와 교수님은 공개적으로 암호화된 메세지를 주고받았지만, 비밀키만은 디멘이가 가지고 있었기 때문에 이 메세지를 복호화할 수 있는 사람은 디멘이밖에 없었습니다.

 

물론, 이런 상황에서는 사실 $n = 187$ 이 소인수분해하기 매우 쉬운 수이기 때문에 다른 학생들도 금방 $p=11, q = 17$ 임을 알아낼 수 있고, 암호키를 계산할 수 있습니다. 하지만 실제 상황에서는 앞서 말했듯이 매우 큰 소수를 이용하기 때문에 유효한 시간 내에 $n$ 을 소인수분해하여 암호키를 계산하기는 불가능합니다.

 

이렇게 RSA 암호에 대한 내용을 마지막으로 정수론 시리즈를 마칩니다. 이후 정수론의 내용으로 원시근과 관련된 내용이 시작되는데 내용이 꽤나 복잡해서 나중에 기회가 될 때 다시 찾아오겠습니다. 여기까지 읽어주셔서 진심으로 감사합니다. 앞으로도 더 좋은 시리즈를 위해 노력하겠습니다 :)