從藝術到科學——密碼學的發展歷程

想來現場觀戰？請戳上圖！（限報100人）

2017年5月WannaCry勒索病毒在全球爆發，大陸部分高校學生反映電腦被病毒攻擊，文檔被惡意加密。勒索病毒肆虐，儼然是一場全球性互聯網災難，給廣大電腦用戶造成了巨大損失。最新統計數據顯示，100多個國家和地區超過10萬台電腦遭到了勒索病毒攻擊、感染。[1]

▲請點擊上面音頻按鈕收聽聲音吧~

WannaCry到底是何方妖孽？

WannaCry是一種「蠕蟲式」的勒索病毒軟體，它使用AES-128和RSA加密演算法惡意加密用戶軟體以勒索比特幣。AES-128和RSA演算法本來是非常優秀的對稱加密演算法，用於加密通信信息避免被敵手獲取，但在壞人手中卻被用來惡意加密用戶的文件，成了勒索工具。也正是因為AES-128和RSA的強大的安全性，導致至今除了像亡羊補牢一樣修復系統漏洞避免感染之外沒有徹底的解決辦法。

那麼AES和RSA又是何種利器，竟讓全世界都束手無策？

要想了解AES和RSA，首先讓我們一起來看看什麼是加密，什麼是密碼學。

生活中我們經常會用到密碼，打開電腦，登陸郵箱，QQ，微博等等，但其實這些密碼並不是真正意義上的密碼，只是口令(password)。密碼學是研究保密通信的一門科學，它研究在不安全的環境中，如何把所要傳輸的信息在發給接收者之前進行秘密轉換以防止第三者對信息的竊取。

密碼學包括密碼編碼學和密碼分析學，這兩個分支形成既對立又統一的矛盾體，安全的密碼機制促使更強大的分析方法的發展，而強大的分析方法又強迫更加安全的密碼機制的誕生，二者在相互鬥爭中共同進步，所以說密碼學的發展史匯聚了人類文明的聰明才智。

我們在討論加密問題的時候都是基於一個通信模型，假設通信雙方Alice和Bob通過一個不安全的通道進行通信，而攻擊者Trudy一直在竊聽他們之間的交流，這種竊聽總是防不勝防，所以Alice和Bob需要將他們之間交流的消息處理成只有他們自己看得懂的「文字」，而在其他人眼中只是一堆亂碼。

古典密碼學主要使用替換的手段進行加密，最早的加密演算法可以追溯到古羅馬時期的凱撒大帝使用的凱撒密碼和武王伐紂時的陰符陰書。其中凱撒密碼是一種單表替換加密技術，明文中的所有字母都在字母表上向後（或向前）移動若干位，以下是一個向後移動13位的例子：

明文：goodgoodstudydaydayup

密鑰：13

密文：tbbqtbbqfghqlqnlqnlhc

稍微複雜一些的還有多表替換的維吉尼亞密碼。這種替換加密雖然乍看之下混亂無序，但通過統計手段就能恢復出密鑰，比如統計密文字母的頻率，並與自然語言中各個字母出現的頻率相對比，從而揭示隱藏在亂序密文後面的加密規律。筆者第一次接觸這種加密方法是在福爾摩斯探案集中《跳舞的小人》一章，裡面介紹了用簡單的小人圖案來代替英文字母，福爾摩斯破譯的方法就是頻率分析法。

下面我們來對密碼機制給出一個嚴格的定義，一個密碼機制是由以下五部分組成[2]：

1. 明文空間P：所有可能的明文組成的有限集；

2. 密文空間C：所有可能的密文組成的有限集；

3. 密鑰空間K：所有可能的密鑰組成的有限集；

4. 加密法則E；

5. 解密法則D；對任意的密鑰k，都存在一個加密法則ek和相應的解密法則dk，且對任意明文x，均有dk(ek(x))=x。

公開密碼機制

如何保證一個密碼機制的安全性呢？一般人會認為不讓別人知道明文是以何種方式加密的就行了，也就是說將加密演算法保密，但是這個方法並不可靠，因為加密演算法的種類畢竟是有限的，窮舉起來不是沒有可能，而一旦知道了是用何種演算法進行加密，破解也就是分分鐘的事兒。因此，19世紀荷蘭語言學家和密碼學家奧古斯特·柯克霍夫提出：密碼機制的安全性不依賴於演算法的保密性，密碼系統應該就算被所有人知道系統的運作步驟，只要密鑰不泄露，就仍然是安全的。公開加密演算法相當於讓所有人都能來分析破譯，對演算法本身的安全性提出了更高的要求，而一旦攻擊成功，結果一般會公開發表，演算法的使用者能及時做出調整，避免更大的損失。現在大多數民用保密都使用公開的演算法，但用於政府或軍事機密的加密演算法通常仍是保密。

密碼學與戰爭

對密碼學需求最高的莫過於軍事領域，在戰爭中信息最為寶貴，一條簡短消息的泄露可能會決定一場戰爭的輸贏和成千上萬條性命，第二次世界大戰的時候正是波蘭和英國密碼學家破譯了德軍使用的恩尼格瑪（ENIGMA）密碼機，才使得戰局出現轉機，拯救了更多人的生命，其中的代表人物就是圖靈，2014年上映的電影《模仿遊戲》將這段歷史帶入到了大眾的視野。

圖靈

模仿遊戲

從藝術到科學

