3.5 高级数据加密标准AES

3.5.1 AES的背景

1997年4月15日，美国国家标准和技术研究所（NIST）发起了征集AES算法的活动，并成立了专门的AES工作组，目的是为了确定一个非保密的、公开披露的、全球免费使用的分组密码算法，用于保护下一世纪政府的敏感信息，并希望成为秘密和公开部门的数据加密标准。1997年9月12日，NIST公布了AES算法候选提名的最终要求，AES的基本要求是：比三重DES快而且至少和三重DES一样安全，分组长度128比特，密钥长度为128/192/256比特。1998年8月20日，NIST召开了第一次AES候选会议，并公布了15个候选算法。1999年3月22日举行了第二次AES候选会议，会议对15个算法在安全性、代价和实现特性等方面进行了评估，从中选出5个。入选AES的5种算法是MARS、RC6、Serpent、Twofish、Rijndael。2000年4月13日，在第三次AES候选会议上，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，美国商务部部长Norman Y. Mineta宣布，经过三年来世界著名密码专家之间的竞争，Rijndael数据加密算法最终获胜。NIST指出，之所以最终选择Rijndael是因为它是安全性、性能、效率、实现方便性和灵活性的最佳组合。AES将成为新的公开的联邦信息处理标准（Federal Information Processing Standard，FIPS）——一种用于美国政府组织保护敏感信息的加密算法。美国国家标准技术研究所预测AES会被广泛地应用于组织、学院及个人。

3.5.2 AES的数学基础

先来回顾一下抽象代数的一些基本概念。

3.5.2.1 代数运算

若干个（有限或无限多个）固定事物的全体叫做一个集合。组成一个集合的事物叫做这个集合的元素（有时简称元）。

一个没有元素的集合叫空集合。

集合A和集合B的所有共同元素组成的集合叫做A和B的交集A∩ B。

由至少属于A和B之一的一切元素组成的集合叫做A和B的并集 ∪A B。

令 A1，A2，…，An是 n 个集合，由一切从 A1，A2，…，An里顺序取出的元素组（a1，a2，…，an）（ai∈Ai）所做成的集合叫做A1，A2，…，An的积，记为A1×A2×…×An。

假如通过一个法则φ，对于任何一个A1×A2×… ×An的元素（a1，a2，…，an）（ai∈Ai），都能得到一个唯一的集合D的元素d，那么这个法则φ叫做集合A1×A2×… ×An到集合D的一个映射。元素d叫做元素（a1，a2，…，an）在映射φ之下的像；元素（a1，a2，…，an）叫做元素d在映射φ之下的逆像。

一个映射常用以下符号来描写

φ：（a1，a2，…，an）→d=φ（a1，a2，…，an）

一个A×B到D的映射叫做一个A×B到D的代数运算，一个代数运算用“◦”来表示，，为方便起见，可以写成a◦b。

假如◦是一个A×A到A的代数运算，我们就说集合A对于代数运算◦来说是封闭的，也说◦是A的二元代数运算。

称一个集合A的代数运算◦适合结合律，假如对于A的任何三个元素a，b，c来说，都有（a ◦b）◦c=a ◦（b ◦c）。

称一个A×A到D的代数运算◦适合交换律，假如对于A的任何两个元素a，b来说，都有a ◦b=b◦a。

设⊙，⊕是A上的两个不同的二元运算，称代数运算⊙对⊕适合分配律，假如对于A的任何元素 b，a1，a2 来说，都有 b⊙（a1 ⊕ a2）=（b⊙a1）⊕（b⊙a2）而且（a1 ⊕ a2）⊙b =（a1⊙b）⊕（a2⊙b）。

3.5.2.2 群

一个非空的集合G对于一个叫做乘法◦的代数运算来说做成一个群，假如

（1）G对于乘法来说是封闭的。

（2）结合律成立：，对于G的任意三个元素a，b，c都成立。

（3）G里至少存在一个单位元e，能让，对于G的任何元a都成立。

（4）对于G的每一个元素a，在G里存在一个逆元a-1能让a-1◦a = a◦a-1 =e。

例如，全体整数的集合Z对整数的加法形成一个群，称为整数加群。

一个群叫做有限群，假如这个群的元素个数是一个正整数。否则，这个群叫做无限群。一个有限群的元素的个数叫做这个群的阶。

