암호 문제 풀이 Cryptography

앞에 올린 암호 문제를 약 8일간에 걸쳐 풀어내고 나서 다시 같은 게시판에 올린 글이다.
--------------------
2000년 11월 15일 수요일 오전 5시 58분

제목: 정체불명의 암호문을 해독하고 나서

1. 들어가며
얼마 전에 게시판에 정체불명의 암호문 해독 문제를 낸 적이 있다. 이 글은 그 해독과정을 설명하기 위한 것이다. 가장 먼저 해독한 사람에게 멋진 저녁식사를 대접하려고 했는데 문제를 낸 본인이 먼저 풀어버려서 가족끼리 외식이나 해야겠다.

이 문제는 본인이 암호해독을 공부해 보다가 실전을 접해보기 위해 인터넷을 뒤지던 중 스웨덴의 Royal Institute of Technology라는 대학의 "Foundation of Cryptanalysis" 2000년 봄학기 강의에 나왔던 숙제를 발견하고 그 중 한 문제를 발췌한 것이다.

2. 암호해독
주어진 암호문이 어떤 방식으로 암호화 되었는지, 원문의 언어가 무엇인지도 모르는 상황이기 때문에 우선 암호문 자체의 특성부터 파악해 봄으로써 실마리를 찾아야 했다. 맨 먼저 가장 쉽게 해볼 수 있는 것이 빈도 분석이다. 즉, 암호문 내에 나타나는 각 알파벳 문자의 개수를 세어보는 것이다. 모든 언어는 각 알파벳 글자들의 쓰임이 고르지 않고 편중되게 나타나는 특성이 있다. 즉, 영어의 경우는 E가 대략 전체 문장의 12%를 차지할 정도로 심한 편중현상을 보이고 그 외에 T, N, R, O, A, I, S 등의 순으로 그 빈도가 높게 나타난다. 반면 X, Z 등은 거의 나타나지 않는다. 만약 단순치환방식, 즉 A->C, B->D, C->E, D->F, ..., Y->A, Z->B와 같은 일대일 변환방식이 쓰였다면 (예: ATTACK->CVVCEM) 글자 자체는 바뀌었다 하더라도 원문의 글자들이 가지고 있던 특성은 그대로 유지된다. 위의 변환 규칙의 경우 E가 치환된 G가 암호문에서 가장 높은 빈도로 나타날 것이다.

이러한 글자 편중 현상을 정량적으로 분석하는 방법 중에 Index of Coincidence라는 것이 있다. 간단히 설명하면, 만약 어떤 문장이 완전히 random하게 구성되어 있다면 임의의 두 글자를 택했을 때 그 두 글자가 동일한 글자일 확률은 1/26 (=0.0385)이다. 반면 만약 평문 (plaintext)에 대해 위와 같은 확률 분석을 해보면 그 값은 0.0385보다 훨씬 높게 나타나고 (문자빈도의 편중현상 때문에), 영어의 경우는 약 0.0667의 값을 갖는다. 주어진 문장에서의 확률을 구해보고 그 값과 random 문장일 때의 값과를 비교한 수치가 Index of Coincidence (IOC)이다. IOC가 1에 가까울수록 random text의 특성을 갖는 것이고 1.73 (0.0667/0.0385)에 가까울수록 평문의 특성을 갖는다. 만약 주어진 암호문이 평문의 특성을 갖는다면 그것은 단순치환이 사용되었거나 아니면 transposition, 즉 글자자체는 변환하지 않고 글자의 위치만 바꾸는 방식이 쓰였다고 볼 수 있다.