1949年香農發表了論文《保密系統的信息理論》[3]，該文提出了混淆(confusion)和擴散(diffusion)兩大設計原則，為對稱密碼學（主要研究發送者的加密密鑰和接收者的解密密鑰相同或容易相互導出的密碼體制）建立了理論基礎，從此密碼學成為一門科學。

香農

對稱密碼學主要由分組密碼和流密碼構成，在分組密碼演算法中，明文消息被分成若干個分組，加密和解密都是對這些分組進行操作，而流密碼則是使用一個密鑰流生成器產生一串與消息等長的密鑰比特流，再與明文進行異或操作，流密碼一次只加密一個比特，與分組密碼相比，流密碼需要更大的處理能力，所以說流密碼更適用於硬體平台實現，分組密碼更適用於軟體平台實現。經典的分組密碼演算法有DES和AES，流密碼演算法有Trivium和學者自主設計的祖沖之演算法(ZUC)。

在分組密碼的設計中，充分利用擴散和混淆，可以有效地抵抗對手根據密文的統計特性推測明文或密鑰。

擴散就是讓明文中的每一位影響密文中的許多位，或者說讓密文中的每一位受明文中的許多位的影響。這樣可以隱蔽明文的統計特性。當然，理想的情況是 讓明文中的每一位影響密文中的所有位，或者說讓密文中的每一位受明文中所有位的影響。比如AES中ShiftRows 部分。 混淆就是將密文與密鑰之間的統計關係變得儘可能複雜，使得對手即使獲取了關於密文的一些統計特性，也無法推測密鑰。使用複雜的非線性代替變換可以達到比較好的混淆效果，比如使用多個S盒，而簡單的線性代替變換得到的混淆效果則不理想，比如凱撒密碼。乘積和迭代有助於實現擴散和混淆，當然這個過程應該是可逆的。

密碼學的新方向——公鑰密碼學

1976年，Whitfield Diffie和Martin Hellman發表了論文《密碼學的新方向》[4]，標誌著公鑰密碼學的誕生，他們也因此獲得了2015年的圖靈獎。

公鑰密碼體制的特點是採用兩個相關的密鑰將加密與解密操作分開，一個密鑰是公開的，稱為公鑰，用於加密；另一個密鑰保密，為用戶專有，稱為私鑰，用於解密。公鑰密碼與之前的密碼學完全不同，因為公鑰演算法的基礎不再是香農提出的代替和置換，而是基於一種特殊的數學函數——單向陷門函數。單向陷門函數的特點是：易計算，但難求逆，即滿足以下幾點：

1.若k和x已知，求y = fk(x)容易計算；

2.若k和y已知，求x = fk-1(Y) 容易計算；

3.若y已知但k未知，則求x = fk-1 (y)是不可行的。

這裡的容易計算是指能在多項式時間內解決，計算上不可行是指計算的時間複雜度是指數級的。

最經典的公鑰加密演算法莫過於1978年由Rivest，Shamir和Adleman用數論方法構造的RSA演算法[5]，它是迄今為止理論上最成熟最完善的公鑰密碼體制，並已得到廣泛應用。RSA演算法的安全性可以歸約到大整數分解的困難性，即給定兩個大素數，將它們相乘很容易，但是給出它們的乘積，再找出它們的因子就很困難。目前為止，世界上尚未有任何可靠的攻擊RSA演算法的手段，只要其密鑰長度足夠長而且使用方法得當，用RSA加密的信息是不能被破解的。這就是為什麼WannaCry病毒那麼令人束手無策。

結語

隨著人類科技水平的進步，計算機的計算能力增長得越來越快，這無疑給密碼分析提供了有力的工具，因此對密碼機制的安全性提出了更高的要求，驅動著密碼從業者不斷推陳出新，保衛網路空間的安全。同時還要提高警惕，不要讓密碼演算法這柄利劍傷害到用戶本身，避免類似於WannaCry的勒索病毒再次爆發。最後，信息安全最薄弱的環節其實是用戶本身，相當對的安全事件不是由於技術的漏洞，而是人的疏忽，所以希望大家都能重視密碼學，保護自身在網路空間的安全。

參考文獻

1. 騰訊新聞：全球爆發電腦勒索病毒 多所大學校園網被攻擊http://news.qq.com/a/20170513/001170.htm

2. Stinson D R. Cryptography: theory and practice[M]. CRC press,2005.

3. Shannon C E. Communication theory of secrecy systems[J]. Bell Labs Technical Journal, 1949, 28(4):656-715.

4. Diffie W, Hellman M. New directions in cryptography[J]. IEEE transactions on Information Theory, 1976, 22(6):644-654.

5. Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J].Communications of the ACM, 1978, 21(2):120-126.

編輯：吉星

近期熱門文章Top10

↓ 點擊標題即可查看 ↓

1. 吃了一暑假的西瓜，我終於發明了能避開所有瓜籽的科學吃瓜法！

2. 想找女朋友嗎？別急，看了這篇文章你就不想了

3. 大橋耗資百萬，通車僅四個月竟被大風吹斷，卻成為建造史上的里程碑

4. 在七夕前夕，我終於用數學方法找到了脫單的竅門！

5. 他是最接近終極理論的人，被稱為當今愛因斯坦

6. 他所創學派9奪諾獎，辯倒物理群雄無數，連愛因斯坦都未曾贏過

7. 為了讀碩讀博，你放棄過喜歡的人嗎？

8. 她如何用一個申不到經費、被稱作學校之恥的項目，革新了整個研究領域、掀起了如今的AI浪潮？

9. 讓你失望了，地震雲並不存在

10. 下雪後為什麼感覺很安靜？

點此查看以往全部熱門文章