一个群叫做交换群，假如a◦b = b◦a，对于G里的任何两个元素a，b都成立。

若一个群的每一个元素都是G的某一个固定元素a的乘方，我们把G叫做循环群，我们也说G是由元素a所生成的，并且用符号G =（a）来表示。a叫做G的一个生成元。

例如，整数加群形成一个循环群，它的生成元仅有1和-1，为无限循环群。

整数同余类环Zn中的全部元素对同余类加法所形成的群，是一个阶为n的循环群。若a和n互素，则由a决定的模同余类[a]就是Zn的生成元。事实上，∀[b]∈Zn，必有一个整数k使得a · k ≡ b（mod n）。这样，我们有：

k[a] = [a]+[a]+ … +[a] = [k· a] = [b]（有k个[a]）

整数同余类环 Zn的乘法可逆元的全体组成的集合对同余类乘法形成一个群 Zn*，这个群是交换群，一般不是循环群，以 Z12*为例，Z12* = {[1],[5],[7],[11]}，它不是循环群。仅当 n为素数的时候，Zn*为循环群。

3.5.2.3 环

一个集合R叫做一个环，假如：

（1）R对于一个叫做加法“+”的代数运算成为一个交换群。

（2）R对于一个叫做乘法“◦”的代数运算来说是封闭的。

（3）这个乘法适合结合律a◦（b◦c）=（a◦b）◦c，对于属于R的任意元素a，b，c都成立。

（4）◦对+的分配律成立，a◦（b + c）= a◦b + a◦c，（b + c）◦a = b◦a + c◦a。

例如，全体整数构成的集合对于普通加法和乘法来说成为一个环。全体有理数构成的集合对于普通加法和乘法来说成为一个环。

环R被称为含有单位元的环，是指R内含有乘法单位元“1”，使得∀a∈R，有a◦1=1◦a = a。

一个环叫做一个交换环，假如a◦b = b◦a，对于属于R的任意两个元素a，b都成立。

例如，剩余类环Zn为整数模n剩余类的集合Zn={[0]，[1], …, [n -1]}，它对剩余类的加法和乘法构成一个含有单位元“[1]”的交换环。取大于1的正整数n，则n的一切整数倍形成的集合nZ对数的加法和乘法形成了一个不含单位元“1”的交换环。

整环：含有乘法单位元“1”而无零因子的交换环称为整环。

若在一个环里，a≠0，b≠0但a◦b = 0，就说a是这个环的一个左零因子，b是这个环的一个右零因子。

任何一个整环都至少含有两个元素。恰含有两个元素的整环是存在的，例如F2 = {0，1}它对模2的加法乘法运算形成一个整环，事实上，它为二元域。

3.5.2.4 有限域GF（p）

一个环被称为除环（或斜域），是指该环的非零元全体对“◦”形成一个群。

一个可交换的除环称为域。

例如，Fp为整数模p的剩余类环，p为素数，可以验证它为域。因为Fp中的元素有限，称它为有限域；又因为p为素数，又称为素域。

域首先必是整环；反之则不然。

一个元素个数有限的域称为有限域，或者伽罗瓦域（Galois field）。

有限域中运算满足交换律、结合律和乘法对加法的分配律。加法的单位元是0，乘法的单位元是1，每个非零元素都有一个唯一的乘法逆元。

通俗地讲，域是一个包含两种运算的集合，其中一种运算叫加法，另一种运算叫乘法。如果把加法的逆运算叫减法，把乘法的逆运算叫除法时，域是一个在其元素之间可以自由地进行加、减、乘、除运算且保持运算结果仍在其内的一个集合。数域只是域中的一种，特点是元素都是数。典型的数域有：有理数域、实数域和复数域。

密码学中用到很多有限域中的运算，因为可以保持数在有限的范围内，且不会有取整的误差。最常用的两个域是GF（p）和GF（2n）。

有限域中元素的个数为一个素数p，或者一个素数的幂pn，记为GF（p）或GF（pn），其中p为素数。GF（p）是整数集合{0，1，…，p-1}，其运算为模素数p的运算。

3.5.2.5 多项式运算和有限域GF（2n）

对于一元多项式 f（x），多项式运算可分为三种：使用代数基本规则的普通多项式运算；系数在有限域GF（p）中，即系数运算是模p运算的多项式运算；系数在有限域GF（p）中，且多项式被定义为模一个n次多项式m（x）的多项式运算。

