学文网摘要：AES作为广泛使用的高级数据加密标准，其密码算法的安全性取决于非线性部件S盒的密码特性。本文首先学习了AES算法的基本加解密过程，特别分析了AES优化算法采用的时空折衷的思想。然后从布尔函数出发，利用C语言实现了AES的 S盒，推导和计算了S盒平衡性、非线性度等密码特性，说明AES抗差分和抗线性攻击的本质原因。最后利用拉格朗日插值法，拟合了S盒的代数表达式。结果表明AES S 盒代数表达式项数过少，表达式比较简单，存在一定的安全隐患。
关键词：分组密码 AES算法 S盒 密码特性 代数表达式
中***分类号：TP309 文献标识码：A 文章编号：1007-9416（2013）11-0113-01
计算机通信网的发展对信息的安全保密要求日益增长，未来的数据传输和存储都要求有密码的保护，为了实现同一水平的安全性和兼容性，提出了数据加密标准化。AES已经代替DES成为新一代主流分组密码标准算法，它能够抵抗差分密码分析及线性密码分析，比过去的DES和3DES更为有效、安全和灵活。
S盒作为许多分组密码的唯一非线性部件，决定了整个密码算法的安全强度。在设计和分析分组密码时，必须要考虑到S盒的密码性质。好的S盒保证了密码能够抵抗现有的已知攻击，而其任何不好的性质也将影响到整个密码算法的安全性。
1 AES算法及优化原理
1.1 AES算法的优化原理
AES算法结构的核心是轮函数，它效率的高低对整个算法的实现速度有着很大的影响，设计高效的轮变换就是提高AES算法运行效率的关键所在。通过对作进行优化，将上述四个步骤（S盒，行移位，列混淆和轮密钥）融合构造表，通过简单的查表和异或运算得到每一次作的结果，便可省去复杂的求逆、矩阵乘和循环移位操作，达到了优化的目的。
2 AES算法的S盒密码性质验证
2.1 AES算法的S盒[1]
AES算法的S盒基于数学方法设计，主要由以下两个变换合成而构造出来：
①求逆运算，将字节看作GF（28）的元素，取其在既约多项式下的逆：。
②仿射运算，将求逆结果与GF（2）上固定矩阵M相乘，然后与固定向量相加。
仿射运算消除了有限域乘法运算的不动点0，1。
2.2 AES算法的S盒的快速实现
对AES算法的S盒分步分析：
求逆运算可以通过查表来提高速度，即通过扩展的欧几里得算法，预先构造GF（28）上256个元素的逆存在数组里。
仿射运算，是矩阵的乘法运算，可以分步处理。将矩阵与向量的乘法运算简化为向量的循环移位运算。
2.3 AES S盒的密码特性验证[4]
2.3.1 平衡性
定义1：函数：，当输入遍历所有取值时，输出“1”的个数等于输出“0”的个数，则称满足平衡性。
对于AES算法，S盒是置换操作，置换操作是一一对应，即当输入遍历0到255时，其输出也从0到255，因而统计布尔函数S输出比特位，发现含128个“1”和128个“0”，满足平衡性。
2.3.2 非线性度
定义1：设f：是一个n元布尔函数，称
为的非线性度。其中表示全体n元线性和仿射函数之集，表示函数和之间的汉明距离。
计算AES算法S盒的非线性度是112，虽然其S盒的函数并不是Bent函数，（Bent函数的非线性度的上界可以达到 ），但是其非线性程度已经非常接近完全非线性函数。
2.3.3 差分均匀性
差分均匀度是用来衡量算法抵抗差分攻击的能力。AES算法S盒的差分均匀度较小，接近最小值 1，抗差分攻击能力强，有较高的安全性。
2.3.4 严格雪崩准则
定义1：设，是元布尔函数，若对任意的，是平衡函数，则称满足严格雪崩准则。
对于AES算法，其严格雪崩性与S盒密切相关。编程分别验证了改变明文和密钥时的雪崩特性。
①改变明文的雪崩特性。设定一个原始明文，通过轮流改变明文全部128比特的每一位，得到对应的密文，并统计最多、最少和平均改变位数。结果表明：对于三种密钥长度，平均改变位数将近为分组长度的一半，即64比特长，而最多和最少改变位数偏离该值15%左右，从安全的角度看，AES的S盒具有良好的雪崩特性。
②改变密文的雪崩特性。设定一个原始明文和原始密钥，通过轮流改变密文全部128比特的每一位得到相应的密文，统计最多、最少和平均改变位数，结果表明：平均改变位数将近为分组长度的一半64，最多和最少改变位数同样偏离该值15%左右，从安全的角度看，具有良好的雪崩特性。严格雪崩准则用于衡量S盒的输入改变对输出改变的随机性，AES S盒良好的扩散性，保证了输入输出改变量的均匀性，进而有效地抵抗了差分攻击。
2.3.5 代数表达式与项数
3 结语
S盒密码特性的好坏直接决定了密码算法的安全性。AES S盒满足密码设计所要求的平衡性、非线性性、差分均匀性和扩散性[3]。特别地，非线性度从本质上说明AES算法具备良好的非线性特性，能够有效抵抗线性攻击；差分均匀度保证了AES算法能抵抗差分攻击。虽然其代数表达式项数不多，但从目前对AES的攻击来看，AES的S盒还是很安全的。
参考文献
[1]Joan Daemen，Lars Knudsen，Vincent Rijmen.The Block Cipher Square[J].Fast Software Encryption，1997，1267：149-l65.
[2]冯登国，吴文玲.《分组密码的设计与分析》.清华大学出版社，2000：1.
[3]温巧燕，杨义先.《现代密码学中的布尔函数》.科学出版社，2000：8.
转载请注明出处学文网 » AES算法S盒性质验证