이 블로그에 댓글란이 있다고 해보자. 비밀 댓글 구현이 번거로우니, 공개 댓글란에 나만 이해할 수 있는 암호 형식으로 댓글을 받기로 하자.

이 때 내 블로그에 들어오는 불특정 다수에게 뭐라고 공지해야 암호를 받을 수 있을까? 암호화 규칙을 섣불리 공지했다간 독자들이 서로의 암호문을 쉽게 파훼할 것이다.

예를 들어 [A는 01, B는 02, ..., Z는 26, Space는 27]이라고 하면 누구나 아래 암호문의 의미를 알 수 있다.

09271215220527251521 ➡︎ I LOVE YOU

암호화 규칙을 공개하지 않고 개별적으로 안내하는 방법은 어떨까? 아쉽지만 실효성이 낮다.

첫째, 일단 블로그 독자 중 누가 비밀 댓글을 원하는지 알 수가 없다.

둘째, 설령 안다고 하더라도 그 수가 너무 많을 수 있다. 일일이 규칙을 알려주는 게 꽤나 번거로울 것이다.

셋째, 심지어 그 수가 적더라도 암호 규칙을 제각기 다르게 만들어야 하는 불편함이 있다.

이렇게 난감한 상황에서 사용할 수 있는 것이 RSA 암호화다. RSA는 암호 규칙을 공개적으로 알려주고도, 암호문을 공지자만 풀 수 있는 비법이다.

RSA의 배경에는 단순한 수학 원리가 숨어 있다. 이 원리를 이해하고 나면 지식의 유용성을 실감할 것이다. 처음 읽을 때는 어렵게 느껴지지만 한 번 이해하고 나면 단순하다.

===

우선 소수 $p$ 와 $q$ 의 곱으로 만든 $n$ 을 가정하자. 예를 들어 $p=3,\; q=5$ 라면 $n = p \times q = 15$ 이다.

그 다음, $n$ 보다 작으면서, $n$ 과 서로소인 $m$ 을 가정하자.

그리고 뜬금 없지만 $k=(p-1)(q-1)$ 를 가정하자. 우리의 예에서는 $k = (3-1)(5-1)=8$ 이다.

자, 이 때 $m^k$ 를 $n$ 으로 나누면 $1$ 이 남는다! 이 사실은 오일러가 밝혔는데, 증명 없이 받아들이기로 하자.

이제 위 법칙으로부터 $m^k \times m$ 을 $n$ 으로 나누면 $m$ 이 남는다는 사실을 도출할 수 있다.

즉 $m^{(k+1)}$ 을 $n$ 으로 나누면 다시 $m$ 이 튀어나온다는 뜻이다. 왠지 암호화에 요긴하게 쓰일 것 같다는 느낌이 들지 않는가?

직접 도출해보자. 우리가 알다시피, $m^k$ 를 $n$ 으로 나누면 $1$ 이기 때문에, $m^k$ 는 $n$ 의 배수에 $1$ 을 더한 숫자다.

그러니 $m^k = ln + 1$ 이라고 하자. 이제 여기에 $m$ 을 곱하면, 다음과 같다.

$m^k \times m = lnm + m$ .

그러면 이 숫자를 $n$ 으로 나누면 $m$ 이 남는 것이 자명해진다. $lnm$ 은 $n$ 으로 나누어 떨어지고, $m$ 은 $n$ 보다 작으면서 $n$ 과 서로소이니까.

===

이쯤에서 암호화를 생각해보자. 독자들이 보내려는 비밀 메시지를 $m$ 이라고 하자. 여기에 $k+1$ 을 제곱한 다음 $n$ 으로 나누면 원래의 메시지 $m$ 이 나온다. 느낌은 살짝 오는데, 뭔가 아쉽다.

아쉽게도 문제가 있다. 독자들에게 "$k+1$ 을 제곱한 후 $n$ 으로 나눈 나머지를 댓글로 달아주세요"라고 하면, 감추고자 했던 비밀 메시지가 댓글에 달리는 것밖에 되지 않는다. 수학 법칙 한 가지가 더 필요하다.