一个一元n（n≥0）次多项式的表达形式如下：

f（x）= anxn+an-1xn-1+…+a1x1+a0

其中，ai是某个指定的数集S中的元素，该数集叫系数集，且an≠0，我们称f（x）是定义在系数集S上的多项式。

现在考虑这样的多项式，它的系数是域F中的元素，这样的多项式集合关于多项式乘法和多项式加法是一个环，称为多项式环，记为F [x]。对域上的多项式进行多项式运算时，除法是可能的，但并不表示可以整除。一般来说，会产生一个商式和一个余式

f（x）= q（x）g（x）+ r（x）

与整数运算相似，我们可以把余式r（x）写为f（x）mod g（x），如果余式r（x）= 0，可以说g（x）整除f（x），记为g（x）| f（x），等价地可以说g（x）是f（x）的一个因式或除式。

域F上的多项式f（x）被称为不可约的，当且仅当f（x）不能表示为两个基本多项式（两个多项式都在F上，次数都低于f（x））的积。与整数相似，一个不可约多项式称为素多项式。

设集合S由域Zp上次数小于n的所有多项式组成，每一个多项式具有如下形式：f（x）= an-1xn-1+ an-2xn-2 + … + a1x1 + a0，其中ai在集合{0，1，2，…，p-1}上取值。S中共有pn个不同的多项式。如果定义了合适的运算，那么每一个这样的集合都是一个有限域。定义包含以下几条：

（1）该运算遵循基本代数规则中的普通多项式运算规则。

（2）系数运算以p为模。

（3）如果乘法运算的结果是次数大于n-1的多项式，必将其除以某个次数为n的不可约多项式m（x）并取余式。

设F为有限域，m（x）= xn + m1xn-1 + m2xn-2 + … + mn，mi∈F，为F上的n次不可约多项式，以m（x）为模的同余类环E=F[x]/<m（x）>可视为F上的一个有限域。当多项式的系数为Zq中的元素，q为一素数，这个域称为GF（qn）。有限域GF（23）的元素为：0，1，x，x +1，x2，x2 +1，x2 + x,x2+ x +1。

实际上所有的加密运算（包括对称密钥和公开密钥算法）都涉及整数集上的算术运算。如果某种算法使用的运算之一是除法，那么就必须定义域上的运算。我们希望整数集中的数与给定的二进制位所能表达的信息一一对应，n位二进制编码所代表的数的个数为2n。

特别地，GF（2n）中的多项式f（x）= an-1xn-1 + an-2xn-2 + … + a1x1 + a0可以由它的n个二进制系数（an-1 an-2…a1 a0）唯一地表示。因此，GF（2n）中的每一个多项式都可以表示成一个n位的二进制数。

在硬件上利用线性反馈移位寄存器可以快速地实现GF（2n）上的运算。GF（2n）上的运算通常比GF（p）上的运算快。

3.5.2.6 GF（28）的构造

AES使用有限域GF（28）上的运算，选定GF（2）上的一个8次不可约多项式m（x）= x8 + x4+ x3 + x +1，以m（x）为模的同余类F2[x]/<m（x）>可以形成一个有限域，GF（28）中的多项式 f（x）= a7x7 + a6x6 + … + a1x1 + a0可用一个字节表示为（a7，a6，a5，a4，a3，a2，a1，a0），ai∈F2，于是GF（28）中两元素的和可以通过相应的两个字节的异或完成：

（01010111）⊕（10000011）=（11010100）

对应于

（x6 + x4 + x2 + x +1）+（x7 + x +1）= x7 + x6 + x4 + x2

而两个元素的乘法，需要进行字节对应的多项式的乘法，再模m（x）= x8 + x4 + x3 + x+1，例如，两字节（01010111），（10000011）的乘⊙，相当于（x6+x4+x2+x+1）×（x7+x+1）= x13 + x11 + x9+ x8 + x6 + x5 + x4 + x3 +1（mod m（x））= x7 + x6 +1（=（11000001））。

另一方面，某字节对应于f（x）∈F2[x]/<m（x）>，求这个字节的逆，就是求f（x）-1，可用Euclid算法，算出u（x），v（x）∈F2[x]，使

u（x）f（x）+ v（x）m（x）= 1

于是

f（x）-1 = u（x）（mod m（x））

