高级数据加密标准.ppt

《高级数据加密标准.ppt》由会员分享，可在线阅读，更多相关《高级数据加密标准.ppt（60页珍藏版）》请在三一文库上搜索。

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年新密码开始试用并征求意见。 民众要求公开算法，

2、并去掉法律监督。 1994年颁布新密码标准（EES）。 1995年5月贝尔实验室的博士生M.Blaze在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)的全体元素构成加法交换群，线性空

4、间。 GF(28)的非零元素构成乘法循环群。 GF(28)中的元素有多种表示： 字节： 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+b

5、0 例：字节5701010111的多项式表示： 01010111 x6+x4+x2+x+1,三、数学基础,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)表示

6、 x乘法 xtime：用 x乘 GF(28)的元素 例： xtime(57)=x(x6+x4+x2+x+1)= 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加 字乘法

7、：设a和c是两个字，a(x)和c(x)是其字多项式，AES定义a和c的乘积为 b(x)=a(x)c(x) mod x4+1,三、数学基础,3、 AES的字表示与运算 字乘法：设a(x)=a3x3 + a2x2 + a1x + a0 c(x)=c3x3 + c2x2 + c1x + c0 b(x)=b3x3 + b2x2 + b1x + b0 b(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 c

8、3 b3 = a3 c0 + a2 c1 + a1 c2 + a0 c3,三、数学基础,3、 AES的字表示与运算 字乘法：写成矩阵形式 b0 = c0 c3 c2 c1 a0 b1 = c1 c0 c3 c2 a1 b2 = c2 c1 c0 c3 a2 b3 = c3 c2 c1 c0 a3 注意：1.x4+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

9、 01 00 00 b2 p3 = 00 00 01 00 b3 注意：因为模x4+1，字x乘法相当于字节循环移位；,三、数学基础,四、AES的基本变换,1、AES的数据处理方式 字节 字 状态 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 a

10、2,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、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,Rou

11、ndKey) 轮密钥加变换 ,四、AES的基本变换,3、轮变换加密轮函数 最后一轮的轮变换： Round(State,RounKey) ByteSub(State); S盒变换 ShiftRow(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盒

12、(DES),8,8,6,4,四、AES的基本变换,4、S盒变换 ByteSub(State) S盒变换: a)将输入字节用其GF(28)上的逆来代替； b)对a)的结果作如下的仿射变换： （以x0 x7作输入，以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

13、 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盒变换的第一步是把字节的值用它的乘法逆来代替，是一种非线性变换。 由于系数矩阵中每列都含有 5个1，这说明改变输入中的任意一位，将影响输出中的 5位发生变化。 由于系数矩阵中每行都含有 5个1，这说明输出中的每一位，都与输入中的 5位相关。,四、AES的基本变换,5、行移位变换 ShiftRow(State) 行移位变换对状态的行进行循环移位。 第 0行不移位，第1行移 C1字节，第2行移 C2字节，第3行移 C3字节。 C1，

