一种AES S盒改进方案的设计

刘连浩，崔  杰，刘上力，马虹博

 (中南大学 信息科学与工程学院, 湖南 长沙, 410083)

摘　要： S盒作为AES算法惟一的非线性运算，直接决定算法的性能。针对S盒的仿射变换对周期为4，迭代输出周期不大于88，而且代数表达式只有9项的缺陷提出了改进方案，并构造新的S盒。该改进S盒具有周期16仿射变换对，迭代输出周期为256，而且S盒和逆S盒代数表达式项数分别达到252项和254项。将改进的S盒与AES的S盒在平衡性、严格雪崩准则、非线性度等10种代数性质方面进行比较，结果表明改进S盒具有更好的代数性质，抗代数攻击的能力更强。

关键词：AES S盒；仿射变换；代数表达式

中图分类号：TP309.7         文献标识码：A         文章编号：1672-7207(2007)02-0339-06

Design of an improved method of AES S-box

LIU Lian-hao, CUI Jie, LIU Shang-li, MA Hong-bo

 (School of Information Science and Engineering, Central South University , Changsha 410083, China)

Abstract: S-box is the unique nonlinear operation for advanced encryption standard (AES) and affects the capability of the algorithm. For S-box, the period of affine transformed pair is 4, the period of iterative-output is less than 88 and algebraic expression has only 9 items. Based on these characteristics, an improved S-box was constructed, with period of affine transformed pair as 16, period of iterative-output as 256 and algebraic expression of improved S-box and InvS-box as 252 items and 254 items respectively. The improved S-box was compared with AES S-box in 10 algebraic properties, such as the balance, strict avalanche criterion, non-linear degree, resistance against the XSL attack, etc. The results suggest that the improved S-box has better algebraic characteristics and stronger resistance against algebraic attack.

Key words: AES S-box; affine transform; algebraic expression

随着信息技术的发展，人们对信息安全越来越重视，对加密性能的要求越来越高^[1-4]。Rijndael在2000年10月2日被确定为美国高级加密标准(AES)，自从Rijndael算法被提出以来，一直受到密码学界的关注，出现了许多攻击AES的方法，但目前尚未存在对完整Rijndael算法的成功攻击^[5-9]。S盒作为AES惟一的非线性部件，对算法抵抗各种攻击起着关键性的作    用^[10-11]。王珩波^[12-13]通过分析S盒的仿射变换，指出其仿射变换对的周期为4，没有达到最大的周期16， S盒的迭代输出具有短周期现象，且周期均不大于88，而LIU等^[14]指出AES S盒的代数表达式只有9项，存在表达式过于简单的问题。鉴于S盒存在的以上不足，本文作者分析了S盒布尔函数的6种代数性质和只有9项的代数表达式，并提出构造S盒的改进方案。采用该方案构造的S盒具有周期为16的仿射变换对，迭代输出周期达到256，严格雪崩准则距离为372，S盒和逆S盒代数表达式分别为252项和254项。

1  AES S盒构造原理

1.1  AES S盒构造原理

AES的S盒运算是一个独立作用于状态字节的非线性变换，包括2个步骤：在有限域GF(2⁸)中的求乘法逆运算和GF(2)下的仿射变换运算。

a. 输入，求，其中定义如下：

b. 在GF(2)⁸中的元素分量为(x₇, x₆, x₅, x₄, x₃, x₂, x₁, x₀)，仿射变换定义：

即b(x)=a(x)(x⁷+x⁶+x⁵+x⁴+1)+(x⁷+x⁶+x²+x)mod(x⁸+1)。其中：a(x)和b(x)分别是GF(2)域下x和y的代数表达式。

1.2  AES S盒仿射变换对周期

定义1   

其中，，。简记为：。

AES S盒仿射变换L_{143, 99}: u(x)=1+x⁴+x⁵+x⁶+x⁷, v(x)=x+x²+x⁶+x⁷。

若记

则仿射变换，记，则有　，令，则，其中E为8×8的单位阵。

定义2  如果存在正整数n满足，则称L_u,v是周期的。若n是周期中最小的正整数，则称L_u,v的周期为n。

