숫자를 이용하는 암호학

 

냉전시대가 끝나면서 첩보원들은 더 이상 할 일이 없어진 것일까?

사실 암호는 군사용으로 주로 사용되어 왔으나 현대에는 우리의 일상생활과 밀접한 관계를 가지게 되었다.

정보의 초고속도로라 불리는 인터넷에서 중요한 데이터를 주고 받는 경우는 암호가 필수적이다. 이렇게 인터넷까지 생각하지 않더라도 은행 현금지급기를 사용할 때 우리는 비밀 번호를 사용한다.

사회가 발전하고 복잡해 질수록 암호학은 더욱 필요하게 되는 것이다. 이러한 곳에 필요한 암호는 수학적 이론에 바탕을 두고 있다.

그러나, 1920년대까지만 하더라도 문자를 다른 문자로 바꾸는 대치암호, 문자의 위치를 적당히 서로 바꾸어놓아서 다른 사람이 알아보지 못하도록 치환한 전치암호 또는 이 두 가지를 혼합한 곱암호 등이 사용되었다. 그 이 후 1950년대까지는 기계를 이용하여 복잡하게 대입과 치환을 동시에 적용한 암호체계가 사용되었다. 이 암호체계는 독일이 사용한 ENIGMA와 미국이 사용한 M-209 등이 있다. 그러나, 이 방법은 컴퓨터의 등장으로 너무 쉽게 해독되어 더 이상 사용할 수 없게 되었다.

컴퓨터 시대에 사용되는 암호는 다양하며 암호화 과정과 복호화(풀이) 과정에 모두 컴퓨터를 사용한다.

오늘날 사용되는 암호 중에는 공개키 암호체계라는 것이 있다. 이것은 암호화 과정과 복호화 과정이 모두 공개되어 있는 암호체계이다. 그러나 쉽게 공격할 수 없는 것은 소인수분해의 어려움 때문이다. 이것은 1977년 미국의 MIT대학의 Ronald Rivest, Adi Shamir 그리고 Leonard Adleman 세 사람이 고한한 방법으로 RSA 공개키 암호체계라 불린다. 이 암호는 오늘날 매일 수백, 수천만 번씩 사용되고 있는 암호체계이다. 이 암호체계의 밑바탕에는 아래의 정리가 사용되고 있다.

가 소수라면 보다 작은 모든 자연수 에 대하여 로 나누어 진다. 다른말로 하면, 로 나누었을 때, 항상 나머지가 1이다.

이 정리는 페르마의 작은 정리라고 한다. 이 정리는 350년 전에 이미 증명되었다.

 

RSA 암호 보기

이제 RSA 암호체계에 따른 암호화와 복호화에 대하여 간단한 숫자를 이용하여 예를 들어보자. 여기서는 두 개의 숫자의 쌍 (7, 143)을 사용하기로 하고 이것을 모든 사람이 알 수 있도록 공개한다. 실제로 암호화에는 이런 작은 수가 아니고 두 수 모두 수백자리가 되는 매우 큰 숫자를 사용한다. 이와 동시에 공개 숫자를 만들어 공개한다. 여기서는 103이라는 수이다. 물론 이들 수는 아무렇게나 선택한 것이 아니고 암호화 규칙에 따른 숫자들이다. 알려진 숫자는 복호화 할 수 있는 열쇠는 없는 수이다. 대신 복호화 열쇠는 암호화 된 메시지를 받는 쪽에서만 알고 있다. 이 수는 다른 어떤 사람에게도 전달될 필요가 없다. 이들 숫자가 어떻게 나온 것인지 뒤에서 설명하기로 한다.

 

공개 숫자 (7, 143)을 이용하여 143 이하인 비밀 번호를 암호화 하는 방법

 이제 W를 143 이하인 스위스 은행 비빌 계좌번호라고 하자. 메시지를 보내는 사람은 이 번호를 안전하게 받을 사람에게 보내고자 한다. 보내는 사람은 을 계산한 다음 을 143으로 나눈 나머지를 계산한다. 여기서 7은 공개된 첫 번째 숫자이고, 143은 두 번째 숫자이다. 즉,

           ( )

이다. 이 때, 가 바로 암호화 된 것이다.

 

복호화(암호 풀기)

받는 사람이 받은 것은 이다. 이제 를 풀어서 를 찾아 내어야 한다. 이제 받는 사람은 을 계산한다. 이 때, 103은 받는 사람만이 알고 있는 비밀 번호이다. 의 계산 결과를 143으로 나누어 나머지를 찾아낸다. 즉,

            ( )

이다. 놀라운 사실은 는 항상 보낸 사람의 원래의 숫자인 와 같다는 것이다.

 

실제 숫자를 이용한 보기

이제 스위스 은행 계좌번호가 71이라고 해 보자.

받는 사람

보내는 사람

(7, 143)이라는 공개 암호키를 공개하여 누구나 알 수 있도록 한다.

그러나 복호화 암호인 103은 아무에게도 알려주지 않는다.

 

 

"71"이라는 계좌번호를 보내기를 원하는데, 암호화 공개키(7,143)을 안다.

