AES算法原理

AES算法原理及实现2015.4.20AES算法简介AES（TheAdvancedEncryptionStandard），又称Rijndael加密法，该演算法为比利时密码学家JoanDaemen和VincentRijmen所设计，结合两位作者的名字，以Rijdael命名。是美国联邦政府采用的一种分块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPSPUB197，并在2002年5月26日成为有效的标准。2006年，高级加密标准已然成为对称密钥加密中最流行的演算法之一。它被预期能成为人们公认的加密包括金融、电信和政府数字信息的方法。美国国家标准与技术研究所(NIST)在2002年5月26日建立了新的高级数据加密标准(AES)规范。AES是一个新的可以用于保护电子数据的加密算法。明确地说，AES是一个迭代的、对称密钥分组的密码，它可以使用128、192和256位密钥，并且用128位（16字节）分组加密和解密数据。与公共密钥密码使用密钥对不同，对称密钥密码使用相同的密钥加密和解密数据。通过分组密码返回的加密数据的位数与输入数据相同。迭代加密使用一个循环结构，在该循环中重复置换（permutations）和替换(substitutions）输入数据。AES算法描述AES算法是基于置换和代替的。置换是数据的重新排列，而代替是用一个单元数据替换另一个。AES使用了几种不同的技术来实现置换和替换,包括:字节代换(SubBytes),行循环移位(ShiftRows)，列混合(MixColumn)运算，密钥加(AddRoundKey)。表1-1AES的密钥长度和加密轮数列表密钥长度(32bit)(Nk)分组长度(Nb)加密轮数(Nr)AES-1284410AES–1926412AES-2568414图1-1AES的加密/解密流程图密文输出轮密钥加明文输入密钥扩展密钥第1轮第9轮第10轮第10轮第9轮第1轮ω[4,7]ω[36,39]ω[40,43]ω[0,3]字节代换行移位列混合列混合行移位字节代换字节代换轮密钥加轮密钥加行移位轮密钥加……密文输入明文输出轮密钥加逆字节代换逆列混合逆行移位逆字节代换逆字节代换逆行移位轮密钥加逆行移位逆列混合……轮密钥加轮密钥加1.字节代换(byteSub)字节代换是非线性变换，独立地岁状态的每个字节进行。代换表(即S-盒)是可逆的，由以下两个变换得到：首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，’00’映射到自己。其次，对字节做如下的(GF(2)上的，可逆的)仿射变换：y0y1y2y3y4y5y6y71000111111000111111000111111000111111000011111000011111000011111x0x1x2x3x4x5x6x711000110=x⊕字节代换状态矩阵按照下面的方式映射成为一个新的字节：把该字节的高4位作为行值，低4位作为列值，得到S盒或逆S盒的对应元素作为输出。例如输入字节0x12，取S盒的第0x01行盒0x02列，得到0xC9。字节代换(ByteSub)a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35b00b01b02b03b04b05b10B11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35S盒aijbij2.行移位(ShiftRow)在行循环移位变换中，状态阵列的后3行循环移位不同的偏移量。第0行不移动。第1行循环移位C1字节，第2行循环移位C2字节，第3行循环移位C3字节。偏移量C1、C2、C3与分组长度Nb有关，如下表所示：NbC1C2C3412361238134行移位示意图a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35a00a01a02a03a04a05a11a12a13a14a15a10a22a23a24a25a20a21a33a34a35a30a31a32左移0位左移1位左移2位左移3位3.列混合(MixColumn)列混合运算将状态(State)的列看作是有限域GF(28)上的多项式a(x)，与多项式c(x)=’03’x3+’01’x2+’01’x+’02’相乘(在模(x4＋1)下)。b(x)=c(x)xa(x)(modx4+1)b0b1b2b3=02030101010203010101020303010102a0a1a2a3图1-2列混合运算示意图a00a01a02a04a05a10a11a12a14a15a20a21a22a24a25a30a31a32a34a35a0jb00b01b03b04b05b10b11b13b14b15b20b21b23b24b25b30b31b33b34b35a1ja3ja2jb0jb1jb3jb2j☉c(x)4.密钥加密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。a00a01a02a03a04a05a10a11a12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00k01k02k03k04k05k10k11k12k13k14k15k20k21k22k23k24k25k30k31k32k33k34k35b00b01b02b03b04b05b10b11b12b13b14b15b20b21b22b23b24b25b30b31b32b33b34b35⊕=图1-3密钥加运算示意图AES的密钥调度密钥bit的总数=分组长度x(轮数Round+1)当分组长度为128bit且轮数为10时，轮密钥长度为:128x(10+1)=1408bit将初始密钥扩展成扩展密钥轮密钥从扩展密钥中取，第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，以此类推。密钥扩展ω[0]ω[1]ω[2]ω[3]k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33密钥扩展以128bit为例，对数组ω扩充40个新列，构成总共44列的扩展密钥数组。新列按照以下的方式递归产生：(1)如果i不是4的倍数，那么第i列由等式ω[i]=ω[i-4]⊕ω[i-1]确定；(2)如果i是4的倍数，那么第i列由等式ω[i]=ω[i-4]⊕T(ω[i-1])确定；ω[0]ω[1]ω[2]……ω[42]ω[43]ω[0]ω[1]ω[2]ω[3]AES密钥扩展图ω[4i]ω[4i-3]ω[4i-2]ω[4i-1]⊕ω[4i]ω[4i+1]ω[4i+2]ω[4i+3]T⊕⊕⊕密钥扩展函数T由三部分组成：字循环移位、字节代换和轮常量异或。(1)字循环移位：将1个字中的4个字节循环左移1个字节，即将输入字[b0,b1,b2,b3]变换为[b1,b2,b3,b0]。(2)字节代换：对字循环的结果使用S盒进行字节代换。(3)轮常量异或：将前两步的结果同轮常量Rcon[j]进行异或，其中j表示轮数。轮常量是一个字，使用轮常量是为了防止不同轮中产生的轮密钥的对称性或相似性。表1-9轮常量值表J12345Rcon[j]0100000002000000040000000800000010000000J678910Rcon[j]2000000040000000800000001B00000036000000表1–3S盒置换表0123456789ABCDEF0637C777BF26B6FC53001672BFED7AB761CA82C97DFA5947F0ADD4A2AF9CA472C02B7FD9326363FF7CC34A5E5F171D83115304C723C31896059A071280E2EB27B275409832C1A1B6E5AA0523BD6B329E32F84553D100ED20FCB15B6ACBBE394A4C58CF6D0EFAAFB434D338545F9027F503C9FA8751A3408F929D38F5BCB6DA2110FFF3D28CD0C13EC5F974417C4A77E3D645D1973960814FDC222A908846EEB814DE5E0BDBAE0323A0A4906245CC2D3AC6291951479BE7C8376D8DD54EA96C56F4EA657AAE08CBA78252E1CA6B4C6E8DD741F4BBD8B8AD703EB5664803F60E613557B986C11D9EEE1F8981169D98E949B1E87E9CE5528DFF8CA1890DBFE6426841992D0FB054BB16表1–4逆S盒置换表0123456789ABCDEF052096AD53036A538BF40A39E81F3D7FB17CE339829B2FFF87348E4344C4DEE9CB2547B9432A6C2233DEE4C950B42FAC34E3082EA16628D924B2765BA2496D8BD125472F8F66486689816D4A45CCC5D65B69256C704850FDEDB9DA5E154657A78D9D84690D8AB008CBCD30AF7E45805B8B345067D02C1E8FCA3F0F02C1AFBD0301138A6B83A9111414F67DCEA97F2CFCEF0B4E673996AC7422E7AD3585E2F937E81C75DF6EA47F11A711D29C5896FB7620EAA18BE1BBFC563E4BC6D279209ADBC0FE78CD5AF4C1FDDA8338807C731B11210592780EC5FD60517FA919B54A0D2DE57A9F93C99CEFEA0E03B4DAE2AF5B0C8EBBB3C83539961F172B047EBA77D626E169146355210C7D