AES S盒的仿射变换对(143, 99)，u=143=　(11110001)₂, v=(11000110)₂，满足，故S盒的仿射变换周期为4。而根据AES的S盒的仿射变换的构造方法，经计算对于任意形成的可逆仿射变换对的周期只有1，2，4，8，16共5种情况，即周期最大可达到16，而AES的S盒选用了周期为4的仿射变换对。

1.3  AES S盒的迭代输出周期

AES的S盒的迭代输出周期有5个^[13]，分别是87，81，59，27，2，且87+81+59+27+2=256，所以，每个周期轨道之间没有交叉点。S盒全空间的容量是256，但元素点的周期都小于88，还有周期为2的迭代轨道，所以，S盒的迭代输出存在短周期现象。

2  AES S盒的代数性质

一个具有良好的代数性质的S盒能够保证算法抵抗各种密码分析的攻击。在AES算法中对长度为128bit的明文加密运算，S盒共用到160次，因此，S盒的任何不好的性质都将影响到整个算法的安全性。S盒是1个8位输入8位输出的多输出布尔函数，8个布尔函数之间的相互制约、相互影响。即使8个函数同时具有某种性质，它们构成的多输出布尔函数却未必具有类似的性质^[15]，所以，有必要对S盒的整体代数性质进行分析。

定义3  设是GF(2)ⁿ到GF(2)ⁿ的多输出布尔置换，称为F(x)的差分均匀度。

差分均匀度是用来衡量算法抵抗差分攻击能力的指标。布尔置换的差分均匀度越接近最小值1，抗差分分析能力越强^[15]。AES S盒的差分均匀度是4，具有一定的抵抗差分攻击的能力。

定义4  设F(x)=(f₁(x), …, f_n(x))是GF(2)ⁿ到

GF(2)ⁿ的多输出布尔置换，若，满足F(x)+F(x+α)常量，则称α为F(x)的线性结构。

AES S盒没有非零线性结构^[15]。

定义5  设F(x)=(f₁(x), …, f_n(x))是GF(2)ⁿ到

GF(2)ⁿ的多输出布尔置换，如果对且w(α)=1即α的汉明重量为1时，有

w(f_i(x+a)+f_i(x))=2^n-1(1≤i≤n)，

则称F(x)满足严格雪崩准则(SAC)。

定义6  设F(x)=(f₁(x), …, f_n(x))是GF(2)ⁿ到

GF(2)ⁿ的多输出布尔置换，称

为F(x)的严格雪崩准则距离。

显然当l=0时，F(x)满足严格雪崩准则。当F(x)不满足严格雪崩准则时，l越小布尔置换越接近严格雪崩准则。AES S盒并不满足严格雪崩准则，其严格雪崩准则距离是432。

定义7  F(x)=(f₁(x), …, f_n(x))是GF(2)ⁿ到GF(2)ⁿ的多输出布尔置换，称为F(x)的非线性度。L_n[X]表示全体线性函数之集。

非线性度是衡量密码系统抗线性攻击能力强弱的指标。从这个意义上讲，非线性度越高越好，但当非线性度达到最高时，其他性能将变弱。通过计算发现AES S盒的N_F=112，而文献[15]中指出完全非线性函数的非线性度N_F=2^n-1-2^n/2-1，即2^8-1-2^8/2-1=120，所以，S盒不是完全非线性函数，但是，其非线性度已经非常接近完全非线性函数的非线性度。

定义8  在域GF(2⁸)中，给定r个含有t项的方程，定义式为抗代数攻击的阻力(Resistance of algebraic attacks，RAA)。

对于AES，t=81，r=23，n=8，计算得到AES S盒的抗代数攻击阻力。Hee等^[16]指出，安全密码的S盒的抗代数攻击阻力应不小于2³²，而AES S盒的，这可能成为其遭受攻击的切入点。

从上面的分析可以看出，AES的S盒多输出布尔置换存在着一些缺陷，而且代数表达式尽管有足够高的次数，但只有9项被认为过于简单^[14]。AES S盒的代数表达式如下：

　　LIU等^[14]中针对S盒的代数表达式只有9项的问题，提出将求乘法逆运算和仿射变换的计算顺序调换，使改进S盒具有255项的代数表达式，而且其严格雪崩准则距离是408，但是，通过求逆S盒的表达式发现其代数表达式只有9项，而且这种构造的S盒的仿射变换周期仍是4，迭代输出周期也小于88，并没有达到改进的效果，与AES的S盒具有几乎相同的代数性质。