14、C2，C3按表取值 Nb C1 C2 C3 4 1 2 3 6 1 2 3,四、AES的基本变换,5、行移位变换 ShiftRow(State) 行移位变换属于置换，本质在于把数据打乱重排。 AES的行移位变换属于线性变换。,四、AES的基本变换,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(

15、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 a1 b2 = 01 01 02 03 a2 b3 = 03 01 01 02 a3,四、AES的基本变换,7、轮密钥加变换 AddRoundKey() 把轮密钥与状态进行模2相加。 轮密钥根据密钥产生算法产生。 轮密钥长度等于数据块长度。,四、AES的基本变换,轮密钥根据密钥产生算法通过用户密 钥得到。 密钥产生分两步进行：密钥扩展和轮 密钥选

16、择 密钥扩展将用户密钥扩展为一个扩展 密钥。 密钥选择从扩展密钥中选出轮密钥。,五、轮密钥生成,1、密钥扩展 密钥扩展产生扩展密钥。 用一个字元素的一维数组WNb*(Nr+1)表示扩展密钥。 用户密钥放在数组最开始的Nk个字中。 其它的字由它前面的字经过处理后得到。 有 Nk6 和 Nk6 两种密钥扩展算法。,五、轮密钥生成,1、密钥扩展 Nk6 的密钥扩展 最前面的Nk个字是由用户密钥填充的。 之后的每一个字Wj等于前面的字Wj-1与Nk 个位置之前的字Wj-Nk的异或。 而且对于Nk的整数倍的位置处的字，在异或之前，对Wj-1进行Rotl变换和ByteSub变换，再异或一个轮常数Rcon

17、。,五、轮密钥生成,五、轮密钥生成,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是一个字里的字节以字节为单位循环左移位函数，设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

18、的密钥扩展相比， Nk6 的密钥扩展的不同之处在于：如果j被Nk除的余数4，则在异或之前，对Wj-1进行ByteSub变换。 增加了ByteSub变换 。因为当Nk6时密钥很长，仅仅对Nk的整数倍的位置处的字进行ByteSub变换，就显得ByteSub变换的密度较稀，安全程度不够强。,五、轮密钥生成,2、轮密钥选择 根据分组的大小，依次从扩展密钥中取出轮密钥。 前面的Nb个字作为轮密钥0，接下来的Nb个字作为轮密钥1。 W W0 W1 WNb-1 WNb W2Nb-1 第一轮密钥 第二轮密钥,五、轮密钥生成,六、AES的加密算法,AES的加密算法由以下部分组成： 一个初始轮密钥加变换。 Nr-

19、1轮的标准轮变换。 最后一轮的非标准轮变换。,加密算法：,Encryption(State,CipherKey) KeyExpansion(CipherKey, RoundKey) AddRoundKey(State, RoundKey) For(I=1;INr;I+) Round(State, RoundKey) ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, RoundKey) FinalRound(State, RoundKey) ByteSub(State); ShiftRow(State);

20、AddRoundKey(State, RoundKey)； 注意: 第一步和最后一步都用了轮密钥加，因为任何没有密钥参与的变换都是容易被攻破的。,算法可逆是对加密算法的基本要求。 AES的加密算法不是对合运算，解密算法与加密算法不同。 AES的巧妙之处：虽然解密算法与加密算法不同，但是解密算法与加密算法的结构相同。 把加密算法的基本运变换成逆变换，便得到解密算法。,七、 AES的基本逆变换,AES的各个基本变换都是可逆的。 1、轮密钥加变换的逆就是其本身 (AddRoundKey)-1= AddRoundKey 2、行移位变换的逆是状态的后三行分别移位Nb-C1，Nb-C2，Nb-C3个字节。

21、,七、 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)=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

22、 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,七、 AES的基本逆变换,5、解密的密钥扩展 解密的密钥扩展与加密的密钥扩展不同； 解密的密钥扩展定义如下： 加密算法的密钥扩展。 把InvMixColumn应用到除第一和最后一轮外的所有轮密钥上。,七、 AES的基本逆变换,6、逆轮变换 标准逆轮变换 Inv_

