« Project Euler - Problem 58 | トップページ | 平方根の求め方 »

2009年8月31日 (月)

Project Euler - Problem 59

問題はこちらをご覧ください。


面倒くさそうだったので、しばらくほったらかしにしていたのですが、「暗号解読」(サイモン・シン著)を読んだら解法のヒントがあったので、解いてみました。

「ある程度の長さをもつ普通の英文」の場合、"e" が最頻出文字であることが分かっています。

今回の暗号は 3 文字のキーワードが使われているので、暗号化された文章を三文字おきにグループ分けすると、その中のグループの頻出文字に "e" が含まれていることが予想されます。

そこで、それぞれのグループの出現頻度の高い順に 5 つの文字を拾い上げて、それが "e" だったと仮定してキーワードの文字を推測してみました。

今回は元の文字のコードをキーワードのコードと "xor" することで暗号化しているので、暗号化された文字のコードと元の文字のコードを "xor" するとキーワードのコードが返ってきます。

# -*- coding: utf-8 -*- # # = 鍵となる文字を探す # class Array # == 数字の出現頻度を数え上げて、多い順に並べて返す。 def count h = Hash.new(0) self.each do |n| h[n] = h[n] + 1 end return h.to_a.sort_by{|a| a[1]}.map{|a| a[0]}.reverse end end cipher_text = open("cipher1.txt"){|file| file.read} cipher_arr = cipher_text.split(",").map{|str| str.to_i} # text_arr を鍵の同じ文字に対応する 3 つの部分に分ける。 part = Array.new 3.times{|i| part[i] = Array.new} cipher_arr.each_with_index do |n, i| part[i % 3].push(n) end # 各パートで頻出する 5 文字を "e" に見立てて鍵の文字を推測する。 part.each do |arr| p arr.count.take(5).map{|n| (n ^ "e".ord).chr} end

今回の文章はあまり長い文章ではなかったので、さすがに "e" が最頻出とはなっていませんでしたが、それらしいキーワードを想定するだけの材料にはなりました。


それでは、キーワードが分かったところで、暗号文を復号してみましょう。

# -*- coding: utf-8 -*- # # = 暗号文を解読する # cipher_text = open("cipher1.txt"){|file| file.read} cipher_arr = cipher_text.split(",").map{|str| str.to_i} key_word = "***" # "***" の代わりに鍵となる 3 文字を入れる。 key = key_word.split("").map{|i| i.ord} arr = Array.new cipher_arr.each_with_index do |n, i| arr.push(n ^ key[i % 3]) end plain_text = arr.map{|i| i.chr}.join puts arr.inject(:+) puts plain_text

正しく復号されれば、数字と聖書の一節が英文で表示されるはずです。


ところで、今回は三つのグループのいずれでも "e" が最頻出文字となっていませんでした。

そこで、最頻出文字は何だったかを調べてみました。すると……なんと " " (半角スペース)でした。

確かに、アルファベットの中では "e" が最頻出かもしれませんが、今回のように「半角スペース」まで含めて暗号化されれば、「半角スペース」が最頻出になりますよね。もう少し良く考えれば想像できたかもしれません。


実際に問題を解いた後、他の人の解き方を調べてみたら、問題文の「平文はよく用いられる英単語を含んでいる」という部分から、暗号文の文字列が "the" や "was" などの単語に復号できる部分を探してそこからキーワードを推測している方が何人かいらっしゃいました。

それでも正解が得られているようなので、間違った解法というわけではないのでしょうが、「平文はよく用いられる英単語を含んでいる」という一文は、「単語の出現頻度は極端に偏っていない」ということを強調したかったのでは?と私は思っています。

« Project Euler - Problem 58 | トップページ | 平方根の求め方 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/46078752

この記事へのトラックバック一覧です: Project Euler - Problem 59:

« Project Euler - Problem 58 | トップページ | 平方根の求め方 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