4 高级加密标准

现代密码学概论7/29/202610:56AM1主讲人：潘森杉第4讲高级加密标准代换置换网络（SPN）例：l=m=Nr=4,十六进制表示：0000—0,…,1111—Fz0123456789ABCDEF

s

E4D12FB83A6C5907z12345678910111213141516

p15913261014371115481216从32比特密钥K=(K1,…,K32)开始，对轮数r=1,…5定义Kr是由K4r-3开始16个比特组成。如K=00111010100101001101011000111111，则K1=0011101010010100,K2=1010100101001101,K3,K4,K5设明文x=0010011010110111加密过程：w0=0010011010110111K1=0011101010010101u1=0001110000100011(1C23)→(45D1)v1=0100010111010001w1=0010111000000111……最后得到密文y=1011110011010110高级加密标准(AES)AES概述1997.01.02，美国国家标准和技术协会(NIST)宣布征集一个新的对称密钥分组密码作为取代DES的新的加密标准1997.09.12，正式公开征集AES，规定要求一个加密算法公开、强度相当于3重DES，必须至少支持128bit的分组长度；可选择128、192、256比特的密钥长度，强度相当于3重DES，应该比3重DES更高效1998.08.20，公布了15个AES候选算法，征求公众评论1999.04.15，第一轮截至，选出了5个候选算法，分别为MARS,RC6,Rijndael,Serpent和Twofish.2000.10.02，宣布选中Rijndael来建议作为AES，该算法由两个比利时密码学家Daemen和Rijmen共同设计。511/10/1510:57一个小故事：国际数据加密标准(IDEA),来学嘉和JamesMassey于1990年公布的第一版(PES推荐加密标准ProposedEncrytionStandard),1991年，Biham和Shamir演示了差分密码分析攻击后，增加了强度(IPES,ImprovedPES),1992年更名为IDEA，曾一度被认为是最好最安全的分组密码算法(Schneier)，若不是专利和商业许可证的障碍，甚至可能替换DES……1998年8月12日，在首届AES会议上指定了15个候选算法。1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，NIST宣布了获胜者—Rijndael算法（比利时的Daemen和Rijmen），2001年11月出版了最终标准FIPSPUB197。Rijndael密码简介Rijndael是具有分组长度和密钥长度均可变的分组密码。以128bit情形介绍其工作原理711/10/1510:571.128bit的消息被分成16个字节(byte)，每字节8个bit,记为：2.128bit的密钥被分成16个字节(byte)，每字节8个bit,记为：811/10/1510:573.内部结构表示成一个4×4矩阵：911/10/1510:574.多轮迭代(128bit时是10轮)State是轮消息矩阵，同时为输入和输出，RoundKey是轮密钥矩阵，由输入密钥通过密钥表导出。一轮的完成将导致State的元素改变值，加密时第一轮的State输入就是明文消息矩阵，最后一轮的输出State就是密文消息矩阵。AES算法执行过程明文x，将状态State初始化为x,并进行AddRoundKey操作：即RoundKey与State异或对前Nr-1轮中每一轮依次对State:进行SubBytes(用S盒)；(字节代换)进行ShiftRows；(行移位)进行MixColumns；(列混合)进行AddRoundKey；(轮密钥加)第Nr轮依次进行：SubBytes；ShiftRows；AddRoundKey将State定义为密文y.S-Box637C777BF26B6FC53001672BFED7AB76CA82C97DFA5947F0ADD4A2AF9CA472C0B7FD9326363FF7CC34A5E5F171D8311504C723C31896059A071280E2EB27B27509832C1A1B6E5AA0523BD6B329E32F8453D100ED20FCB15B6ACBBE394A4C58CFD0EFAAFB434D338545F9027F503C9FA851A3408F929D38F5BCB6DA2110FFF3D2CD0C13EC5F974417C4A77E3D645D197360814FDC222A908846EED814DE5E0BDBE0323A0A4906245CC2D3AC629195E479E7C8376D8DD54EA96C56F4EA657AAE08BA78252E1CA6B4C6E8DD741F4BBD8B8A703EB5664803F60E613557B986C11D9EE1F8981169D98E949B1E87E9CE5528DF8CA1890DBFE6426841992D0FB064BB16十六进制数(EA)16所对应的行为14，列为10(从0开始)，S盒中在此位置的是(87)16，则(EA)16被替换为(87)16。而在解密过程中，(87)16对应的8行7列值为(EA)16。实际上，同样的数据经过S盒变换后再经过逆S盒变换，即可得到原始的数据，所以字节代替和逆字节代替是一个互逆的过程。(S-Box)⁻¹5C096AD53036A538BF40A39E81F3D7FB7CE339829B2FFF87348E4344C4DEE9CB547B9432A6C2233DEE4C950B42FAC34E082EA16628D924B2765BA2496D8BD12572F8F66486689816D4A45CCC5D65B6926C704850FDEDB9DA5E154657A78D9D8490D8AB008CBCD30AF7E45805B8B34506D02C1E8FCA3F0F02C1AFBD0301138A6B3A9111414F67DCEA97F2CFCEF0B4E67396AC7422E7AD3585E2F937E81C75DF6E47F11A711D29C5896FB7620EAA18BE1BFC563E4BC6D279209ADBC0FE78CD5AF41FDDA8338807C731B11210592780EC5F60517FA919B54A0D2DE57A9F93C99CEFA0E03B4DAE2AF5B0C8EBBB3C83539961172B047EBA77D626E169146355210C7DS盒的比较①S盒变换是DES的唯一的非线性变换，是DES安全的关键。②AES使用16个相同的S盒，DES使用8个不相同的S盒。③AES的S盒有8位输入8位输出，DES的S盒有6位输入4位输出。ShiftRow(State)行移位变换

