結城浩氏の「暗号技術入門 第3版 秘密の国のアリス」を読んでいく中で、折角なので自分でも勉強ついでにコーディングをしてみました。
今回は単一換字暗号と頻度分析について学んでいきます。
単一換字暗号とは
単一換字暗号とは、各アルファベットにおいて一対一の対応関係を作り暗号化します。
シーザー暗号では、ただアルファベットを一律でずらすだけのため、鍵空間としては26パターンしかないですが、単一換字暗号の場合は26!となるため鍵空間は大きくなります。
頻度分析とは
頻度分析とは、平文で使われる文字の頻度を分析するものです。
頻度分析ではブルートフォースアタックで解読するのは困難となりますが、文字や単語の出現頻度などで推測することにより解読することを可能とします。
そのため、平文は長い方が解読しやすくなります。
Pythonで単一換字暗号を実装
では、Pythonで単一換字暗号を実装していきます。
from collections import defaultdict
import re
import string
import random
def key_gen():
key = list(string.ascii_uppercase)
random.shuffle(key)
key_dic = {}
for i, s in enumerate(list(string.ascii_lowercase)):
key_dic[s] = key[i]
return key_dic
def enc_simple_substitution_cipher(lines, key_dic):
enc_lines = ""
for s in lines:
enc_lines += key_dic[s]
return enc_lines
lines = """some plain text""".lower()
lines = re.sub(r"[,.!?':;*()\-\n ]", "", lines)
key_dic = key_gen()
enc_lines = enc_simple_substitution_cipher(lines, key_dic)
print(enc_lines)
# 実行結果
# JGRFTCYFVCKJGTTGSTURBFWVZGPQVCACTCKJGTTGSTURBCLQVCACTKCLQVGCKJGTTGSTURBANLQVGPANLQVGPCKJGTTGSTURBANLQVCARTGIYVRTCKJGTTGSTURBBGKTGIKQRSKGCKJGTTGSTURBIGBKGSGRIRJCVCTZANFBTKKQGACRVARKGKRSGBTKQGACRVGBNFWUTNJSGRDTUGSFVGKRVTUNFWUQSRATCARVCTZJGRTKQFSCTZGSSNSKKUNFVIBGOGSQRKKKCVGBTVZFBVGKKGPQVCACTVZKCVGBAGICBTUGYRAGNYRLJCWFCTZSGYFKGTUGTGLQTRTCNBTNWFGKKTUGSGKUNFVIJGNBGRBIQSGYGSRJVZNBVZNBGNJOCNFKMRZTNINCTRVTUNFWUTURTMRZLRZBNTJGNJOCNFKRTYCSKTFBVGKKZNFSGIFTAUBNMCKJGTTGSTURBBGOGSRVTUNFWUBGOGSCKNYTGBJGTTGSTURBSCWUTBNMCYTUGCLQVGLGBTRTCNBCKURSITNGPQVRCBCTKRJRICIGRCYTUGCLQVGLGBTRTCNBCKGRKZTNGPQVRCBCTLRZJGRWNNICIGRBRLGKQRAGKRSGNBGUNBDCBWWSGRTCIGRVGTKINLNSGNYTUNKG
上記はある文章を単一換字で暗号化してみました。
これを頻度分析で解読していきたいと思います。
Pythonで頻度分析をしてみる
それでは上記の暗号文を頻度分析で解読してみます。
インタラクティブに文字を置換できるように以下のメソッドを追加してみます。
def frequency_analysis(enc_lines):
dict = defaultdict(int)
for word in enc_lines:
dict[word] += 1
dict = sorted(dict.items(), key=lambda x:x[1], reverse=True)
print(dict)
print(enc_lines)
while (True):
target = input("対象の文字：")
str = input("置き換える文字：")
enc_lines = enc_lines.replace(target, str)
print(enc_lines)
# 実行結果
[('G', 88), ('T', 75), ('R', 53), ('C', 52), ('K', 45), ('N', 41), ('B', 40), ('V', 33), ('S', 32), ('U', 29), ('F', 21), ('J', 20), ('Q', 20), ('A', 17), ('I', 17), ('Z', 15), ('L', 15), ('Y', 11), ('W', 11), ('P', 6), ('O', 5), ('M', 4), ('D', 2)]
JGRFTCYFVCKJGTTGSTURBFWVZGPQVCACTCKJGTTGSTURBCLQVCACTKCLQVGCKJGTTGSTURBANLQVGPANLQVGPCKJGTTGSTURBANLQVCARTGIYVRTCKJGTTGSTURBBGKTGIKQRSKGCKJGTTGSTURBIGBKGSGRIRJCVCTZANFBTKKQGACRVARKGKRSGBTKQGACRVGBNFWUTNJSGRDTUGSFVGKRVTUNFWUQSRATCARVCTZJGRTKQFSCTZGSSNSKKUNFVIBGOGSQRKKKCVGBTVZFBVGKKGPQVCACTVZKCVGBAGICBTUGYRAGNYRLJCWFCTZSGYFKGTUGTGLQTRTCNBTNWFGKKTUGSGKUNFVIJGNBGRBIQSGYGSRJVZNBVZNBGNJOCNFKMRZTNINCTRVTUNFWUTURTMRZLRZBNTJGNJOCNFKRTYCSKTFBVGKKZNFSGIFTAUBNMCKJGTTGSTURBBGOGSRVTUNFWUBGOGSCKNYTGBJGTTGSTURBSCWUTBNMCYTUGCLQVGLGBTRTCNBCKURSITNGPQVRCBCTKRJRICIGRCYTUGCLQVGLGBTRTCNBCKGRKZTNGPQVRCBCTLRZJGRWNNICIGRBRLGKQRAGKRSGNBGUNBDCBWWSGRTCIGRVGTKINLNSGNYTUNKG
まず最初の実行結果から各文字の出現回数を降順で表示しています。
文字の頻度ではe、次にtが多いので各文字を置換してみます。
JeRFtCYFVCKJetteStURBFWVZePQVCACtCKJetteStURBCLQVCACtKCLQVeCKJetteStURBANLQVePANLQVePCKJetteStURBANLQVCARteIYVRtCKJetteStURBBeKteIKQRSKeCKJetteStURBIeBKeSeRIRJCVCtZANFBtKKQeACRVARKeKRSeBtKQeACRVeBNFWUtNJSeRDtUeSFVeKRVtUNFWUQSRAtCARVCtZJeRtKQFSCtZeSSNSKKUNFVIBeOeSQRKKKCVeBtVZFBVeKKePQVCACtVZKCVeBAeICBtUeYRAeNYRLJCWFCtZSeYFKetUeteLQtRtCNBtNWFeKKtUeSeKUNFVIJeNBeRBIQSeYeSRJVZNBVZNBeNJOCNFKMRZtNINCtRVtUNFWUtURtMRZLRZBNtJeNJOCNFKRtYCSKtFBVeKKZNFSeIFtAUBNMCKJetteStURBBeOeSRVtUNFWUBeOeSCKNYteBJetteStURBSCWUtBNMCYtUeCLQVeLeBtRtCNBCKURSItNePQVRCBCtKRJRICIeRCYtUeCLQVeLeBtRtCNBCKeRKZtNePQVRCBCtLRZJeRWNNICIeRBRLeKQRAeKRSeNBeUNBDCBWWSeRtCIeRVetKINLNSeNYtUNKe
上記の"ette"の文字は"better"ではないかと推測されるため、各文字も併せて置換してみます。
beRFtCYFVCKbettertURBFWVZePQVCACtCKbettertURBCLQVCACtKCLQVeCKbettertURBANLQVePANLQVePCKbettertURBANLQVCARteIYVRtCKbettertURBBeKteIKQRrKeCKbettertURBIeBKereRIRbCVCtZANFBtKKQeACRVARKeKRreBtKQeACRVeBNFWUtNbreRDtUerFVeKRVtUNFWUQrRAtCARVCtZbeRtKQFrCtZerrNrKKUNFVIBeOerQRKKKCVeBtVZFBVeKKePQVCACtVZKCVeBAeICBtUeYRAeNYRLbCWFCtZreYFKetUeteLQtRtCNBtNWFeKKtUereKUNFVIbeNBeRBIQreYerRbVZNBVZNBeNbOCNFKMRZtNINCtRVtUNFWUtURtMRZLRZBNtbeNbOCNFKRtYCrKtFBVeKKZNFreIFtAUBNMCKbettertURBBeOerRVtUNFWUBeOerCKNYteBbettertURBrCWUtBNMCYtUeCLQVeLeBtRtCNBCKURrItNePQVRCBCtKRbRICIeRCYtUeCLQVeLeBtRtCNBCKeRKZtNePQVRCBCtLRZbeRWNNICIeRBRLeKQRAeKRreNBeUNBDCBWWreRtCIeRVetKINLNreNYtUNKe
今度は"bettert"と続いているため、前後を考えると"isbetterthan"という文章ではないかと推測してみます…。
こんなことを繰り返していると、平文が以下の"The Zen of Python"であることがわかります。
Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat is better than nested. Sparse is better than dense. Readability counts. Special cases aren't special enough to break the rules. Although practicality beats purity. Errors should never pass silently. Unless explicitly silenced. In the face of ambiguity, refuse the temptation to guess. There should be one-- and preferably only one --obvious way to do it. Although that way may not be obvious at first unless you're Dutch. Now is better than never. Although never is often better than *right* now. If the implementation is hard to explain, it's a bad idea. If the implementation is easy to explain, it may be a good idea. Namespaces are one honking great idea -- let's do more of those!