문제에 주어진 암호문에 대해 IOC를 계산해보면 약 1.06의 값이 나온다. 이것은 거의 1에 근접한 것으로 알파벳의 모든 글자가 골고루 쓰이고 있음을 보여준다. 이 계산을 통해 적어도 한 글자 단순치환방식은 아니라는 것을 알 수 있다. 다음에 고려해봐야 하는 것은 두 글자씩 짝을 지어 치환됐을 가능성이다. 즉 ATTACK의 경우 AT, TA, CK로 나눈 뒤 각각을 한 단위로 치환하는 것이다. 이런 방식이 쓰였는지 알아보는 방법은 위의 IOC 방법을 확장하여 계산하면 된다. 즉, 위에서는 random일 때 1/26이었지만 두 자 치환의 경우는 1/(26*26)이 된다는 점만 다르다. 주어진 암호문을 이 방식으로 계산해보면 IOC_2 값이 1.16이 나온다. 역시 random인 1에 가까운 값이다. 따라서 어떤 형태든 단순치환은 쓰이지 않았다는 것을 뜻한다.

여기서 본인은 암호문이 복합치환 (polyalphabetic) 방식을 사용했을 것이라는 쪽으로 방향을 잡았다. 복합치환은 한 개의 원문 글자가 복수개의 암호문자로 나타나게 된다는 특성이 있다. 즉, ATTACK이 VBFGVM처럼 변환된다. 평문의 T가 암호문에서는 B와 F로 나타나는 반면 암호문의 V는 평문의 A또는 C를 뜻한다. 이처럼 더 이상 평문과 암호문에 쓰인 알파벳이 일대일의 관계를 갖지 않게 됨으로써 암호해독을 어렵게 만든다.

복합치환의 가장 대표적인 방식은 Vigenere라는 암호방식이다. 간단히 설명하면 26 X 26 테이블을 만드는데, 첫번째 행은 A~Z의 순서로 채우고 두번째 행은 B~Z,A의 순서, 세번째 행은 C~Z,A,B의 순서 등으로 채워나가서 맨 마지막 열은 Z,A~Y로 채워지는 테이블이다. 다음에는 암호 키를 정한다. 가령 HELLO가 키라고 하자. ATTACK을 HELLO를 키로 Vigenere 암호화 하면, 먼저 키의 첫자가 H이므로 H로 시작하는 행을 선택한 뒤 평문의 첫자인 A열과 만나는 글자 (H)를 암호문으로 적는다. 계속해서 키의 E 행과 평문의 T열이 만나는 글자 (Y), L행과 T열 (E), L행과 A열 (L), O행과 C열 (Q), H행과 K열 (R)의 순서로 암호화시킨다. 키의 마지막 글자까지 갔으면 다시 맨 첫자로 돌아간다. 이런 방식을 순환복합치환이라고 한다. 이 방식의 약점은 키의 주기에 맞추어 사용되는 알파벳이 반복된다는 점이다. 즉, 앞의 예에서 ATTACK의 첫 A자를 암호화한 키와 K자를 암호화한 키는 동일한 H이고 따라서 동일한 알파벳이 사용되었다 (A->H, B->I, …). 이러한 약점을 이용하는 방법은 앞에서 설명한 IOC를 일정한 주기의 글자마다 사용해보는 것이다. 즉, 만약 키가 5글자라고 가정하면 매 다섯번째 글자들만 모두 모은 다음 이들에 대해 빈도분석을 통해 IOC를 구해보는 것이다. 여러 주기값을 가정하고 각각에 대해 IOC를 구해보면 대부분은 random값 (1.00)에 가깝게 나타나지만 실제 키 주기와 일치하게 되면 뚜렷하게 높은 수치를 갖는다. 이를 통해 복합치환이 사용됐다는 증거를 갖게 되고 그 때의 키 주기를 알 수 있게 된다. 문제에 주어진 암호문을 이런 방식으로 분석해보니 복합치환의 성격을 가지고 있고, 그 때의 키 주기는 24인 것으로 나타났다.

