[[379130]]

背景

在1949年，Shannon的The mathematical theory of communication [9]是現代密碼學的理論基礎,也標志著密碼算法的重心向應用數學上的轉移。文中提出分組密碼算法應該遵循混淆(Confusion)和擴散 (Diffusion)兩大準則，密碼體制的完善保密性， ”乘積”密碼體制 。其中”乘積”密碼體制對Feistel之后提出Feistel密碼結構具有指導意義。柯克霍夫原則 (Kerckhoffs Principle)[7]由Kerckhoffs在19世紀提出：即使密碼系統的任何細節已為人悉知,只要密匙(key,又稱密鑰或秘鑰)未泄漏,它也應是安全的 。Shannon 有句近似的話: 敵人知道系統，稱為香農公理。密碼學中公鑰密碼和對稱密碼用來保護數據的機密性，如圖1。

圖1 密碼學

公鑰密碼：Whitefield與Martin Hellman在1976年[4]提出了Diffie-Hellman密鑰交換協議/算法 (Diffie-Hellman Key Exchange/Agreement Algorithm)，公鑰密碼開始發展。公鑰密碼是運用陷門單向函數原理編制的加密密鑰公開，解密密鑰保密的密碼。公鑰密碼的安全性理論基礎是計算復雜性理論。公鑰密碼的安全性指計算安全性，通常是基于特定數學難題的計算困難性而設計的，主要有大整數因子分解的困難性，有限域上離散對數的難解性，橢圓曲線加法群上離散對數的難解性等。第一個比較完善的公鑰密碼算法是Rivest、Shamir和 Adleman在1978年提的RSA[8]公鑰密碼算法，它的安全性基礎是大整數因子分解的困難性。對稱加密：對稱密碼與公鑰密碼體制相比，對稱密碼算法算法簡單，效率高，適合加密大量數據。對稱加密算法指加密和解密使用相同密鑰。對稱加密算法的安全性取決于加密密鑰的安全性。對稱加密算法的優點在于加解密的高速度和使用長密鑰時的難破解性。對稱密碼根據對明文加密方式的不同，可分為：流密碼和分組密碼。

分組密碼

分組密碼 (block cipher) 的數學模型是將明文消息按分組密碼的分組長度劃分成定長的信息塊，每個信息塊分別在密鑰的控制下變換成等長的輸出消息。對稱密碼算法的輪函數f都包含子密鑰操作，線性操作，非線性操作3部分。其中非線性操作主要混淆，線性操作主要擴散。通過將輪函數f多次迭代 (圖 2 ) 達到高安全強度。分組密碼易于軟硬件實現且不需要同步，因此在現代密碼產品和分組交換網絡中有著廣泛的應用。

圖2 分組密碼算法

對稱密碼算法都是基于以下兩種本原操作：

1.混淆 (Confusion): 是一種使密鑰與密文之間的關系盡可能模糊的加密操作;2.擴散 (Diffusion): 是一種為了隱藏明文的統計特性而將一個明文符號的影響擴散到多個密文符號的加密操作。按照算法結構的不同，分組密碼可以分為兩類：Feistel 結構、SPN 結構。

Feistel 結構

Feistel 結構的分組密碼：令F為輪函數;令K1，K2，……，Kn 分別為第1，2，……，n輪的子密鑰。那么基本構造過程如下：

1. 將明文信息均分為兩塊：(L0， R0);2. 在每一輪中，進行如下運算(為當前輪數):Li+1=Ri;Ri+1=Li ⊕ F(Ri,Ki);

Feistel結構(圖3)一次僅一半的數據進入F函數，它的優點在于：由于它是對稱的密碼結構，所以加密和解密過程就極為相似，只有密鑰使用方式不同。Feistel結構的優勢在于加解密方式相同、節省資源;缺點是擴散速度低，為達到一定的安全性通常需要迭代更多的輪數。Feistel結構代表算法有DES算法、ISO/IEC 國際標準算法Camellia、Blowfish、日本NTT公司的DES算法在軟件應用方面的后補 FEAL算法、以及我國的商業分組密碼標準 SM4 等。

圖3 Feistel結構

DES(Data Encryption Standard,即數據加密標準)是一種使用密鑰加密的分組密碼算法，1977年被美國聯邦政府的國家標準局確定為聯邦資料處理標準 (FIPS)，并授權在非密級政府通信中使用，隨后該算法在國際上廣泛流傳開來。DES設計中使用了密碼算法設計的兩個原則：混淆和擴散，使用乘積密碼的概念來逼近理想分組密碼，其目的是抗擊敵手對密碼系統的統計分析 [10]，包括Kasiski 測試法和重復指數法 。由于DES分組比較短、密鑰短、運算速度較慢等自身原因，以及計算機計算能力的提升，線性分析[5]和差分分析[1]等分析方法的發展，DES的安全性受到了極大地威脅。3DES(即Triple DES) 是 DES向AES過渡的加密算法，它使用2個56位的密鑰對數據進行三次加密，密鑰長度變成 112位，加密的過程是加密-解密-加密，解密的過程是解密-加密-解密，比起最初的 DES，3DES更為安全。

