"보물을 찾고 싶으면 암호를 풀어라" 쫓고 쫓기는 암호학의 세계

채진석 교수(인천대학교 컴퓨터공학과)

  “우리는 음지(陰地)에서 일하며 양지(陽地)를 지향한다.”

  이 말은 국가정보원의 전신인 중앙정보부와 안전기획부의 부훈이라고 한다. 컴퓨터과학에서도 이렇게 음지에서 일하며 양지를 지향하는 사람들이 있는데, 이들이 바로 암호학과 관련된 일을 하는 사람들이다. 이들은 음지에서 일하기 때문에 누가 새로운 암호 기법을 발견했는지, 또 누가 암호 해독에 성공했는지 등을 알 수 없는 경우가 많이 있다. 

  얼마 전 미국 중앙정보국(CIA) 박물관의 '암호문 조각'을 만든 조각가가 20년 동안 풀리지 않은 마지막 암호에 대한 결정적인 힌트를 공개했다.

CIA 본부 앞에 서 있는 조각물 '크립토스'에 새겨진 암호. CIA 내부에서도 답을 못 내놓아 문제였다.(출처:www.wired.com 사진 Adrian Gaut)

   '크립토스(Kryptos·그리스어로 '감춰진'이라는 뜻)'라는 이름을 가지고 있는 두루마리 모양의 이 암호문 조각은 1990년에 만들어졌다. 총 4개 영역(총 869자)으로 나뉜 크립토스 암호문 중 시구(詩句)·좌표·역사에 관한 내용을 각각 담은 1~3번 암호문은 미국의 컴퓨터 전문가 짐 길록리(James Gillogly)에 의해 1999년 이미 풀렸다. 그러나 4번 암호문은 지금까지 수많은 사람들의 시도에도 불구하고 정확하게 해독하는 사람이 없었는데, 이 조각을 만든 짐 샌본(James Sanborn)은 암호전문가라는 사람들이 보내오는 오답에 지쳐서 결국 2010년말에 97자로 이루어진 알파벳 암호문 중 6자를 힌트로 내놓은 것이다. 샌본이 공개한 힌트는 알파벳 중 64~69번째에 해당하는 NYPVTT가 BERLIN으로 해독된다는 것이다.

  암호의 역사를 살펴보면 여러가지 재미있는 일이 많이 일어났는데, 그 중에서도 백미를 꼽으라고 한다면 1885년 발간되어 50센트에 판매된 빌 페이퍼(Beale Papers)라는 소책자에 소개된 암호를 들 수 있다.

"보물이 묻혀있다" 솔깃하지만...

   이 책의 개략적인 내용은 서부 개척 시대에 빌(Thomas Jefferson Beale)이라는 사람이 1818년 뉴멕시코주의 산타페 근처에서 현재 가치로 따지면 한화로 약 700억원(미화 6천5백만불 상당)이 넘는 금은보화를 발견하여 버지니아주의 베드포드 카운티에 묻어 놓고, 이 보물이 묻힌 위치를 세 개의 암호문으로 나누어 자신이 자주 드나들던 여관 주인인 모리스(Robert Morriss)에게 맡겨 놓았다고 한다. 

  빌은 편지를 맡겨 놓으면서 10년 내에 자신이나 자신의 일행이 돌아오기 전까지는 암호문을 개봉하지 말라고 하고, 세인트루이스에 살고 있는 자신의 친구가 이 암호문을 풀 수 있는 열쇠가 담긴 편지를 보내 줄 것이라고 했는데, 결국 이 편지는 도착하지 않았다. 이 일을 까맣게 잊고 있던 모리스는 1843년이 되어서야 암호문을 발견하게 되었는데, 혼자서는 암호문을 해독하기 어렵게 되자, 친구에게 이 암호문을 넘겨서 해독을 부탁하게 된다. 이렇게 암호문을 넘겨받은 친구는 여러 해의 노력 끝에 거의 포기할 무렵이 되어서야 가까스로 두 번째 암호문을 해독하는데 성공하게 된다.
 

