利用多进制组合快速构造S盒的AES算法设计

王海龙， 孟繁军， 张跃军， 张增平

（1.内蒙古师范大学 网络技术学院，内蒙古呼和浩特 010022；2.内蒙古师范大学计算机与信息工程学院，内蒙古呼和浩特 010022；3.北京政法职业学院 信息技术系，北京 100024）

AES是一种迭代分组密码，采用的是代替置换网络（SPN）。将明文分组长度固定为128b，而且仅支持128、196、256b的密钥长度，AES加密过程又包括1个作为初始轮的初始密钥加法（AddRoundKey），接 着 进 行 9 次 轮 变 换（Round），最后再使用1个轮变换（FinalRound）。其中包含的SubBytes（）是AES密码中唯一的非线性变换。字节代替变换SubBytes（）是可逆的，由2个可逆变换复合而成。它是一个砖匠置换，该置换包含1个作用在状态字节上的S盒。

目前有关S盒设计准则的研究已经有较大的进展，其中以文献［1－2］的工作最具有代表性，字节代替变换（即S盒变换）是许多分组密码算法中的唯一非线性部件，它的密码强度决定了整个分组密码算法的安全强度，对于分析AES算法的强度具有重要意义。文献［3］利用有限域上的迹变换，证明了AES算法中S盒的各坐标函数均线性等价。文献［4］利用布尔函数的谱分布和自相关系数给出了一种求各坐标函数等价变换矩阵的一种方法。

S盒主要提供了分组密码算法所必须的混淆作用，但如何全面准确地度量S盒的密码强度，如何设计安全有效的S盒是分组密码设计和分析中的研究难题［5］。S盒主要有以下一些设计准则：非线性度、差分均匀度、代数次数及项数分布、相关免疫性等［6－8］。基于以上设计准则，人们提出了许多构造方法，如随机选取并测试、使用数学函数等方法。随机选取方法要求设计者有足够的时间和计算能力，而使用数学函数可以构造一些好的S盒，目前常用的此类S盒有指数函数和对数函数、有限域GF（2n）上的逆映射以及有限域上的幂函数［9］。

1 算法设计

1.1 加解密算法思想

在AES算法加密中，字节代替变换（Sub－Bytes（））中需要进行S盒替换，转换过程描述如图1a所示。多进制组合加密算法理论是建立在多类S盒理论基础之上的，具体过程可描述为：首先构造出一类S盒，再找出这类S盒与十六进制的转换关系（假定这个多进制转换为M进制转换）；在AES算法的SubBytes（）中状态转换时，针对状态元素，通过M进制转换关系将Sub－Bytes（）状态的值转换成M进制，然后再对应这个M进制的S盒进行M进制砖匠替换；对替换出来的结果再进行M进制的转换，这样就得到了SubByetes（）想要的结果［10］。通过多进制组合改进后的SubBytes（）转换过程如图1b所示［11］。

在AES算法解密中，逆字节代替变换（Inv－SubBytes（））同样也要进行相应的替换，InvSub－Bytes（）是SubBytes（）的逆变换。它将状态中的每一个字节非线性地变换为另一个字节，此次的替换是针对逆S盒进行的。多进制组合解密算法理论的具体过程可描述为：首先构造出加密算法中S盒的逆S盒，再找出逆S盒与十六进制的转换关系，假定这个多进制转换为M进制转换（肯定与加密算法过程中的进制相同）；在AES算法的InvSubBytes（）中状态转换时，针对状态元素，将InvSubBytes（）状态的值转换成M进制，然后再对应这个M进制的逆S盒进行M进制砖匠替换；再对替换出来的结果进行M进制的转换，这样就得到了InvSubByetes（）想要的结果［9］。

图1 SubBytes的转换过程

1.2 算法实例

1.2.1 加密实例

首先任意构造一个M进制的S盒，这里以4×4矩阵的S盒为例来说明。4×4的S盒中字节替代值见表1所列，字节代替变换过程中的状态初值见表2所列。

表1 4×4S盒－字节xy的四进制代替值

表2 SubBytes（）过程中状态初值

表3 SubBytes（）过程中经过多进制组合后状态初值

1.2.2 解密实例

在解密过程中，根据加密的M进制的S盒，构造出对应的4×4矩阵的逆S盒，见表4所列；InvSubBytes（）过程中状态初值见表5所列；Inv－SubBytes（）过程中经过多进制组合后状态初值见表6所列［12－13］。