을 계산한 다음 143으로 나누어 나머지 124를 얻는다. 이 124가 바로 71을 암호화 한 것이다. 받는 사람에게 124를 보낸다.

받는 사람은 암호화 된 숫자인 124를 받는다.

복호화 비밀 번호 103을 이용하여 을 계산한다. 이 계산 결과를 143으로 나눈 나머지를 구하면 71을 얻는다. 원래 보내는 사람이 보내고자 한 비빌 번호이다.

 

 

실제로 은 9,095,120,158,391이고 143으로 나눈 나머지는 124이다.

또,

41921187047849896446113000569294530888483668997732

04563462712256522091467113393955570394059267518521

20295128082399197025904149290880430936965565127870

27350058759384015077439569484127475589434834019120

3449588494106624 

이다. 매우 큰 수이지만 143으로 나눈 나머지는 71이다.

물론 우리가 문자로 된 메시지를 보내고자 한다면 문자를 치환하는 등의 방법으로 숫자로 바꾸어 앟호화 한 다음에 보낼 수 있다. 이 때에도 보낸 사람이 보낸 숫자를 받는 사람이 받아서 숫자 103으로 지수를 취하고 143으로 나눈 나머지를 구하면 숫자로 된 메시지를 얻을 수 있고 숫자를 문자로 치환하면 원래 메시지를 얻는다.

 

의문점

위의 보기에서 사용한 방법은 여러 가지 의문점이 있다. 예를 들면

1. 실제로 사용하는 숫자는 7, 143 등이 아니고 수백자리나 되는 큰 수를 사용한다. 예를 들어 수백자리인 두 수 , 에 대하여(컴퓨터를 사용한다고 하더라도) 실제로 을 계산할 수 있는가?

2. 여기서 7, 143, 103은 어디서 나온 숫자인가?

3. 어떻게 이러한 암호화, 복호화가 실제로 맞아 주는가? 그저 놀라운 현상일 뿐인가?

 

큰 수에 대한 큰 지수는 계산 가능한가?

답은 불가능하다는 것이다.

앞에서 을 계산하였을 때 200자리가 넘는 큰 수가 나왔다.

문제  두 수 , 를 모두 100자리 수라고 하자. 이 때, 를 계산한 결과를 종이에 쓸 수 있을까?

답은 불가능하다는 것이다. 실제로 은 약 자리 수가 된다. 현재 이 우주에 있는 모든 원자를 모두 합하여 개 이내라고 보고 있다. 과는 비교가 되지 않을 정도로 작은 것이다. 그러므로, 자리 수를 나타내려면 우주의 모든 원자 하나하나에 엄청나게 많은 수를 기록해야 할 것이므로 불가능하다. 이렇게 어떤 컴퓨터도 계산할 수 없는 수라면 과연 어떻게 계산할 수 있을까?

실제로 우리가 원하는 숫자는 계산 과 같은 계산 결과가 아니고 어떤 수로 나눈 나머지이다. 이 나머지는 쉽게 계산할 수 있다.

 

암호화에 사용된 숫자는 어디서 온 것일까?

 

숫자 7, 143, 103은 어떻게 얻은 수일까?

받는 사람은 다음과 같은 방법으로 숫자 7, 143, 103을 선택한 것이다.

받는 사람의 준비

두 개의 서로 다른 소수 를 선택한다. 여기서는 11과 13 이다. 다른 사람은 이 두 소수를 알지 못한다.

두 소수를 곱한다. 여기서는 을 얻는다. 이것이 바로 공개 암호키 두 수 중 하나이다. 실제로는 곱이 알려지더라도 숫자가 너무 커서 소인수분해를 할 수 없기 때문에 두 수가 어떤 수인지 알 수 없다.

두 소수에서 각각 1을 뺀다. 여기서는 11-1=10, 13-1=12 이다. 이 두 수 모두와 서로소인 하나의 수 를 임의로 선택한 다. 여 기서는 10과 12의 곱 120과 서로소인 7을 선택하였다. 이것이 다른 하나의 공개 암호키이다.

두 수 120과 7을 사용하여 두 정수 d와 y를 찾는다. 이 두 정수는 7d-120y=1이 되는 수이다. 여기서는 이므로 d는 103이다. 이것이 복호 화 과정에서 사용할 키이다. 이 수는 받는 사람만 알고 있다. 103을 계산을 통해 알아낼 수 있는 것도 받는 사람뿐이다. 143을 소인수분해할 수 있는 사람은 받는 사람뿐이기 때문이다.

 

이와 같은 방법으로 , , , 를 선택하여 암호화, 복호화하면 항상 맞아준다.

 

왜 틀림 없을까?

이 질문에 대한 해답은 정수론의 이론을 필요로 한다. 앞에서 말한 작은 페르마의 정리가 기본적으로 사용된다. 수학을 좀 더 공부하여 RSA공개키 암호에 대한 이론과 실제를 알아 보고 보다 더 간편하면서도 깨기 어려운 암호체계 만들기에 도전해 보자.암호학을 공부한 사람은 사회에서 대접을 받고 있다.암호학은 수학적 이론이 실제로 유용하게 활용되는 좋은 예라고 할 수 있다.

수학을 공부하는 것은 시간낭비이거나 쓸데없는 일이 아니다.