背景
在1949年,Shannon的The mathematical theory of communication [9]是现代密码学的理论基础,也标志着密码算法的重心向应用数学的转移。本文提出,分组密码算法应遵循混淆(Confusion)和扩散 (Diffusion)完善密码系统的保密性,”乘积” ”乘积”密码体制对Feistel之后提出Feistel密码结构具有指导意义。柯克霍夫原则 (Kerckhoffs Principle)[7]由Kerckhoffs在19世纪,即使密码系统的任何细节已经被知道,只要密钥(key,又称密钥或秘钥)未泄漏,也应为安全 。Shannon 有句近似的话: 敌人知道系统,称为香农公理。密码学中公钥密码和对称密码用来保护数据的机密性,如图1。
图1 密码学
公钥密码:Whitefield与Martin Hellman1976年[4]提出Diffie-Hellman关键交换协议/算法 (Diffie-Hellman Key Exchange/Agreement Algorithm),公钥密码开始发展。公钥密码是利用陷门单向函数原理编制的加密密钥披露和解密密钥保密密码。公钥密码的安全理论基础是计算复杂性理论。公钥密码的安全性是指计算安全性,通常是基于特定数学问题的计算难度,主要包括大整数因子分解、有限区域离散对数、椭圆曲线加法组上离散对数等。第一个更完美的公钥密码算法是Rivest、Shamir和 Adleman在1978年提的RSA[8]公钥密码算法的安全基础是大整数因子分解的难度。对称加密:与公钥密码系统相比,对称密码算法简单、高效,适用于大量数据的加密。对称加密算法是指使用相同的密钥进行加密和解密。对称加密算法的安全性取决于加密密钥的安全性。对称加密算法的优点是加密的高速度和使用长密钥时的难破解性。对称密码可分为流动密码和分组密码。
分组密码
分组密码 (block cipher) 的数学模型是将明文信息按分组密码的分组长度划分为固定长度的信息块,每个信息块在密钥控制下转换为等长输出信息。对称密码算法的轮函数f包括子密钥操作、线性操作和非线性操作。非线性操作主要混淆,线性操作主要扩散。通过轮函数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.