數學中的戰爭，戰爭中的數學——漫談密碼（2）

作者：@謝鈞

長文慎入！多圖殺貓！

在上一篇中，@Banana9學長對密碼學做了一個很好的介紹概括。那麼在這一篇中，就由我來給大家介紹一些具體的信息加密與密碼破解的方式。看完這一篇，大家也能變成密碼學的小能手，不僅可以巧妙地保護自己的隱私，還可以給鐘意的妹紙/漢紙寫一封浪漫的without wax的密碼情書（誤）。本文將由淺而深，最難只要求大家掌握高中數學基礎，請各位放心閱讀！

本篇內容：

一、古典密碼學

1.1 斯巴達將軍的腰帶——變位字謎

1.2 經久耐用的「數字、字母替換」

1.3 凱撒密碼

1.4 凱撒平方

1.5 如何破譯古典密碼

二、現代密碼學

2.1 對稱加密

異或運算

流密碼與塊密碼

電子密碼本（ECB）

加密塊鏈（CBC）

數據加密標準（DES）

高級加密標準（AES）

下一篇內容（敬請期待）：

2.2 非對稱加密（更多未知驚喜）

在密碼學發展的歷史中，主要分為兩個階段，一個是古典密碼學，另一個則是現代密碼學。我們就先從較為簡單的古典密碼學開始：

-------------------------------------------古典密碼學-------------------------------------------

1. 在公元前405年，Lysander，一位古希臘的斯巴達將軍，便將一份加密後的信息寫在了腰帶的背後。解碼時，將腰帶纏繞在特製的木棍上，便能讀出正確的信息。

這種通過改變字母順序的加密方式，被稱為變位字謎（Anagram），常常被用於許多密碼學相關的文學與影視作品當中。例如在丹·布朗的處女作《數字城堡》中，遠誠友加所編造出來的同夥諾斯·達科塔（NDakota）即是友加本名（Tankado）的替換。而在其成名作《達芬奇密碼》中，Anagram的應用更是喪心病狂，例如盧浮宮館長死前留下的遺言，「O, Draconian devil. Oh, lame saint. （嚴峻的魔鬼，跛足的聖人）」代表著「Leonardo da Vinci. The Mona Lisa.（萊昂納多·達芬奇，蒙娜麗莎）」； 「So dark the con of man（男人的騙局是如此陰暗）」代表著「Madonna of the Rocks（岩中聖母）」。而最為人熟知的Anagram，應當還要屬J·K·羅琳所著《哈利波特》系列小說中的伏地魔：其原名為Tom Marvolo Riddle，替換後變為「I am Lord Voldemort」.

2. 古希臘人還發明過另一種用數字替換字母的加密方式：

這種加密方式簡單快捷，而且可以衍生出許多變體，因此一直沿用至第一次世界大戰。

3. 在古典密碼中，最為著名的，便是在上一篇中所提到的「凱撒密碼」。它的加密方式在上一篇中也有講到，因此在這裡就不再贅述了。類似的加密還有Alberti密碼盤：

4. 另一個與凱撒有關的，則是「凱撒平方」。雖然名稱與「凱撒密碼」相近，但是實際原理卻完全不同，反倒是與Lysander相似。其基本原理，是將長度為完全平方數n^2（例如9、16、64等）的明文寫依次在n*n的正方形中（如從左到右），然後改變順序（如從上到下）將正方形中的字母抄下，即為密文。

5. 那麼，當我們遇到古典密碼時，要怎麼破譯他們呢？

第二種與第三種加密方式，是逐字替換，即明文單位與密文單位一一對應。這個概念在高中數學（基本在高一）中的集合與映射中就有提到，相信大家不會陌生。如果是喜歡看福爾摩斯的童鞋們，大概這時候已經猜到了答案。當然，這裡還要照顧一下沒看過的孩紙們，我們還是從頭開始。

密文單位與明文單位一一對應，導致了一個很明顯的問題：密文中每個信息單位（一般情況下為字母）出現的頻率，也會等於明文中某個特定信息單位出現的頻率。可是，無論在何種自然語言體系當中，不同的文字單位都有其特定的出現頻率。尤其在長篇幅、有意義的文字序列中，這個現象表現的尤為明顯。以最典型的英語為例，26個字母的使用頻率分別為（數據來源：Letter frequency (English)）：