세 개의 편지에 나누어져 있는 암호문의 내용은 다음 사이트를 참조.  http://www.jimloy.com/puzz/beale.htm

빌 페이퍼의 전문은 다음 사이트에 나와 있다. http://www.unmuseum.org/bealepap.htm

   두 번째 암호문을 해독하는 열쇠가 된 문서는 너무나도 유명한 미국의 독립선언서(Declaration of Independence)였다. 빌의 암호문은 숫자와 콤마의 나열로 이루어져 있는데, 이 숫자는 어떤 문서나 책에 나와 있는 단어에 순서대로 번호를 붙인 것이다. 예를 들어, 두 번째 암호문의 맨 처음 나오는 115라는 숫자는 독립선언서의 115번째 단어를 의미하는 것인데, 독립선언서에서 115번째 단어를 찾아보면 instituted이므로 빌의 암호문은 이 단어의 첫 글자인 i로 해독된다.

  두 번째 암호문을 해독한 이후 이 소책자의 저자는 용기백배하여 다시 암호 해독에 몰입하게 되는데, 저자의 평생에 걸친 노력에도 불구하고 나머지 암호문을 해독하는 데는 실패하게 된다. 결국 암호문을 해독하느라 거의 폐인이 되다시피 한 저자는 이 일은 반드시 남는 시간에 취미 삼아 해야 하는 것이지 절대로 자신처럼 생업을 내팽개치고 가족들에게 고통을 주어서는 안된다는 교훈을 결론으로 남기고 있다.

영드 '셜록' 두번째 에피소드에 나오는 중국 고문자도 어떤 책의 페이지와 문장을 의미했죠. (운영자 쏘댕기자 주)

  역사상 문헌에 나와 있는 첫 번째 암호는 로마의 카이사르가 사용한 것으로 알려져 있는데, 카이사르는 하나의 문자 대신에 세 번째 뒤에 오는 문자를 사용하여 암호문을 작성하였다. 예를 들어, A라는 문자 대신에 세 번째 뒤에 오는 문자인 D를 사용하여 암호문을 작성하는 것이다. 이러한 암호화 기법은 컴퓨터를 사용하지 않고도 금방 풀 수 있지만, 암호라는 것을 처음으로 대하는 고대에는 꽤 어려운 것이었나 보다. 

  고대에서 최근까지 암호의 역사를 살펴보면 항상 암호 제작자들에 맞서는 암호 해독가들이 승리하여 왔다. 암호 제작자들이 아무리 복잡하게 암호를 만들어도 결국은 암호 해독가들에 의해 풀리고 만 것이다.  

  현대의 암호는 매우 복잡한 체계를 갖추고 있으므로 컴퓨터의 도움이 없이는 암호화할 수도 없고, 복호화할 수도 없다. 최근까지만 해도 암호화와 복호화에 모두 동일한 키(열쇠)를 사용하는 대칭 키 암호화 기법을 사용하고 있었지만, 암호문을 받는 모든 사람들에게 키를 안전하게 분배하는 것이 사실상 불가능하다는 것을 알게 된 이후로는 공개 키 암호화 기법이라는 것을 사용하고 있다. 대칭 키 암호화 기법에서는 키를 꼭꼭 감추는데 비해 공개 키 암호화 기법에서는 공개 키와 비밀 키로 나누어 공개 키는 전화번호부와 같이 누구나 접근할 수 있는 장소에 공개하고, 비밀 키만을 감춘다. 

  공개 키 암호화 기법은 200자리 수가 어떤 두 개의 100자리 소수를 곱해서 만들어졌는지를 아는 데는 아무리 빠른 컴퓨터를 사용한다고 해도 수백만 년의 시간이 걸린다는 소수의 성질을 사용하고 있다. 100자리 소수는 너무 큰 수이므로 2자리 소수를 사용하여 대표적인 공개 키 암호화 기법인 RSA 알고리즘을 간략하게 설명해 보자.

  우선 3개의 2자리 소수를 선택한다. 여기서는 47, 79, 97을 선택했다고 하자. 우선 세 소수 중에서 가장 큰 소수인 97을 비밀 키(s)로 삼고, 나머지 두 소수인 47과 79를 x와 y로 놓은 다음, x와 y를 곱한 결과인 3713을 N으로 놓는다. 그런 다음 간단한 수식 ps mod (x-1)(y-1) = 1 이 되는 공개 키(p)를 구하게 되는데, 이 수식을 풀어보면 만족하는 공개 키는 37이 된다. 이렇게 구한 공개 키 37과 N 값 3713이 모든 사람들에게 공개된다. (**mod에 대한 설명은 다다음 단락에 나옵니다.)

