密码学高级数据加密标准AES

1、密 码 学高级数据加密标准AES一、AES的概况1、历史时间：1997年美国政府向社会公开征集高级数据加密标准（AES）；1998年8月20日从应征的21个算法中选出15个。1999年8月又选中其中5个算法。2000年10月2日再选出1个算法。2001年11月26日接受其作为标准。2001年12月4日正式公布：FIPS197。Federal Information Processing Standards 一、AES的概况2、AES产生的背景 1984年12月里根总统下令由国家保密局研制新密码标准，以取代DES。 1991年新密码开始试用并征求意见。 民众要求公开算法，并去掉法律监督。 199

2、4年颁布新密码标准（EES）。 1995年5月贝尔实验室的博士生在PC 机上用45分钟攻击法律监督字段获得成功。 1995年7月美国政府放弃用EES加密数据。1997年美国政府向社会公开征AES。一、AES的概况3、AES的设计要求 安全性：抵抗所有已知攻击； 实用性：适应各种环境，速度快； 扩展性：分组长度和密钥长度可扩展。 一、AES的概况4、整体特点 分组密码:分组长度和密钥长度可变，可独立地为128/192/256等,现在一般取 128 。 面向二进制的密码算法:能够加解密任何形式的计算机数据。 不是对合运算:加、解密使用不同的算法。 综合运用置换、代换、代数等多种密码技术 整体结构：

3、基本轮函数加迭代。轮数可变，10一、AES的概况5、应用 许多国际组织采用为标准。 尚未大范围应用。 产品形式：软件（嵌入式，应用软件） 硬件（芯片，插卡）6、结论只有通过实际应用的检验才能证明其安全。我们相信：经过全世界广泛分析的AES是不负众望的。二、框图128位明文初始轮密钥加S盒变换行移位与列混淆轮密钥加128位密文迭代控制密钥轮密钥产生轮函数Nr个轮密钥Nr轮1、AES的基础域是有限域 GF(28) 一个GF(2)上的8次既约多项式可生成一个 GF(28) GF(28)的全体元素构成加法交换群，线性空间。GF(28)的非零元素构成乘法循环群。 GF(28)中的元素有多种表示： 字节：

4、 GF（28）=a7,a6,a1,a0 多项式形式： GF（28）=a7x7+a6x6+a1x+a0 指数形式：GF(28)*=0, 1 254 对数形式：GF(28)*=0, 1 254 GF(28)的特征为 2 。 三、数学基础2、 AES的GF(28)表示AES采用的既约模多项式： m(x)=x8+x4+x3+x+1 AES采用GF(28)的多项式元素表示。 字节Bb7b6b5b4b3b2b1b0可表示成GF(2)上的多项式： b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0 例：字节5701010111的多项式表示： 01010111 x6+x4+x2+x+1

5、 三、数学基础2、 AES的GF(28)表示加法：两元素多项式的系数按位模 2加例2：5783D4(x6+x4+x2+x+1)(x7+x+1)= x7+x6+x4+x2 乘法：两元素多项式相乘，模 m(x) 例3：5783C1 (x6+x4+x2+x+1)(x7+x+1)=x7+x6+1 mod m(x) 乘法单位元：字节01 多项式 1乘法逆元：设a(x)的逆元为b(x)，则 a(x)b(x)=1 mod m(x) 。根据Euclid算法求出。三、数学基础2、 AES的GF(28)表示 x乘法 xtime：用 x乘 GF(28)的元素例： xtime(57)=x(x6+x4+x2+x+1)=

6、 x7+x5+x3+x2+x xtime(83)=x(x7+x+1)= x8+x7+x mod m(x) =x7+x4+x3+1若x7的系数0，则为简单相乘：系数左移。若x7的系数1，则取模m(x)，减x8+x4+x3+x+1 。三、数学基础3、 AES的字表示与运算AES数据处理的单位是字节和字一个字4个字节一个字表示为系数取自GF(28)上的次数低于4次的多项式例： 字：57 83 4A D1 57x3+83x2+4Ax+D1字加法：两多项式系数按位模2加 字乘法：设a和c是两个字，a(x)和c(x)是其字多项式，AES定义a和c的乘积为 b(x)=a(x)c(x) mod x4+1三、数