表4 4×4逆S盒－字节xy的四进制代替值

表5 InvSubBytes（）过程中状态初值

表6 InvSubBytes（）过程中经过多进制组合后状态初值

2 算法测试

2.1 模拟实验

通过C＃语言实现AES算法和利用多进制组合的AES算法对图片进行加密解密效果，如图2a和图2b所示。

通过模拟实验，能够看出多进制组合后的AES加密算法与原AES加密算法在对图像进行加密和解密时，能够得到相同的效果，从而验证了多进制组合AES算法的可行性。

图2 AES与多进制组合对图像加解密的影响

2.2 测试结果分析

下面给出原图、AES算法加密后的图和经过多进制组合的AES算法加密后的图3类图像的各种通道的直方图比较效果，如图3～图6所示。

通过分析比较各通道直方图相关参数，可得出如下结果：① 像素均无变化；②2种算法对中间值都有变化，但是变化值相同；③ 平均值和标准偏差变化都不相同。

在平均值上，亮度、绿色和蓝色，多进制组合AES算法比原来算法稍微偏高，而红色偏低。在标准偏差上，亮度、红色和蓝色，多进制组合AES算法比原来算法稍微偏高。

因此，如果把多进制组合AES算法应用在图像加密方向上，与原算法相比，更有利于图像加密，对图像置乱效果增强。再结合其他算法，可以达到更加满意的效果［14］。

图3 亮度通道比较

图4 红色通道比较

图5 绿色通道比较

图6 蓝色通道比较

3 结束语

针对AES算法中的S盒构造问题，本文给出了一种快速构造S盒的方法，即多进制组合AES算法，通过这种方法可以快速构造出各种不同的S盒。

经过算法测试实验和实验分析，证明此算法设计较为合理，运算速度得以提高，并在加解密效果上变化不大，有比较广泛的应用前景。

［1］Dawson M H，Tavares S E.An expanded set of design criteria for substitution box and their use in strengthening DES－like cryptosystems［C］／／IEEE Pacific Rim Conference on Communications，Computer and Sigual Processing，1991：191－195.

［2］Dawson M H，Tavares S E.An expanded set of design criteria based on information theory and its relation to differential－like attacks［M］／／Advances in Cryptology：EUROCRYPT’91.Berlin：Springer－Verlag，1991：352－367.

［3］金晨辉，孙 莹.AES密码算法S盒的线性冗余研究［J］.电子学报，2004，32（4）：639－641.

［4］Gligoroski D，Moe M E G.On deviations of the AES S－box when represented as vector valued Boolean function［J］.International Journal of Computer Science and Network Security，2007，7（4）：156－161.

［5］胡 斌，金晨辉.AES算法S盒中的等价线性变换［J］.计算机工程与应用，2005（22）：70－72.

［6］冯等国，宁 鹏.S盒的非线性准则之间的关系［J］.通信学报，1998，19（4）：72－76.

［7］冯登国.线性结构与非线性度之间的关系［J］.电子学报，2000，28（1）：139－141.

［8］陈令羽，宋国民，徐 齐，等.DES在数字高程模型信息伪装中的应用研究［J］.合肥工业大学学报：自然科学版，2012，35（2）：189－192，279.

［9］刘晓晨，冯国登.满足若干密码学性质的S盒的构造［J］.软件学报，2000，11（10）：1299－1302.

［10］Nyberg K.Differentially uniform mappings for cryptography［C］／／Helleseth T.Advances in Cryptology，Proc EUROCRYPT’93，LNCS 765.Berlin：Springer－Verlag，1994：55－64.

［11］阮传概，孙 伟.近世代数及其应用［M］.北京：北京邮电大学出版社，2001：351－403.

［12］Ziedan I E，Fouad O，Salem D H.Application of data encryption standard to bitmap and JPEG images［C］／／The 20th National Radio Science Conference，2003：16－18.

［13］肖华勇，李建辉.基于AES的S盒图像置乱算法研究［J］.西北工业大学学报，2008，26（1）：74－77.

［14］杨 钒，薛模根.复合混沌二级置乱图像加密算法研究［J］.合 肥 工 业 大 学 学 报：自 然 科 学 版，2009，32（8）：1128－1131.