（一）Python密碼學之旅---02古典密碼之凱撒密碼推廣

02-04

安全性是密碼學不可迴避的話題，是密碼演算法最為重要的特性。一旦密碼演算法被破解，那麼人們將不再使用它。古典密碼在用現代的眼光來看，都是不安全的，可以被分析破解。隨著計算機技術的發展和破譯方法的推陳出新，很多原來安全的密碼也會變得不安全。比如DES演算法，因被暴力破解而不再使用了。

本節將從安全性的角度，對凱撒密碼進行分析，在此基礎上介紹它的推廣版本。

一、凱撒密碼的分析

回顧下凱撒密碼：其基本思想是：通過把字母移動一定的位數來實現加密和解密。例如，密匙是把明文字母的位數向後移動三位，那麼明文字母B就變成了密文的E,依次類推，X將變成A，Y變成B，Z變成C。

也就是說，當密鑰key=3時，明文字母表和密文字母表分別是：

明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC

那麼，請問密鑰有多少種可能？

很簡單25個。因為當key=26時，明文還是不變換。

因此，可以通過窮舉法，很輕易地進行破解！

凱撒密碼的破解演算法窮舉演算法比較簡單，在此不作贅述，留給讀者自行編寫。

二、凱撒密碼的推廣

凱撒密碼的密鑰空間有限，導致安全性極差，那麼如何對它進行改進呢？

一個簡單的思路是：將明文字元進行任意替換，也就是「a」可以替換為26個字元，「b」在剩餘25個字元中任意選擇一個，依次類推。我們將這樣的凱撒密碼稱之為「凱撒密碼推廣演算法」。n

那麼「凱撒密碼推廣演算法」的密鑰量是多少呢？

答案是26！= 4.0329146× $10^{26}$ （26的階乘）。大家可以用Python來計算下26的階乘。這是一個極為巨大的數字，比DES的密鑰大10個數量級。試想下，如果計算機每秒運行1萬次窮舉攻擊演算法，那麼完全運算完需要多長的時間呢？

實現代碼為：

class ECaesarCipher( ):n def __init__(self, message=None):n self.message = messagen self.cipherMessage=""n n #獲取「a」到」z「的順序字元表n pT=tuple(string.ascii_lowercase)n n #建立隨機化的密文字元表n cT=[]n temp=range(0,26)n random.shuffle(temp)n for x in temp:n cT.append(pT[x])n n #建立密碼本，即明文、密文對照表，這裡使用了字典結構n self.keyTable={}n for x,y in zip(pT,cT):n self.keyTable[x]=yn n n def encrypt(self):n self.cipherMessage=""n n for x in self.message:n if x== :n self.cipherMessage+= n elif x.isupper():n self.cipherMessage+=self.keyTable[x.lower()].upper()n else:n self.cipherMessage+=self.keyTable[x]n n return self.cipherMessagen n def decrypt(self):n keyTableDec=dict((value,key) for key,value in self.keyTable.iteritems())n message=""n if self.cipherMessage:n for x in self.cipherMessage:n if x== :n message+= n elif x.isupper():n message+=keyTableDec[x.lower()].upper()n else:n message+=keyTableDec[x]n n return messagen

演算法建立了ECaesarCipher類，支持大小寫英文字母、空格作為明文字元，初始化時隨機產生明密文對照表。這個明密文對照表也可以稱為密碼本，是必須要私密保存的密鑰。

丟失了密碼本，也就意味著該密碼的破解。二戰中德國使用的ENIGMA密碼機，被成為為當時最可靠的加密系統。在第二次世界大戰開始時，德軍通訊的保密性在當時世界上無與倫比。似乎可以這樣說，ENIGMA在納粹德國二戰初期的勝利中起到的作用是決定性的。然而1941年英國海軍在Joe Baker-Cresswell艦長的鬥牛犬號軍艦捕獲德國潛艇U-110才真正拿到德國海軍用的密碼機和密碼本，這讓原本連數學天才圖靈也破譯不出的德軍密碼機得到破譯。

我們來運行一下：

>>ec=ECaesarCipher("I want to fly to sky")n>>print ec.keyTablen{a: q, c: f, b: y, e: v, d: g, g: e, f: r, i: u, h: x, k: p, j: z, m: d, l: n, o: s, n: o, q: b, p: c, s: m, r: i, u: h, t: w, w: k, v: j, y: l, x: a, z: t}n>> ec.encrypt()nU kqow ws rnl ws mpln>>ec.decrypt()nI want to fly to skyn

三、凱撒密碼推廣演算法的安全性分析

該演算法密鑰量如此的巨大，如果「明密文對照表」得到有效的保護，它是安全的嗎？

並不是。自然語言有一定的統計規律，如每個字元出現的頻度是不同的。下圖為英文中每個字元的使用頻度（見參考文獻3）。我們發現e的頻度是最高的，為12.702%。前五位的是e、t、a、o、i，而後五位是k、j、x、q、z。

每個字母使用頻度的不同為破譯代替密碼提供了密鑰信息。密文字母出現的概率對應著明密文對照表中明文字母出現的概率。只要統計出密文中每個字母的概率，再將其與自然語言中概率相同的字母一一對應，便可找出相應明文。除此之外，還可以統計出雙字母，三字母及多個字母組合的概率，以提高破譯的準確性。

但對於特殊的明文段落，統計分析有時也會束手無策。1969年法國作家喬治斯．佩雷克寫了一本200頁的小說《逃亡》，其中沒有一個含有字母e的單詞。更令人稱道的是英國小說和評論家吉爾伯特．阿代爾成功地將《逃亡》譯成英文，而其中居然也沒有一個字母e。阿代爾將這本譯著取名為《真空》。

四、總結

在密碼學和信息安全中，安全是相對的，是有條件的安全。一般指的是在現有計算資源和已知演算法條件下，在多項式時間內無法攻破該演算法。比如廣泛使用的RSA演算法，目前認為是安全的，但在量子計算機出現後，使用Shor可以攻破它。現有密碼學面臨著量子計算機的威脅，很多人在研究抗量子演算法（或後量子演算法）。

請大家在閱讀後，使用Python自行編寫凱撒密碼推廣演算法的破解演算法。

參考文獻：

彭長根.現代密碼學趣味之旅.金城出版社.2015
Enigma machine - Wikipedia
Letter frequency. https://en.wikipedia.org/wiki/Letter_frequency