我們可以很明顯地看到，字母E的使用頻率遠高於其他字母，另外字母T、A也都有較高的使用頻率；而字母J、Q、X、Z的使用頻率則相對較低。利用這一點，讓我們可以在沒有計算機的幫助下，也有極大的機率在短時間內破解出古典加密方式的密碼。在福爾摩斯探案集約翰·特納的故事中，對於密文「dv mvvw blfi svok」，便是將密文中出現次數最多的字母「v」認定為日常使用頻率最高的字母「e」，然後順藤摸瓜破解出明文為「we need your help」。

而隨著科學技術的進步，古典密碼受到了越來越嚴峻的挑戰。因為需要加密的情報越來越多，而敵人監聽的情報越多，結果就越符合基本分布頻率，密碼也就越容易被破譯；加上計算機的出現，在計算機強大的枚舉能力面前，古典密碼那簡單的字母代換已經不再是一個難題。因此，二戰中的德軍，專門為此發明了加密機Enigma。Enigma類似一台老式打字機（見下圖左），每個按鍵上標寫的是明文字母；而在每個按鍵下面，則是印滿字母的圓盤，按下按鍵後自動打出對應的密文字母（見下圖右）。通過旋轉按鍵下面的圓盤，即可輕易改變字母的替換方式。二戰時德軍利用Enigma，至少每天改變一次加密方式，以此來應對盟軍情報部門的監聽。饒是如此，德軍仍然有不少重要情報被破譯。

而第一種與第四種加密方式，是變位替換。而變位替換之所以一直沒被作為主流的加密方式，在於其過於容易被識別。由於變位替換並不改變字母本身，而是改變其排列順序，因此密文的字母頻率會遵循自然語言的字母頻率。尤其當密文越長，該現象也越為明顯，越容易被識別；而如果密文過短，一來嚴重限制了能夠傳輸的信息量，二來被破解的可能性也越大。但是變位替換是最富有藝術性的古典加密方式之一，尤其是當明文與密文都有意義的時候，常能令人嘖嘖稱奇，回味無窮。

-------------------------------------------現代密碼學-------------------------------------------

隨著計算機技術的發展，古典加密方式越來越不能夠滿足信息加密與傳輸的作用。因此，以計算機技術為基礎的現代密碼學應運而生。與古典密碼學相比，現代密碼學的內容更為艱深，藝術性也更低。雖然我仍然能夠保證將難度限制在高中數學範圍內，但該部分將不再同古典密碼一樣擁有豐富而有趣的例子了。若各位看官到這裡知難而退，不必為此感到羞愧；若有興趣的讀者願意進一步深究，下面便為你們敞開現代密碼學的大門：

由於現代密碼學是建立在計算機技術的基礎之上，因此在接下來的內容中，明文、密文以及其他所有的編碼方式，都將以二進位來表示。至於自然語言與二進位之間的轉換，一般按照ASCII（美國信息交換標準代碼）作為規範。

在現代密碼學中，信息的加密與解密，都要依靠一把「鑰匙」。這把「鑰匙」的本質，是一串數據，或者說是一條信息。而根據「鑰匙」種類的不同，我們將現代密碼學分為兩大類，對稱加密與非對稱加密。

1. 對稱加密，指的是將明文加密，以及破解密文所使用的「鑰匙」，是同一把「鑰匙」。在介紹加密演算法之前，我們得先了解一下數學邏輯中的「異或」運算。

異或運算，它的符號為「⊕」。真值表如下：

異或運算有這樣一種性質，(X⊕Y)⊕Y=X。即對於X而言，使用相同的數字對其做兩次異或運算，將仍然獲得原來的X。因此對稱加密的最基本方式，便是將明文與同等長度的「鑰匙」，按位依次做異或運算，即得到密文；而解密時，將密文再與「鑰匙」按位異或，便得到明文，如圖。

然而這種簡易的加密方式有個致命的缺點，就是每個鑰匙在使用一次之後就必須丟棄，不能重複使用。一旦重複使用，密文就會輕易地被破解。至於原因么，我就吊一弔大家的胃口，放到後面來說。

而在密碼的加密與傳輸過程中，又分為流密碼（Stream Cipher）與塊密碼（Block Cipher）兩種。流密碼的思想很簡單：按位加密、按位傳輸。而塊密碼，則將明文與鑰匙分成許多等長的小塊（Block），每次按塊加密再按塊傳輸，如圖：