7、学基础3、 AES的字表示与运算字乘法：设a(x)=a3x3 + a2x2 + a1x + a0 c(x)=c3x3 + c2x2 + c1x + c0 b(x)=b3x3 + b2x2 + b1x + b0b(x)=a(x)c(x) mod x4+1，则 b0 = a0 c0 + a3 c1 + a2 c2 + a1 c3 b1 = a1 c0 + a0 c1 + a3 c2 + a2 c3 b2 = a2 c0 + a1 c1 + a0 c2 + a3 c3 b3 = a3 c0 + a2 c1 + a1 c2 + a0 c3 三、数学基础3、 AES的字表示与运算字乘法：写成矩阵形式 b

8、0 = c0 c3 c2 c1 a0 b1 = c1 c0 c3 c2 a1 b2 = c2 c1 c0 c3 a2 b3 = c3 c2 c1 c0 a34+1是可约多项式，字c(x)不一定有逆； 2.但在AES中选择c(x)固定，且有逆。 三、数学基础3、 AES的字表示与运算字x乘法：p(x)=xb(x) mod x4+1写成矩阵形式： p0 = 00 00 00 01 b0 p1 = 01 00 00 00 b1 p2 = 00 01 00 00 b2 p3 = 00 00 01 00 b3注意：因为模x4+1，字x乘法相当于字节循环移位； 三、数学基础四、AES的基本变换1、AES的

9、数据处理方式 字节 字 状态2、状态 加解密过程中的中间数据。 以字节为元素的矩阵，或二维数组。四、AES的基本变换2、状态 符号：Nb明密文所含的数据的字数。 Nk密钥所含的数据的字数。 Nr迭代轮数。 例：Nb4时的状态 Nk4时的密钥数组 a0,0 a0,1 a0,2 a0,3 k0,0 k0,1 k0,2 k0,3 a1,0 a1,1 a1,2 a1,3 k1,0 k1,1 k1,2 k1,3 a2,0 a2,1 a2,2 a2,3 k2,0 k2,1 k2,2 k2,3 a3,0 a3,1 a3,2 a3,3 k3,0 k3,1 k3,2 k3,3 四、AES的基本变换2、状态 Nb

10、、Nk、Nr之间的关系： Nr Nb=4 Nb=6 Nb=8 Nk=4 10 12 14 Nk=6 12 12 14 Nk=8 14 14 14 四、AES的基本变换3、轮变换加密轮函数 标准轮变换： Round(State,RoundKey) ByteSub(State); S盒变换 ShiftRow(State); 行移位变换 MixColumn(State); 列混合变换 AddRoundKey(State,RoundKey) 轮密钥加变换四、AES的基本变换3、轮变换加密轮函数 最后一轮的轮变换： Round(State,RounKey) ByteSub(State); S盒变换 Sh

11、iftRow(State);行移位变换 AddRoundKey(State,RoundKey) 轮密钥加变换注：最后一轮的轮变换中没有列混合变换。四、AES的基本变换4、S盒变换 ByteSub(State) S盒变换是AES的唯一的非线性变换，是AES安全的关键。AES使用16个相同的S盒，DES使用8个不相同的S盒。AES的S盒有8位输入8位输出，DES的S盒有6位输入4位输出。 S盒(AES)S盒(DES)8864四、AES的基本变换4、S盒变换 ByteSub(State) S盒变换: a)将输入字节用其GF(28)上的逆来代替； b)对a)的结果作如下的仿射变换： （以x0 x7作输

12、入，以y0 y7作输出。）四、AES的基本变换4、S盒变换 ByteSub(State) y0 1 0 0 0 1 1 1 1 x0 1 y1 1 1 0 0 0 1 1 1 x1 1 y2 1 1 1 0 0 0 1 1 x2 0 y3 = 1 1 1 1 0 0 0 1 x3 + 0 y4 1 1 1 1 1 0 0 0 x4 0 y5 0 1 1 1 1 1 0 0 x5 1 y6 0 0 1 1 1 1 1 0 x6 1 y7 0 0 0 1 1 1 1 1 x7 1四、AES的基本变换4、S盒变换 ByteSub(State) 注意：S盒变换的第一步是把字节的值用它的乘法逆来代替，是

