高级数据加密标准AES课件.ppt
高级数据加密标准AES背景AES的数学基础AES加密算法描述AES解密算法算法评价结论背景现代计算机速度的迅速提高，使得只有56bit密钥的DES算法的安全性面临着极大的挑战。1997年，NIST公开征求AES（Advanced Encryption Standard）作为2001年以后的数据加密标准。1998年8月，AES召开第一次候选会，确定15个算法入围。1999年3月，AES召开第二次候选会，有5个算法入围（MARS,RC6,Rijndael,Serpent和Twofish）。2000年10月，NIST选出由比利时的Joan Daemen和Vincent Rijmen提交的Rijndael算法作为AES。2001年夏天，NIST颁布新的信息处理标准（FIPS），将Rijndael算法作为AES。AES的数学基础(1)有限域GF(28)上定义了4种运算：“+”、“”、“X”和带系数的多项式乘运算“”。对字节b，用多项式表示为：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0“+”运算：两个字节相加，相当于字节的每一位简单异或。例：5783d4(57)16=(01010111)2x6+x4+x2+x+1(83)16=(10000011)2 x7+x+15783(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2(11010100)2(d4)16AES的数学基础(2)“”运算：选择一个不可约多项式：m(x)=x8+x4+x3+x+1，“”运算为两多项式相乘后进行模m(x)的运算。例：57 83c1(57)16=(01010111)2x6+x4+x2+x+1(83)16=(10000011)2 x7+x+157 83(x6+x4+x2+x+1)(x7+x+1)mod(x8+x4+x3+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+x+x6+x4+x2+x+1)mod(x8+x4+x3+x+1)=(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1)x7+x6+1(11000001)2(c1)16(x13+x11+x9+x8+x6+x5+x4+x3+1)mod(x8+x4+x3+x+1):X5+x3x8+x4+x3+x+1x13+x11+x9+x8+x6+x5+x4+x3+1x13 +x9+x8+x6+x5x7+x6+1x11+x4+x3+1x11+x7+x6+x4+x3AES的数学基础(3)“X”运算：b X=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x求乘法逆元：因为m(x)是GF(28)上的不可约多项式，所以对于任意b(x)，都可以用扩展的Euclid算法求a(x)，使得 a(x)b(x)+c(x)m(x)=1 因而 a(x)b(x)mod m(x)=1 即 b1(x)mod m(x)=a(x)例：求(x7+x6+1)关于模m(x)x8+x4+x3+x+1的乘法逆元。辗转相除：x8+x4+x3+x+1(x7+x6+1)(x+1)+(x6+x4+x3)x7+x6+1=(x6+x4+x3)(x+1)+(x5+x3+1)x6+x4+x3=(x5+x3+1)x+(x3+x)x5+x3+1=(x3+x)x2+1扩展的Euclid算法：1=(x5+x3+1)(x3+x)x2 (x5+x3+1)(x6+x4+x3)+(x5+x+1)x)x2 =(x5+x3+1)(1+x3)+(x6+x4+x3)x2 =(x7+x6+1)+(x6+x4+x3)(x+1)(1+x3)+(x6+x4+x3)x2 =(x7+x6+1)(1+x3)+(x6+x4+x3)(x4+x3+x2+x+1)=(x7+x6+1)(1+x3)+(x8+x4+x3+x+1)+(x7+x6+1)(x+1)(x4+x3+x2+x+1)=(x7+x6+1)(x5+x3)+(x8+x4+x3+x+1)(x4+x3+x2+x+1)因此，(x7+x6+1)1 mod(x8+x4+x3+x+1)x5+x3 AES的数学基础(4)带系数的多项式乘运算“”：令a(x)=a3x3+a2x2+a1x+a0,b(x)=b3x3+b2x2+b1x+b0,其乘积 c(x)=a(x)b(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0其中，c0=a0 b0 c1=a1 b0 a0 b1 c2=a2 b0 a1 b1 a0 b2 c3=a3 b0 a2 b1 a1 b2 a0 b3 c4=a3 b1 a2 b2 a1 b3 c5=a3 b2 a2 b3 c6=a3 b3对（x4+1）取模得d(x):d(x)=a(x)b(x)=d3x3+d2x2+d1x+d0其中，d0=a0 b0 a3 b1 a2 b2 a1 b3 d1=a1 b0 a0 b1 a3 b2 a2 b3 d2=a2 b0 a1 b1 a0 b2 a3 b3 d3=a3 b0 a2 b1 a1 b2 a0 b3注意：xi mod(x4+1)=xi mod 4AES加密算法描述加密算法概述一圈变换密钥扩展加密算法描述加密算法概述（1）AES算法与以往的基于Feistel网的密码（如DES）不同，算法的每一步都是可逆的。算法的明文块长可以为128bit，192bit或256bit，密钥也可以分别为128bit，192bit或256bit。算法有多圈相同的运算，每一圈包括4个步骤：非线性代替（S-盒）行循环左移（ShiftRow）列混合变换（MixColum）与扩展密钥相异或每一圈的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变换和循环左移算法定义的所有运算都是在有限域GF(28)上进行的加密算法概述（2）算法中进行运算的单位包括：1个字节1列1行用字节数组表示的整个加密块加密块数组中，n可以是3，5，7，所代表的加密块分别表示128bit，192bit和256bit。ai,ja0,ja1,ja2,ja3,jai,0ai,1ai,3a0,2a0,3a1,2a1,3a2,2a2,3a0,0a0,1a1,0a1,1a2,0a2,1a3,0a3,1a3,2a3,3a0,na1,na2,na3,n加密算法概述（3）令Nr代表算法的圈数，Nk代表密钥长度/32，Nb代表块长度/32，则算法的圈数Nr的取值与Nk和Nb的关系为：除最后一圈不做列混合变换外，每一圈都经过4步相同的操作：NrNb4 Nb6 Nb8Nk4101214Nk6121214Nk8141414Round(State,RoundKey)ByteSub(State);/S-盒 ShiftRow(State);/行循环左移 MixColumn(State);/列混合变换 AddRoundKey(State,RoundKey);/与扩展密钥相异或一圈变换（1）非线性代替（S-盒）：包括2步在GF(28)上求每个字节关于模m(x)的乘法逆元素，00的逆元定义为00；应用GF(2)上的一个仿射变换：一圈变换（2）每个字节aij经过以上2步变换后，记为bij。可以将每个可能的aij值对应的bij值制成表格，通过查表的方式来实现S-盒代替，见下表。其中xy代表1个字节的16进制表示。一圈变换（3）行循环左移（ShiftRow）：每一行以字节为单位循环左移，左移的字节数见右表。因此，第1行不移位，第2行左移1个字节列混合变换（Mixcolumn）：对每一列中每个字节a(x)，令b(x)=c(x)a(x)，其中c(x)为：c(x)=03x3+01x2+01x+02与扩展密钥相异或：aijkijbijNbC1C2C3412361238134一圈变换（4）一圈结构图：Step1.ByteSub(State)Step2.ShiftRow(State)Step3.MixColumn(State)Step4.AddRoundKey(State,RoundKey)StateS-盒行循环左移c(x)AARoundKeyRound(State,RoundKey)密钥扩展（1）扩展密钥是一个以4字节大小为单位(用Word表示)的线性数组。当Nk大于6的时候有一点不同。开始Nk个Word是加密用的密钥，以后每个Word通过对K实行变换得到。当Nk6时，若Nk i，则Wordi=Wordi-1 Wordi-Nk;若Nk|i，则先循环左移，然后查非线性变换表（S-盒），之后再与常量Rconi/Nk异或，其中：Rconi=(RCi,00,00,00)，RC1=1，RCi=x(RCi-1)=x(i-1)。最后，与Wordi-Nk异或。当Nk8时，若i mod Nk=4，则先查非线性变换表，再与Wordi-Nk异或。密钥扩展的伪代码：KeyExpansion(byte key4*Nk,word wNb*(Nr+1),Nk)for(i=0;i Nk;i+)wi=wordkey4*i,key4*i+1,key4*i+2,key4*i+3;for(i=Nk;i Nb*(Nr+1);i+)word temp=wi-1;if(i%Nk=0)temp=SubWord(RotWord(temp)Rconi/Nk;else if(Nk=8 and i%Nk=4)temp=SubWord(temp);wi=wi-Nk temp;密钥扩展（2）可以从扩展密钥中选择Round key，例如：当Nb6,Nk4时，扩展密钥和各圈子密钥的选择如下：加密算法描述整个算法可以用 下面的代码表示：Rijndael(State,CipherKey)KeyExpansion(CipherKey,ExpandedKey);AddRoundKey(State,ExpandedKey);for(i=1;iNr;i+)Round(State,ExpandedKey+Nb*i);FinalRound(State,ExpandedKey+Nb*Nr);AES解密算法（1）由于Rijndael算法的每一步都是可逆的，因此一圈的逆过程如下：InvRound(State,RoundKey)AddRoundKey(State,RoundKey);InvMixColumn(State);InvShiftRow(State);InvByteSub(State);AES解密算法（2）列混合变换的逆变换InvMixColumn：s(x)=c-1(x)s(x)对于0jNb，有循环左移的逆变换为循环右移相应的字节数AES解密算法（3）逆S-盒：先做逆仿射变换，然后求GF(28)上模m(x)的乘法逆元，也可以做成一个查找表（逆S-盒）。算法评价(1)所有的运算定义在有限域GF(28)上，算法执行时除了一个查表操作外，其它的运算都是简单的异或和移位，运行速度很快。在每一圈运算和密钥扩展中都应用了非线性操作，大大增强了抗差分和线性密码分析能力。轮运算：（1）所有操作都是可逆的；（2）每一步对一定攻击都有很强的抵抗能力，S-盒能抵抗差分和线性密码分析，行循环左移能抵抗截断差分密码分析及Square攻击，列混合达到了扩散的目的；（3）能在广泛的硬件平台上高效快速地执行；（4）每一步操作都易于描述。算法评价(2)密钥扩展：（1）非线性操作防止了仅仅由密钥的差分而导致每一圈子密钥的差分；（2）密钥扩展产生的效果使每一圈子密钥都不同；（3）有效地抵抗密钥相关分析及已知部分密钥的分析；（4）消除了每圈中以及圈与圈之间的对称性；（5）运行速度快，易于描述。抵抗常见攻击：研究表明，AES算法能够抵抗差分和线性密码分析、截断差分分析、Square攻击和相关密钥分析等攻击方法；没有弱密钥，因此对密钥的选择没有限制；最有效的攻击方法是密钥穷举攻击，而这对于二十年内的计算能力是不可能的。结论Rijndael 算法集高安全性、高性能、高效率、易实现及伸缩性强于一身，能应用于广泛的计算环境，密钥建立高效且灵活。很低的存储要求，使之在有空间限制的环境中执行。能抵抗各种常用的攻击方法。密钥和块长都设计得很灵活，在圈数选择方面能提供一定的灵活性。圈运算对指令级并行很具潜力。加密的逆运算有一些限制。在智能卡上解密过程相对加密过程难于执行，需要更多的代码和循环。对于软件，加密和解密需要不同的代码和查找表。对于用硬件来实施加密和解密，解密只能部分地重用加密过程用到的电路。第七章第七章 有限域理论有限域理论 域是一类有良好的运算性质，而且应用非常广泛的代数结构.我们在线性代数中所学的矩阵、向量空间以及线性变换等理论都是在常用的数域实数域、复数域，或有理数域上讨论的.这些数域的特点就是，可以在其中自由地进行加、减、乘、除(只要除数不为0)运算.在计算机、通信理论、编码学及密码学中，一类重要的域有限域发挥着重要作用.本章将对信息安全中常用的有限域理论进行较为深入地讨论.主要介绍有关域的基本理论,包括域的扩张的基本概念、有限域的性质与构造等.作为信息安全专业的本科生应较好地掌握有限域的性质、有限域中的运算以及有限域的构造.7.1域的基本性质7.2 有限域的基本概念与性质有限域的基本概念与性质设(F,+,)是域，如果F是有限集，那么称其是有限域.如前面提到的F2=(0，1,+,)就是一个有限域,而且是最小的有限域.又如整数模3剩余类环Z3是含有3个元素的有限域.把有限域的元素个数称为有限域的阶(order).如F2的阶为2,Z3的阶为3.7.3 最小多项式与本原多项式最小多项式与本原多项式
