文献あり

1.1 Simple substitution ciphers (単一換字式暗号)

1.1 Simple substitution ciphers

暗号理論の自主ゼミを行っており、その学習成果をまとめるためにこの記事を書きました。ゼミでは普段洋書をテキストとして使用していますが、この記事ではその内容を日本語で分かりやすく解説しています。今回は暗号の中でも単純な単一換字式暗号について説明します。

1.1.1 Cryptanalysis of simple substitution ciphers

単一換字式暗号はざっくり言うと、元の文字を別の文字に一対一で置き換える暗号のことです。

次のような写像を定義します。

$f:\{a,b,c,\cdots,x,y,z\}\rightarrow \{A,B,C,D,\cdots,X,Y,Z\}$

写像$f$は、小文字のアルファベットを大文字のアルファベットに変換するというルールを表しています。

このとき、暗号化前の文字は、異なる文字に割り当てられるとします。(つまり、写像$f$は全単射である)

暗号化した文字列から元の文字を一意的に復元するためには、
「異なる平文の文字が同じ暗号の文字に対応してしまう」ことを避ける必要がある。
そのため、写像は全単射でなければならない。

このような状況で、小文字のアルファベットから大文字のアルファベットに変換する手法を使って単一換字式暗号を考えていきます。

この暗号を考える上で、以下のことは前提としておきたいと思います。

➀小文字（$a〜z$）を1文字ずつ、大文字（$A〜Z$）のいずれかに割り当てていく。
②一度使った大文字は、他の小文字の割り当て先として再利用できない（被りはNG）。

上を踏まえたうえで、$\{a,b,c,\cdots,x,y,z\}$の中から一つを選びます。例えば、$a$を選んだとします。このとき、$a$を$\{A,B,C,D,\cdots,X,Y,Z\}$の中から好きなものに変換することができます。アルファベットは全部で26個あるので、全部で26通りの選び方があります。

今回は、簡単のために$a\rightarrow A$に変換したとします。($f(a) = A$とする。)

この操作を繰り返していきます。

次に$b$を$\{A,B,C,D,\cdots,X,Y,Z\}$から好きなものに選んでいきたいところですが、$a$を大文字にするのに$A$を使ってしまっているため、$b $の対応先は$A$を除いた$\{B,C,D,\cdots,X,Y,Z\}$の中から選ばなくてはなりません。このとき、$b$の対応先の選び方は25通りです。

つまり、2つの文字の対応先の選び方は$26\cdot 25 = 650$通りと求めることができます。

これをすべてのアルファベットにおいてやると、

$26\cdot 25\cdot 24\cdots 1 = 26! = 403291461126605635584000000$通りあるということが分かります。

これは$10^{26}$よりも大きな数です。$a\rightarrow A$のように各アルファベットをどの文字に置き換えるかをまとめた一つの対応表のことを、暗号理論ではkey(鍵)といいます。

例えばこんな状況を考えます。

EveさんがBobのある一つのメールを傍受した。彼女は、このメールを単一換字式暗号で考えられうるすべてのパターンを試すことで解読しようとしている。

このように事前にkeyを知らない状態で、暗号を解こうとすることを暗号解読といいます。

もし、Eveさんが1秒間に100万もの選択肢を試すことができたとすると、すべてのパターンを試すのに$10^{13}$年かかります。宇宙の年齢が$10^{10}$年といわれているので、EveさんはBobのメールを解読することは不可能ということになります。なので、Bobのメールは安全で、心配する必要はないという結論が得られます。

本当にそうでしょうか？

この暗号が絶対解けないかといわれると、実はそうではないのです。

Your opponent always uses her best strategy to defeat you, not the strategy that you want her to use. Thus the security of an encryption system depends on the best known method to break it. As new and improved methods are developed, the level of security can only get worse, never better.
出典：An Introduction to Mathematical Cryptographyより引用

書かれている内容を日本語訳すると、次のようになります。

『相手はあなたが使ってほしい戦略ではなく、暗号を解読するために最も効果的な手段を常に使ってくる。暗号システムの安全性は、その暗号を破るために現在知られている最も優れた方法によって決まる。新しく、より優れた解読方法が見つかれば、暗号の安全性は低下することはあっても、向上することはない』

単一換字式暗号は、非常に多くのパターンが存在するものの、実際は非常に簡単に解けてしまいます。実際、毎日の新聞や雑誌では、毎日のクロスワードパズルとして暗号のパズルが掲載されているようです。

なので、Eveさんはある規則を持った英語の文章の単一換字式暗号を簡単に解読できてしまうのです。

英語の文字の出現には偏りがあります。例えば、以下のようなものです。
・qのあとにはuがくることが多い
・eやtのような文字がfとcのような文字より多く登場する

Eveさんは暗号化されたメールに含まれる文字の出現頻度を表にまとめると、最も多く登場しているものがeであろうと予想することができます。このようにして、Eveさんはある程度、試行錯誤するとBobのメールを解読することができてしまう。

具体的に解読する手順を簡単にまとめておく。

➀暗号文に登場する文字が何回現れるかを表にまとめる
②最も多く登場した文字をeと推測する。しかし、短文の場合は、出現頻度が英語全体の統計と一致するとは限らないため、頻度だけで対応関係を断定することはできない。
$\rightarrow$複数の候補を考えて試行錯誤する必要がある

ここから先の推測にはいくつかの方法がある。

➂bigram(バイグラム)を見る
bigram：連続する2文字の組み合わせ
➀、②では一つの文字に注目していたが、ここでは二つの文字の組み合わせに注目する。英語では、thやheなどの2文字のペアがよく登場するので、そこから原文を推測しやすくなる。
➃暗号化前の原文の断片を見て、部分的に判明した平文から、他の文字の対応を推測する。

このようにすると、すべてのパターンを試すことなく、単一換字式暗号を解くことができます。

暗号の安全性を考える上では、「数学的な組み合わせの数」だけでなく、「データの構造や言語の偏りを利用した攻撃方法がないか」という視点が重要になります。

今回は以上です。