CHAMBER 4 : POLYALPHABETIC SUBSTITUTION
開放条件：XIII
Polyalphabetic substitution cypher（多表換字暗号）とは、平文の1つの文字種が、暗号文の複数の文字種に対応する暗号です。
この暗号として最もよく使われるものは、Vigenere cipher（ヴィジュネル暗号）です。
この暗号では、暗号化にあたり「鍵」となる単語を用います。
全体難易度
論理：★★★☆☆
閃き：★☆☆☆☆
暗号化手順
|
+
|
... |
暗号化の手順を、例を用いて説明します。
平文「PLAINTEXT」を、鍵「KEY」で暗号化するとします。
まず、平文の各アルファベットに、鍵の各アルファベットを、巡回させて対応させます。
P L A I N T E X T
K E Y K E Y K E Y
次に、「鍵」の各アルファベットを、A=1、…、Z=26（※）として、数字に対応させます。
P L A I N T E X T
11 5 25 11 5 25 11 5 25
最後に、その数字の分だけ、平文のアルファベットを後ろにずらします。
A Q Z T S S P C S
これで、暗号文の完成です。
復号する場合は、暗号文のアルファベットを、「鍵」に応じた数字の数だけ手前にずらすことで復号できます。
注
|
+
|
... |
一般的にはA=0、Z=25で対応させますが、このゲームにおいてはA=1、Z=26が使われています。
|
|
復号化手順
|
+
|
... |
この暗号の解読では、Kasiski's test（カシスキー・テスト）と呼ばれる方法が知られています。
鍵の長さの特定
|
+
|
... |
第一に、鍵の長さ（文字数）を特定します。
THEやANDなど、1つの文章の中に繰り返し登場することがある単語に着目します。もし平文の同じ文字列が、同じ鍵の周期で暗号化された場合、暗号文に登場する文字列も一致します。
よって、暗号文の中で同じ文字列となっている箇所の長さを求めることで、その長さの約数が鍵の長さの候補となります。そのような箇所の長さを複数求めた場合、それらの公約数が鍵の長さの候補となります。
注
|
+
|
... |
上記方法に関して、以下の2点の疑問が生じるかもしれません。
- 平文の同じ単語が、全て別の文字列になる可能性はないか
- 平文の異なる文字列が、暗号文で同じ文字列になる可能性はないか
前者は、鍵の長さが長い場合はその可能性もありますが、鍵の長さが短い場合は高確率で同じ文字列が発生するため、問題にはなりません。
特に、鍵の長さ（文字数）よりも同じ単語の登場回数が多い場合、必ず同じ単語が発生します。
後者は、同じ単語が同じ文字列になる確率に比べて極めて低確率であり、ほぼ無視できます。
平文が N 文字、繰り返し登場する単語が n 文字、鍵の長さが k 文字のとき、
同じ単語が同じ文字列になる確率は、1文字あたり「1/k」ですが、
別の文字列が偶然一致する確率は、1文字あたり「N/26^n」程度しかありません。
|
|
鍵の特定
|
+
|
... |
第二に、鍵の長さで暗号文を区切り、解読します。
区切ったそれぞれをMonoalphabetic cipherとして捉えると頻度分析が有効となるため、容易に解読が可能です。
前のCHAMBERと異なり、このCHAMBERのアルファベット変換はCaesar暗号でありランダムではありません。そのため、頻度分析によって本来のA～Zの頻度と同じようなグラフになるように、暗号文のアルファベットをずらすことで特定ができます。
|
余談
|
+
|
... |
以上の説明でわかる通り、この暗号は鍵の長さが長いほど解読が難しくなり、最も難しいのは暗号文の長さ以上に鍵の長さが長いときです。しかし、暗号を送るために同等以上の鍵を共有するのは、あまり意味がありません。鍵の長さはせいぜい15文字の覚えられる程度にしたいのですが、これを使って100文字の平文を周期を被らせずに暗号化するには、どんな方法が考えられるでしょうか。
例1
|
+
|
... |
例として、鍵を「DECRYPT THESE MSG」とします。
このとき、平文を「DECRYPT」「THESE」「MSG」で3回vigenere cipherとして暗号化します。このとき周期は、各文字数の公倍数である7*5*3=105となるため、100文字以上の周期で暗号化が可能になります。
|
例2
|
+
|
... |
例として、平文を「THIS IS PLAIN TEXT」、鍵を「KEY」とします。
元の鍵に平文自身を付与した文字列を新しく作成します。（「KEYTHISISPLAINTEXT」）
これを新たな鍵として、暗号化を行います。
「THISISPLAINTEXT」+「KEYTHISISPLAINT」→「EMHMQBIUTYZUNLN」
この方法の場合、実質無限の長さの鍵が得られます。
（これはAutokey Cipherと呼ばれ、専用の解読方法が存在します。）
|
|
|
※解答は、ROT13で暗号化して記載しています。詳しくは、
よくある質問をご参照ください。
PUZZLE 01
HINT
|
+
|
... |
HINT 1
|
+
|
... |
「BGL」には、ヒントの「ASH」が割り当てられ、「AND」に復号される。
|
|
ANSWER
|
+
|
... |
GUHAQRENAQYVTUGAVAT
|
PUZZLE 02
HINTs
|
+
|
... |
HINT 1
|
+
|
... |
最初の「JCW」の「J」と、後半の「JCW」の「J」は、15文字離れている。
よって、鍵の長さで考えられるものは、1文字、3文字、5文字、15文字。
|
HINT 2
|
+
|
... |
「JCW」を復号すると「THE」になると仮定して、鍵を求める。
|
|
ANSWER
PUZZLE 03
HINTs
|
+
|
... |
HINT 1
|
+
|
... |
ショートカットする手段もあるが、ここでは一般的な方法（Kasiski's test）に則って解読してみよう。
まずは、鍵の長さを特定する。（本ページ冒頭の説明参照）
コピペ用暗号文
LAFLUIWOYWPADUFHSNBVSWVNDZQDUF
RBPLUYQPLWLPHZRLUEDUBSYMIPRDIJ
HTYQUCUZYLKFRSKHZBUHULUEKPQFOY
LYSSAMWOCWHZOLGDTDDPPOFDDTGOPY
UDGWOYOSDRYKVVDVLAULRZYGWPLJZY
QKYPTWVLJIAFHHSWOMUVDDAPLMJLUE
PVLRNPDWFXWMQAFHZSEQCFAGQDFLJF
LHLDSWCLMQLFXUBULBDUBVPVWFQHWY
UHRHJGSOCUZZXAGEVLILQVAFDARKPQ
LZCQAGULJBUCZAMPL
|
HINT 2
|
+
|
... |
繰り返し登場する3文字以上の文字列を着色した。
これらの同色同士の間隔の公約数が鍵の長さの候補となる。
LAFLUIWOYWPADUFHSNBVSWVNDZQDUF
RBPLUYQPLWLPHZRLUEDUBSYMIPRDIJ
HTYQUCUZYLKFRSKHZBUHULUEKPQFOY
LYSSAMWOCWHZOLGDTDDPPOFDDTGOPY
UDGWOYOSDRYKVVDVLAULRZYGWPLJZY
QKYPTWVLJIAFHHSWOMUVDDAPLMJLUE
PVLRNPDWFXWMQAFHZSEQCFAGQDFLJF
LHLDSWCLMQLFXUBULBDUBVPVWFQHWY
UHRHJGSOCUZZXAGEVLILQVAFDARKPQ
LZCQAGULJBUCZAMPL
例えば、2つ目のLUEと3つ目のLUEの間隔は96文字であるから、
鍵の長さはである1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 96のいずれかの可能性が高い。
同様の方法で公約数を求めると、鍵の長さは
となる。
|
HINT 3
|
+
|
... |
鍵の長さが特定できたら、暗号文を鍵の長さごとに区切り、頻度分析を行う。
すなわち
1文字目、4文字目、7文字目、…
2文字目、5文字目、8文字目、…
3文字目、6文字目、9文字目、…
のグループに分け、それぞれのアルファベット頻度を算出する。
|
HINT 4
|
+
|
... |
各グループの頻度は、本来のアルファベットの頻度をアルファベット順に何文字か回転させたものになっている。
よって、本来のアルファベット頻度をアルファベット順にずらした26通りの頻度に対して、各グループに近いものをそれぞれ求める。
機械的に実施する場合は、交差エントロピーを用いてズレを数値化するとよい。
|
|
ANSWER
最終更新：2024年08月13日 12:59