由於塊密碼將鑰匙也分成了等長的小塊，所以鑰匙的每個小塊既可以用單塊重複，也可以不重複。若小塊不重複，則與流密碼相似，鑰匙長度與明文長度相同，其安全性較高，但是需要處理的數據量也較大。若小塊重複，則大大縮短了鑰匙長度，加密解密的速度更快，但是安全性較低。其典型代表為ECB（Electronic Code Book，電子密碼本），基本原理如圖。

鑰匙的重複使用容易導致安全問題，這在前面提到過，每個鑰匙在使用一次之後就應當丟棄。而在ECB中，同一個鑰匙被多次使用，更增加了其危險性。具體原因如下：

假設我們有n條信息Mi(i=1,2,...,n)，對它們使用同一個鑰匙K進行加密，則密文Ci=Mi⊕K。當有人獲取了兩條或以上的密文Ci、Cj(i≠j)時，將Ci⊕Cj，便可以得到Mi⊕Mj（證明：Ci⊕Cj=(Mi⊕K)⊕(Mj⊕K)=Mi⊕Mj）。那麼只要有任意一條信息被破解，其他所有信息也都將被破解。而即使在改進加密方式，不再使用異或運算加密，相同的明文塊在加密後，其密文塊也仍然相同。如此，對方便可以使用類似破解古典密碼學的方式，使用頻率分析來破解ECB加密後的密文。

為了解決ECB的安全問題，同時仍然保證其鑰匙長度短、加密速度快等優點，CBC（Cipher Block Chaining，加密塊鏈）等方式依次被研發出來。由於篇幅限制（我好像已經寫了好多的樣子(*/ω╲*)……），這裡僅簡要介紹CBC的加密方式。

CBC的加密方式，簡要來說，就是將前一段的密文，作為後一段明文加密的鑰匙；而接收到密文後，也如此依次解密。基本原理如圖：

與ECB相比，CBC較好地提高了安全性。只要被竊聽的密文不連續，對方便很難破解出明文。

而目前使用最為廣泛的塊密碼，則是DES（Data Encryption Standard，數據加密標準）。但是在講DES之前，需要先介紹DES的基礎，Feistel加密法。

Feistel加密法，是將明文塊拆解成長度相等的左右兩塊，將右半部用鑰匙加密後，再用左半部進行二次加密，得到密文的右半部；而密文的左半部，則直接等同於明文的右半部。如圖：

聽上去挺簡單，感覺要破解好像也沒什麼難度。但是這並不是Feistel的核心，它的思路是，一次加密不夠？那就把密文當成明文，多來幾次……注意到圖中的「F」了嗎？它代表的是輪函數，即在每一輪（每一次加密）中，它所使用的鑰匙K是不一樣的。於是，下面才是Feistel的正常畫風：

而DES的演算法加密，主要就是建立在Feistel的基礎之上。DES將輸入的明文分割成64位長的塊，先對每個明文塊中的位子重新進行組合變換，置換方式如圖

看不清楚是嗎？沒事，我也看不清楚……反正不是重點，你們記住在DES中順序是換過了的就行了……

在將明文塊內的位置順序變換之後，DES會對變換後的明文塊進行連續16輪的Feistel加密。每一輪中進行加密使用的鑰匙，都是由56位的主鑰匙所導出的不同的子鑰匙。關於子鑰匙的導出，以及利用子鑰匙加密過程中的排列擴張、S-Box替換、P-Box排列等，感興趣的童鞋可以私信我，這裡就不再多說了（我覺著可能已經有好多童鞋看不下去了……）。

童鞋們，堅持住！我就講最後一題，最後一題！！講完就下課！！！

啊，歷史的車輪滾滾向前，長江後浪推前浪。作為1977年提出的「前浪」DES，雖然目前的使用仍然比較廣泛，但是也快要被2002年提出的AES（Advanced Encryption Standard，高級加密標準）給拍死在沙灘上了。在RSA lab舉辦的DES Challenge II-2比賽中，EFF（Electronic Frontier Foundation）在56個小時內便破解出了一個DES鑰匙（RSA又是一個大坑，我們將在下節課與這位可愛的大坑見面）。

於是乎，更流弊的加密演算法應運而生，那就是由Joan Daemen和Vincent Rijmen所設計的Rijndael加密法稍加修改而成的AES。要明白AES到底咋回事，我們得先了解AES中的四種基本操作：輪函數加密、位元組替換、移行與混列。其中輪函數加密與DES中的輪函數加密相同，這裡不再贅述。

