RSA 암호화 - RSA의 작동 원리

RSA 암호화

• RSA 암호화 - 개념편
• RSA 암호화 - 수학편: RSA와 소수
• RSA 암호화 - 수학편: 나머지 계산
• RSA 암호화 - RSA의 동작 방식
• RSA 암호화 - RSA의 작동 원리

[알림] 이 글은 RSA 암호화 시리즈의 5편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다!

---

오일러 정리

RSA 암호화에서는 페르마 소정리가 일반화된 정리 격인 오일러 정리가 핵심 역할을 한다.

오일러 정리
서로소인 두 정수 $a$와 $n$에 대해 $a^{\phi (n)} \equiv 1\:(\mathrm{mod}\:n)$이다.
여기서 $\phi(n)$은 오일러 피 함수로 $n$ 미만의 자연수 중 $n$과 서로소인 수의 개수를 말한다.

오일러 피 함수는 자기 자신보다 작은 자연수 중 자신과 서로소인 자연수의 개수를 계산한다. 만약 $n=pqr$($p,q,r$는 소수)라면 $\phi (n)$의 값은 다음과 같이 쓸 수 있다.

$\phi (n)=n(1-\frac{1}{p})(1-\frac{1}{q})(1-\frac{1}{r})$

 

이는 다음과 같은 이유로 성립한다.

1부터 $n$까지의 자연수 중
$-\frac{n}{p}$으로 $p$의 배수를 거르고, $-\frac{n}{q}$로 $q$의 배수를 거르고, $-\frac{n}{r}$으로 $r$의 배수를 거른 후
$+\frac{n}{pq}$, $+\frac{n}{qr}$, $+\frac{n}{rp}$으로 각각 $pq$, $qr$, $rp$의 배수를 더해준다. 가령 $pq$의 배수는 $p$의 배수와 $q$의 배수로 2번 빼줬기 때문이다.
마지막으로 $pqr=n$은 원래 1개 있다가 세 번 뺀 후 세번 더했으므로 한 개 남아 있다. 따라서 $-\frac{n}{pqr}$으로 1개를 빼줘야 한다.

 

이상의 정리를 $n=pq$($p,q$는 소수)에 적용시켜보면 $\phi(n)$의 값은 다음과 같다.

$\phi(n)=pq(1-\frac{1}{p})(1-\frac{1}{q})$$=pq-p-q+1$$=(p-1)(q-1)$

---

RSA의 작동 원리

여기까지 왔으면 RSA라는 게 지금까지의 원리를 벗어나서 작동하지 않는다.

 

이하의 내용에 나오는 문자는 모두 이 글에서 사용한 문자를 그대로 사용한다. 미리 보고 오면 좋겠다.

 

원문 $a$가 있다. 이 원문은 정수이다. 이를 암호화하면 암호문 $x$는 다음과 같이 생성된다.

$x=a^e\:\mathrm{mod}\:N$

 

그리고 복호화는 다음과 같이 하여 $a^{\prime}$을 얻는다. 당연히 $a=a^{\prime}$이여야 한다.

$a^{\prime}=x^d\:\mathrm{mod}\:N$

 

 

$a=a^{\prime}$임은 다음과 같이 증명할 수 있다.

$x$에 암호화하는 방법을 대입하면 다음과 같다.

$a^{\prime}=x^d\:\mathrm{mod}\:N=(a^e\:\mathrm{mod}\:N)^d\:\mathrm{mod}\:N$

 

위의 식은 다음 식으로 변형 가능하다.

$a^{\prime}=a^{ed}\:\mathrm{mod}\:N$

이가 성립하는 이유는 나머지라는 것은 먼저 계산하든 완전한 수를 얻은 후 거기에 나머지를 한 번만 쓰던 같기 때문이다. 이에 관한 자세한 설명은 이 글을 참고하면 좋겠다.

 

$ed$의 값은 적당한 정수 $k$가 존재하여 $ed=k(p-1)(q-1)+1$이라 쓸 수 있다. 이는 $e$와 $d$를 생성한 규칙에서 나온 것이다. 여기서 $(p-1)(q-1)=\phi(N)$이므로 $ed=k\phi(N)+1$이다. 이를 위의 식에 대입하면 다음과 같다.

$a^{\prime}=a^{k\phi(N)+1}\:\mathrm{mod}\:N$

 

여기서 나머지 연산의 성질(먼저 하던 나중에 한 번만 하던 결과는 같다)을 이용하면 다음과 같이 정리된다.

$a^{\prime}=(a^{\phi(N)}\:\mathrm{mod}\:N)^k \times a\:\mathrm{mod}\:N$

 

$a^{\phi(N)} \:\mathrm{mod}\:N = 1$이므로(오일러 정리) 식 중 이 부분은 1로 바꿀 수 있다. 따라서 다음과 같이 쓸 수 있다.

$a^{\prime}=1^k \times a\:\mathrm{mod}\:N$

 

1의 거듭제곱은 항상 1이고, 어떤 수이던 1을 곱하면 그대로 나오니 1은 무시하자. 그리고 $0\leq a<N$이였기 때문에 $a\:\mathrm{mod}\:N=a$이다. 따라서 다음이 성립한다.

$a^{\prime}=a$

 

원문이랑 복호화된 정보랑 일치하는 것이 증명됐다!

 

---

RSA의 보안

RSA암호를 깨고자 한다. 알고 있는 정보는 공개키뿐이고 이를 활용해서 비밀키를 알아내는 것이 목표이다.

공개키는 $N$과 $e$값이다. $N=pq$이고 $e$는 $(p-1)(q-1)$과 서로소인 어떤 정수이다.

비밀키는 $ed$를 $(p-1)(q-1)$로 나눈 나머지가 1이 되게 하는 정수 $d$로 간단히 적당한 정수 $k$에 대해 $ed=k(p-1)(q-1)+1$이다.

 

우선 $e$로는 알 수 있는 정보가 거의 없다. $(p-1)(q-1)$의 값이 몇이던 그와 서로소인 값은 엄청나게 많다. $e$는 그중 하나일 뿐이며 따라서 $e$의 값으로 $d$나 $(p-1)(q-1)$의 값을 알 수는 없다.

 

남은 방법은 $N=pq$임을 이용해서 $p,q$의 값을 각각 구하는 것이다. 이때 $p,q$는 1은 아니고 소수이다. 즉, $N$을 소인수 분해하면 $p$와 $q$의 값을 쉽게 구할 수 있지만... 이게 시간이 너무 오래 걸린다.

차세대 스펙의 RSA 암호화는 $N$이 4096비트의 정수로 거의 1200자리를 넘는 정수이다. 그럼 $p$와 $q$는 못해도 600자리의 소수일 텐데 2부터 소수들을 쭈욱 대입하는 것은 말도 안 되게 오래 걸린다.

 

이런 소인수분해의 난해함으로 RSA는 보안이 유지된다.

---

마치며

이번 글을 마지막으로 RSA 암호화에 대한 글을 마친다. 현재 RSA 암호는 세계적으로 가장 대표적으로 알려진 비대칭키 암호화 방법으로 금융거래, 인증서, SSL/TLS에서 키 교환 등 여러 보안이 중요한 분야에서 사용되고 있다.

이 글을 통해 전 세계의 인터넷 보안을 지키고 있는 RSA에 대해 더욱 깊게 이해했으면 한다.