Decoding Simple XOR cipher
XOR 暗号 の解読

解読に利用する性質

XOR の性質

同じ値で 2 度 XOR をとると元の値になる．

例:
A: 0100 0001
+
T: 0101 0100
+
T: 0101 0100
= 0100 0001

例えば，平文を英語アルファベット 20 文字， p₁,p₂,...,p₂₀ とする．但し， 各 p_i は一文字分，すなわち 8bit の組である． 平文が "This is..." であれば，p₁=01010100 (Tのアスキーコー ド), p₂=01101000 (hのアスキーコード), である．同様に， キーが 3 文字 k₁,k₂,k₃ であるとすると， 20 文字の暗号文は c₁,c₂,...,c₂₀, と書 け，以下の関係になる．

c₁, c₂,..., c₂₀ とそれ自身を右にずら したものの XOR を以下の 2 つの場合に分けて考える．

ずれ量がキーの長さの倍数(この例では 3 の倍数)である場合

このことから，ずれ量がキーの長さの倍数のとき，XOR をとった結果がゼロに なるのは，A: 平文から選んだ文字 2 個が一致する確率である．

ずれ量がキーの長さの倍数でない場合

この場合はキーが相殺されることはない．乱数と XOR を取ると乱数になるこ とが知られている．今回のシステムのキーは，00000000 から 01111111 の間 でランダムに設定するので，この場合に XOR をとった結果がゼロになるのは B: 任意の 7 ビットのパターンが一致する確率である．

英語の性質

ずれ量がキーの長さの倍数でない場合の， "B: 任意の 7 ビットのパターンが一致する確率" はビットパターンが 2 の 7 乗個 あることから 1/128 と求められる．一方 ずれ量がキーの長さの倍数の場合の"平文から選んだ文字 2 個が一致する確率" は英語のアルファベットがランダムに出現しないことから B: よりずっと高い． これを利用して暗号文からキーの長さを推測することができる．暗号文をいく つかずらし，一致する確率を計算する，という作業をずらし量 1,2,3,... に 対して順に行い，確率が上るすらし量を探せばよい．

キーの長さを求めたあとは， 各アルファベットの出現頻度の違いを利用して 解読を行なえばよい．アルファベットの出現頻度は高いものから順に， "空白"(18.59%)， "e"(10.31%)， "t"(7.98%)， "a"(6.42%)，であることが知られている(大文字小文字は無視している)． 今回は空白記号の出現頻度が確率が最も高いということを主に利用する．