3  S盒的改进方案设计

通过以上对AES的S盒的结构和代数性质的分析，发现S盒之所以存在代数表达式只有9项的不足是与构造S盒的求乘法逆元和仿射变换的计算顺序有关，而仿射变换周期和迭代输出周期则与所采用的仿射变换对有关，所以，S盒的代数性质可以通过修改仿射变换对和构造S盒的计算顺序来达到比较好的效果。但采用一次仿射变换无法满足所构造的S盒和逆S盒的代数表达式均具有较多项数的不足，所以，针对以上问题提出构造S盒的改进方案。本方案采用仿射变换对替换原来S盒的仿射变换对，并采用3步实现，即对字节元素进行1次仿射变换后求乘法逆元，然后再进行1次仿射变换。S盒改进方案的运算步骤如下：

a. 首先进行1次仿射变换对为的仿射变换，该仿射变换定义如下：

b. 求乘法逆元：

c. 再进行1次仿射变换对为的仿射变换，输出结果y。

。

对于上面S盒的构造方案中的仿射变换对，其对应的逆S盒仿射变换对为，则对应的逆S盒构造方案如下：

a. 首先进行1次仿射变换，选取的仿射变换对为：

。

b. 求乘法逆元

c. 再进行仿射变换对为的仿射变换，输出结果x：

。

通过运算得到新S盒替换表如表1所示，通过编程计算得到新S盒的代数表达式系数表如表2所示。

表1  本文改进方案构造的S盒替换表

Table 1  S-box substitution table of improved method in this paper

表2  改进S盒的代数表达式系数表

Table 2  Algebraic expression coefficient table of improved S-box

4  本文S盒与AES S盒性能的比较

从上面的构造方法可以看出，与文献[14]中的构造方法相比，本文作者提出的S盒的构造方法与AES的构造方法多进行了1次仿射变换。这样，就使得在S盒及逆S盒构造过程中求逆之前均有1次仿射变换，解决了AES中S盒及文献[14]中逆S盒表达式过于简单的问题，使改进方案所构造S盒及逆S盒的表达式都具有较多项。而通过修改仿射变换对，增大了仿射变换周期和迭代输出周期，使S盒更加接近严格雪崩准则，同时在平衡性、差分均匀度、非零线性结构、非线性度和抗代数攻击阻力等性质方面与AES的S盒相同。本文作者测试了改进S盒的各项代数性质，并与AES的S盒、文献[14]中改进的S盒进行比较，结果如表3所示。

表3  3种S盒代数性质对比表

Table 3  Comparison of algebraic properties of three S-box

从表3可以看出，本文作者提出的改进S盒的严格雪崩准则距离为372，优于AES S盒的432和文献[14]中改进S盒的408；本文改进的S盒及其逆S盒的代数表达式项数分别达到252项和254项，解决了AES中S盒及文献[14]中逆S盒表达式过于简单的问题。本改进方案所采用的仿射变换对周期为16，明显优于AES S盒和文献[14]中S盒所采用的周期为4的仿射变换对；本构造S盒的迭代输出周期为256，而另2种方案构造的S盒的迭代输出周期均不超过88。总之，本文构造的S盒具有更好的代数性质。

5  结　论

a. 分析了AES S盒的平衡性、严格雪崩准则、抗代数攻击阻力等6种代数性质，指出AES S盒的仿射变换对周期小，迭代输出周期短，并且代数表达式只有9项。

b. 提出构造S盒的改进方案，先对字节元素在GF(2)域下进行仿射变换，然后对元素求乘法逆元，最后再对元素乾地仿射变换，这样，使改进的S盒和逆S盒均具有复杂的代数表达式，S盒和逆S盒代数表达式项数分别达到252项和254项，而采用的仿射变换对的仿射变换对周期达到16，并且改进S盒的迭代输出周期达到256。

c. 实验结果表明本文构造的S盒比AES的S盒和文献[14]中改进的S盒的严格雪崩准则距离都小。改进的S盒具有复杂的代数结构和良好的非线性特性，具有很强的安全性。

