移動式のブログ

ガジェット、アニメ、プログラミング、考えたことその他色々・・・特にこれといったテーマはないカオスなブログです。

単換字暗号と頻度分析

f:id:idoushiki:20180828235220p:plain

暗号化のやり方で単換字暗号という方式がある。
単換字暗号は、アルファベットを並び替えるやり方だ。

暗号化のやり方

例えば、
アルファベトの
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"を
"QWERTYUIOPASDFGHJKLZXCVBNM"
に並び替えて対応させれば、


A→Q
B→W
C→E
D→R
E→T
F→Y
G→U
H→I
I→O
J→P
K→A
L→S
M→D
N→F
O→G
P→H
Q→J
R→K
S→L
T→Z
U→X
V→C
W→V
X→B
Y→N
Z→M

AはQでBはWで・・・といった感じになる。

このやり方で"YOU ARE BAKA"を暗号化すると
"NGX QKT WQAQ"になる。

何通りの組み合わせがあるか

アルファベットは26文字ある。
まず、26文字のうち一つを別の文字に対応(A→Qのように)させてペアにしたら、残りは25通りの選び方があり、またペアを作ったら24通りの選び方があり…と繰り返していくと、
26×25×24×...3×2×1という感じになる。
そして、アルファベットのペアは26!つまり、403291461126605635584000000通り(27桁)存在する。
そのため、復号できる組み合わせを総当たりで探そうとしても26!の組み合わせから探さなければいけない。

復号する方法

英語の文章で出現する文字には偏りがある。
例えば、英語の長文があるとして、その文章に含まれているアルファベットの出現数を数えたら、「e」が最も多く現れると言われている。
次に「t」「a」「o」「i」などが多く出て来るようだ。
しかし、「z」「x」「q」「j」などはあまり出てこないようだ。
このようなアルファベットの出現頻度を利用すれば元の文を復号することができる。
例えば、暗号文に含まれるアルファベットの数をカウントして、「T」が最もたくさん現れた場合は「T」は長い英文で出現頻度の高い「E」なのではないかと予想がつく。
そして、「Z」が「T」の次にたくさん現れるなら、「Z」は「T」「A」「O」「I」のどれかであると予想できる。
このように1文字1文字調べていき、復号することができる。
このような方法を頻度分析と言う。

頻度分析 (暗号) - Wikipedia

実際に頻度分析をやってみる

以下のようなコードで文字列中のそれぞれの文字の出て来る回数を求めることができる。

このコードで英文を調べた結果は以下のようになる
f:id:idoushiki:20180828232732p:plain

英語で書かれた物語の一部を利用して、Pythonのプログラムですべてのアルファベットの出て来る数を数えたら以下のようになった。
'b': 129, 'a': 543, 't': 685, 'h': 465, 'l': 305, 'x': 8, 'y': 196, 'i': 497, 's': 435, 'q': 4, 'z': 1, 'm': 213, 'p': 95, 'v': 60, 'e': 800, 'g': 114, 'f': 147, 'c': 146, 'o': 619, 'u': 253, 'n': 457, 'r': 353, 'j': 15, 'k': 92, 'w': 196, 'd': 353,

確かにeが1番多く出てくる。そしてt、a...といった感じに英文に出て来る文字に偏りが出て来る。
ウイキペディアに英文で頻出するアルファベットの表があるのだが、だいたいそれと同じようになっている。
頻度分析 (暗号) - Wikipedia

長い英文に出て来る文字を一つ一つ数えて、出て来る割合を棒グラフにすると、出て来る文字の量は以下のグラフのようになるようだ。
f:id:idoushiki:20180831003201j:plain



今回の"ABCDEFGHIJKLMNOPQRSTUVWXYZ"を
"QWERTYUIOPASDFGHJKLZXCVBNM"に対応させたやり方だと、以下のようになる。
't': 800, 'v': 196, 'b': 8, 'o': 497, 'x': 253, 'j': 4, 'p': 15, 'n': 196, 'u': 114, 'c': 60, 'y': 147, 'm': 1, 'q': 543, 'a': 92, 'i': 465, 'f': 457, 'w': 129, 'l': 435, 'd': 213, 's': 305, 'e': 146, 'k': 353, 'h': 95, 'g': 619, 'r': 353, 'z': 685

なぜ頻度分析で元の文を復号できるのか

サイコロはどの数字の目も1/6の確率ででる。
数回振っただけではたまたま1ばかり多く出るとか2しか出なかったとかあるかもしれない。
しかし、サイコロを振る回数を増やしていけばどの目も出る確率が1/6に限りなく近づいていく。
そして、1万回とか振ってみて出た目を全て数えれば、どの目も全部ほぼ1/6の確率で出ることになる。
このようなことを「大数の法則」と言うようだ。


英文を書いた時に出るアルファベット26文字全てが同じ頻度で出て来るなら頻度分析は利用できない。
しかし、英文の特性からしてそれなりに内容のあるまともな長い文章を書けばかならず「e」が多く含まれていて、次に「t」が多く含まれていてと偏りが出てしまう。
アルファベットには頻出文字に偏りがある。
そのため文章の量が多くなればなるほど、その偏りが強く現れるようになる。
そして、頻度分析 (暗号) - Wikipediaこの画像の出現頻度とほぼ同じになっていく。
そのため、単換字暗号でどう暗号化しても文字の出現頻度を分析すれば、どの文字がどの文字に対応しているかがわかってしまうのだ。

しかし、数単語で構成されたような英文など、文章が短すぎると暗号前の文章を復号するのは難しい。




独学プログラマー Python言語の基本から仕事のやり方まで

新品価格
¥2,376から
(2018/8/28 23:29時点)