2012年9月12日水曜日

プロジェクトオイラー 問59

プロジェクトオイラーの問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索してください。

問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での値の和を求めよ.

-----


注意!!!
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。






私の解答例は以下です。畳んでいます。
def g(s, n):
	import itertools
	for t in itertools.product(s, repeat=n): yield "".join(t)

def f(sIn, a, n):
	L = [int(t) for t in open(sIn).read().split(",")]
	for s in g(a, n):
		M = ([ord(t) for t in s]*len(L))[:len(L)]
		N = [i^j for i,j in zip(L, M)]
		R = [chr(i) for i in N]
		t = "".join(R)
		if " the " in t: return sum(N), s, t

import os
sIn = os.path.join(os.path.dirname(__file__), "cipher1.txt")
a = "abcdefghijklmnopqrstuvwxyz"
n = 3
print f(sIn, a, n)


2つの関数を使っています。

1.関数g(s, n)
・文字列sからn個選んだ直積を連結した文字列を返します。
 直積とは、重複を許し順番が違えば別のものとして扱う組み合わせです。
 例えば、abcから2つ選んだ直積は、aa,ab,ac,ba,bb,bc,ca,cb,ccです。

・import itertools
 標準モジュールitertoolsを使えるようにしておきます。

・for t in itertools.product(s, repeat=n): yield "".join(t)
 標準モジュールitertoolsにあるproduct関数で、文字列sからをn個選んだ直積の構成要素のタプルを生成し、for文のループ変数tに設定します。
 forループの中で、タプルtを区切り文字無しで連結し、yield文で返します。
 yield文で返すと、返した時点で処理内容が一旦凍結され、再度呼び出されたときに処理を再開して続きの処理による値を返します。
 このような動きをするyield文で返す関数をジェネレータ関数といいます。
 なお、単発呼び出しで終了するreturn文で返す関数はイテレータ関数といいます。
 また、product関数はpython2.6以上です。
 python2.5にもitertoolsモジュールはありますが、product関数が含まれていません。

2.関数f(sIn, a, n)
・主処理です。
・入力ファイルsInの中の文字列を、指定した文字列aからn個選んだ秘密鍵sによって順にxor演算で復号した数値列N、及びこれをasciiコード扱いして得られる復号文字列tがあるとき、数値列Nの合計値、キー文字列s、復号文字列tを返します。

・引数sInは入力ファイルのフルパス、文字列aは秘密鍵の構成文字候補の文字列、nは秘密鍵の桁数です。

・L = [int(t) for t in open(sIn).read().split(",")]
 暗号文の各数値をもつリストLを作成します。
 入力ファイルsInを開き、その内容をすべて読み込んで、カンマで区切った文字列を
 ループ変数tに設定します。
 このtをfor文の前に送り、int関数で数値化してリストLとします。
 なお、開いたファイルオブジェクトはpythonがタイミングをみて閉じくれます。

・for s in g(a, n):
 関数gで文字列aからn個選んだ秘密鍵候補をループ変数sとします。

・M = ([ord(t) for t in s]*len(L))[:len(L)]
 Mは、秘密鍵候補sの構成要素の数値を暗号文の長さまで繰り返した復号用鍵のタプルです。
 内包表記のループ変数tとして秘密鍵候補sの文字1つずつを、for文の前に送り、ord関数でasciiコードとして対応する数値にしてリスト化します。
 このリストをlen(L)倍、つまり暗号文の長さ倍して、秘密鍵を順に繰り返し連結した状態にしてから、[:len(L)]で暗号文の長さの分だけ取り出しておきます。
 
・N = [i^j for i,j in zip(L, M)]
 Nは復号化した数値のリストです。
 zip関数で上記のリストLとリストMから1つずつ組み合わせて取り出し、ループ変数i,jとし、内包表記のfor文の前に送り、^演算子で数値j,jのxorを計算しリストにため、リストNとします。

・R = [chr(i) for i in N]
 復号数値リストNから1つずと取り出しchr関数でascii文字化してリストにため、リストRとします。
 
・t = "".join(R)
 上記の文字列リストRの要素を区切り文字無しで連結し、復号文tとします。

・if " the " in t: return sum(N), s, t
 復号が正しいか判定します。
 判定は「よく用いられる英単語」があるという問題文に従い、半角空白ではさんだ「 the 」としてみました。結果的にこれで判定できました。
「 the 」があれば、復号化した数値リストNの要素の合計、秘密鍵、復号文tを返します。

3.関数の外
・import os
 ファイルを扱うので、標準モジュールosを使えるように取り込んでおきます。

・sIn = os.path.join(os.path.dirname(__file__), "cipher1.txt")
 暗号文のフルパスです。
 「__file__」は実行するpythonファイルのフルパスです。
 os.path.dirname関数で親フォルダまで取得し、ファイル名とともに、
 os.path.joinでパス表示を連結しました。
 つまり、暗号文は実行するpythonファイルと同じフォルダに置いて実行するように記述しています。
 
・a = "abcdefghijklmnopqrstuvwxyz"
 秘密鍵の候補です。問題文から小文字のアルファベットです。

・n = 3
 秘密鍵の桁数です。問題文から3としました。

 

解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
107359
秘密鍵はgod。平文の内容は、聖書ヨハネによる福音書の第1章第1節から第14節。

(追記)
・20130129 ネタバレ注意の追記など

0 件のコメント:

コメントを投稿