13、一种非线性变换。由于系数矩阵中每列都含有 5个1，这说明改变输入中的任意一位，将影响输出中的 5位发生变化。由于系数矩阵中每行都含有 5个1，这说明输出中的每一位，都与输入中的 5位相关。四、AES的基本变换5、行移位变换 ShiftRow(State)行移位变换对状态的行进行循环移位。第 0行不移位，第1行移 C1字节，第2行移 C2字节，第3行移 C3字节。 C1，C2，C3按表取值 Nb C1 C2 C3 4 1 2 3 6 1 2 3四、AES的基本变换5、行移位变换 ShiftRow(State)行移位变换属于置换，本质在于把数据打乱重排。AES的行移位变换属于线性变换。四、AES的

14、基本变换6、列混合变换 MixColumn(State)列混合变换把状态的列视为GF(28)上的多项式a(x)，乘以一个固定的多项式c(x)，并模 x4+1: b(x)=a(x)c(x) mod x4+1其中，c(x)=03x3+01x2+01x+02列混合变换属于代替变换。c(x)与x4+1互素，从而保证c(x)存在逆多项式d(x),而c(x)d(x)=1 mod 。 只有逆多项式d(x)存在，才能正确进行解密。6、列混合变换 MixColumn(State) b(x)=a(x)c(x) mod x4+1写成矩阵形式 b0 = 02 03 01 01 a0 b1 = 01 02 03 01

15、a1 b2 = 01 01 02 03 a2 b3 = 03 01 01 02 a3 四、AES的基本变换7、轮密钥加变换 AddRoundKey() 把轮密钥与状态进行模2相加。 轮密钥根据密钥产生算法产生。 轮密钥长度等于数据块长度。 四、AES的基本变换轮密钥根据密钥产生算法通过用户密 钥得到。密钥产生分两步进行：密钥扩展和轮 密钥选择密钥扩展将用户密钥扩展为一个扩展 密钥。密钥选择从扩展密钥中选出轮密钥。 五、轮密钥生成1、密钥扩展密钥扩展产生扩展密钥。用一个字元素的一维数组WNb*(Nr+1)表示扩展密钥。 用户密钥放在数组最开始的Nk个字中。其它的字由它前面的字经过处理后得到。有

16、Nk6 和 Nk6 两种密钥扩展算法。 五、轮密钥生成1、密钥扩展 Nk6 的密钥扩展最前面的Nk个字是由用户密钥填充的。之后的每一个字Wj等于前面的字Wj-1与Nk 个位置之前的字Wj-Nk的异或。而且对于Nk的整数倍的位置处的字，在异或之前，对Wj-1进行Rotl变换和ByteSub变换，再异或一个轮常数Rcon 。 五、轮密钥生成五、轮密钥生成 W0 W1 W2 WNk-1 WNk WNk+1 用户密钥 当 j 不是Nk的整数倍时: WjWj-Nk Wj-1当 j 是Nk的整数倍时:WjWj-Nk ByteSub (Rotl ( Wj-1) ) Rconj/Nk; 说明： Rotl是一个

17、字里的字节以字节为单位循环左移位函数，设W（A，B，C，D），则Rotl（W）（B，C，D，A）。轮常数Rcon与Nk无关，且定义为： Rconi = (RCi, 00， 00， 00) RC0 = 01 RCi = xtime(RCi-1) 五、轮密钥生成1、密钥扩展 Nk6 的密钥扩展说明： 与Nk6 的密钥扩展相比， Nk6 的密钥扩展的不同之处在于：如果j被Nk除的余数4，则在异或之前，对Wj-1进行ByteSub变换。增加了ByteSub变换 。因为当Nk6时密钥很长，仅仅对Nk的整数倍的位置处的字进行ByteSub变换，就显得ByteSub变换的密度较稀，安全程度不够强。 五、轮密

18、钥生成2、轮密钥选择 根据分组的大小，依次从扩展密钥中取出轮密钥。 前面的Nb个字作为轮密钥0，接下来的Nb个字作为轮密钥1。 W W0 W1 WNb-1 WNb W2Nb-1 第一轮密钥 第二轮密钥 五、轮密钥生成六、AES的加密算法AES的加密算法由以下部分组成：一个初始轮密钥加变换。 Nr-1轮的标准轮变换。最后一轮的非标准轮变换。加密算法：Encryption(State,CipherKey) KeyExpansion(CipherKey, RoundKey) AddRoundKey(State, RoundKey) For(I=1;INr;I+) Round(State, Round

19、Key) ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, RoundKey) FinalRound(State, RoundKey) ByteSub(State); ShiftRow(State); AddRoundKey(State, RoundKey)； 注意: 第一步和最后一步都用了轮密钥加，因为任何没有密钥参与的变换都是容易被攻破的。 算法可逆是对加密算法的基本要求。AES的加密算法不是对合运算，解密算法与加密算法不同。AES的巧妙之处：虽然解密算法与加密算法不同，但是解密算法与加密算法的结构相