再者，x×f（x）= a7x8 + a6x7 + … + a1x2 + a0x（mod m（x）），若a7 = 0，则乘积相当于将f（x）所对应的字节做左移位（left shift）；若a7 =1，则须将乘积再与m（x）-x8 = x4 + x3 + x +1所对应的字节（00011011）做异或。

例如

则

f（x）= x6 +x4 +x2 +x+1 =（01010111）

则 x× f（x）（mod m（x））=（01001110）+（00011011）=（01010101）= x6 +x4 +x2 +1

3.5.3 对AES的描述

3.5.3.1 AES的特点和结构

Rijndael为AES所定义的迭代式分组密码算法，它的分组长度（block length）和密钥长度（key length）是可以各自独立的，当然它们都可以是128位、192位或256位。AES输入-输出分组规定为128位，支持128位、192位和256位三种密钥长度，有较好的数学理论作为基础，结构简单、速度快。AES参数取决于密钥长度的选择，表3.9给出了AES的参数配置。

AES不属于Feistel结构，加密、解密相似但不对称，它采用的是SP网络结构，如图3.9所示，在这种密码的每一轮中，轮输入首先被一个由子密钥控制的可逆函数S作用，然后再对所得结果用置换（或可逆线性变换）P作用。S和P分别被称为混淆层和扩散层，主要起混淆和扩散作用。与Feistel网络相比，每一轮对整个数据分组进行了处理，因而可以得到更快的扩散。

图3.10（a）是AES加密算法的框图。第一轮之前，应用了一个密钥加层。它对密码的安全性不做任何贡献。为了使得加密和解密在结构上更为相似，最后一轮的线性混合层与其他的混合层不同。可以证明它不会影响算法的安全性。AES的每一轮由四个阶段组成，如图3.10（b）所示，分别是：

● 字节代替：用一个S盒完成分组的按字节代替。

● 行移位：是一个简单的置换。

● 列混淆：一个利用在域GF（28）上的算术特性的代替。

● 密钥加层：轮密钥简单地异或到中间状态上。

3.5.3.2 AES算法流程

假设State表示数据，以及每一轮的中间结果，RoundKey表示每一轮对应的子密钥，算法如下：

第一轮之前执行AddRoundKey（State，RoundKey）

            Round（State，RoundKey）{
              ByteSub（State）；
              ShiftRow（State）；
              MixColumn（State）；
              AddRoundKey（State，RoundKey）；
            }
            FinalRound（State,RoundKey）{
              ByteSub（State）；
              ShiftRow（State）；
              AddRoundKey（State，RoundKey）；
            }

3.5.3.3 字节代替变换

AES用状态（State）表示输入和输出数据，以及每一轮的中间结果。一个状态可以表成4 行Nb列的一个矩阵，其中Nb=分组长度/32。密钥（Cipher key）也表示成一个4行Nk列的矩阵，其中Nk=密钥长度/32。图3.11给出了当明文分组为128 bit，密钥长度也为128 bit时的状态和密钥矩阵。这里，矩阵的每个元素为1 字节，明文分组和密钥以字节为单位在矩阵中按照从上到下从左到右的顺序排列。

字节代替是一个非线性的字节代替，独立地在每个状态字节上进行运算。S盒输入和输出都是8 bit的，是由两个可逆变换复合而成，首先在有限域GF（28）中取逆元，零元00的逆元规定为00。其次，将所得逆元再经过下面定义的[GF（2）上的]仿射变换的作用。逆元是为了确保每个值在表中刚好出现一次，仿射变换有助于打破原有模式。完整的代替表如表3.10所示。例如，字节21用第2行、第1列的FD代替。设S盒中的输入字节记为（x7，x6，x5，x4，x3，x2，x1，x0），输出字节记为（y7，y6，y5，y4，y3，y2，y1，y0），AES的字节代替变换可以描述如下：

3.5.3.4 行移位变换

虽然AES指定分组长度只能为128，但是原来的Rijndael算法却允许128位、192位和256位的分组。对于128位和192位的分组，将状态（State）中的第i行循环左移（i-1）字节，对256位的分组，第3行和第4行额外再移一个字节。具体移位字节见表3.11。

还是以Nb = 4（128 bit）为例

3.5.3.5 列混淆变换

在列混淆变换中，将状态的列视为有限域GF（28）上的四维向量并且被GF（28）上的一个固定的可逆方阵A左乘，设输入状态为（a0j，a1j，a2j，a3j），输出状态为（b0j，b1j，b2j，b3j），列混淆变换可描述如下：

