컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다. 예를 들면 대문자 A는 65, 별표(‘*’)는 42, 소문자 k는 107이라는 값을 가집니다.
현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII 코드로 바꾸고 각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다. 이 방법의 장점은 암호화와 복호와에 동일한 키를 사용할 수 있다는 것입니다. 예를 들어 65 XOR 42 = 107 이고, 107 XOR 42 = 65가 됩니다. 암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다. 암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 2개를 함께 확보하지 않는 한 해독은 불가능합니다.
하지만 이 방법은 대부분의 경우 실용적이지 못하므로, 원문보다 짧은 비밀키를 사용하게 됩니다. 이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다. 이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만 또한 쉽게 기억할 수 있을 정도로 짧아야 한다는 미묘한 균형이 요구됩니다.
이번 문제를 위해서 준비한 암호화 키는 단 3개의 영어 소문자이고, cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다. 원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고, 원문에 포함된 ASCII 코드값의 총합을 구하세요.
http://euler.synap.co.kr/prob_detail.php?id=59
접근
이 문제는 포럼에서도 재미있다는 반응이 제법 많은 문제로, 실제로도 다양한 스킬을 요구하면서 재미도 있는 문제이다. 실제로 주어진 힌트와 몇 가지 사실을 통해서 필요한 정보를 정리해보자.
가장 중요한 힌트는 암호화된 데이터의 원문이 평범한 영어문장이라는 점이다. 암호를 깨는 작업에서 가장 중요한 정보를 꼽으라면 어떤 코드가 가장 자주나타나는지, 그리고 실제로 원문에는 어떤 글자가 가장 많을 것인지하는 것이다. 3글자의 키가 각 문자에 대해 번갈아가면서 적용되므로, 가장 자주 나타나는 3개의 코드들이 각각 원문에서 가장 많은 글자와 암호화 키의 각 바이트가 결합한 것이라고 추정할 수 있다.
여기서 평범한 영어 문장이라는 조건이 중요한데, 흔히 알려지기로는 알파벳 ‘E’가 가장 자주 나타나는 글자로 알려져 있다. 하지만 이 정보는 실제로는 올바르지 않은데, 영어 알파벳 중에서 가장 자주 쓰이는 글자가 E 인것은 맞지만, 실제로 영문 뉴스 기사 등의 글을 긁어다가 조사해보면 가장 많이 나타나는 문자는 공백임을 알 수 있다.
키의 길이가 3이므로, 각 코드 값과 20(공백문자의 아스키코드 값)을 XOR 연산한 결과가 가장 자주 나타나는 문자 9개 정도를 뽑아내면 이 중에 키를 구성하는 문자가 3개는 반드시 포함될 것이다.
9개의 문자 중에서 중복을 허용하여 3개를 뽑는 순열로 전체 키 후보를 만들 수 있다. 각 키 후보로 데이터를 복호화해서 성공하는지도 검사를 해야한다. 이 때에도 ‘일반적인 영어 문장’이라는 힌트가 중요한데, 영단어 중에서 가장 자주 등장하는 단어가 바로 ‘the’이므로, 복호화한 텍스트에서 the 가 나타나는 빈도를 세고, the가 가장 많이 나타나는 텍스트가 복호화에 성공한 것으로 판단할 수 있다.
혹은 복호화한 결과에서 알파벳, 숫자, 공백, 문장부호를 제외한 특수문자가 포함돼 있는지를 보는 방법도 있을 것이다. (여기서는 사용하지 않았다.)
키 후보 찾기
from typing import Iterable, Sequence, Generator, TypeVar
T = TypeVar('T')
# itertools.cycle 대체
def cycle(xs: Iterable[T]) -> Generator[T, None, None]:
while True:
for x in xs:
yield x
# 중복순열 생성기
def product(xs: sequence[T], n: int=0) -> Generator[Tuple[T, ...], None, None]:
if n == 0:
n = len(xs)
def helper(acc: Sequence[T], rem: Sequence[T], k: int) -> Generator[Tuple[T, ...], None, None]:
if k == 0:
yield acc
return
for x in rem:
yield from helper((*acc, x), rem, k - 1)
yield from helper(tuple(), xs, n)
# 키 후보 찾기
def guess_key(codes: list[int]) -> list[int]:
res: dict[int, int] = {}
for c in codes:
d = c ^ ord(' ')
res[d] = res.get(d, 0) + 1
return [item[0] for item in sorted(res.items(), key=lambda x: x[1], reverse=True)][:9]위에서 작성한 guess_key() 함수는 정수 리스트 형식의 코드를 받아서, 가장 많이 반복되는 코드로 키를 구성하는 후보를 찾아준다. 이제 이 후보들을 사용하여 실제 텍스트를 찾아보자.
def decode(codes: list[int], key: Iterable[int]) -> str:
return ''.join(chr(x ^ y) for x, y in zip(codes, cycle(key)))
def solve(data: list[int]):
message, the = '', 0
for ks in product(guess_key(data)):
body = decode(data, ks)
temp = body.count('the')
if temp > the:
message, the = body, temp
return message
with open('cipher1.txt') as f:
codes = [int(c) for c in f.read().decode().strip().split(',')]
result = solve(codes)
print(result)
print(sum(map(ord, result))문제를 다시 풀어보면 확인하니, 예전에 풀었을 때와 지문으로 주어지는 데이터가 다르다. 예전 데이터는 키 후보를 상위 3개만 추출하면 ['o', 'd', 'g'] 였고, 이를 가지고 만들 수 있는 ‘가장 영어권스러운 단어’로 “god”을 떠올리게 되는데, 이 단어가 키였다. 새롭게 바뀐 데이터 기준으로는 다른 키가 사용되었다. (원래 문장도 다르기 때문에 답이 다르다.)