[理知논술/고교 교과 논술]<2>소수와 암호

입력 2006년 3월 28일 03시 00분

코멘트: 개

좋아요: 개

정수론은 고교 수학 교과서에서 1학년 1학기에 다루고, 수학의 여러 영역 중 중요한 영역이며, 또 현대인의 실생활에 필수적인 은행의 전자결제 시스템을 비롯한 전자상거래를 가능하게 한 수학이론이다. 수학교과의 암기된 지식이나 풀이 과정 혹은 단답형 답안을 피해야 하는 통합논술 수리영역의 출제자 입장에서 보면 가장 매력적인 주제가 정수론이고 그중에서도 암호이론이 아닐까.

[제시문1]

줄리우스 카이사르는 각각의 알파벳을 그보다 3개 앞에 있는 알파벳으로 대치하는 방식을 이용한 암호를 사용하였다. 고대 로마는 J, U, W가 없는 23개의 알파벳을 사용하였다. 카이사르의 암호 열쇠는 다음과 같다.

보통 알파벳

암호

카이사르(Caesar)의 이름을 이 방식으로 표기하면 ‘FDHXDV’가 된다. 이 방법은 ‘카이사르 방식’으로 알려져 왔다.

[제시문2]

다른 언어도 마찬가지지만 영어 문장에 사용하는 알파벳은 각자 고유한 출현 빈도를 가지고 있다. 오른쪽의 표는 이 빈도를 설명하고 있는데 띄어쓰기 기호나 따옴표 등은 제외했다. 오른쪽 위의 표는 1982년 영국의 베커가 신문과 소설 등을 두루 조사해 10만362개의 문자에 대한 출현 빈도를 계산한 것이다.

[제시문3]

문자	상대적 빈도(%)	문자	상대적 빈도(%)
a	8.167	n	6.749
b	1.492	o	7.507
c	2.782	p	1.929
d	4.253	q	0.095
e	12.702	r	5.987
f	2.228	s	6.327
g	2.015	t	9.056
h	6.094	u	2.758
i	2.966	v	0.978
j	0.153	w	2.36
k	0.772	x	0.15
l	4.025	y	1.974
m	2.406	z	0.074

(1) 하나의 자물쇠로 잠긴 금고를 다른 사람에게 보내는 경우, 받는 사람이 그 금고를 열어 보기 위해서는 두 사람의 열쇠가 반드시 일치해야 한다. 보내는 사람이 자신의 열쇠로 자물쇠를 잠가 금고를 보내면 받는 사람도 자신의 열쇠로 바로 그 자물쇠를 열 수 있어야 하기 때문이다.

(2) A, B 두 사람이 서로 다른 두 개의 자물쇠 열쇠를 가지고 있는 경우에는 사정이 좀 복잡해진다. 이때 A가 B에게 금고를 안전하게 보내는 방법은 다음과 같다. A가 자신의 열쇠로 a 자물쇠를 잠근 후 B에게 보낸다. B는 자신이 가진 열쇠로 b 자물쇠를 잠그고 a, b 두 개의 자물쇠가 모두 잠긴 금고를 A에게 다시 전달한다. A는 자신의 열쇠로 잠겨 있는 a 자물쇠를 연다. 그러면 금고는 B가 잠근 b 자물쇠로 잠겨 있는 상태가 된다. 이 상태의 금고를 B에게 보내면 B가 다시 자신의 열쇠로 b 자물쇠를 연다. 이때 금고가 전달되는 과정에서는 항상 잠긴 상태에 있으므로 A, B 이외의 타인은 금고를 열 수 없다.

(3) 두 소수 p=887과 q=997의 곱이 884339임을 계산하기는 쉽지만, 거꾸로 884339를 소인수분해하여 두 소인수 887과 997을 찾는 것은 간단하지 않다. p와 q가 130자리이면 현재의 계산 방법과 컴퓨터로 이를 소인수분해하는 데 1개월 정도 걸리고, 400자리이면 1010년이 걸린다. 이 사실을 이용하면 전자상거래나 은행의 전자금융거래에서 쓰일 수 있는 암호 체계를 만들 수 있다. 예를 들어 당신의 주민등록번호에 400자리의 두 소수의 곱을 곱해서 정보를 전달하면 이 정보가 비록 도중에 해킹당해서 타인에게 노출되더라도 해킹한 사람이 당신의 주민등록번호를 알아내기 위해서는 1010년 이상의 시간이 걸리게 될 것이다.

문제 1

카이사르의 암호체계와 같이 알파벳을 일대일로 치환해서 암호화하는 경우, 비록 그 치환방법을 복잡하게 바꾸더라도 치명적인 약점에 노출된다. 만일 당신이 암호분석가이고 당신의 책상 위에 놓여 있는 암호가 알파벳을 일대일로 치환하여 만들었다는 사실을 알고 있다면 당신은 어떠한 방법으로 암호를 해독하겠는가?

문제 2

전자금융거래를 이용하여 은행거래를 하고자 하는 당신은, 당신의 주민번호를 은행에 안전하게 전달하고자 한다. [제시문3]의 (3)에서 제시한 사실과 (2)에서 제시한 금고 전달 방법을 이용하여 중간에 경유하는 컴퓨터가 해킹당할지라도 당신의 주민등록번호를 안전하게 전달할 수 있는 가장 단순한 체계도를 제시하고, 그 방법이 타당함을 서술하라.

문제 3

카이사르의 암호체계와 당신이 작성한 암호체계를 비교하여 각각의 장단점을 서술하여라.

▽문제 해결의 실마리▽

문제 1

입수된 암호의 문장이 길거나, 혹은 여러 문장을 확보하고 있다고 생각해 보면 의외로 쉬운 문제이다. 그 암호문에서 출현 빈도가 가장 높은 문자는 사실 알파벳 e를 암호로 바꾼 문자일 가능성이 높다. 만일 당신이 꽤 많은 암호문을 확보할 수 있다면 그 가능성도 매우 높아질 것이다.

문제 2

[제시문3]의 (2)에서 주민등록번호를 금고로, 열쇠를 매우 큰 소수의 곱으로 치환해서 생각해 보면 문제가 요구하는 암호전달 체계를 만들 수 있다. 그러면 자물쇠는 ‘주민등록번호×매우 큰 소수’가 될 것이다. 만일 컴퓨터가 해킹을 당해서 누군가 이 정보, 즉 주민등록번호와 매우 큰 두 소수의 곱을 알아낼지라도 당신의 주민등록번호를 알아내는 데는 인류가 지금까지 살아온 시간보다 훨씬 더 많은 시간이 걸리게 될 것이다.