作者：@謝鈞

長文慎入！多圖殺貓！

在上一篇中，@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。