参考文献：

[1] 刘连浩. 计算机实时通信中一种新的数据加密技术[J]. 中南工业大学学报：自然科学版，2000，31 (1)：84-86.

LIU Lian-hao. A new date encryption technology in computer real-time communication[J]. Journal of Central South University of Technology：Natural Science, 2000, 31(1): 84-86.

[2] 孙克辉，盛利元，张纪成，等. 机动车身份信息IC卡读写系统的设计与实现[J]. 中南工业大学学报：自然科学版，2002, 33(5): 543-546.

SUN Ke-hui, SHENG Li-yuan, ZHANG Ji-cheng, et al. Design and implement of an IC card read-write system for vehicle identity information[J]. Journal of Central South University of Technology：Natural Science, 2002, 33(5): 543-546.

[3] 刘颖琦，周学军. 网络信息系统安全研究[J]. 中南工业大学学报：自然科学版，2002，8 (3)：249-251.

LIU Ying-qi, ZHOU Xue-jun. Study on security of network information system[J]. Journal of Central South University of Technology：Natural Science，2002，8 (3)：249-251.

[4] Matsui M. Linear cryptanalysis method for DES cipher[C]// Advances in Cryptology-EuroCrypt’93. Berlin: Springer- Verlag, 1994: 386-397.

[5] Daemen J, Knudsen L, Rijnmen V. The block cipher square[C]// Fast Software Encryption. 4th International Workshop. Haifa: Springer-Verlag, 1997: 149-165.

[6] Ferguson N, Kelsey J. Improved cryptanalysis of Rijndael[C]// Fast Software Encryption, 7'th International Workshop. New York: Springer-Verlag，2001: 213-230.

[7] Coron J. Resistance against differential power analysis for elliptic curve cryptosystems[C]//Proceedings of CHES'99, LNCS1717. Berlin: Springer-Verlag, 1999: 292-302.

[8] Murphy S，Robshaw M J B. Essential algebraic structure within the AES[C]//Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology. London: Springer-Verlag, 2002: 1-16.

[9] Kocher P, Jaffe J, Jun B. Introduction to differential power analysis and related attacks[EB/OL]. http:// www.cryptography. com/dpa/technical/, 1998.

[10] 卢开澄. 计算机密码学[M]. 北京：清华大学出版社，2003.

LU Kai-cheng. Computer cryptology[M]. Beijing: Tsinghua University Press, 2003.

[11] Daemen J, Rijmen V. AES proposal: Rijndael[EB/OL]. http://www.east.kuleuven.ac.be/~rijmen/rijndael, 1999.

[12] 王衍波. AES 的S-盒中仿射变换的性质[J]. 解放军理工大学学报：自然科学版, 2002, 4(2): 5-9.

WANG Yan-bo. Property of affine transformation in S-box of AES[J]. Journal of PLA University：Science and Technology，2002, 4(2): 5-9.

[13] 王衍波. AES的结构及其S-box分析[J]. 解放军理工大学学报：自然科学版，2002, 3(3): 13-17.

WANG Yan-bo. Analysis of structure of AES and its S-box[J]. Journal of PLA University: Science and Technology, 2002, 3(3): 13-17.

[14] LIU Jing-mei, WEI Bao-dian, CHENG Xiang-guo, WANG Xin-mei. An AES S-Box to increase complexity and cryptographic analysis[C]//19th International Conference on Advanced Information Networking and Applications. Taibei: ISI Proceedings, 2005: 724-728.

[15] 温巧燕，钮心忻，杨义先. 现代密码学中的布尔函数[M]. 北京：科学出版社，2000.

WEN Qiao-yan, NIU Xin-yi, YANG Yi-xian. Boolean function in modern cryptology[M]. Beijing: Science Press, 2000.

[16] Hee J, Lee D H. Resistance of S-boxes against algebraic attacks[EB/OL]. http://www.math.snu.ac.kr/ jhcheon/Published/ 2004_FSE/FSE04_CL.pdf, 2004.

收稿日期：2006-12-20

作者简介：刘连浩(1959-)，男，教授；从事信息安全与网络通信研究

通讯作者：崔　杰；电话：0731-8837871；E-mail: cvjxabcd@126.com