‘창과 방패’ 암호의 세계

이 글을 읽는 독자들 중에 혹시 내기를 좋아하는 사람이 있다면, 30명이 넘는 사람들이 모여 있는 동창회 모임 같은 곳에서 다음과 같은 내기를 해 보라.

어떤 축구장에 23명의 사람들이 있다고 하자. 축구의 한 팀은 11명이므로 2개 팀이면 선수가 22명이고, 여기에 심판 1명을 포함하여 23명의 사람들이 모여서 축구 경기를 시작하려고 한다. 문제는 이 축구장에 모여 있는 23명 중에 생일이 같은 사람이 한 쌍 이상 있느냐이다. 축구장에는 다양한 연령대의 사람들이 있을 수 있으므로 출생 연도는 신경 쓰지 않고 생일만을 고려한다고 하자. 1년이 365일이고, 두 사람의 생일이 같을 확률은 365분의 1이므로 23명 정도로는 생일이 같은 사람이 한 쌍 이상 나올 가능성이 매우 낮다고 생각할 것이기 때문에 대부분의 사람들은 생일이 같은 사람이 없다는 쪽, 즉, 모든 사람의 생일이 다를 것이라는 쪽에 내기를 걸 것이다. 그런데 이 경우 확률을 계산해 보면 최소한 2명이 같은 생일을 가질 가능성은 50%를 약간 넘는다. 즉, 23명이 있는 모임이라면 내기에서 이길 확률은 반반이다. 

똑같아 보이지만 오른쪽이 진짜 그림인 반면 왼쪽은 장문의 메시지를 숨겨놓은 암호그림. (경향신문DB)

 

그러나 모임 인원이 30명 이상이 된다면 이야기가 완전히 달라지는데, 30명의 경우 이길 확률은 70%가 넘고, 40명이면 이길 확률이 90%에 육박하게 된다. 필자는 알고리즘 강의 시간에 가끔씩 이 문제를 가지고 학생들과 내기를 하곤 하는데, 아직까지 수강생 수가 30명이 넘는 경우에 내기에서 졌던 적은 없었다.

이것을 암호학에서 사용하는 용어로는 생일 공격(birthday attack) 또는 생일 역설(birthday paradox)이라고 부른다. 기본적으로 암호를 만들기 위해서는 키(key)라는 것이 필요한데, 생일 공격 이론에 따르면 365개의 키 값 중에 23개만 골라내도 같은 키 값을 가진 것이 나올 가능성이 50%를 넘게 되므로, 암호해독을 할 때 키 값을 모두 대입하지 않아도 동일한 키 값을 찾아낼 확률이 높아지는 것이다.

현대인의 일상생활은 본인이 의식하든지 의식하지 않든지 관계없이 암호와 밀접하게 관련되어 있다. 본인의 일기를 부모님이 보지 못하도록 암호화하는 매우 초보적인 것에서부터 은행을 통해 인터넷 뱅킹을 할 때 사용하는 복잡한 것에 이르기까지 암호는 우리 삶의 구석구석에 깊숙이 뿌리 내리고 있는 것이다.

그런데 암호화된 문서는 기본적으로 사람들의 호기심을 불러 일으켜서 암호화할 때 사용한 키 값 없이 암호문을 알아내려는 시도를 하게 하는데, 이것을 암호해독이라고 부른다. 

현재 우리가 사용할 수 있는 암호화 방법은 여러 가지가 있는데, 이 중에는 해독이 쉬운 것도 있고 어려운 것도 있다. 암호문을 만들 때 기본적으로 고려해야 할 것은 암호해독을 원하는 사람이 얼마나 많은 비용을 지불할 것인가 하는 점이다. 예를 들어, 본인의 일기를 암호문으로 만든 경우 부모님은 암호해독을 위한 비용을 거의 지불하려 하지 않을 것이므로 가장 간단한 암호화 방법이면 충분할 것이다. 그러나 국가 간의 전쟁 중에 공격 명령을 암호화하는 것이라면 상대국에서 아무리 많은 비용이 들더라도 암호해독을 하려 할 것이므로 이 경우에는 가장 복잡하고 안전한 암호화 방법을 사용해야 할 것이다.

<페르마의 마지막 정리>라는 책으로 유명한 사이먼 싱이 쓴 <암호의 과학>이라는 책에 보면, 컴퓨터의 아버지로 부르는 앨런 튜링이 2차대전 중에 독일군의 암호를 해독하는 이야기가 소개되어 있다. 당시 영국에서는 수학자, 과학자, 언어학자, 고전학자, 체스 전문가, 십자말풀이 전문가 등 다양한 사람들이 팀을 이루어 독일군의 암호를 해독하는 일을 하고 있었는데, 튜링은 이곳에서 일하면서 천재적인 재능을 발휘하여 독일군의 암호문에 일정한 형식이 있다는 것을 알아차리게 된다. 예를 들어, 독일군은 날마다 새벽 6시가 조금 지났을 때 일기예보를 암호화해서 송신하고 있었다. 그러므로 오전 6시5분에 도청된 암호문에 날씨라는 독일어 wetter가 들어 있을 확률은 거의 100%에 가깝다는 것을 알게 된 튜링은 이러한 힌트를 사용하여 독일군의 암호문을 해독하는데 큰 공을 세우게 된다.

인류의 역사는 암호와 밀접한 관계를 가지고 있다. 

암호는 전쟁의 승패를 뒤바꾸기도 했고, 수많은 왕과 왕비의 목숨을 앗아가기도 했으며, 누군가 새로운 암호화 방법을 개발하면 곧이어 또 다른 누군가가 암호를 해독하는 방법을 개발하여 왔다. 

따라서 지금까지 인류가 만들어 놓은 암호화 방법 중 아직 해독 방법을 모르는 것이 있더라도 언젠가는 누군가가 해독하는 방법을 찾게 될 것이고, 또 다른 누군가는 아무도 풀지 못하는 새로운 암호화 방법을 개발할 것이다. 

그런 의미에서 암호를 공부하는 것은 자신이 창의적이라고 생각하는 사람이라면 평생을 걸고 도전해 볼만한 가치가 있다.