23、Round(State,Inv_RoundKey) Inv_ByteSub(State); Inv_ShiftRow(State); Inv_MixColunm(State); AddRoundKey(State,Inv_RoundKey); ,七、 AES的基本逆变换,6、逆轮变换 最后一轮的逆变换： Inv_FinalRound(State,Inv_RoundKey) Inv_ByteSub(State); Inv_ShiftRow(State); AddRoundKey(State,Inv_RoundKey); ,七、 AES的基本逆变换,八、AES的解密算法,加密算法不是对合运算： (

24、AES)-1AES 解密算法的结构与加密算法的结构相同 解密中的变换为加密算法变换的逆变换，且密钥扩展策略稍有不同。,Decryption(State,CipherKey) Inv_KeyExpansion(CipherKey,Inv_ RoundKey); AddRoundKey(State,Inv_ RoundKey); For(I=1;INr;I+) Inv_Round(State, Inv_ RoundKey); Inv_ByteSub(State); Inv_ShiftRow(State); Inv_MixColumn(State); AddRoundKey(State, Inv_

25、RoundKey ； Inv_FinalRound(State,Inv_RoundKey) InvByteSub(State); InvShiftRow(State); AddRoundKey(State, Inv_ RoundKey )； ,解密算法：,九、AES的实现,适应多种环境，高效，方便是AES的突出优点。 由于AES的基本运算由ByteSub、MixColumn、ShiftRow和AddRoundKey变换构成，因此AES的实现主要是这些变换的实现。 其中ShiftRow和AddRoundKey的实现比较容易，因此主要是ByteSub和MixColumn变换的实现问题。 有了这些基

26、本运算的实现，便可以有效地实现整个AES。,九、AES的实现,实现方法：软件 硬件 软件方法：基于算法描述 基于查表,九、AES的实现,1、基于算法描述的软件实现 AES的算法描述是一种程序化的描述，便于实现。 AES的四种基本变换都比较简单，便于实现。 用 C语言仿照算法描述，可方便地实现。 这种实现的速度不是最快的！,九、AES的实现,2、基于查表的软件实现 用查表实现算法是一种高效的软件设计方法。 时空折换是信息科学的基本策略。 用查表实现算法，就是用空间换取时间。 目前计算机系统的存储空间大、而且便宜，为查表实现算法提供了物资基础。,九、AES的实现,2、基于查表的软件实现 S盒的实现

27、 实现S盒变换的最快方法是，直接计算出S盒的变换的结果，并存储造表，使用时时直接查表。因为ByteSub变换是字节函数，所以表的规模不大，只含256个元素。 注意：解密时用的是逆S盒，因此共需要造两个S盒表。,列混合变换 MixColumn的实现 b(x)=a(x)c(x) mod x4+1 写成矩阵形式 b0 = 02 03 01 01 a0 b1 = 01 02 03 01 a1 b2 = 01 01 02 03 a2 b3 = 03 01 01 02 a3 主要运算是GF(28)上的乘法 GF(28)的非零元素构成循环群，可通过加法和查表实现乘法。,九、AES的实现,列混合变换 MixC

28、olumn的实现 注意：解密需要逆变换 a(x)=b(x)d(x) mod x4+1 d(x)=0Bx3+0Dx2+09x+0E 写成矩阵形式 a0 = 0E 0B 0D 09 b0 a1 = 09 0E 0B 0D b1 a2 = 0D 09 0E 0B b2 a3 = 0B 0D 09 0E b3 仍可通过加法和查表实现GF(28)的乘法。,九、AES的实现,轮函数的查表实现 整个轮函数都可以通过查表盒一些简单的运算来实现。,九、AES的实现,十、AES的安全性,能够抵抗目前所有的已知攻击： 穷举攻击。 差分攻击。 线性攻击。 Square攻击。,十一、AES的评说,1、AES的体现 AE

29、S体现商农的密码设计理论。 体现了公开设计原则：公开算法 AES代表当今商业密码的最高水平。,2、AES需要经过实际应用的检验 AES的大规模应用才刚刚开始； 实践是检验商用密码的唯一标准。,大作业,以AES作为加密算法开发出文件加密软件系统： 具有文件加密和解密功能； 具有加解密速度统计功能； 采用密文反馈链接和密文挪用短块处理技术； 具有较好的人机界面。,复习题,1、对比AES和DES有什么不同？ 2、AES的解密算法与加密算法有什么不同？ 3、在GF（28）中，01的逆元素是什么？ 4、对于字节“ 00”和“ 01”计算S盒的输出。 5、证明c(x)与d(x)互逆，模x4+1。 6、证明:xi mod (x4+1)=xi mod 4,