RSA 알고리즘 티셔츠도 있나 봅니다. (출처: http://marcellodesales.wordpress.com)

  공개 키 암호화 기법의 핵심은 N의 값 3713이 공개되었을 때, 이 수가 어떤 두 소수 x와 y로 곱해졌는지 알아내는데 시간이 많이 걸려야 한다는 것이다. 물론 이 예와 같이 4자리 수의 경우에는 금방 풀 수 있겠지만, N이 200자리 수가 되면 문제가 완전히 달라진다. 

  이렇게 구한 키 값과 N 값을 가지고 “AB”라는 문장을 암호화한다고 하면, A 대신 01을 사용하고, B 대신 02를 사용하여 숫자로 나타낸 다음 공개 키 37을 사용하여 102³⁷ mod 3713을 계산하면 된다. 여기서 사용된 mod는 3713으로 나눈 나머지를 반환하는 연산자이다. 이 계산은 윈도우에서 기본으로 제공하는 계산기를 사용하면 쉽게 계산할 수 있다.

  계산기를 공학용으로 설정하고 나서, 다음과 같은 과정을 따라 해 보라. ① 102를 입력 ② 'x^y' 키를 누름 ③ 37을 입력 ④ 'Mod' 키를 누름 ⑤ 3713을 입력 ⑥ '=' 키를 누름. 이러한 과정을 거치면 계산 결과로 1366이 나오는데, 이 값이 37이라는 공개 키로 암호화시킨 암호문이 된다. 복호화를 위해 비밀 키 97을 사용하여 1366⁹⁷ mod 3713의 계산을 수행해 보면, 계산 결과로 원래 숫자인 102가 나오는 것을 확인할 수 있을 것이다.

  여기서는 설명을 위해 2자리의 소수로 비밀 키와 공개 키를 만들었지만, 실제 RSA 알고리즘에서는 100자리의 비밀 키와 공개 키, 200자리의 N이 사용되고 있다.

  이러한 공개 키 암호화 기법은 현재로는 안전하다고 여겨지지만, 앞으로 누군가 200자리 수가 어떤 두 100자리 소수의 곱인지를 빠르게 알아내는 방법을 발견한다면 언제든지 해독될 수 있을 것이다. 이것이 암호 해독의 역사에서 발견되는 필연적인 역사 법칙이다.   

필자 채진석은

1964년 서울생. 어린 시절을 부산에서 보냈고, 서울대학교 컴퓨터공학과에서 1998년 박사학위를 받았다. 1997년 한국학술재단 부설 첨단학술정보센터에서 전국 대학도서관의 목록 데이터를 통합하여 종합목록을 구축하는 사업에 참여했으며, 1998년 8월부터 인천대학교 컴퓨터공학과에서 학생들을 가르치고 있다. 우리 사회의 어려운 이웃들과 친구되기 운동을 펼치는 사회복지법인 한벗재단에서 이사로 일하면서, 장애인들의 컴퓨터 사용을 도와주는 정보통신 보조기기와  접근성을 높이는 소프트웨어 개발에 힘쓰고 있다. 정보화 역기능 및 정보격차 해소에 기여한 공로로 2009년 12월 행정안전부 장관 표창을 받았다.