書記が数学やるだけ#869 シーザー暗号・アフィン暗号・ヒル暗号の解読
古典暗号の解読法について代表例を示す。
問題
表：OCZRCFCAFLCAHZRCEVWZCXUZIZCUWVAPXCPZAHAPQIQAPCFCPHCSZEVWAVCUZINLWURBEUZWSCWVUEPCXAQCUZWSZPIVKEWLWZYFPAJWXCHAPZRCSAQQAVXCHCVSCFPAQAZCZRCMCVCPILOCLHIPCIVXUCSEPCZRCNLCUUWVMUAHLWNCPZYZAAEPUCLJCUIVXAEPFAUZCPWZYXAAPXIWVIVXCUZINLWURZRWUSAVUZWZEZWAVHAPZRCEVWZCXUZIZCUAHIQCPWSI
説明
暗号解読の方法のうち，暗号文単独攻撃（暗号文のみ手がかりとする）には総当たり攻撃や頻度分析が挙げられる。このほか，既知の平文から攻撃する方法などもある。
解答
総当たり攻撃（ブルートフォースアタック）とは，暗号解読方法のひとつで，可能な組合せを全て試すやり方である。例えばシーザー暗号であれば，シフト数は25通りなので，これを全て試せば簡単に解読できる。一方でアフィン暗号は乗算に多いて12通り考えられるので，計312通りであり，これも全て試すのは容易である。
一方でヒル暗号は，区切る文字数を大きくすると鍵数は急激に膨張し，総当たり攻撃に強いと言える。
ここまで見てきた暗号は全て単一換字式暗号であることから，平文の文字に対して暗号文の文字が常に同じ文字に変換される。この場合，アルファベットの頻度から対応する文字を推測する頻度分析が有効である。
一般的な英文における頻度の例として，アメリカ独立宣言の冒頭部分を見てみる。
When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation.
import matplotlib.pyplot as plt
from collections import Counter
import string
#サンプルの英語テキスト （例：アメリカ独立宣言の冒頭部分）
english_text = """ When in the Course of human events, it becomes necessary for one people to dissolve the political bands which have connected them with another, and to assume among the powers of the earth, the separate and equal station to which the Laws of Nature and of Nature's God entitle them, a decent respect to the opinions of mankind requires that they should declare the causes which impel them to the separation. """
#小文字に変換し 、アルファベット以外の文字を除去
english_text = english_text.lower()
english_text = "".join(filter(lambda x: x in string.ascii_lowercase, english_text))
#文字頻度をカウント
letter_counts = Counter(english_text)
#頻度順 （降順）にソート
sorted_letters = sorted(letter_counts.items(), key=lambda x: x[1], reverse=True)
#ソートしたデータを取得
letters, frequencies = zip(*sorted_letters)
#ヒストグラムを作成
plt.figure(figsize=(10, 5))
plt.bar(letters, frequencies, color='lightcoral', edgecolor='black')
plt.show()一般的な英文では，概ね e, t, a, o, i, n, ..., j, x, q, z の順で出現する。
次に暗号文の頻度分析を行う。この場合，english_textに暗号文を代入すれば良いためコードは省略。このグラフから，C→E，Z→Tであることが推測できる。このほか，THEなどの頻出用語などを用いることで候補を絞ることができる。
※問題の平文（アメリカ合衆国憲法前文より）；
We the People of the United States, in Order to form a more perfect Union, establish Justice, insure domestic Tranquility, provide for the common defence, promote the general Welfare, and secure the Blessings of Liberty to ourselves and our Posterity, do ordain and establish this Constitution for the United States of America.
頻度分析のほか，アフィン暗号やヒル暗号などは既知平文攻撃にも弱いことが知られている。以下はアフィン暗号が2つの既知平文から解読可能であることの証明である。
具体的にA-1とBを求める例。
なお，第二次世界大戦でナチス・ドイツが用いたエニグマ (Enigma) の解読において，画一的な挨拶文や導入部，規定どおりの気象報告，結語として用いられた「ハイル・ヒトラー」などの平文が解読に大きく寄与したとされる。
本記事のもくじはこちら：