이제 문제는 이 24자의 암호 키가 무엇인가를 알아내는 것이다. 이 부분이 가장 어려웠는데,여러가지 방법이 있을 수 있겠지만 본인이 최종적으로 성공한 것은 빈도 그래프를 비교해보는 방식이었다. 키의 주기에 따라 주어진 암호문을 24개의 문자군으로 나눈 뒤 각 문자군내에서의 글자별 빈도를 그래프로 표시한다. 가로축은 알파벳이고 세로축은 빈도수이다. 이렇게 하여 총 24개의 그래프를 얻을 수 있다. 이들 그래프를 쳐다보고 있다가 이들간의 어떤 규칙을 발견할 수 있었다. 즉 그래프의 envelope가 모두 유사하다는 것이었다. 물론 위치는 모두 틀렸지만, 가령 가장 높은 값을 갖는 글자로부터 n 만큼 떨어진 글자는 늘 거의 빈도가 나타나지 않았고 그 옆의 글자도 마찬가지라는 특성이 모든 그래프에서 보였다. 원래 영어 평문에 나타난 글자들의 빈도를 그래프로 그려보면 뚜렷한 envelope 특성이 나타난다. 24개의 그래프들을 이러한 영어 평문 빈도 그래프와 비교해보면 기형적으로 Q가 많이 나타난다는 점을 제외하고는 상당히 닮은 모습을 보였다. 그래서 일단은 Q를 무시하고 가장 영어 평문 빈도와 닮은 그래프를 A 그래프라고 부르고 나머지들은 A 그래프로부터 shift된 개수에 맞추어 각각 글자를 부여하였다. 즉, A 그래프에 비해 한 칸 오른쪽으로 shift되어 있는 그래프는 B 그래프, 두 칸 shift된 그래프는 C 그래프라고 하는 식이다. 이런 방식으로 24개의 그래프에 각각 글자를 부여해보니 다음과 같은 키가 나타났다.

TRANSPOSITIONWIDTHTWENTY

나 자신도 경악을 금치 않을 수 없었다. TRANSPOSITION WIDTH TWENTY!! 단순히 그래프의 모습에 따라 영문자를 부여한데 따라 이렇게 선명한 영어가 우연히 나타날 수 있는 확률은 극히 적으리라 생각했다. 드디어 Vigenere 키를 찾은 것이다. 나는 당장 Vigenere decipher 프로그램을 짜고 문제의 암호문과 위의 키를 주고 풀어보도록 했다. 그러나 결과는 예상과는 달리 알아볼 수 없는 또 다른 random text였다. 결과에 실망했지만 곧 키의 내용을 떠올렸다. Transposition 폭이 20자라... 분명히 Vigenere 암호화 전에 어떤 형태의 transposition 변환을 한 것이고 그 폭이 20자라고 가르쳐주는 것 같았다. 우선 Vigenere 출력문에 대해 IOC를 계산해 보았다. 값이 1.75로 나왔다. 이는 영어 평문 1.73에 근접하는 것으로 문장자체는 random으로 보이지만 영어 평문과 동일한 문자 빈도를 보이고 있다는 증거였다. 이런 경우는 한 글자 단순치환이 쓰였거나 아니면 transposition이 쓰였다고 보면 된다. 나는 키의 내용이 의미가 있을 것이라고 보고 transposition 쪽으로 방향을 잡았다.

맨 먼저 쉽게 생각해볼 수 있는 것은 폭이 20자라고 했으므로 columnar 변환의 일종이라고 보고 변환해 보는 것이다. Columnar 변환은 원문을 가로방향으로 n글자만큼 쓸 때마다 행을 바꾸어 모두 작성한 뒤 열 (column) 방향으로 읽어냄으로써 문자를 섞는 방식이다. 이를 역으로 변환하려면 총 글자수가 N이라고 할 때 주어진 문장을 열 방향으로 N/n 만큼 채운 뒤 열을 바꾸는 방식으로 행렬을 채우고 마지막에 행 방향으로 읽어내면 된다. 이 경우는 총 글자가 2,000자였으므로 세로로 100자, 가로로 20자의 행렬을 만들면 됐다.

이렇게 변환을 한 결과도 평문으로 보이는 단어들이 하나도 보이지 않았다. 혹시 영어가 아니라 다른 말이 아닐까도 생각해 봤지만 일단 언어라고 보기 힘들 정도로 단어를 조합할 수 없었다. 혹시 폭이 20자가 아닐지도 모른다는 생각에 각종 폭으로 변환을 시도해봤지만 마찬가지였다.

