第5章 高级加密标准 高级加密标准(AdvancedEncryptionStandard,AES)是目前被全世界广泛采用的一 种加密标准,它在2001 年取代了DES 成为新的加密标准。相比DES,AES 具有更长的 密钥长度和分组长度,并且更加侧重于软件运行效率,已然成为对称密钥加密中最流 行的算法之一。AES 加密和解密过程使用两套算法,是一对互逆操作,在变换过程中, 交替使用代换和置换两种操作以达到加密效果。就目前情况来看,AES 具有较高的安 全性。 5.1 高级加密标准的起源 随着计算能力的突飞猛进,已经超期服役的DES 显得力不从心,在1999 年NIST 发 布的一个新版本的DES 标准指出,DES 仅能用于遗留的系统,同时3DES 将取代DES 成 为新的标准。3DES 提高了密钥长度,并且由于是基于DES 的,安全性得以保证。如果 仅考虑算法安全,3DES 的确成为了最近二十多年的一个加密算法标准[21,22,26]。 但是3DES 的首要缺点在于软件实现该算法的速度较慢。起初DES 是为20 世纪70 年代中期的硬件实现所设计的,难以由软件高效地实现。在3DES 中轮的数量DES 的三 倍,故其效率更低。另一个缺点是DES 和3DES 的分组长度均为64 比特。就效率和安 全性而言,分组长度应更长[29]。 由于这些缺点,NIST 在1997 年公开征集新的高级加密标准AES,要求安全性能不 低于3DES,同时应具有更好的运行性能。除了这些一般的要求之外,NIST 特别提出了 高级加密标准必须是分组长度为128 比特的对称分组密码,并能支持长度为128 比特、 192 比特和256 比特的密钥[34-36]。 1998 年8月12 日,在首届AES 候选方案会议上公布了AES 的15 个候选算法,任由 全世界各机构和个人攻击和评论,这15 个候选算法是CAST256 、CRYPTON 、E2 、 DEAL 、FROG 、SAFER+ 、RC6 、MAGENTA 、LOKI97 、SERPENT 、MARS 、Rijndael、 DFC 、Twofish、HPC 。 1999 年3月,在第2届AES 候选方案会议上,经过对全球各密码机构和个人对候选 算法分析结果的讨论,NIST 从15 个候选算法中初选出了5个,分别是RC6 、Rijndael、 SERPENT 、Twofish和MARS 。 现代密码学概论(第2版) 2000 年4月13 日至14 日,NIST 召开了第3届AES 候选方案会议,继续对最后5 个候选算法进行讨论。 2000 年10 月2日,NIST 宣布Rijndael作为新的AES 。 至此,经过3年多的讨论,Rijndael终于脱颖而出成为高级加密标准,但是在成为标 准的过程中,NIST 也对其进行了一些修改。 Rijndael并非AES 严格地说,AES 和Rijndael加密方法并不完全一样(虽然在实际应用中二者可以 互换), 因为Rijndael加密方法可以支持更大范围的分组和密钥长度[36](AES 的分组 长度固定为128 比特,密钥长度则可以是128 比特、192 比特或256 比特;而Rijndael 使用的密钥和分组长度可以是32 比特的整数倍,以128 比特为下限,256 比特为上 限)。加密过程中使用的密钥由Rijndael密钥生成方案产生。 5.2 代换置换网络结构 代换置换网络(substitution-permutationnetwork,SPN)将数学运算应用于分组密 码,如AES 、Square、SAFER 等。SPN 将输入的明文进行交替的代换操作和置换操作以 产生密文,这些操作均可以使用异或、移位等操作进行,使其在软件和硬件上均可很好地 实现[37]。每一轮使用的子密钥产生于输入的密钥,甚至在有些基于SPN 算法的加密算 法中,用于代换操作的 S 盒也是基于子密钥产生的。图5-1为一个使用2轮SPN 结构的 简单算法,其中单轮经过密钥异或、 S 盒代换和 P 盒置换三个步骤。 图5- 1 简单SPN 网络 68 第5章高级加密标准 高级加密标准的结构 5.3 AES 使用SPN 作为基础进行设计,保留了SPN 的框架,但是在每轮SPN 中添加了 列混合的线性变换过程,并且指定了分组长度为128 比特,但是密钥可以是128 比特、192 比特或256 比特[38]。 5.1 总体结构 3. 图5-2展示了AES 加密过程的总体结构。明文分组的长度为128 比特,密钥可以为 3种长度。根据密钥的长度,AES 算法被称为AES-128 、AES-192 和AES-256,并且密钥 图5- 2 AES 加密过程 69 现代密码学概论(第2版) 长度的改变也将导致SPN 轮次的改变,具体数值见图5-2中的表格。后续小节将以128 比特密钥AES 作为示例进行讲解。 加密和解密算法的输入是一个128 比特的分组,通常将这个分组描述为一个4×4 的 字节方阵,存储于状态数组,并在加密或解密的各个阶段被修改。而在整个AES 算法中, 变换状态分组的子算法有7个,分别为字节代换、逆字节代换、行移位、逆行移位、列混合、 逆列混合和轮密钥加变换[39,40]。 128 究竟比56 强多少? 假设可以制造一台可以在1秒内穷举破解DES 密码的机器,那么使用这台机器破 解一个128 比特AES 密码需要大约149 万亿年的时间(更进一步比较,宇宙一般被认 为存在了不到300 亿年)。 3.详细结构 5.2 在AES-128 的加密过程中,明文首先被复制入state数组中,进行一次初始变换(实 际上是一次轮密钥加变换), 紧接着进行9轮变换和最后第10 轮的变换。在9轮变换中, 每一轮均按照字节代换、行移位、列混合和轮密钥加这样的顺序进行。但是在最后一轮 (即第10 轮)变换中则只进行3种变换,即字节代换、行移位和轮密钥加。解密过程中密 文同样被复制入一个状态数组并进行一次初始变换(使用加密第10 轮密钥的轮密钥加变 换), 接着进行与加密过程对应的9轮变换和第10 轮变换。在9轮变换中,每一轮均按照 逆向行移位、逆向字节代换、轮密钥加和逆向列混合这样的顺序进行。在最后一轮,即第 10 轮变换中,只进行逆向行移位、逆向字节代换和轮密钥加。从图5-3可以看出,加密和解 密是一组互逆过程,解密中的操作均是加密中对应操作的逆向过程,使得密文恢复成明文。 3.轮密钥加变换 5.3 轮密钥加变换是一个状态数组和子密钥异或的操作。如图5-4所示,参与运算的是 状态数组和子密钥,变换结果由二者按比特异或运算得出。 轮密钥加变换非常简单,却能根据密钥去影响状态数组中的每一位。密钥扩展的复 杂性和AES 其他阶段(如SPN 的重复操作)的复杂性共同确保了AES 的安全性。 3.字节代换 5.4 字节代换和逆字节代换实际上就是一个 S 盒代换的过程。AES 中定义了两个 S 盒,即 S 盒和逆 S 盒,其中加密的字节代换使用 S 盒,解密的逆字节代换使用逆 S 盒。 如表5-1和表5-2所示, S 盒和逆 S 盒均是由16×16 字节组成的矩阵,包含了8比特 所能表示的256 个数的置换。状态数组中的每字节按照如下的方式代换为一个新的 字节:把该字节的高4比特作为行值,低4比特作为列值,以这些行列值从 S 盒或逆 S 盒中索引到位置的元素作为输出。例如,在加密过程中,十六进制数(EA)16 所对应 87)EA)16 的行为14,列为10(从0开始), S 盒中在此位置的是(16,则(16 将被代换为(87)。 第5章高级加密标准 图5- 3 AES-128 加解密详细流程 71 现代密码学概论(第2版) 图5- 4 轮密钥加示意图 而在解密过程中,(16 对应的8行7列值为(。实际上,同样的数据经过 S 盒变换 87)EA)16 后再经过逆 S 盒变换,即可得到原始的数据,所以字节代换和逆字节代换是一个互逆的 过程。 表5- 1 S 盒 63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76 CA82C97DFA5947F0ADD4A2AF9CA472 C0 B7FD9326363FF7CC34A5E5F171D831 15 04C723C31896059A071280E2EB27 B275 09832C1A1B6E5AA0523BD6B329 E32F84 53D100ED20FCB15B6ACBBE394A4C58 CF D0EFAAFB434D338545F9027F503C9F A8 51A3408F929D38F5BCB6DA2110FFF3 D2 CD0C13EC5F974417C4A77E3D645D19 73 60 81 4F DC 22 2A 90 88 46 EE D8 14 DE5E 0B DB E0323A0A4906245CC2D3AC629195 E479 E7 C8 37 6D 8D D5 4E A96C 56 F4 EA 65 7A AE 08 BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A 70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E E1F8981169D98E949B1E87E9CE5528 DF 8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 64 BB 16 表5- 2 逆 S 盒 5C096AD53036A538BF40A39E81 F3D7FB 7C E3 39 82 9B 2F FF 87 34 8E 43 44 C4 DE E9 CB 54 7B 94 32 A6 C2 23 3D EE 4C 95 0B 42 FA C3 4E 08 2E A1 66 28 D9 24 B2 76 5B A2 49 6D 8B D1 25 72F8F66486689816D4A45CCC5D65 B692 6C704850FDEDB9DA5E154657A78D9D 84 90D8AB008CBCD30AF7E45805B8B345 06 D0 2C 1E 8F CA 3F 0F 02 C1 AFBD 03 01 13 8A 6B 72 续表 第5章 高级加密标准 3A 91 11 41 4F 67 DC EA 97 F2 CF CE F0 B4 E6 73 96 AC 74 22 E7 AD 35 85 E2 F9 37 E8 1C 75 DF 6E 47 F1 1A 71 1D 29 C5 89 6F B7 62 0E AA 18 BE 1B FC 56 3E 4B C6 D2 79 20 9A DB C0 FE 78 CD 5A F4 1F DD A8 33 88 07 C7 31 B1 12 10 59 27 80 EC 5F 60 51 7F A9 19 B5 4A 0D 2D E5 7A 9F 93 C9 9C EF A0 E0 3B 4D AE 2A F5 B0 C8 EB BB 3C 83 53 99 61 17 2B 04 7E BA 77 D6 26 E1 69 14 63 55 21 0C 7D 5.3.5 行移位 行移位和逆行移位如同其名称一样,是一个简单的移位过程。不过根据状态数组行 标不同,每一行移动的位数也不同。如图5-5所示,按照大多数程序语言来说,在加密过 程中,第0行循环左移0个字节,第1行循环左移1字节,第2行循环左移2字节,第3行 循环左移3字节。而在解密过程中,就是这个操作的逆过程,即循环左移改变成循环 右移。 图5-5 行移位示意图 在不同密钥长度的AES中,行移位的长度略不相同。在AES-128和AES-192中,行 移位的偏移量是0、1、2和3,而在AES-256中,行移位的偏移量是0、1、3和4。 5.3.6 列混合 列混合是对每列独立地进行操作,每列中的每字节被映射为一个新的值,该值由该列 中的4字节通过函数变换得到。该变换可以由下面所示的基于状态的矩阵乘法表示。 02 01 01 03 03 02 01 01 01 03 02 01 01 01 03 02 é . êêêêê ù . úúúúú S0,0 S1,0 S2,0 S3,0 S0,1 S1,1 S2,1 S3,1 S0,2 S1,2 S2,2 S3,2 S0,3 S1,3 S2,3 S3,3 é . êêêêê ê ù . úúúúú ú = S'0,0 S'1,0 S'2,0 S'3,0 S'0,1 S'1,1 S'2,1 S'3,1 S'0,2 S'1,2 S'2,2 S'3,2 S'0,3 S'1,3 S'2,3 S'3,3 é . êêêêê ê ù . úúúúú ú 在逆向列混合中,和列混合一样,仅仅是与状态运算的矩阵不同,使用的矩阵如下 所示。 73 现代密码学概论(第2版) 0e 09 0d 0b 0b 0e 09 0d 0d 0b 0e 09 09 0d 0b 0e é . êêêêê ù . úúúúú S0,0 S1,0 S2,0 S3,0 S0,1 S1,1 S2,1 S3,1 S0,2 S1,2 S2,2 S3,2 S0,3 S1,3 S2,3 S3,3 é . êêêêê ê ù . úúúúú ú = S'0,0 S'1,0 S'2,0 S'3,0 S'0,1 S'1,1 S'2,1 S'3,1 S'0,2 S'1,2 S'2,2 S'3,2 S'0,3 S'1,3 S'2,3 S'3,3 é . êêêêê ê ù . úúúúú ú 行移位是算法对行进行变换,而列混合是算法对列进行变换,经过行移位和列混合的 状态数组已经完全变样,从而使算法的安全性更好。 在列混合和逆向列混合中,乘积矩阵中的每个元素均是一行和一列中的对应元素的 乘积之和。在这个矩阵运算中的乘法和加法都是被定义在有限域上的运算,且是基于 GF(28)的。关于GF(28)上的乘法和加法可详见5.5节,如果读者对此没有兴趣而只想知 道计算机中如何操作,那么可以跳过5.5节前面部分,直接阅读5.5.6节。 AES的软件优化 使用32或更多比特寻址的系统可以事先对所有可能的输入创建对应表,利用 查表实现字节代替、行移位和列混合步骤以达到加速的效果。这么做需要产生4个 表,每个表都有256个格子,一个格子记载32比特的输出;约占4KB(4096字节)存 储器空间,即每个表占1KB的存储器空间。如此一来,在每个加密循环中只需要 查16次表,作12次32比特的异或运算,以及轮密钥加步骤中4次32比特异或 运算。 若目标的平台存储器空间不足4KB,那么也可以利用循环交换的方式一次查一个 256格32比特的表。 5.3.7 密钥扩展算法 AES-128中的密钥扩展算法的输入值是16字节,输出值是一个由176字节组成的移 位线性数组。这足以为AES-128提供初始变换和其他10轮中的每一轮提供16字节的 轮密钥。 输入密钥被直接复制到扩展密钥数组的4个字(字长为32字节)。然后每次用4个字 填充扩展密钥数组余下的部分。在扩展密钥数组中,每个新增的字w[i]的值依赖w[i-1] 和w [i-4]。在4个情形中有3个使用了异或运算。对w 数组中索引为4的倍数的元 素,采用了更复杂的函数计算。图5-6(a)展示了密钥扩展算法的整体流程,图5-6(b)展示 了w 数组中索引为4的倍数的元素所采用的函数g。 函数g 的输入为一个4字节的字,首先进行一次字移位,再对每个字按照表5-1进 行一次S 盒的代换,最后与轮常量Rcon[j]相异或。轮密钥Rcon[j]由1个RC[j]和3 个0字节组成,其中RC[j]的值如下。 RC[j]= 1, j=1 2*RC[j-1], j >1且RC[j-1]<8016 RC[j]=2*RC[j-1]+1B16,j >1且RC[j-1]>=8016 ì . í .. .. 同样,该过程中的乘法也是定义在GF(28)上的。在AES-128中的RC 值可以参考 74 第5章 高级加密标准 表5-3(十六进制表示)。 图5-6 AES密钥扩展算法 表5-3 AES-128密钥扩展中的RC 值 j 1 2 3 4 5 6 7 8 9 10 RC[j] 01 02 04 08 10 20 40 80 1B 36 5.4 AES设计上的考虑 AES作为新一代的标准替代了DES地位,必然在设计时考虑到一些已有的攻击[41], 同时还需要考虑一些可能存在的攻击方法。与DES相比,AES在设计上有什么特点呢? 1. 扩散速度更快 AES算法是一种SPN 体制,与DES的Feistel体制的每次循环时有一半数据未被更 改不同,AES将数据中的所有比特同等对待,使输入比特的扩散影响更快,通常两轮循环 就足以得到完全的扩散,即所有的128比特输出都完全依赖128比特输入。而这一扩散 效果有一部分依赖行移位和列混合。 75 现代密码学概论(第2版) 2. S 盒的构造方法 与DES的S 盒构造方法存在神秘色彩不同,AES的S 盒构造使用一种简单而清晰 的方法,这样就可以避免任何建立在算法上的陷门,从而使其得到广泛应用。 3. 抗攻击能力 AES的S 盒是基于有限域建立的,用它对抗差分分析和线性分析效果显著。AES- 128的轮数为10轮,这是因为较低的轮次会导致蛮力攻击成功。密钥扩展函数中的循 环常量用于消除在循环过程中生成每个循环差别的对称性,并且使用S 盒以防止攻击 者在知道部分密钥的情况下发起攻击。而128比特的密钥相较于DES的56比特,防 穷尽搜索的能力更强,且最大可支持256比特密钥,提供更高的防护级别[42]。但是随 着计算能力的提高和攻击方式的优化,精心保护的AES也会存在安全隐患。例如,针对 重用掩码AES算法的侧信道碰撞攻击在噪声为0.0029时,成功率能够达到95%[43]。上 海交通大学郁昱教授曾在BlackHat现场演示侧信道攻击破解SIM 卡AES-128加密,用 其方法能使用一张克隆SIM 卡成功伪装成卡主,更改支付宝的密码,而且有可能将账户 中的资金全部盗走。 对于AES设计上的改进,主要集中在提高硬件的吞吐量[44,45]和算法安全性[46]两 方面。 5.5 有限域 在古典密码学中,常以模运算作为密码学加密运算技术。而随着计算机能力的提升, 单纯的模运算并不安全。AES引入了数论中的有限域,提高了加密算法抵抗攻击的能 力。本节将简单讨论有限域的知识,主要侧重其在计算机上的实现,详细的理论不在本书 的讨论范围。在讨论有限域前,需要先介绍一个有趣的问题———多项式算术,这里只讨论 单自变量的多项式。 5.5.1 什么是有限域 有限域是一个有限集合S 再添加两种特定运算的代数系统,与现实生活中的十进制 运算不同的是,其上自定义的加法运算和乘法运算只要满足以下条件,即可以认为S 是 一个有限域。 ① 加法的封闭性:如果a 和b 属于S,则a+b 也属于S。 ② 加法结合律:对S 中任意元素a,b,c 有a+(b+c)=(a+b)+c。 ③ 加法单位元:S 中存在一个元素a,使得对于S 中任意元素b,有a+b=b+a=b, 通常记a 为0。 ④ 加法逆元:对于S 中的任意元素a,S 中一定存在一个元素-a,使得a+(-a)= (-a)+a=0。 76