ShiftRow(State)行移位变换作用于S盒的输出，对状态数组的每一行循环左移不同的字节。 若密钥为128位的情况，第0行保持不变，其他行内的字节循环左移，第1行移动1个字节，第2行移动2个字节，第3行移动3个字节。s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33ShiftRow(State)变换

s00s01s02s03s11s12s13s10s22s23s20s21s33s30s31s32ShiftRow(State)MixColumn(State)列混合变换

MixColumn(State)将状态数组上的每一列看成F28上的一个多项式，且与一个固定的多项式c(x)进行模M(x)＝x4＋1乘法，其中多项式c(x)＝{03}x3＋{01}x2＋{01}x＋{02}a00a01a02a03a10a11a12a13a20a21a22a23a30a31a32a33

MixColumn(State)变换

b00b01b02b03b10b11b12b13b20b21b22b23b30b31b32b33

c(x)有限域有限元素个数加法阿贝尔群加法的封闭性：如果a和b属于S，则a+b也属于S；加法结合律：对S中任意元素a，b，c有a+(b+c)=(a+b)+c；加法单位元：S中存在一个元素a，使得对于S中任意元素b，有a+b=b+a=b，通常记a为0；加法逆元：对于S中的任意元素a，S中一定存在一个元素-a，使得a+(-a)=(-a)+a=0；加法交换律：对于S中的任意元素a和b，使得a+b=b+a；非零元素的乘法阿贝尔群乘法对加法有分配律对于S中任意元素a，b，c，有a(b+c)=ab+ac，(a+b)c=ac+bc177/29/202610:56AM有限域定一个素数p，则元素个数为p的有限域GF(p)被定义为整数{0,1,…,p-1}的集合Zp，其运算为模p的算术运算例，Z2为素数阶有限域有限域中元素的个数称为“阶（order）”187/29/202610:56AM素数幂阶有限域

GF(23)以x3+x+1为模的多项式运算加法运算表：197/29/202610:56AM+00000101001110010111011101xx+1x2x2+1x2+xx2+x+1000001xx+1x2x2+1x2+xx2+x+1001110x+1xx2+1x2x2+x+1x2+x010xxx+101x2+xx2+x+1x2x2+1011x+1x+1x10x2+x+1x2+xx2+1x2100x2x2x2+1x2+xx2+x+101xx+1101x2+1x2+1x2x2+x+1x2+x10x+1x110x2+xx2+xx2+x+1x2x2+1xx+101111x2+x+1x2+x+1x2+xx2+1x2x+1x10素数幂阶有限域

GF(23)以x3+x+1为模的多项式运算×00000101001110010111011101xx+1x2x2+1x2+xx2+x+1000000000000001101xx+1x2x2+1x2+xx2+x+1010x0xx2x2+xx+11x2+x+1x2+1011x+10x+1x2+xx2+1x2+x+1x21x100x20x2x+1x2+x+1x2+xxx2+11101x2+10x2+11x2xx2+x+1x+1x2+x110x2+x0x2+xx2+x+11x2+1x+1xx2111x2+x+10x2+x+1x2+1x1x2+xx2x+1207/29/202610:56AM乘法法运算表： 令bj(x)＝c(x)

aj(x)（0≤j≤3，

表示模x4＋1乘法），由于xi

mod(x4＋1)＝xi

mod4，可以将其表示成矩阵乘法。MixColumn(State)变换矩阵相乘

02030101010203010101020303010102a0ja1ja2ja3j=b0jb1jb2jb3jAddRoundKey(State,RoundKey)与子密钥

AddRoundKey(State,ExpandedKey)只是简单的将密钥按位异或到一个状态上。AddRoundKey(State,ExpandedKey)变换

s00s01s02s03s10s11s12s13s20s21s22s23s30s31s32s33k00k01k02

k03k10k11k12k13k20k21k22k23k30k31k32k33b00b01b02b03b10b11b12b13b20b21b22b23b30b31b32b33XORSubByte是为了得到一个非线性的代换密码ShiftR