이렇게 시간이 흐르던 중 갑자기 columnar 변환을 할 때 세로로 읽어내는 과정에서 좌에서 우로 순서대로 읽어내는 것이 아니라 뒤섞인 순서로 읽어냈을 수도 있다는 점을 깨달았다. 즉, 위에서 100 X 20으로 배열된 문장에서 각 행의 순서는 맞지만 행 내의 각 열의 위치가 뒤섞였다는 것이다. 이제 문제는 20자의 뒤섞인 글자들을 가지고 의미있는 단어를 만들어내고 그 단어가 구성되도록 전체 열 위치를 변경시켰을 때 다른 행에서도 의미있는 단어가 만들어지는지 보면 됐다. 문제는 20글자로 만들어볼 수 있는 단어가 너무 많다는 것이다. 그 때 아까 잠시 무시했던 Q의 개수가 떠올랐다. 일반 영문에서 Q는 잘 나타나지 않음에도 불구하고 E나 T보다도 많이 나타나고 있는 것은 분명히 null이거나 space일 것으로 생각했다. 만약 space라면 한 행내의 Q의 개수가 어느 정도 한 행에 들어있는 단어의 개수를 짐작하게 해줄 수 있었다. 첫 행에는 Q가 하나뿐이었고 이것은 19글자로 두 개의 단어만 만들어야 한다는 것을 의미했다. Anagram을 푸는 프로그램을 구해다가 19글자를 주고 2단어를 만들어보라고 했다. 100개 정도의 조합이 나왔는데 그 중에 COMBINATORIAL이라는 단어가 가장 가능성있어 보였다. 첫 행의 글자들이 COMBINATORIAL을 이루기 위한 순서에 따라 전체 열의 위치를 바꾸는 작업을 수행해 나가면서 그 밑의 행들도 알아볼 수 있는 단어들이 나타나기 시작했다. 드디어 암호를 푼것이다.

이후에 완전한 원문을 찾아내는 것은 약간의 guesswork만 필요한 일이었다. 암호문의 열에 좌에서 우로 1~20의 번호를 붙였다고 하면, 원문은 17, 19, 3, 14, 10, 8, 12, 7, 20, 18, 2, 5, 1, 9, 13, 4, 6, 15, 11, 16의 순서로 열을 재배열하면 찾을 수 있다. 아래에 약간의 space 조정을 거친 원문을 싣는다.
several combinatorial maximization problems have the following property the naive algorithm which simply chooses a solution at random from the solution space is guaranteed to give a solution of expected weight at least some constant times the weight of the optimal solution for instance applying the above randomized algorithm to maxcut yields a solution with expected weight at least half the optimal weight for a long time better polynomial time approximation algorithms than the randomized ones were not known to exist for many of the problems with the above property this situation changed when goemans and williamson citegoewil showed that it is possible to use semidefinite programming to approximate maxcut and maxtwos at within frieze and jerrum citefrijer showed that it is possible to construct a olynomial time approximation algorithm which is better than the simple randomized one also for maxkcut systems of linear equations mod p is a basic and very general combinatorial problem which exhibits the property described above the naive randomized algorithm which chooses a solution at random approximates the problem within p recently hstad cite has studied systems of linear equations mod p with exactly k unknowns in each equation and showed that it is actually np hard to approximate the problem within p epsilon for all epsilon all p and all kge in this paper we study another problem of this type systems of linear equations mod p with at most two unknowns in each equation when p this problem has been studied previously citegoewil has but for p not much is known we use semidefinite programming combined with randomized rounding to show that for systems of linear equations mod p with at most two variables per equation it is possible to do better than the naive randomized heuristic specifically we show that there exists for all p a randomized polynomial time algorithm which approximates the problem within kappapp where kappap for all p on the negative side we show that it is np hard to approximate the problem within some consta
3. 뒷 얘기
원문 자체는 무슨 논문 abstract의 TeX 소스에서 변환한 것으로 보인다. 뭔가 재밌는 내용이 나올 것으로 기대했는데 별 내용이 아니어서 약간은 실망했다. 그러나 전체 풀이 과정 자체는 여러가지로 흥미 있었다. 특히 전혀 힌트가 없이 문제를 하나씩 풀어나가는 것은 옛날에 어드벤처 게임을 하는 것과 비슷한 느낌이었다. 막상 풀고나니 섭섭한 느낌도 들었다. 그 동안은 혼자 할 일 없을 때 뭔가 매달려볼 것이 있었는데 갑자기 사라진 느낌이다. 그러나 어쩌겠는가 또 뭔가 새로운 문제와 마주치겠지 기대하며 이 글을 마친다.