20、同。把加密算法的基本运变换成逆变换，便得到解密算法。 七、 AES的基本逆变换AES的各个基本变换都是可逆的。1、轮密钥加变换的逆就是其本身 (AddRoundKey)-1= AddRoundKey2、行移位变换的逆是状态的后三行分别移位Nb-C1，Nb-C2，Nb-C3个字节。 七、 AES的基本逆变换3、列混合变换的逆因为列混合变换是把状态的每一列都乘以一个固定的多项式c(x) :b(x)=a(x)c(x) mod x4+1所以列混合变换的逆就是状态的每列都乘以c(x)的逆多项式d(x)： d(x)=(c(x) )-1 mod x4+1 c(x)=03x3+01x2+01x+02 d(x)

21、=0Bx3+0Dx2+09x+0E七、 AES的基本逆变换4、S盒变换的逆首先进行逆仿射变换；再把每个字节用其在GF(28)中的逆来代替。 七、 AES的基本逆变换S盒的逆仿射变换： 0 0 1 0 0 1 0 1 y 0 1 x 0 1 0 0 1 0 0 1 0 y 1 1 x 1 0 1 0 0 1 0 0 1 y 2 0 x 2 1 0 1 0 0 1 0 0 y 3 0 x 3 0 1 0 1 0 0 1 0 y 4 0 x 4 0 0 1 0 1 0 0 1 y 5 1 x 5 1 0 0 1 0 1 0 0 y 6 1 x 6 0 1 0 0 1 0 1 0 y 7 0 x 7

22、七、 AES的基本逆变换5、解密的密钥扩展解密的密钥扩展与加密的密钥扩展不同；解密的密钥扩展定义如下：加密算法的密钥扩展。把InvMixColumn应用到除第一和最后一轮外的所有轮密钥上。七、 AES的基本逆变换6、逆轮变换标准逆轮变换 Inv_Round(State,Inv_RoundKey) Inv_ByteSub(State); Inv_ShiftRow(State); Inv_MixColunm(State); AddRoundKey(State,Inv_RoundKey); 七、 AES的基本逆变换6、逆轮变换最后一轮的逆变换： Inv_FinalRound(State,Inv_Ro

23、undKey) Inv_ByteSub(State); Inv_ShiftRow(State); AddRoundKey(State,Inv_RoundKey); 七、 AES的基本逆变换八、AES的解密算法加密算法不是对合运算： (AES)-1AES解密算法的结构与加密算法的结构相同解密中的变换为加密算法变换的逆变换，且密钥扩展策略稍有不同。Decryption(State,CipherKey) Inv_KeyExpansion(CipherKey,Inv_ RoundKey); AddRoundKey(State,Inv_ RoundKey); For(I=1;INr;I+) Inv_Ro

24、und(State, Inv_ RoundKey); Inv_ByteSub(State); Inv_ShiftRow(State); Inv_MixColumn(State); AddRoundKey(State, Inv_ RoundKey ； Inv_FinalRound(State,Inv_RoundKey) InvByteSub(State); InvShiftRow(State); AddRoundKey(State, Inv_ RoundKey )；解密算法：九、AES的实现适应多种环境，高效，方便是AES的突出优点。由于AES的基本运算由ByteSub、MixColumn、Sh

25、iftRow和AddRoundKey变换构成，因此AES的实现主要是这些变换的实现。其中ShiftRow和AddRoundKey的实现比较容易，因此主要是ByteSub和MixColumn变换的实现问题。有了这些基本运算的实现，便可以有效地实现整个AES。九、AES的实现实现方法：软件 硬件软件方法：基于算法描述 基于查表 九、AES的实现1、基于算法描述的软件实现AES的算法描述是一种程序化的描述，便于实现。AES的四种基本变换都比较简单，便于实现。用 C语言仿照算法描述，可方便地实现。这种实现的速度不是最快的！九、AES的实现2、基于查表的软件实现用查表实现算法是一种高效的软件设计方法。时空折换是信息科学的