RSA 공개 열쇠의 이해.

‘RSA 공개 열쇠 방식’의 암호화는 다음의 3단계 과정이 필요하다.

1단계 : 공개 열쇠 만들기.

1. 암호를 받는 쪽에서는 아무거나 두 소수, p와 q를 생각한다.
2. p와 q를 곱해 N을 만든다.

3. 아무 숫자나 다음 식을 만족하는 두 숫자를 생각한다.

1=(e*d)mod[(p-1)(q-1)]

4. mod()는 나머지를 구하는 함수다. 40mod(7)은 40을 7로 나눈 나머지를 구하라는 말이다. 답은 5다.

5. N과 e는 공개 열쇠다. 전화로 불러줘도 되고 사람들에게 알려줘도 된다. 전혀 문제가 없다.

2단계 : 암호 만들기.

1. 이제 암호를 만드는 쪽에서는 공개 열쇠 N과 e를 써서 암호를 만들어보자. 문제는 다른 사람들도 모두 이 공개 열쇠를 알고 있다는 사실이다. 열쇠는 공개돼 있지만 받는쪽에서만 풀 수 있어야 한다.

2. 먼저, 문서의 모든 글자를 이진수로 바꾸고 다시 십진수로 바꾼다. 이 숫자를 M이라고 한다. 우리는 지금부터 M을 암호로 바꾼다.

3. 다음 식을 써서 암호 C를 만든다.

C=M^emod(N)

3단계 : 암호 풀기.

1. 암호 C를 받아서 원래 문서 M으로 풀어보자.
2. 공식은 간단하다. N과 d를 집어넣으면 된다.

M=C^dmod(N)

3. N과 e는 공개돼 있지만 다른 사람들은 p와 q를 알 방법이 없다. 한번 더 계산해서 만든 d는 더 알 수 없다.

백문이 불여일견, 예제를 풀어보자.

1단계 : 공개 열쇠 만들기.

1. 이정환은 두 소수 11과 17을 생각하고 곱해서 공개 열쇠 N을 187로 잡는다.

2. 이정환은 대충 d를 23로 놓고 다음 공식에 넣어서 공개 열쇠 e를 7으로 잡는다.

1=(e*d)mod[(p-1)(q-1)]

1=(7*23)mod(10*16)
1=161mod(160)

3. N과 e, 187과 7을 공개한다. 얘들아, 우리 이걸로 암호 만들거다. 풀 수 있으면 풀어봐라.

2단계 : 암호 만들기.

1. 백우진은 ‘X’를 암호화하려고 한다. 이진수로 바꾸면 1011000, 다시 십진수로 바꾸면 M은 88이 된다. 백우진은 M을 공개 열쇠 N과 e, 187과 7을 써서 암호로 바꾼다.
2. 공식에 집어넣는다.

C=M^emod(N)

C=88⁷mod(187)
C=40867559636992mod(187)
C=11

3. 40867559636992을 187로 나누면 나머지가 11이 나온다는 이야기다. 11이 암호다. 11를 이정환에게 보낸다.

3단계 : 암호 풀기.

1. 이정환은 이제 암호 C, 11을 풀어 원래 숫자 M을 찾아내야 한다.

2. 공식에 집어넣는다. N과 d는 각각 187과 23이다.

M=C^dmod(N)

M=11²³mod(187)
M=895430243255237372246531mod(187)
M=88

3. 88, 암호를 풀었다. N은 공개 열쇠지만 d는 이정환만 아는 숫자다. 처음에 생각한 숫자 p와 q를 곱해서 N을 만들고 이걸 조합해서 d와 e를 만들었는데, 공개된 N과 e만 가지고 d를 찾기는 굉장히 어렵다. 거의 불가능하다.

‘RSA 공개 열쇠 방식’은 MIT 컴퓨터 사이언스 실험실의 론 리베스트와 아디 샤미르, 레너드 애들먼, 세 사람이 발명했다. RSA는 이들의 머릿글자 모음이다. 이 암호화 방식의 핵심은 소인수 분해에 있다.

두 소수 p와 q를 곱해서 공개 열쇠 N을 만들면 이걸 쥐고 아무리 난리법석을 떨어도 원래 숫자를 찾을 방법이 없다.

35가 5와 7로 나눠져 있다는 건 쉽게 알 수 있다. 소인수 분해는 하나하나 숫자를 맞춰보는 수밖에 딱히 방법이 없다. 숫자가 커지면 슈퍼컴퓨터를 돌려도 몇십년씩 걸린다. 17과 19607843을 곱하면 333333331이 된다는 건 쉽게 알 수 있지만 그걸 찾기가 어렵다는 이야기다. 실제로 수학자들은 수백년동안 이 숫자가 소수라고 생각해왔다.

여기서 문제를 한번 더 뒤집어 공개 열쇠를 두개 만들어 놓고 이걸 꼬아서 혼자만 아는 결정적인 열쇠 d를 만들어 놓으면 당신의 암호는 거의 완벽하다고 할 수 있다.

위의 예제에서 공개 열쇠 N과 d는 각각 187과 23이다. 이걸 풀려면 N이 먼저 뭐와 뭐의 곱인가 알아야 한다. 그리고 그 뭐와 뭐에서 각각 1을 뺀 숫자의 곱을 구하고 거기서 다시 1을 뺀 수가 d의 몇배인가도 알아야 한다. 몇배인가만 알면 암호는 풀리겠지만, 한번 해봐라. 결코 만만치 않다.

187 정도면 어떻게 풀릴 수도 있지만 보통은 자릿수가 308 이상이다. 한번 보겠는가.

42862803482534211706798214808651328230664709384460955058223172
53594081284811174502841027019385211055596446229489549303819644
28810975665933446128475648233786783165271201909145648566923460
34861045432664821339360726024914127372458700660631558817488152
09209628292540917153643678925903600113305305488204665213841469
51941511609433057270365759591953092186117381932611793105118548
0744699627495237

이게 308자리 숫자다. 이게 뭐와 뭐, 두 소수의 곱으로 돼 있는가 맞춰봐라. 이 정도면 1억대의 PC를 한꺼번에 돌려도 1000년이 넘게 걸린다고 한다. 현재의 과학기술로는 이런 암호를 풀 방법이 없다.

도움 말씀 : 백우진.
참고문헌 : ‘코드북’, ‘현대수학의 여행자, ‘수학: 양식의 과학’, ‘영부터 무한대까지’, ‘수학의 황제 가우스’.