基于AES的短分组加密技术的改进

1、 157基于 AES 的短分组加密技术的改进刘连浩,崔 杰,胡睿达,刘上力(中南大学信息科学与工程学院,长沙 410083摘 要:介绍了基于 AES 的短分组加密算法,研究并指出算法中 S 盒的大小对加密性能有很大影响。通过求逆、作仿射变换构造了新的 十进制 S 盒,空间是原先的 10倍。将新 S 盒应用于短分组加密仿真系统中,分析发现其增强了算法的抗攻击能力,提高了算法的安全性。 实验仿真结果表明,新 S 盒使加解密的各项扩散率指标有明显提高,加密过程中密钥对密文的扩散率提高了 25%。 关键词:短分组; AES ; S 盒;加密Improvement on Short-block Encr

2、yption Technology Based on AESLIU Lianhao, CUI Jie, HU Ruida, LIU Shangli(College of Information Science and Engineering, Central South University, Changsha 410083【 Abstract 】 This paper introduces the short-block encryption algorithm based on AES, studies the S-box of the algorithm, and points out

3、that thesize of S-box has great influence on encryption performance. The new decimal S-box is constructed by taking multiplicative inverse and applyingaffine transformation, and its size is 10 times of the original one. And the new S-box is applied in the short-block encryption simulationsystem, and

4、it shows that the new S-box strengthens the resistance of the algorithm against attack and improves the security of the encryption algorithm.Experiments and simulation indicate that the new S-box improves all the diffusion rate, during which thekey to cipher in encryption processincreases by 25 perc

5、ent.【 Key words】 short-block; AES; S-box; encryption计 算 机 工 程 Computer Engineering第 33卷 第 14期Vol.33 No.14 2007年 7月July 2007安全技术 文章编号:1000 3428(200714 0157 03文献标识码:A中图分类号:TP301.6计算机适宜处理十六进制数,即二进制,加密算法一般 针对十六进制数进行设计,加密通信中密文一般由通信线路 传送,其加密技术已很成熟。但在国民经济的某些应用中, 因为通信双方没有直接联系,密文由人传送,属于免介质通 信,所以对密文的进制和分组长度有很

6、严格的要求,要求短 分组的十进制密文能表示最大信息量。如在预付费代码表计 等应用中对密文就作如此要求,购买信息的密文为固定长度 12、 16位等十进制数,由人传送和输入。该短密文要表示购 买量、 表计 ID 、 购买次数、 信息校验和用身份户认证等信息。 进制转换很容易实现,但通过进制转换得到的固定长度密文 不能表示最大信息量。如 6位十六进制数,其十进制数的最 高位只能为 0到 4。因此,进制转换得到的十进制数密文不 能表示最大信息量。此外,短分组加密应用 (如预付费代码表 计 中要求同一明文对于不同的购电次数或不同表计加密产 生的密文不同,采用 AES 1,2加密不能满足这种要求。基于 A

7、ES 的短分组加密技术 3很好地解决了此问题,本文对其进 行了研究,并提出了改进方案。1 短分组加密算法的 4种运算及加密 /解密文献 3提出的基于 AES 的短分组加密算法以 AES 为基础,并对 AES 的 4种加密运算进行重新设计,以满足实际应 用中对短分组加密的要求。 将 AES 中的轮密钥加改为轮密钥 运算控制,不同的密钥加密运算的轮密钥运算控制算法不一 样,使加密算法具有随机性。提出了动态密钥的概念,做到 了加密解密一次一密,使加密算法具有混沌加密算法一次一 密的特点 4,5。因此,该算法同时具有 AES 加密算法、随机 加密算法、混沌加密算法的优点。下面分别对短分组加密算 法中的

8、 4种加密运算及加密 /解密过程进行简要介绍。1.1 S盒替换 (S_box文献 3的短分组加密算法采用的 S 盒是一位十进制 S 盒, S 盒的空间为 GF(10,为了使状态在加 /解密时得到较好 的扩散,该 S 盒替换使替换值与原值有 2bit 的变化。该 S 盒 如图 1所示。01236849图 1 S盒替换表1.2 行移位 (ShiftRows表 1中 Nb 为状态 state 的列数, c i 为第 i 行移位的位数。 状态根据实际使用情况可分为 8位、 12位、 16位、 20位、 24位、 28位、 32位等十进制数。状态中最后 3行循环移位 的位数如表 1所示,即第 0行不移位

9、,第 1行移位 c 1位数, 第 2行移位 c 2位数,第 3行移位 c 3位数。对与小于 4列和大 于 7列的状态移位要进行特殊处理。表 1 位移量与状态列数的关系Nbc 1c 2c 3 说明2 1238位状态,第 2列循环向上移 1位3 12 该行与第 0行交换 12位状态 4 12 3 16位状态 5 12 3 20位状态 8 13 4 32位状态 158 1.3 列混合 (MixColumnAES 列混合中的按位异或加对于十进制数没有可逆性, 文献 3短分组加密算法的列混合采用线性列混合的加密方 法。加密时对每一列的数据进行列混合处理,得到的结果放 回到原来的矩阵中。记加密中列混合矩阵

10、为 A ,解密中逆列混合矩阵为 B ,A 和 B 是互逆正整数矩阵 1, 即 A *B = E mod 10(E 为单位矩阵 。该短分组加密算法采用的列混合矩阵见式 (1。 00 11 22 3353211523mod 1021533215c c c c c c c c s s s s s s s s =(1该短分组加密算法采用的逆列混合矩阵见式 (2。 00 11 22 3359433594mod 1042599435c c c c c c c c s s s s s s s s =(21.4 轮密钥运算控制 (ControlRoundKey由于异或运算对于十进制数没有可逆性,因此该短分组

11、加密算法将 AES 轮密钥加改为轮密钥运算控制。 轮密钥运算 控制程序有 4个入口,不同的入口对应不同的运算。入口由 每一轮加密运算所使用密钥的按位的和模上 4来确定 3。每 一轮加密所用的密钥是由密钥扩展函数根据上一轮加密所用 的密钥扩展得到。1.5 短分组加密算法的加密 /解密用 C 代表 ControlRoundKey , B 代表 S_box, S 代表 ShiftRows , M 代表 MixColumn ,加密流程如下:C BSMC BSMC BSC由于该短分组加密运算中采用的每一种运算都是可逆的,因此解密流程如下:C -1S -1B -1 C -1M -1S -1B -1 C -

12、1M -1S -1B -1 C -12 新 S 盒的设计基于 AES 的短分组加密算法的 S 盒运算是一个独立作用 于状态单元的非线性变换,文献 3中短分组加密算法采用的 是一位十进制 S 盒,其 S 盒空间为 GF (10,由于该 S 盒的运 算域比 AES 的 S 盒 GF (256小得多,因此 S 盒的非线性和扩 散性并非很高。从安全性的角度考虑,目前对 AES 最为可行 的攻击方法就是设计者自己提出的 Square 攻击, 该短分组加 密算法和 AES 具有类似的结构,算法的行移位、列混合和轮 密钥运算控制的基本加密运算域是一位十进制数,如果 S 盒 运算也采用一位十进制数替换,就很容

13、易使用改进的 Square 攻击算法对其实施攻击, 并且攻击的复杂度大大低于 AES 的 相应攻击,其安全性受到一定的威胁。为了有效提高该加密 算法的扩散性和安全性,本文设计了一种新的、两位十进制 数 S 盒, S 盒的空间为 (100GF 。新 S 盒运算包括在有限域(100GF 中的求乘法逆运算和在域 (10GF 下的仿射变换运算两个步骤。 其中, 求逆运算是将两位十进制数看作域 (100GF 的元素,求其在十进制不可化约多项式 2( 1m x x =+下的逆,而仿射变换是求逆结果与 (10GF 上矩阵 M 相乘然后与向量 I 相加。其中, M =2111;向量 I =(2,3T 。 S

14、盒运算具体过程 如下:(1在 GF (102 域,求乘法的逆运算,即对于 GF (102求 GF (102 ,使 2( 1mod 1x =+;(2在 GF (10域作仿射变换: (1100212113y x y x =+ 通过计算得到 GF (102 域上各个元素的逆元。 规定 0元素的逆为其自身。经过仿射变换,得到的新 S 盒如表 2所示。表 2 新两位十进制 S 盒Y97344847282 25 65 10 1628从表 2可以看出, GF (102 域上各个元素的 S 盒替换值遍历整个 GF (102 空间。 通过作仿射变换, 很好地消除了不动点 和对立不动点。3 S盒改进前后加密性能比

15、较3.1 S盒改进前后加密算法安全性比较文献 3短分组加密算法是以 AES 为基础设计的, 秉承了 AES 的许多特点。该算法每一轮的加密分为 S 盒替换、行移 位、列混合和轮密钥运算控制 4个步骤。加密运算的基本域 是状态中的一位十进制数。目前, Square 攻击是对 AES 最为 有效的攻击方法。经研究发现,对于此短分组加密算法可以 使用改进的 square 算法进行攻击。 描述改进 square 攻击算法, 需要定义 2个概念:集和平衡。定义 1 集是一个包含 101个状态的集合,这些状态在 某些十进制位 (称为活动位 上两两互异 (遍历位所有可能取 值 ,而在其他位 (称为非活动位

16、上则完全相同。亦即对任意 状态 , A B 有, , , , , , i ji j i j i j A B i j A B i j = 若(位置上是活动位 若(位置上是非活动位一个有 k 个活动位的 集记为 k 集。定义 2 包含 110个状态的集合 P 在某个位置 (i , j 上是平衡 的,当且仅当所有状态该位置上的位模 10加结果为 0或 5,即位 (i , j 是平衡的 , A P 0(mod5 i j A =+。 显然, 集的活动位是平衡的,但某个位置上的位是平 衡的并不意味着该位是活动的。改进的 Square-4攻击要求选择 10个明文构成一个 1集, 记为 0P 。经过初始轮轮密

17、钥运算控制、第 1轮的 S 盒替换及 行移位后, 0P 经运算产生的中间结果仍旧构成一个 1集。 但 由于列变换的扩散性,列混合使活动性扩散到此列所有位单 元上,因此第 1轮变换的结果是一个 4集, 4个活动位在同 一列上。第 2轮行移位后, 4个活动位分散到 4列上,列混合的结果是一个 16集。因为活动位的线性叠加结果并不意味 着是活动的, 所以第 3轮列混合的结果可能不再是一个 集。但由于 S 盒替换和行移位都是一一映射,并且线性的列混合 和轮密钥运算控制都不影响平衡性。第 3轮结果 3P 即第 4轮 输入的 16位状态仍旧是平衡的。 经过第 4轮 S 盒替换的非线性运算,这些位的平衡性被

18、破坏了。这种平衡性的变化可用 于猜测第 4轮的轮密钥。可见,改进的 Square 攻击完全可以攻击简化的 4轮、 5轮及 6轮短分组加密算法,并且攻击的时间复杂度和数据复 杂度都远远低于 AES 的相应攻击,因此采用一位十进制数 S 盒的加密算法安全性受到一定的威胁。将新的 S 盒应用于此短分组加密算法中能够很好地提高 其安全性。由于新 S 盒是两位十进制数的 S 盒,因此 S 盒运 算对状态中的两位十进制数一起操作,即 S 盒替换的基本运 算域是两位十进制数。而行移位、列混合及轮密钥运算控制 的基本运算域是一位十进制数。在第 1轮加密后,1P 状态中 的某些位的活动性和平衡性可能已经遭到破坏

19、,这样就无法 直接采用改进的 Square 攻击算法进行攻击, 从而大大增加了 Square 攻击的难度, 提高了该短分组加密算法的抗 Square 攻 击能力,安全性得到增强。通过研究发现,改变 S 盒的大小 或者改变行移位的运算域, Square攻击所利用的平衡性将不 再存在,从而可以提高加密算法的抗 Square 攻击能力,而该 结论同样适用于 AES 。3.2 S盒改进前后加密解密扩散率比较将新的两位十进制 S 盒替换文献 3中短分组加密算法 原有的 S 盒,并对替换前后的加密解密扩散率进行了软件仿 真测试分析,分别以 12位、 16位、 20位、 32位十进制数为 加密分组,进行 2

20、到 15轮的加密解密运算测试。下面是 20位十进制数为加密分组所得测试比较结果。改进前后加密过 程中明文对密文扩散率比较结果如图 2所示,密钥对密文扩 图 2 明文对密文扩散率比较结果图 3 密钥对密文扩散率比较结果改进前后解密过程中密文对明文扩散率比较结果如图 4所示,密钥对明文扩散率比较结果如图 5所示。可以看出,增大 S 盒后,加密解密扩散率的各项指标均 有 明 显 提 高 。 其 中 加 密 过 程 中 明 文 对 密 文 扩 散 率 提 高 了 3.3%,密钥对密文扩散率提高了 25%;解密过程中密文对明 文扩散率提高了 1%,密钥对明文扩散率提高了 1.5%。由此 得出, 加密性能很大程度上取决于 S 盒的大小。 在存储空间、 运算速度等条件允许的情况下,适当地增大 S 盒使加解密过 图 5 密钥对明文扩散率比较结果4 结论本文简要介绍了基于 AES 的短分组加密