===

$k+1 = e \times d$ 라고 하자. 그러면 $m^{k+1} = (m^{e})^{d}$ 이다.

이 때, $m^{k+1}$ 을 $n$ 으로 나눈 나머지를 $r$ 이라고 하자.

$m^e$ 를 $n$ 으로 나누어 나머지 $s$ 를 구한 다음, $s^d$ 를 $n$ 으로 나눈 나머지도 $r$ 이다.

알파벳이 너무 많으니, 예를 들어보자. 예가 훨씬 쉽게 느껴질 것이다.

$2^6 = 64$ 를 $5$ 로 나누면 나머지가 $4$ 다. 그리고 $2^6 = (2^{3})^{2}$ 이다.

이제 $2^3$ 을 먼저 $5$ 로 나누어보면, 나머지가 $3$ 이다. 그리고 $3^2$ 을 $5$ 로 나누면 나머지가 $4$ 다.

즉 $2^6$ 을 한 번에 $5$ 로 나누든, $2^6 = (2^{3})^{2} = 2^{3 \times 2}$ 임을 이용해서 두 단계로 나누든, 나머지는 똑같다.

이 또한 증명 없이 받아들이기로 하자.

===

자! 이제 나는 $e, d$ 를 모두 알고 있으니 $k+1$ 을 아는 셈이고, 따라서 $m^{k+1}$ 을 $n$ 으로 나누어 나머지 $m$ 을 구할 수 있게 되었다.

반면 독자들은 $e$ 만 알기 때문에 타인의 메시지 $m$ 을 알아낼 방법이 없다. 그러면서도 자신의 메시지 $m$ 에 $e$ 를 제곱한 후 $n$ 으로 나누어 암호를 만들 수 있다. 공지문은 다음과 같다.

"여러분의 비밀 메시지 $m$ 에 $e$ 를 제곱하세요. 그리고 $n$ 으로 나눈 나머지를 댓글로 달아주세요."

===

예를 들어보자.

나는 독자들에게 $n$ 과 $e$ 를 공개한다. $n=187$ 이고, $e=23$ 이다.

이제 독자가 내게 $m = 9$ 라는 메시지를 보내고 싶다고 해보자. 그는 $9^{23}$ 을 $187$ 로 나눈 나머지 $36$ 을 댓글로 적는다.

다른 독자들은 $36$ 으로부터 $9$ 를 유추할 길이 없다. 역산하기엔 계산량이 너무 크기 때문이다. (물론 우리의 예제는 일부러 작은 수를 사용했기에 역산이 쉽다.)

이제 나는 $36$ 에 어떤 수를 제곱해야 할까? 바로 $7$ 이다. 왜인지 이해가 안 된다면, 맨 위에서부터 차근차근 다시 읽어보자.

$k+1 = 161$ 이고, $e=23$ 이기 때문에 $d=7$ 이다.

어쨌든, $36^7$ 을 $187$ 로 나누면 나머지가 몇일까?

짜잔! 바로 $9$ 이다.

다시 한 번 정리해보자.

$n = p \times q$ 일 때, $m^{(p-1)(q-1) + 1}$ 을 $n$ 으로 나누면 $m$ 이다.

그리고 $m^{(p-1)(q-1)+1} = (m^{e})^{d}$ 라면, $m^e$ 를 $n$ 으로 나눈 나머지에 $d$ 를 제곱하고 한 번 더 $n$ 으로 나누었을 때 나머지가 $m$ 이다.

따라서 $n$ 과 $e$ 를 공개하면, 사람들은 암호를 만들 수 있고 나는 $d$ 를 이용해 원본 메시지를 얻을 수 있다.

이게 RSA의 수학 원리다. 물론 모든 수를 대입해보는 brute force 해킹이 있을 수 있어서, 실제로는 $p, q, e, d$ 모두 엄청 큰 수를 이용한다.