【Project Euler】Problem 59: XOR暗号

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 59. XOR暗号

原文 Problem 59: XOR decryption

問題の要約：ファイルの暗号化されたASCIIコードからXOR暗号キーとして使われた3文字を推測して復号文のASCIIコードの和を求めよ

以下のような条件のもと暗号を解読する問題です。

• 暗号方式はa-zの小文字からなる3文字のASCIIコードを巡回してXORをとる。
• 元の文は普通の英文

考え方は「頻度分析 (暗号)(Wikipedia)」というものを使います。要はすべての可能なキーで復号してみて結果の出現頻度がそれらしいものをキーの候補とします。

今回はキーが3文字を巡回してXORを取るということなので、

1. 暗号文を3文字おきに３つのグループに分ける
2. 各々のグループa-zすべての文字のAsciiコードで複合
3. 複合されたテキストの文字の出現頻度を調べる（Counter）
4. 出現頻度トップ３に" "と"e"が含まれるものをキーの候補（most_common）

それをプロクラムにしたのがこちらです。（リストencaに暗号文のAsciiコードが入っているところからのコード。ファイルからの読み込みは下の方に載せました。）

from collections import Counter
keys = [k for k in range(ord('a'),ord('z')+1)]   # ascii code for a-z
# return the best key candidate, assuming " " and "e" are in top3 common chars 
def bestKey(ea):
  for k in keys: 
    da = [c^k for c in ea]
    top3 = list(dict(Counter(list(map(chr,da))).most_common()[:3]).keys())
    if " " in top3 and "e" in top3:
      return k

# enca : encorded ascii code
EK = [bestKey([enca[i] for i in range(j, len(enca), 3)]) for j in range(3)]
print(f"encryption key: {''.join(list(map(chr,EK)))}")
deca = [enca[i]^EK[i%3] for i in range(len(enca))]
print(f"Answer: {sum(deca)}")
print(f"Original Text: {''.join(list(map(chr,deca)))}")

ファイルからの読み込みのコードです。

#show upload dialog
from google.colab import files
uploaded = files.upload()
f = open("p059_cipher.txt")
fstr = f.read()
f.close()
enca = fstr.split(',')
enca = list(map(int,enca))
print(len(enca),enca[:20])

（開発環境：Google Colab）