[[379130]]

背景

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

圖1 密碼學(xué)

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

分組密碼

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

圖2 分組密碼算法

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

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

Feistel 結(jié)構(gòu)

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

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

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

圖3 Feistel結(jié)構(gòu)

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

圖4 DES算法

代換-置換網(wǎng)絡(luò) (Substitution-Permutation Network，SPN) 結(jié)構(gòu)

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

圖5 代換-置換網(wǎng)絡(luò) (Substitution-Permutation Network,SPN)結(jié)構(gòu)

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

圖6 SPN結(jié)構(gòu)的密碼算法

注解：

(1)乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng),使得最后結(jié)果的密碼強度高于每個基本密碼系統(tǒng)產(chǎn)生的結(jié)果。

(2)乘積密碼指順序地執(zhí)行兩個或多個基本密碼系統(tǒng),使得最后結(jié)果的密碼強度高于每個基本密碼系統(tǒng)產(chǎn)生的結(jié)果。

(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] 思路是對一份用周期性多表密碼加密的密文，確定其中所有的重復(fù)出現(xiàn)的字母串，計算他們之間的距離，并對這些距離進行因子分解，出現(xiàn)頻率較高的因子很可能是密鑰的長度。

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

參考文獻：

[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.