ハッカソンテーマ「単一換字式暗号の自動解析プログラムの作成」

2012/05/20

第2回 SECCONつくば大会ハッカソンのテーマに、

「単一換字式暗号の自動解読プログラムの作成」

というものがありました。
残念ながら今回は、このテーマでは応募がありませんでしたが、「単一換字式暗号の自動解析プログラムの作成」について、その出題意図を少しお話させてください。

世界のCTF大会では、大抵、一定量の「単一換字式暗号」の問題がでてきます。
これは、CTFの問題を作成する側のパワー不足などにも原因があると思うのですが、問題の作成は簡単にできるのですが、問題を解く側には一定量の負荷をかけられるからです。

しかし、この「単一換字式暗号」、じつは古くからよく知られており、シャーロック・ホームズの「踊る人形」(1904)や、エドガー・アラン・ポーの「黄金虫」(1843)で解説されているくらいカビの生えた暗号で、現代の情報教育では、暗号授業のオリエンテーションとして触れられる程度でしかなかったものです。

ところが、これが、現在、世界的に流行っているCTFの問題中に、一定量を占めています。

私はこれは実におかしいと思います。
原因は、自動解析のプログラムが一般に出回っていないからだと思ったのです。
 これもヘンといえばヘンです。
だって、これはプログラム向きの探索問題だからです。

解読には、

・英文字の出現頻度表
・ 英単語、英熟語のデータベース

が必要になるでしょう。
そして、与えられた「暗号文」の頻度分析をおこなった上で、出現頻度表を元に,
単語の一部の英文字を仮定して 、データベースとのマッチングを進め、
他の文字を確定していく・・・という作業を続けます。
もちろん、最終的に全部の単語が解読できれば解読完了です。
途中で失敗した場合は、「仮定」した文字を一つずつ戻していき、他の文字で
探索してみます。

素直に考えるとこんな感じですが、これらをできるだけ一瞬で解けるアルゴリズムを
考えて、実装してほしいのです。

そして、あなたの手で、こんなカビの生えたCTF問題は墓場に封じ込めて欲しいのです。

どなたかSECCON大会とは関係なくても、このようなプログラムを作成して、公開して
みませんか?