圖4 DES算法

代換-置換網絡 (Substitution-Permutation Network，SPN) 結構

SPN結構(圖5)的密碼算法一次處理全部的數據。相同長度的分組密碼算法，SPN結構與Feistel 結構的F輪函數相比，Feistel結構的F函數處理的數據長度為SPN結構的F函數的一半。SPN結構相較于Feistel結構具有更好的擴散性;但加解密不對稱造成了一定程度的實現資源浪費。SPN結構的代表算法包括AES、Serpent、韓國加密標準ARIA等。

圖5 代換-置換網絡 (Substitution-Permutation Network,SPN)結構

在1991年E Biham和A Shamir提出差分分析[1]，1994年Matsui提出線性分析[5]之后，同樣伴隨計算機計算能力的不斷提升，分組長度為64bit和16輪異或、置換、代換、移位的Feistel結構的DES不能保證足夠的安全。1997年4月15日，美國ANSI發起征集AES(advanced encryptionstandard) [3] [11]的活動，旨在尋找替代DES的對稱加密算法，比利時密碼學家Joan Daemen和Vincent Rijmen提出的Rijndael成為獲勝者，Rijndael使用的是SPN結構，基于寬軌跡策略 (wide trail strategy)設計，能夠很好的抵抗差分密碼分析及線性密碼分析。AES的非線性部件為具有較好的差分傳播性質的8比特S盒，線性部件通過小MDS矩陣與置換組合實現大MDS 矩陣達到最佳擴散。高級加密標準 (Advanced Encryption Standard，AES)[2]由美國國家標準與技術研究院(NIST)于2001年11月26日發布于FIPS PUB 197[6]，并在2002年5月26日成為有效的標準。2006 年，高級加密標準已然成為對稱密鑰加密中最流行的算法之一。AES在軟件及硬件上都能快速地加解密，易于實現，且只需要很少的存儲器。

圖6 SPN結構的密碼算法

注解：

(1)乘積密碼指順序地執行兩個或多個基本密碼系統,使得最后結果的密碼強度高于每個基本密碼系統產生的結果。

(2)乘積密碼指順序地執行兩個或多個基本密碼系統,使得最后結果的密碼強度高于每個基本密碼系統產生的結果。

(3) Kerckhoffs Principle states that the security of a cryptosystem must lie in the choice of its keys only; everything else (including the algorithm itself) should be considered public knowledge。

(4)Kasiski 測試法 [10] 思路是對一份用周期性多表密碼加密的密文，確定其中所有的重復出現的字母串，計算他們之間的距離，并對這些距離進行因子分解，出現頻率較高的因子很可能是密鑰的長度。

(5)重復指數法 [10] 利用隨機文本和英文文本的統計概率差別來分析密鑰長度。

參考文獻：

[1] Eli Biham and Adi Shamir. Differential cryptanalysis of des-like cryptosystems. In Advances in Cryptology - CRYPTO ’90, 10th Annual International Cryptology Conference,Santa Barbara, California, USA, August 11-15, 1990, Proceedings, 1991.

[2] J Daemen. Aes proposal : Rijndael, aes algorithm submission.

http://www.nist.gov/CryptoToolkit, 1999.

[3] Joan Daemen, Vincent Rijmen, and Katholieke Universiteit Leuven. Aes proposal:Rijndael. 1998.

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

[5] Mitsuru Matsui. Linear cryptanalysis method for des cipher (iii). In Workshop on the theory and application of cryptographic techniques on Advances in cryptology, 1995.

[6] National Institute of Standards and Technology. Advanced encryption standard (aes). https://csrc.nist.gov/publications/detail/fips/197/final, 2001.

[7] Fabien A. P. Petitcolas. Kerckhoffs’ Principle, pages 675–675. Springer US, Boston,

MA, 2011.

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

[9] C. E. Shannon. The mathematical theory of communication. Bell Labs Technical Journal, 3(9):31–32, 1950.

[10] M Stamp and R Low. Applied Cryptanalysis: Breaking Ciphers in the Real World. Wiley-Interscience, 2007.

[11] Sam Trenholme. The aes encryption algorithm. https://www.samiam.org/rijndael.html.