오일러 프로젝트 59

오일러 프로젝트 59 번 문제는 포럼에서 많은 이들로부터 “재밌다”는 평가를 많이 듣는 문제이다. 정수로 표현된 암호화된 문구가 주어지고, 세 글자짜리 키를 이용하여 XOR로 처리하여 암호화된 문장이라는 힌트를 기준으로 원래의 문장을 복호화하고, 원문의 ASCII 코드값의 합계를 구하는 것이다.

컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다. 예를 들면 대문자 A는 65, 별표(*)는 42, 소문자 k는 107이라는 값을 가집니다.
현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII코드로바꾸고 각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다. 이 방법의 장점은 앙호화와 복호화에 동일한 키를 사용할 수 있다는 것입니다. 예를 들어 65 XOR 42 = 107이고, 107 XOR 42 = 65가 됩니다.
암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다. 암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 두 개를 함께 확보하지 않는 한 해독은 불가능합니다.
하지만 이 방법은 대부분의 경우 실용적이지 못하므로, 원문보다 짧은 비밀키를 사용하게 됩니다. 이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다. 이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만 또한 쉽게 기억할 수 있을 정도록 짧아야 한다는 미묘한 균형이 요구됩니다.
이번 문제를 위해서 준비된 암호화 키는 단 3개의 영어 소문자이고, cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다. 원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고, 원문에 포함된 ASCII 코드값의 총합을 구하세요.
(http://euler.synap.co.kr/prob_detail.php?id=59)

접근

문제에서 제시된 힌트와 몇 가지 지식을 동원하면 그리 어렵지 않게 풀 수 있는 문제이다.

1.  주어진 문구는 “평범한 영어 문장”이라고 했다. 영어 문장에서 가장 많이 쓰이는 알파벳은 “E”이다. 그러나 그것은 조판에 사용된 알파벳 중에서 가장 빈도가 높은 것이며, 실제 영어 문장 (뉴스 기사 등)을 클리핑해서 카운트하면 가장 많이 쓰이는 문자는 다름 아닌 ‘공백’이다.
2. 따라서 주어진 데이터에서 최빈값 3개를 뽑아본다. 문자들이 공백일 가능성이 높으므로, 이 값들을 공백문자로 만들 수 있는 글자 세 개를 키로 잡을 수 있다. 이 글자들은 공백문자의 코드값과 XOR해서 구한다.
3. 세 개의 키 코드 후보로 만들 수 있는 키 조합은 27가지이다. 예를 들어 A, B, C 세 글자가 키 구성 요소로 뽑혔다면, AAA부터 CCC까지의 조합을 사용할 수 있다.
4. 다시 평범한 영어문장으로 돌아왔을 때, 가장 많이 쓰이는 단어로 the를 꼽을 수 있다. 3의 후보 중에서 the를 만들어 낼 수 있는 키를 찾는다. (만약 이 때 후보가 2개 이상이라면 be, to, of, and 등의 단어를 찾아보도록 한다. 가장 많이 쓰이는 영어 단어는 영문 위키 백과를 참고한다.)

키 찾기

주어진 코드값(정수 리스트)로부터 키에 쓰일 것으로 추측되는 글자의 코드 값 세 개를 찾아보자. 각 코드값의 출현 빈도를 사전을 통해서 계산한 다음, 빈도값 내림차순으로 정렬한 후 상위 세 개의 값을 공백 문자로 만드는 값 세 개를 찾는다.

def guess_key(codes):
  m = dict()
  for c in codes:
    m[c] = m.setdefault(c, 0) + 1
  candidates = [x[0] for x in sorted(m.items(), key=lambda x:x[1], reverse=True)]
  return [x^ord(' ') for x in candidates[:3]]

이렇게 만든 코드로 테스트해보자. 뭔가 감이 온다.

[chr(x) for x in guess_key(codes)]
# ["O", "D", "G"]

디코딩

디코딩 함수는 주어진 정수값을 , 키 배열을 반복하면서 각 원소와 매칭시켜 XOR 연산한다. 그리고 그 결과에 대해서 각 값을 문자로 변형하여 join 시키면 된다. 키의 인덱스를 돌려가면서 쓰기보다는 코드와 지퍼를 만들어서 합치는 것이 깔끔하게 작성되므로  itertools.cycle 을 동원한다.

from itertools import cycle
def decode(codes, key):
  return ''.join(ord(x^y) for x, y in zip(codes, cycle(key)))

최종 검사

최종적으로 검사하기 위한 코드를 만들어보자. 디코딩한 결과에 the 가 포함되어 있는지 결정한다.

from itertools import product
messages = [decode(codes, key) for key in product(guess_key(codes), repeat=3)]
[m for m in message if m.count('the') > 1] ## the 를 2개 이상 포함

혹은 상위 몇 개의 단어를 통해서 다음과 같이 검사하는 함수를 사용해서 필터링할 수도 있다.

def test(message):
  clues = ('the', 'be', 'of', 'and')
  for c in clues:
    if test.count(c) < 2:
      return False
  return True

파이썬 풀이

앞에서도 살펴봤지만, 복호화하는데 필요한 모든 동작은 몇 줄 이내의 코드로 모두 정리되므로 전체 풀이 역시 생각보다 매우 짧다.

from itertools import cycle, product
from urllib.request import urlopen
def e059():
  ## get data
  data = urlopen('http://euler.synap.co.kr/files/cipher1.txt').read().decode()
  codes = [int(x) for x in data.split(',')]
  def decode(key:List[int]) -> str:
    return ''.join(chr(x^y) for x, y in zip(codes, cycle(key)))
  def guess_key() -> [int]:
    m = {}
    for c in codes:
      m[c] = m.setdefault(c, 0) + 1
    return  [x[0]^ord(' ') for x in sorted(m.items(), key=lambda x:x[1], reverse=True)[:3]]
  message = [decode(key) for key in product(guess_key(), repeat=3)\
                         if decode(key).count('the') > 1][0]
  print(sum(ord(x) for x in messages))
%time e059()
## Wall time: 30ms

Swift 풀이

Swift로 이 문제를 푸는 것은 생각보다 까다로웠다. 실제로 이 문제 풀이의 핵심은 코드 리스트 중에서 최빈값을 찾는 것이고 그 외의 나머지는 문자와 코드값의 변환 부분이다.

준비과정들

파일 읽어오기

String.init(contentsOf: URL) 을 이용하면 네트워크 상의 파일로부터 텍스트를 읽어올 수 있다. 주의할 점은 이 이니셜라이저가 예외를 던질 수 있기 때문에 try 와 함께 쓰여야 한다는 점이다.

import Foundation
let codes: [Int] = {
  guard let url = URL(string: "http://euler.synap.co.kr/files/cipher1.txt"),
        let contents =  try? String(contentsOf: url)
  else { return [] }
  return contents.split(separator:",").flatMap{ Int($0) }
}()

코드값을 문자로 바꾸기

파이썬에서는 chr() 이라는 간편한 내장함수로 유니코드 코드값을 문자로 변환할 수 있다. Swift에서는 만들어야 한다. 코드값 하나가 Character 값으로 변환되어야 하고, [Character]를 이용하면 문자열을 만들 수 있다.  따라서 (Int) -> Character? 로 변환하는 함수가 하나 있어야겠다.
코드값으로 Character를 바로 만들 수는 없고 중간과정인 Unicode.Scalar 값을 만들어야 한다.

func chr(_ n: Int) -> Character? {
  guard  let m = Unicode.Scalar(n) else { return nil }
  return Character(m)
}

이 함수를 만들었다면 정수 배열로부터 문자열을 생성하는 것은 간단하다. 아래와 같이 Array 타입을 확장하여 메소드를 하나 추가하자.

extension Array where Element == Int {
  func convertedString() -> String {
    return String(flatMap(chr))
  }
}
print([65,66,67].convertedString()) // 'ABC'

리피터

파이썬의 itertools.cycle 과 같이 키를 반복하여 코드에 매칭할 용도로 리피터가 필요하다. 다음과 같이 만든다.

struct Repeater<T> : Sequence, IteratorProtocol {
  let data: [T]
  var index: Int = 0
  init(elements: [T]) {
    self.data = elements
  }
  mutating func next() -> T? {
    guard !data.isEmpty else { return nil }
    let r = data[index]
    index += 1
    return r
  }
}
// 테스트
let r = Repeater(elements: [65,66,67])
for (i, v) in r.enumerated() {
  print(v)
  if i > 10 { break }
}

이제 리피터를 만들면 주어진 원소들을 빙빙돌면서 내놓게 된다.

키 찾기

왠열? 엄청 간단하다?

func guessKeys(from codes: [Int]) -> [Int] {
  // 공백(스페이스)의 코드값 (20이다)
  let spc: Int = " ".utf8.map{ Int($0) }.first!
  var m = [Int:Int]()
  codes.forEach{ m[$0] = (m[$0] ?? 0) + 1 }
  return m.sorted{ $0.1 > $1.1 }[0..<3].map{ $0.0 ^ spc }
}
// 테스트
print(guessKeys(from: codes).convertedString())

디코딩

리피터를 만들었으니, 디코딩은 쉽게 할 수 있다.

func decode(from codes: [Int], key: [Int]) -> String {
  let decoded = zip(codes, Repeater(elements: key))
                 .flatMap{ chr($0.0 & $0.1 ) }
  return String(decoded)
}

키 조합 및 검사

이 부분에서 좀 고민됐다. 왜냐하면 product 와 같은 함수나 시퀀스가 Swift에는 없기 때문이다. 일단 3중 루프를 도는 것으로 키 조합은 만들 수 있을 듯 한데, 디코딩한 결과에 “the”가 들어있는지는 어떻게 알까? 이는 NSString에서 range(of:String)을 빌려와서 써야 한다.  (아니면 오프셋을 한 칸씩 밀면서 starts(with:) 를 쓰는 방법도 있다.) 하지만 가장 좋은 방법은 찾고자 하는 문자열로 전체 문자열을 쪼개보는 것이다. 그 결과의 원소 개수 -1 이 해당 부분열의 출현횟수가 된다! 문자열을 글자가 아닌 문자열로 쪼개는 것은 components(separatedBy:)를 쓴다. 이 메소드 역시 NSString 으로부터 빌려온 것이다.

// 키 조합
let key = guessKey(from: codes)
let products = key.lazy.flatMap{ x in key.flatMap{ y in key.map{ z in [x, y, z]}}}
for k in products {
  let decoded = decode(codes: codes, key: k)
  if decoded.components(separatedBy: "this").count > 2 {
    print(decoded)
    print(decoded.utf8.map{ Int($0) }.reduce(0, +))
    break
  }
}

최종적으로 정리된 코드는 아래 Gist를 참고.