與DES不同的是，在AES當中，明文被分割成128位長的塊，即每個明文塊長16位元組（1位元組=8位；1byte=8bit）；然後將每個明文塊寫成4*4的矩陣（矩陣，高中數學選修4-2，一般高二就教了；沒學過的童鞋，簡單來說這就像最開頭古典密碼中的方法2，看下圖）。

首先，是位元組替換。其本質與古典加密中的替換相同。只是在計算機的實現過程中，人們開發了一個神器，叫S-Box。它是一個替換表，通過查表即可獲得該位元組所對應的替換位元組。一般AES中的S-Box長這樣：

可能有些童鞋有點看不懂，我稍微解釋一下。AES中每個明文塊長度是128位，在寫成4*4矩陣之後，每個矩陣單位的長度是8位。所以對於每個矩陣單位而言，總共有2^8=256種可能性，正好為16^2。即兩位16進位數剛好能夠完全表示單個明文塊的所有可能性。而表中的橫縱坐標，對應的正是轉換成16進位後的明文塊的第1位與第2位。其中A~F代表16進位數中的10~15。另外相應地，還有一個逆S-Box，標註有替換位元組所對應的原位元組，用於解碼時的逆位元組替換。

然後，是移行。移行是怎樣一個操作呢？我不說話，就上個圖，相信大家都能看得懂：

啊不好意思，上面的圖是逆向移行。正向移行么，把中間那一步反過來就行了。

最後是混列。正向混列為左乘一個矩陣A，逆向混列為左乘一個矩陣B：

可計算得A·B=I，即A、B兩個矩陣互逆。注意在混列的矩陣運算當中，加法是通過轉化成二進位後進行異或運算來實現的。

好的，我們終於講到了AES的結構了。不好意思我也覺得有點累了，還是直接上個圖吧（說的好像我畫個圖更輕鬆一樣~~~~(>_<)~~~~）。

說實話AES與DES都是一個德性，NIST（National Institute of Standards and Technology，美國國家標準與技術研究院）的想法就是，沒有什麼問題是一遍演算法加密解決不了的；如果有，就多加幾遍……不過要注意的是，加密的最終輪與其他不同，不再進行混列操作；因此解密時也相應地略去這一步。

好了，今天就上到這裡，童鞋們辛苦啦！有什麼問題呢可以課後找老濕@謝鈞 討論。下節課呢，將由何老師@何欽堯來給大家講現代密碼學中剩下的內容：非對稱加密。請大家掌聲歡迎！同時也請做好相應的預習工作（非對稱加密涉及到較多的數論知識）與心理準備……

P.S. 若大家對於密碼學的專業書籍感覺閱讀有困難的話，也支持大家看一些密碼學相關的文學與影視作品。例如著名的《福爾摩斯探案集》，丹·布朗的《數字城堡》（《天使與魔鬼》、《達芬奇密碼》、《失落的符號》及《地獄》也比較推薦，但是這幾部涉及的則更多是符號學而非密碼學）。至於電影么，我看的不多，不敢妄言

P.P.S. 碼字辛苦，繪圖更辛苦。未經允許，嚴禁轉載！

P.P.P.S. 本人是在南洋理工大學進行的密碼學學習，因此文中的名詞翻譯可能與國內中文教材有異，請見諒。另外還要感謝@何欽堯學弟對本文的審閱與批改。

參考文獻：

[1] Buonafalce, Augusto, 「An Exercise in Solving the Alberti Disk」. The Cryptogram LIV, 5, ACA, Plano 1999.

[2] Alberti, Leon Battista, A Treatise on Ciphers, trans. A. Zaccagnini. Foreword by David Kahn, Galimberti, Torino 1997.

[3] Carroll, Christine M., BSN, RN, MBA, Cryptology and Cryptography. Salem Press Encyclopedia of Science, January, 2015. 4p.

[4] Lek, Kamol, Rajapakse, Naruemol, Cryptography: protocols, design, and applications. Hauppauge, N.Y. : Nova Science Publishers, c2012.

[5] Piper, F. C., Cryptography: a very short introduction. Oxford ; New York : Oxford University Press, 2002.

[6] Meyer, Carl H. Cryptography: a new dimension in computer data security: a guide for the design and implementation of secure systems. New York : Wiley, 1982.

[7] Alhamdani, Wasim A. Teaching Cryptography Using Design Thinking Approach. Journal of Applied Security Research; Jan-Mar2016, Vol. 11 Issue 1, p78-89, 12p.

推薦閱讀：