3.5.3.6 轮密钥加变换

用简单的比特异或将一个轮密钥作用在状态上，bij=aij+kij，如图3.12所示。轮密钥是通过密钥调度算法从密钥中产生，轮密钥长度等于分组长度。

3.5.3.7 密钥扩展算法

轮密钥是通过密钥调度算法从密钥中产生，包括两个组成部分：密钥扩展和轮密钥选取。密钥扩展算法先将密钥扩展成一个扩展密钥，轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始 Nb个字组成，第二个轮密钥由接下来的 Nb个字组成，如此继续下去。其基本参数如下所述。

轮密钥发生器的输入是初始密钥，长度为32×Nk比特，其中Nk=4，6或者8，其输出为各轮的轮密钥。轮密钥只用在Add RoundKey中，长度等于明文分组，为32×Nb比特。进行Nr轮变换，需要Nr+1个轮密钥，所以总共扩展的密钥长为32 ×Nb×（Nr+1）比特。将轮密钥的序列表示成4行的矩阵，其中每个元素都是一个字节（8 bit），则矩阵需要有Nb ×（Nr+1）列。若设Nb=4，Nr=10，且将第i列记为一个32 bit的字（word）w[i]，我们有

密钥扩展对于N ≤ 6k 和Nk > 6的情形是不同的。当N ≤ 6k 时，密钥扩展的伪代码如下：

            Key Expansion（byte Key[4＊Nk]，word W[Nb＊（Nr +1）]）
            {
                for（i=0;i<Nk;i++）
                    w[i]={Key[4＊i]，Key[4＊i+1]，Key[4＊i+2]，Key[4＊i+3]）：
                for（i=Nk；i< Nb＊（Nr +1）；i++）
                {
                    temp=w[i-1];
                    if（i%Nk==0） temp=SubWord（RotWord（temp）+Rcon[i/Nk]）；

                    w[i]=w[i-Nk]⊕temp；
                }
            }

首轮的w[0]，w[1]，…，w[Nk-1]就是初始的密钥。32 bit的w[i-1]可表示为4个字节：a0 a1 a2 a3，于是，RotWord（w[i-1]）= a1 a2 a3 a0，即将4个字节作为左循环移位。SubWord（a0 a1 a2 a3）= S（a0）S（a1）S（a2）S（a3），即将4个字节分别用S盒进行变换。上两个步骤的结果再与轮常量Rcon[j]异或。每轮的轮常量均不同，定义为Rcon[j] =（Rc[j]，0，0，0），Rc[j]的值以十六进制表示为：

Nk>6与N ≤ 6k 时密钥扩展算法的区别在于，当i满足i-4是Nk的整数倍时，在异或之前，要把AES的S盒作用到w[i-1]的每个字节。

3.5.3.8 AES的解密

在AES的解密算法中，使用各变换算法对应的逆变换，尽管在加密和解密过程中密钥扩展的形式是一样的，但解密算法按逆序使用了扩展密钥。其算法伪代码如下：

第一轮之前执行AddRoundKey（State，RoundKey）

        Round（State，RoundKey）{
            InvShiftRow（State）；逆向行移位
            InvByteSub（State）；逆向字节代替变换
            AddRoundKey（State，RoundKey）；
            InvMixColumn（State）；逆向列混淆
        }
        FinalRound（State,RoundKey）{
            InvShiftRow（State）；
            InvByteSub（State）；
            AddRoundKey（State，RoundKey）；
        }

1．逆向字节代替变换

逆向字节代替变换利用了表3.12所给出的逆S盒。输入FD到逆S盒得到输出21，输入21到S盒得到输出FD。S盒与逆S盒互逆，但S盒不是自逆的。设逆S盒中的输入字节记为（x7，x6，x5，x4，x3，x2，x1，x0），输出字节记为（y7，y6，y5，y4，y3，y2，y1，y0），逆S盒变换也可以用如下方式来描述：

2．逆向行移位变换

AES的逆向行移位变换将状态（state）中的后三行执行相反方向的移位操作，第i行循环右移（i-1）字节，如第3行循环右移2字节。

3．逆向列混淆变换

设输入状态为（a0j，a1j，a2j，a3j），输出状态为（b0j，b1j，b2j，b3j），逆向列混淆变换由如下的矩阵乘法定义：