RSA 암호화 방식의 수학 원리

상황

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

이 때 내 블로그에 들어오는 불특정 다수에게 뭐라고 공지해야 암호를 받을 수 있을까? 암호화 규칙을 공개하지 않을 수는 없다. 왜냐하면 개별적으로 규칙을 안내하기가 번거롭고 사람마다 규칙을 다르게 만들어야 하기 때문이다.

이럴 때 안전하게 사용할 수 있는 것이 RSA 암호화다. RSA는 암호 규칙을 공개적으로 알려주고도, 암호문은 공지한 사람만 풀 수 있는 방법이다. RSA의 배경에는 단순한 수학 원리가 숨어 있다.

준비물

우선 두 개의 소수의 곱으로 만든 수를 가정해야 한다. 예를 들어 p=3, q=5라면 다음과 같은 수가 생긴다.

$$n = p \times q = 15$$

그 다음, n보다 작으면서, n과 서로소인 m을 가정해야 한다.

$$m = 17$$

그 다음, 뜬금 없지만 처음 두 소수에서 각각 1씩 뺀 후 곱한 값을 준비해야 한다.

$$k = (3-1)(5-1) = 8$$

자, 이제 오일러가 밝힌 법칙(이 암호화의 핵심)을 사용하자. 아래 수식이 바로 그것인데, m의 k제곱을 n으로 나누면 1이 된다는 뜻이다.

$$m^k \equiv n \mod 1$$

그렇다면 m의 k제곱에다 m을 한 번 더 곱하면, n으로 나누었을 때 m이 될 것이다. (바로 이해가 안 된다면 공책을 펴시길) m에다가 이런저런 조작을 했는데 m을 뱉어내더라... 왠지 암호화에 요긴하게 쓰일 것 같다는 느낌이 들지 않는가?

암호화

이쯤에서 암호화를 생각해보자. 독자들이 보내려는 비밀 메시지를 m("사랑해요")이라고 하자. 여기에 k+1을 제곱한 다음 n으로 나누면 원래의 메시지 m이 나온다. 이 식을 그대로 쓸 수는 없으니, 조금 변형해야 한다. 그래야 댓글에 m을 쓰지 않아도 내가 오일러의 공식을 사용해 m을 알아낼 수 있다.

추가 도구

m에 제곱되는 k+1를 다시 한 번 어떤 곱으로 표현해야 한다. 아래처럼 말이다.

$$k+1 = e \times d$$

그렇다면 당연히 아래와 같은 식이 성립한다.

$$m^{k+1} = (m^{e})^{d}$$

여기서 신비한 법칙이 성립한다. 좌변을 n으로 나눈 나머지를 r이라고 하자. 우변은 제곱이 두 단계에 걸쳐서 진행된다. 그런데 이 때, 먼저 안쪽의 제곱을 n으로 나눠보자. (1단계)

$$m^e \equiv n \mod s$$

그러면 임의의 숫자 s가 남을 것이다. 이제 이 나머지에다가 d를 제곱한 후 n으로 나누면... (2단계)

$$s^d \equiv n \mod r$$

r이 나온다!

예를 들어 2의 6승을 5로 나누면 나머지가 4다. 그런데 2의 6승은 이렇게도 표현된다.

$$2^6 = (2^{3})^{2}$$

이제 2의 3승인 8을 먼저 5로 나누어보면, 나머지가 3이다. (1단계) 그리고 다시 3의 제곱을 5로 나누면 나머지가 4다. (2단계) 똑같다!

복호화

나는 m을 집어넣고 k+1(e와 d의 곱)을 제곱해서 다시 m을 꺼내는 기계를 갖고 있는 셈이다. 그런데 사용자로부터 m을 받을 수 없으니, 사용자의 m에다가 e를 제곱한 후, n으로 나눈 나머지를 제출하라고 한다. 즉 1단계까지만 하고 나머지를 달라고 한다. 그 숫자에 d를 제곱한 후 n으로 나누면 m이 나오는데, 숫자 d는 나만 알고 있다.

독자들은 e만 알기 때문에 타인의 메시지 m을 알아낼 방법이 없다. 그러면서도 자신의 메시지 m을 암호로 만들 수 있는 셈이다.

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

RSA

여기까지가 RSA의 기본 원리다. 다만 모든 소수를 넣어보는 공격에 당하지 않으려면, 아주 커다란 소수를 이용해야 한다. 실제로는 그렇게 한다. 이게 RSA의 수학 원리다.

암호화 방식은 대칭키 방식과 비대칭키 방식으로 나뉘는데, RSA는 비대칭키 방식에 속한다. 비대칭키 방식은 키를 2개 사용한다. 자유롭게 공개해도 되는 공개키와 개인키(private key)가 그것이다. 우리 예시에선 e가 공개키다. 모두에게 알려줘도 된다. 그리고 d가 개인키다. d까지 알려지면 k+1이 알려지고, 그러면 누구나 m을 구할 수 있게 된다.

비대칭키 방식은 대칭키 암호화를 준비하는 데 요긴하게 쓰인다. 예를 들어보자.

대칭키를 쓰고 싶은데...

남녀공학 기숙 학교에서 여자친구와 편지를 주고 받고 싶은데, 모든 편지 내용은 사감의 검열을 받는다. RSA 방식을 쓰면 여자친구에게 이렇게 말하면 된다.

네가 하려는 말에 e를 제곱한 후 n으로 나눠서 편지를 적어보내

나도 여자친구에게 보낼 때는 여자친구가 알려준 f라는 공개키를 제곱한 후 n으로 나눠서 편지를 보내고 있다. 그런데 너무 불편하다. 그냥 하나의 키를 공유하면 훨씬 암호화도 쉽고, 복호화도 쉽다. 즉 계산이 빨라진다. 예를 들어 179라는 숫자를 서로의 키로 공유하기로 했다고 쳐보자. 비밀 메시지 m에 179를 곱한 후, 거기서 179를 빼고 보내기만 해도 메시지가 철저히 숨겨진다. 받은 쪽에서는 179를 더한 다음 나눠주기면 하면 m을 구할 수 있다.

이런 장점 때문에, 나는 대칭키가 쓰고 싶어졌다. 그럴 때 RSA를 쓰면 된다.

너랑 나만 아는 비밀키를 하나 갖고 있자. 어때? 그리고 그 키를 내게 알려줄 때만 최초 1회 RSA 방식을 쓰자.

그러면 비밀키를 공유하는 과정에서도, 그리고 그 이후에서도 사감에게 암호를 들키지 않을 수 있게 된다. 더불어 한 번 비밀키를 공유한 후부터는 대화가 아주 빨라진다는 장점이 있다. 실제로 채팅 서비스에서는 최초 1회 RSA로 비밀키를 공유하고, 그 후 대화는 비밀키를 이용하여 진행되기도 한다. 대표적인 대칭키 암호화 종류로는 AES가 있다.