덧글

  • 판다 2008/04/29 17:29 # 삭제 답글

    안녕하세요
    다름이아니라 암호문공부를 시작하고있는데요
    우연히 접하게되어서,마침 polyalphabetic을 검색하던 도중에
    오게되었습니다. 인터넷어디를뒤져도 이것을 예로 풀어놓은곳은
    없더라구요. 저도 몇가지 암호문을가지고있지만 제대로푼거는
    transposition문제만 풀었거든요..mono는 guess하기가 너무
    힘들고 poly는 키만찾으면 풀수있다는 생각에...

    그런데 무책님께서 올려놓은글을 읽다가
    어떻게 키를 찾으셧는지 이해가 가지않아서 댓글을 올립니다.
  • 무책 2008/05/02 04:19 # 답글

    판다님 안녕하세요.

    사실 이 암호문을 풀면서 운이 좋았던 (이 자체가 대학 숙제였기 때문이기도 하겠지만) 부분은 이것이 polyalphabetic 중에서도 Vigenere라는 비교적 단순한 방식이 사용되었다는 점과 그 키가 알아보기 쉬운 영문이었다는 점, 그리고 원문이 상당히 길었다는 점일 것입니다.

    Vigenere 방식은 윗 글에서도 설명이 나오지만 알파벳 26x26으로 이루어진 테이블을 사용합니다. 즉,

    ABCD...XYZ
    BCDE...YZA
    CDEF...ZAB
    ...
    ZABC...WXY

    이렇게 구성되죠. 첫번째 행은 원래 알파벳 순서와 같고 두번째 행은 한글자씩 회전된 형태, 세번째 행은 두글자씩 회전된 형태...

    그 다음에 암호문을 일정 글자 간격으로 묶음을 해 봅니다. 가령 세글자 간격이라고 하면 원래 암호문에서 첫번째 글자와 네번째 글자, 일곱번째 글자 등이 한 그룹에 속하고, 두번째 글자, 다섯번째 글자, 여덟번째글자 등이 또 하나의 그룹, 나머지가 마지막 그룹, 이렇게 세 그룹이 나오겠죠. 각 그룹의 IOC를 구해봅니다. 이렇게 간격을 3, 4, 5, 6, ... 등으로 바꿔가며 IOC를 구해보다 보면 급격히 IOC 값이 커지는 간격이 발견됩니다. 그것이 키의 길이가 되는 것이지요. 이 암호문의 경우는 그것이 24였구요.

    자 그럼 스물 네 개의 그룹이 존재하는데, 각 그룹별로 각 알파벳의 빈도수를 구해봅니다. 그러면 위 테이블에서 첫번째 행에 해당하는 키 (A)로 암호화된 그룹의 글자들은 진짜 알파벳과 동일한 빈도수를 보일 것이고, 두번째 행에 해당하는 키 (B)로 암호화된 그룹의 글자들은 진짜 알파벳과 하나씩 옆으로 밀린 빈도수를 보일겁니다. 즉, B가 A와 같은 빈도수, C가 B와 같은 빈도수 이렇게 되는 것이지요. 본문의 글은 이런 것을 그래프로 그려놓고 보다가 발견하는 과정을 적은 것입니다. 그래서 진짜 알파벳과 같은 빈도수 모양을 갖는 것을 A 그룹, 하나 밀린 것을 B 그룹 이렇게 불러놓고 24개 그룹을 순서대로 이름을 붙여보니 본문에서 말한 TRANSPOSITIONWIDTHTWENTY라는 24글자의 키가 나온 것이지요.

    댓글로 설명하려니 힘들지만 이해하시는데 도움이 됐으리라 믿습니다.^^

    암호 공부 열심히 하세요!
댓글 입력 영역