Cryptoanalysis
暗号解読に挑戦

通信ネットワーク工学科の分野から, 暗号解読の作業を体験していただくことで デジタル時代の暗号技術への興味と理解を深めていただきたいと思います.

暗号の仕組み,解読の理論については授業で説明します. 以下では解読作業の手順を説明します.

デモプログラムの起動

以下のリンクを右クリック→ 「別ウィンドウで開く」を利用して暗号解読デモプログラムを起動して下さい.

暗号解読デモプログラム (English version of the demonstration program)

キーの長さを決める

上記「暗号解読デモプログラム」を開いて最初に表示されている,0,1が連続したものが暗号文です.0か1一つを「1ビット」 と言います.画面をよく見ると 8 ビットずつ区切られていることがわかります. コンピュータでは多くの場合 8 ビットを一つのデータのまとまりとして処理します.

この暗号は 8 ビットのデータ数個をキーとして使用します. この個数を「キーの長さ」といいます. キーは前もって送受信者が相談して決めておき,当事者以外には秘密にしておきます. もとの文(平文-ひらぶん-といいます)を暗号文にに変えるためにキーを使い, 逆に暗号文からキーを使って平文に戻します.このキーを第三者(あなた)が 見破れば暗号を破ることができます.

暗号文の下に今回の暗号文の統計データが表示されます. 暗号文は 8 ビットのデータの連続ですが,暗号解読の最初の手がかりとして 暗号文とそれを何文字かずらしたものを並べ,一致する確率を調べます. 例えば「ずれ量」1の「一致確率」は暗号文とそれ自身を1文字先にずらしたものが 一致する確率を計算したものです.

00010100↓ずれ量1
01011011・・・一致?・・・00010100
00010101・・・一致?・・・01011011
00110011・・・一致?・・・00110011
00100010・・・一致?・・・00010101
  ・  ・
  ・  ・
00010100↓ずれ量2
01011011
00010101・・・一致?・・・00010100
00110011・・・一致?・・・01011011
00100010・・・一致?・・・00110011
  ・  ・
  ・  ・

先ほどの「一致確率」の項目を見ると,ある周期で確率が高くなっているはずです. その周期がキーの長さになります. 例えば以下のデータは,ずれ量 3,6,9 の確率が他と比較して高いので キーの長さは "3" になります.数字ではなく桁数に注目します.

ずれ量一致確率
10.0035756853396901
20.0035799522673031
30.0884109916367981
40.0047846889952153
50.0023952095808383
60.0551558752997602
70.0012004801920768
80.0036057692307692
90.0758122743682314

このプログラムではキーの長さは 3 から 5 の範囲でランダムに 選ばれます.

【作業1】
「一致確率」がどの周期で大きくなっているかを見極め, 自分が推定したキーの長さを「キーの長さ」欄に入力し, 「送信」ボタンを押して下さい.

各キーを決める

キーの長さが決まればそれぞれ個別のキー文字の 8 ビットが何なのかを決めます. これができればキーを完全に見破ったことになり,暗号を破ったことになります. (どんな暗号文でも平文に戻すことができる)

例えばキーの長さが 3 の場合でキー文字を最初の文字から順に キー1,キー2,キー3,だったとします(それぞれ8ビット). 暗号文はキーを繰り返し,すなわち キー1,キー2,キー3,キー1,キー2,キー3,キー1,キー2,キー3 ... と並べたものを平文とXORと呼ばれる演算 "⊕" を行って作られます.

平文1 平文2 平文3 平文4 平文5 平文6 平文7 平文8 平文9
キー1 キー2 キー3 キー1 キー2 キー3 キー1 キー2 キー3
|| || || || || || || || ||
暗号文1 暗号文2 暗号文3 暗号文4 暗号文5 暗号文6 暗号文7 暗号文8 暗号文9

キーの長さが 3 の場合,キーは 3 個しかありません. 1, 4, 7, ... 文字めの暗号文は キー1 で, 2, 5, 8, ... 文字めの暗号文は キー2 で, 3, 6, 9, ... 文字めの暗号文は キー3 で変換されています.

キーの長さが 3 の場合,画面の「出現確率」には 1 から 3 までのキー位置の暗号文の統計情報が表示されます. キー位置 1 は暗号文の 1,4,7, ... 番目の文字 についての統計, キー位置 2 は暗号文の 2,5,8, ... 番目の文字 についての統計, キー位置 3 は暗号文の 3,6,9, ... 番目の文字 についての統計です. 同じキー位置の文字はすべて同じキーで暗号化されています. 「1位」にそれぞれのキー位置で最も出現頻度の高かった暗号文の文字とその頻度が 表示されています.

【作業2】
下と同じものをメモ帳に書き込んでください. 「1位」の各欄に各キー位置の 「1位」 に表示された暗号文の 8 ビットを記入して下さい. (今は 2 位以下は使用しません)キーの長さが 3 の場合は キー位置 4 以降は空欄に,キーの長さが 4 の場合は キー位置 5 以降は空欄にして下さい.

キー位置 1 2 3 4 5
1位
空白記号 00100000 00100000 00100000 00100000 00100000
|| || || || ||
キー

次に必要になるのが英語の各文字の出現頻度です.空白文字を含んだ英文 テキストの場合,空白文字が最も出現頻度が高いことが知られています. このことから,各ポジションの「1位」の 8 ビットが 元の平文では空白記号であったと予想します.

空白記号に対応する 8 ビットは ASCII(アスキー)と呼ばれる規格で "001000000" と決められています.

まず,キー1について説明します. 空白記号 ``00100000'' とキー1 で ⊕ 演算を行ったものが 上で 記入した「キー位置1」 の 「1 位」になるように「キー1」を推測します. 具体的には以下のようにしてキーを決定します.

【作業3】
キー位置 1 から順に,上で「1位」欄に記入したビット列の 左から 3 桁目だけを反転(0→1, 1→0)させたものを 「キー」欄に記入して下さい.3 桁目以外は「1位」欄のものを そのまま写して下さい.どのキーの長さ,キー位置でも反転させるのは 3桁目だけです.

【作業4】
作業3で記入したキーすべてを「キー」欄に入力して「送信」ボタンを押して下さい.

自動的に正しいかどうかチェックされます. 正しければ「おめでとうございます」の表示と暗号化される前の平文が, 間違っていれば「キーが正しくありません」の表示と, 指定したキーで復号を試みたものが表示されます.

統計を利用した手法なので手順通りに行っても必ず正しく解読できるとは 限りません.推測したキーが正しくなかった場合で 推定したキーの一部を修正したい場合は,ブラウザの「戻る」ボタンで戻って 入力をやりなおすことができます.推測が間違っていそうなキーについて 1位ではなく 2 位が空白文字だったと仮定してキーを計算し, やりなおしてみて下さい. 問題の選択からやり直したい場合は 「最初からやりなおす」を押して下さい.

解説pdf版


Updated in August 10, 2016, Yamamoto Hirosh