PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 59 / XOR暗号解読

各文字はそれぞれ一意のコードに割り当てられている。よく使われる標準としてASCII (American Standard Code for Information Interchange) がある。ASCIIでは大文字 A = 65,アスタリスク (*) = 42,小文字 k = 107 のようにコードが割り当てられている。

モダンな暗号化の方法としてテキストファイルの各バイトをASCIIに変換し,秘密鍵から計算された値とXORを取る手法がある。XOR関数の良い点は暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号できる点である。

  • 65 XOR 42 = 107
  • 107 XOR 42 = 65

破られない暗号化のためには鍵は平文と同じ長さのランダムなバイト列でなければならない。ユーザーは暗号文と暗号化鍵を別々の場所に保存する必要がある。もし一方が失われると暗号文を復号することは不可能になる。

悲しいかな,この手法はほとんどのユーザーにとって非現実的である。そこで,鍵の変わりにパスワードを用いる手法が用いられる。パスワードが平文より短ければ(よくあることだが)パスワードは鍵として繰り返し用いられる。この手法では安全性を保つために十分長いパスワードを用いる必要があるが,記憶するためにはある程度短くないといけない。

この問題での課題は簡単になっている。暗号化鍵は3文字の小文字である。cipher1.txt は暗号化されたASCIIのコードを含んでいる。また,平文はよく用いられる英単語を含んでいる。この暗号文を復号し,平文のASCIIでの値の和を求めよ。

Problem 59 - Project Euler

下調べ

手始めに a=97 から z=122 までのアルファベット一文字で復号した場合の文字コードを調べました。以下のコードで myList0 は問題文中の cipher1.txt です。

文字コード32は「スペース」,127は「DEL」です。意外なことに文字ごとの違いはほとんどありませんでした。

次に「aaa」で復号してみました。これは明らかに駄目です。スペースやピリオドによる区切りがないのと記号が多すぎるのとで,文字化けにしか見えません。

ASCII文字コード - IT用語辞典

本番

小文字とスペースは10点,大文字と数字は1点として最大値を与える組み合わせを探しました。

はじめは@などの記号があったら大幅減点するコードを書いたのですが,絶対に出てこないとは言い切れないのでやめました。たとえば本文中にメールアドレスが書かれていれば@が出てくるのは当たり前ですよね。

単純なルールの割にうまくいって,パスワードは「god」,その文字コードの和は314*1でした。

後始末

cipher1.txt を「god」で復号した結果は聖書の一部です。

各文字の出現頻度はこのようになります。最も多いのはスペースで,e の約2倍ありました。

文字頻度表 によると,CNN, ABC, VOA の各ニュースの各分野からランダムに4万1600文字を抜き出したときの出現頻度順は次のようになっていたそうです。大体の傾向は似ていますが,ところどころ違っています。

e, a, t, i, o, s, n, r, h, l, d, c, u, m, p, f, g, y, w, b, v, k, j, x, q, z

*1:正解者掲示板に「円周率」との指摘あり。