RSA 암호 체계의 수학적 이해(인수분해와 정수)

 

우리는 주변 사람들과 대화를 할 때 자주하는 말이 있습니다.

‘사람 사는거 비슷해?’

 

위 말처럼 대부분의 사람들이 비슷한 공감대를 가지고 있습니다. 수학도 마찬가지입니다. 누구에게나 어려운 부분이 있고 쉬운 부분이 있습니다.

 

고등학교 인수분해가 기억 나시나요?

 

곱셈공식의 경우 계산 과정이 복잡하기는 하지만 시간만 충분히 주어져 있다면 누구나 해결할 수 있습니다. 그러나 인수분해는 다릅니다. 조금만 어려운 식이 나오면 대부분의 학생들이 문제를 해결하지 못합니다.

 

이는 숫자의 곱셈과 소인수분해에서도 나타납니다. 엄청나게 큰 수라 할지라도 곱하는 것은 문제가 되지 않습니다. 하지만 반대는 어떻까요?

 

48916027을 소인수 분해 해볼까요?

.

.

.

어렵죠? 6991과 6997이라는 두 소수의 곱입니다. 네 자리의 소수의 곱을 소인수분해 하는 것도 쉽지 않다는 것을 알 수 있습니다. 컴퓨터로 계산해도 우리와 다르지 않습니다. 48916027을 1부터 차례로 나누면서 나누어 떨어지는 것을 확인할 뿐입니다.

 

연산이 늘어나면 시간이 오래 걸리고 그 말은 소인수분해가 어려울 뿐이라는 것을 반증할 뿐입니다. 이러한 사실은 수학을 배운 누구나 알고 있습니다.

 

하지만 아는 것을 이용할 생각을 하는 것이 포인트입니다. 이러한 만들기는 쉬우나 원래의 상태로 돌리기는 어렵다는 성질을 보고 이걸 이용해 암호를 만들려고 생각한 것이 RSA암호 체계입니다.

 

일반적인 문장인 평문을 일정한 규칙 혹은 기호로 고쳐 놓은 것을 암호문이라고 합니다. 평문을 암호문으로 변환하는 것을 암호화, 암호문을 평문으로 바꾸는 것을 복호화라 합니다.

 

이와 관련되어 암호화를 하는 암호기법과 암호해독을 연구하는 암호학도 같이 발전되어 갔습니다. 오늘은 이중 공개키 알고리즘 중 가장 널리 알려져 있는 RSA암호 체계에 대해서 알아보겠습니다.

 

먼저 설명을 위한 개념으로 정수론의 몇 가지 개념을 배울 것입니다. 아래 써 있는 내용은 복잡해 보이지만 생각보다 쉽습니다.

 

1. 유클리드 알고리즘(유클리드 호제법)

2. modulus라는 합동식을 나타내는 기호 (mod)

a≡0 (mod m) ⇔ m | a

a≡b (mod m) ⇔ a – b ≡ 0 (mod m)

3. Z_m = {0, 1, ..., m-1}은 법 m에 관한 완전잉여계, (Z_m)^* = {r∊Z_m | (r, m)=1} 기약잉여계

4. 합동식의 해의 존재성

5. (Z_m)^* = {r∊Z_m | (r, m)=1} 기약잉여계, φ(m) = |(Z_m)^*| , φ:N -> R를 Euler의 φ함수

6. Euler 정리

7. Fermat 정리

 

를 배우고 RSA 암호 체계에 대한 설명을 해보도록 하겠습니다.

 

영상으로 2~3편 정도로 예상하고 있습니다.

1편 : https://youtu.be/q3SX1JFUM8Q

2편 : https://youtu.be/RmXivbnu7k8

3편 : https://youtu.be/v_xZ7AUJsoU