AES算法描述详解

1分组密码AES算法2本节主要内容•1AES候选算法产生过程•2Rijndael的数学基础和设计思想•3Rijndael的算法说明3Rijndael密码的设计力求满足以下3条标准：①抵抗所有已知的攻击。②在多个平台上速度快，编码紧凑。③设计简单。2.2Rijndael的设计思想4为实现宽轨迹策略，轮函数3个层中的每一层都有它自己的功能：线性混合层:确保多轮之上的高度扩散；非线性层:将具有最优的最坏情况非线性特性的S盒并行使用；密钥加层:单轮子密钥简单地异或到中间状态上，实现一次性掩盖。2.2Rijndael的设计思想5Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，各自可以独立地指定为128比特，192比特,256比特。3.Rijndael的算法说明61、AES的数据处理方式①字节②字③状态2、状态①加解密过程中的中间数据。②以字节为元素的矩阵，或二维数组。所有的操作都在状态上进行。状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nb，Nb等于分组长度除以32。3.1状态、种子密钥和轮数73.1状态、种子密钥和轮数141414141212141210rN4bN6bN8bN4kN6kN8kN2、状态③符号：Nb－明密文所含的数据字数。Nk－密钥所含的数据字数。Nr－迭代圈数。8算法的输入（包括最初的明文输入和中间过程的轮输入）以字节为单位一a00a10a20a30a01a11a21a31…的顺序放置到状态阵列中。种子密钥以字节为单位按k00k10k20k30k01k11k21k31…的顺序放置到种子密钥阵列中输出（包括中间过程的轮输出和最后的密文输出）也是以字节为单位按相同的顺序从状态阵列中取出3.1状态、种子密钥和轮数93.1状态、种子密钥和轮数AES各个参数10AES算法描述•见WORD图片•AES的算法结构不是Fesitel结构，它每一轮使用代换和混淆并行处理整个分组。因而扩散比DES算法更快。1112Rijndael的轮函数由4个不同的计算部件组成分别是：字节代换BS（ByteSub）,非线性层行移位SR（ShiftRow）,线性层列混合MC（MixColumn）,线性层密钥加ARK（AddRoundKey），线性层3.2轮函数13字节代换是非线性变换，独立地对状态的每个字节进行。代换表（即S-盒）3.2轮函数：字节代换（ByteSub)143.2轮函数：字节代换-S盒15①S盒变换是AES的唯一非线性变换，是AES安全的关键。②AES使用16个相同的S盒，DES使用8个不相同的S盒。③AES的S盒有8位输入,8位输出，DES的S盒有6位输入,4位输出。S盒(AES)S盒(DES)88643.2轮函数：字节代（ByteSub）16S-盒是可逆的，由以下两个变换的合成得到：①首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，'00'映射到自己。②其次，对字节做如下的仿射变换：0011223344556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx3.2轮函数：字节代（ByteSub）17S盒对状态的所有字节所做的变换记为：ByteSub(State)183.2轮函数：字节代换（ByteSub）举例说明S盒的来历第一步：‘83’的乘法逆元是‘80’第二步：按照上述公式做仿射变换，计算得‘EC’与DES的S盒相比更加使人信任193.2轮函数：字节代换（ByteSub）请同学验证‘04’的S盒输出？（‘F2’）第一步：求乘法逆元第二步：做仿射变换程序实现或计算验证200011223344556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx3.2轮函数：字节代换（ByteSub）注意：①S盒变换的第一步是把字节的值用它的乘法逆来代替，是一种非线性变换。②由于系数矩阵中每列都含有5个，这说明改变输入中的任意一位，将影响输出中的5位发生变化。③由于系数矩阵中每行都含有5个，这说明输出中的每一位，都与输入中的5位相关。21①行移位变换对状态的行进行循环移位。不同状态行的位移量不同。②第0行不移位，第1行移C1字节，第2行移C2字节，第3行移C3字节。③C1，C2，C3按表取值④行移位变换属于置换，本质在于把数据打乱重排⑤AES的行移位变换属于线性变换。3.2轮函数：行移位（ShiftRow）223.2轮函数：行移位（ShiftRow）23图3.20行移位示意图（Nb=6）3.2轮函数：行移位（ShiftRow）24例如当Nb=4时，具体的操作如下：3.2轮函数：行移位（ShiftRow）25①列混合变换把状态的列视为GF(28)上的多项式，乘以一个固定的多项式c(x)，并模x4+1:b(x)=c(x)a(x)modx4+1其中，c(x)=03x3+01x2+01x+02②列混合变换属于代替变换。③c(x)与x4+1互素，从而保证c(x)存在逆多项式d(x),而c(x)d(x)=1mod(x4+1)。只有逆多项式d(x)存在，才能正确进行解密。3.2轮函数：列混合（MixColumn）26设b(x)=c(x)a(x)，则3210321002010103030201010103020101010302aaaabbbb3.2轮函数：列混合（MixColumn）27图3.21列混合运算示意图3.2轮函数：列混合（MixColumn）28列混合运算29列混合运算30密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。状态说与轮密钥RoundKey的密钥加运算表示为AddRoundKey(State,RoundKey)3.2轮函数：密钥加（AddRoundKey）313.2轮函数：密钥加（AddRoundKey）32密钥编排指从种子密钥得到轮密钥的过程它由密钥扩展和轮密钥选取两部分组成其基本原则如下:（1）轮密钥的比特数等于分组长度乘以轮数加1；例如要将128比特的明文经过10轮的加密，则总共需要（10+1）*128=1408比特的密钥。（2）种子密钥被扩展成为扩展密钥；（3）轮密钥从扩展密钥中取，其中第轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。3.3密钥编排33(1)密钥扩展①密钥扩展产生扩展密钥。②用一个4字节字元素的一维数组W[Nb*(Nr+1)]表示扩展密钥。③数组中最开始的Nk个字为种子密钥。④其它的字由它前面的字经过递归处理后得到。⑤有Nk≤6和Nk6两种密钥扩展算法。3.3密钥编排34(1)密钥扩展⑴Nk≤6的密钥扩展①最前面的Nk个字是由种子密钥填充的。②之后的每一个字W[j]等于前面的字W[j-1]的与Nk个位置之前的字W[j-Nk]的异或。③而且对于Nk的整数倍的位置处的字，在异或之前，对W[j-1]的进行如下变换：;字节的循环移位RotByte-即当输入字为(a,b,c,d)时，输出字为(b,c,d,a);用S盒进行变换次位元组-;异或轮常数Rcon[i/Nk]3.3密钥编排353.3密钥编排36①当Nk≤6时，扩展算法KeyExpansion(byteKey[4*Nk],W[Nb*(Nr+1)]){for(i=0;iNk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);//扩展密钥的前面4个字由种子密钥组成for(i=Nk;iNb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=SubByte(RotByte(temp))^Rcon[i/Nk];//i是NK的整数倍是要特殊处理W[i]=W[i-Nk]^temp;}}举例:Nk=4,Nb=4,Nr=10373.3密钥编排异或轮常数Rcon[i/Nk]:Rcon[i/Nk]=(RC[i],’00’,’00’,’00’)RC[0]=‘01’RC[i]=2⊙RC[i-1]i12345678910RC[i]01020408102040801b36Rcon[i]01000000020000000400000008000000100000002000000040000000800000001b0000003600000038②当Nk6时，扩展算法KeyExpansion(byteKey[4*Nk],W[Nb*(Nr+1)]){for(i=0;iNk;i++)W[i]=(Key[4*i],Key[4*i+1],Key[4*i+2],Key[4*i+3]);//扩展密钥的前面4个字由种子密钥组成for(i=Nk;iNb*(Nr+1);i++){temp=W[i-1];if(i%Nk==0)temp=SubByte(RotByte(temp))^Rcon[i/Nk];//i是NK的整数倍是要特殊处理elseif(i%Nk==4)temp=SubByte(temp);//i是4的整数倍是要特殊处理W[i]=W[i-Nk]^temp;}}39(2)轮密钥选取轮密钥i（即第i个轮密钥）由轮密钥缓冲字W[Nb*i]到W[Nb*(i+1)]给出图3.23Nb=6且Nk=4时的密钥扩展与轮密钥选取3.3密钥编排4041Encryption(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);AddRoundKey(State,RoundKey)；}}注意:第一步和最后一步都用了圈密钥加，因为任何没有密钥参与的变换都是容易被攻破的。3.4加密算法42Decryption(State,CipherKey){Inv_KeyExpansion(CipherKey,Inv_RoundKey);AddRoundKey(State,Inv_RoundKey);For(i=1;iNr;i++)Inv_Round(State,Inv_RoundKey);{Inv_ShiftRow(State);Inv_ByteSub(State);AddRoundKey(State,Inv_RoundKey；Inv_MixColumn(State);}Inv_FinalRound(State,Inv_RoundKey){InvShiftRow(State);InvByteSub(State);AddRoundKey(State,Inv_RoundKey)；}}3.4解密算法43•算法可逆是对加密算法的基本要求。•AES的巧妙之处：虽然解密算法与加密算法不同，但是解密算法与加密算法的结构相同。•把加密算法的基本运变换成逆变换，便得到解密算法。AES的基本逆变换44•AES