次课分组密码AES-Rijndael.ppt

一、分组密码概述 二、DES 三、分组密码运行模式 四、IDEA 五、AES,第三章 分组密码,5. 高级加密标准(AES),AES的起源 AES的设计原则 AES算法描述,1. AES的起源,1997年9月，NIST征集AES方案，以替代DES。 1999年8月，以下5个方案成为最终候选方案：MARS, RC6, Rijndael, Serpent, Twofish。 2000年10月，由比利时的Joan Daemen和Vincent Rijmen提出的算法最终胜出。（ Rijndael 读成Rain Doll。）,Rijndael的数学背景,(1) GF(28)的定义 假设一个字节b由b7b6b5b4b3b2b1b0组成，我们可以把这些bi想象成一个7次多项式的系数，而这些系数不是0就是1： b7 x7+ b6 x6+ b5 x5+ b4 x4+ b3 x3+ b2 x2+ b1 x + b0 例如，(57)16的二进制表示法为(0101,0111)2表示成多项式，则为： x6+ x4+ x2+ x + 1,不同的表示方法会影响到GF(28)上运算的复杂性。,(2) 加法 两个多项式的加法，则是定义为相同指数项的系数和再模余2，简单的说就是作EXOR运算(i.e., 1+1=0)。例如： (57)16+(83)16=(01010111)2+(10000011)2 = (11010100)2 = (D4)16 或是(x6+x4+x2+x+1) + (x7+x+1) = x7+x6+x4+x2 每个元素的加法逆元等于自己，所以加法和减法相同。,(3)乘法 在乘法里面，多项式相乘之后的结果很容易造成溢位的问题，解决溢位的方式是把相乘的结果，再模余一个不可分解的多项式m(x)。在Rijndael中，定义一个这样子的多项式为 m(x)=x8+x4+x3+x +1或是(11B)16 例如： (57)16(83)16 = ( x6+ x4+ x2+ x + 1) ( x7+ x + 1) = x13+ x11+ x9+ x8+ x7+x7+ x5+ x3+ x2+x+x6+ x4+ x2+ x + 1 = (x13+ x11+ x9+ x8+ x6+ x5+ x4+ x3+ 1) modulo (x8+ x4+ x3+ x + 1) = x7+ x6+ 1=(C1)16,乘法满足交换律、分配律，且有单位元01和乘法逆元。,100011011,x乘法-GF(28),定义为： xb(x)=b7 x8+ b6 x7+ b5 x6+ b4 x5+ b3 x4+ b2 x3+ b1 x2 + b0x (mod m(x) 分析： 当b7=0，求模结果不变。 当b7=1，乘积结果减去m(x)。 结论： x(十六进制数02)乘b(x)，可先对b(x)在字节内左移一位（最后一位补0）; 若b7=1，再与11B做逐比特异或。 该运算记为： b=xtime(a) 所以，x的幂乘运算可重复应用xtime来实现；任意常数乘法可通过对中间结果相加实现。,例如：57 13可按如下方式实现： 57 01=xtime(57)=57 57 02=xtime(57)=AE 57 04=xtime(AE)=47 57 08=xtime(47)=8E 57 10=xtime(8E)=07 57 13=57 (01 02 10)=FE,m(x)=x8+x4+x3+x +1或是(11B)16,系数在GF(28)上的多项式,4个字节构成的向量可以表示为系数在 GF(28)上的次数小于4的多项式。 例如：a(x)=a3x3+a2x2+a1x+a0，其中a3、a2、a1、a0分别表示1个字节（8bit，表示为16进制数） 多项式的加法就是对应系数相加。 即4字节向量的逐比特异或。 多项式乘法取模M(x)=x4+1 例如： a(x)=a3x3+a2x2+a1x+a0 b(x)=b3x3+b2x2+b1x+b0 c(x)=a(x)b(x)= c3x3+c2x2+c1x+c0,a(x)=a3x3+a2x2+a1x+a0 b(x)=b3x3+b2x2+b1x+b0 c(x)=a(x)b(x)= c3x3+c2x2+c1x+c0 所以 c0=a0b0a3b1 a2b2 a1b3 c1=a1b0a0b1 a3b2 a2b3 c2=a2b0a1b1 a0b2 a3b3 c3=a3b0a2b1 a1b2 a0b3 上述计算可表示为,取模M(x)=x4+1,2. AES的设计思想,能抵抗所有已知的攻击； 在各种平台上易于实现，速度快； 设计简单。,与Feistel结构的轮函数不同，Rijndael没有这种结构，其轮函数是由3个不同的可逆均匀变换组成的，称它们为3个“层”。,每一层都有它自己的功能： 线性混合层 确保多轮之上的高度扩散； 非线性层 将具有最优的“最坏情况非线性特性”的S盒并行使用； 密钥加层 单轮子密钥简单地异或到中间状态上，实现一次性掩盖。,Rijndael算法说明,1. 状态、种子密钥和轮数 2. 轮函数 3. 密钥编排 4. 加密算法 5. 加解密的相近程度及解密算法,表 1. 分组长度和密钥长度的不同取值,Rijndael是一个分组密码算法，其分组长度和密钥长度相互独立，都可以改变。,任意搭配,状态、种子密钥,状态（State）：密码运算的中间结果称为状态。 State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。 Nb=明文分组长度（bits） 32 Nb可以取的值为4，6，8，对应的分组长度为128， 192， 256 bits。 种子密钥的表示： Cipher Key类似地用一个4行的矩阵阵列来表示，列数记为Nk。 Nk=种子密钥长度（bits）32 Nk可以取的值为4，6，8，对应的密钥长度为128， 192， 256 bits。,Fig 3. 当Nb=6时的状态和Nk=4时的密钥布局,Nb = 6 Block Length = 192 bits,Nk = 4 Key Length = 128 bits,AES 算法的一般描述（128bit）,Rijndael Round的构成,ByteSubstitution,ShiftRow,MixColumn,+,Round Key,一般的轮变换(19),ByteSubstitution,ShiftRow,+,Round Key,最后一轮的轮变换(10),字节代换,行移位,列混合,密钥加,AES 算法加密部分的实现,明文分组和密钥的组织排列方式 (128bit),Fig 1. 以分组为128bits为例组成的阵列,在Rijndael中使用了许多字节层级的运算，而这些运算是以GF(28)为基础架构。 也有一些采用了4-byte的字组运算。,1个字节 （8比特）,Fig 2. 以明文分组（或密钥）为128bits、192bits 、256bits为例组成的阵列,Fig 4. 分组长度和密钥长度均为128 bits时的Rijndael加密算法框图(10轮),Data / Key Addition,Rnd 0,Rnd 1,Rnd 8,Final Rnd,Key Schedule,Cipher Text,Key,Plain Text,结尾轮跟前面各轮不同。,表 2. 轮数（Round）的不同取值,Nb,Nr,Nk,用伪代码表示的Rijndael轮变换,一般的轮变换 Round(State, RoundKey) ByteSubstitution(State); ShiftRow(State); MixColumn(State); AddRoundKey(State, RoundKey); ,结尾轮变换 FinalRound(State, RoundKey) ByteSubstituion(State); ShiftRow(State); AddRoundKey(State, RoundKey); ,字节代换 行移位 列混合 密钥加,ByteSubstitution(字节代换),ByteSubstitution是一个非线性的字节替代，独立地对状态的每个字节进行运算。代换表（S-box）是可逆的。它由以下两个变换合成得到。 1. 将字节在有限域GF( )上求乘法逆元，00映射到它自身。 2. 对字节在GF(2)上进行下面的仿射变换：,字节x与给定的矩阵相乘，其结果再加上固定向量值63（二进制表示）。,Fig 6. ByteSubstitution 该变换可以用一个256字节的表来实现,取逆 仿射变换,S-box,Rijndael的S-box,ShiftRow(行移位),行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。 第0行不移动；第1行循环移位C1字节；第2行循环移位C2字节；第3行循环移位C3字节。 偏移量C1、C2、C3与分组长度Nb有关，如下表所示：,128 192 256,Fig 7. ShiftRow（128bit，Nb=4）,循环左移1字节,循环左移2字节,循环左移3字节,MixColumn(列混合),将状态的列看作是有限域GF( )上的多项式a(x)，与多项式 相乘(模 )。列混合运算也可以写为矩阵乘法。 令b(x) = c(x) a(x)，写成矩阵形式为：,b0 02 03 01 01 a0 b1 = 01 02 03 01 a1 b2 01 01 02 03 a2 b3 03 01 01 02 a3,系数是十六进制的,Fig 8. MixColumn 这一运算作用在每一列上, C(X),2.4 AddRoundKey(轮密钥加),将轮密钥与状态按比特异或。 轮密钥是通过Key Schedule过程从密码密钥中得到的，轮密钥长度等于分组长度。,A3,3 K3,3 B3,3 (mod 2),Fig 7. Rijndael加密及解密的标准结构 Block , Key Length = 128 bits,Plaintext(128 bits),ByteSubstitution,MixColumn,Ciphertext(128 bits),K0,Ki,i=10,ShiftRow,for i=1 to 10,Ciphertext(128 bits),K10,InvMixCoumn,InvShiftRow,InvByteSubstitution,Ki,Plaintext(128 bits),i = 9,for i=9 to 0,加密,解密,用伪代码表示的Rijndael加密算法,Rijndael ( State, CipherKey ) KeyExpansion ( CipherKey, ExpandedKey ); AddRoundKey ( State, ExpandedKey ); For ( i=1; iRnd; i+ ) Round ( State, ExpandedKey + Nb*i ); FinalRound ( State, ExpandedKey + Nb*Rnd ); ,提前进行密钥扩展后的Rijndael加密算法描述,Rijndael ( State, ExpandedKey ) AddRoundKey ( State, ExpandedKey ); For ( i=1; iRnd; i+ ) Round ( State, ExpandedKey + Nb*i ); FinalRound ( State, ExpandedKey + Nb*Rnd ); ,AES 的密钥调度 密钥调度包括两个部分：密钥扩展和轮密钥选取。,轮密钥bit的总数分组长度（轮数Round1） 例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128(101)1408bits。 将种子密钥扩展成一个扩展密钥。 轮密钥从扩展密钥中取：第一个轮密钥由扩展密钥的第一个Nb个字(4/6/8字节)，第二个圈密钥由接下来的Nb个字(4字节)组成，以此类推。,密钥扩展(eg.128bit),+,+,+,先看K5、K6、K7的生成。,Byte Substitution,ShiftRow,+,Rcon,+,看K4的生成。,GF(28)中的循环常量,Wi-4,Wi-3,Wi-2,Wi-1,Wi,Byte Substituion,Byte Rotate,+,Rcons,+,Key expansion,4 = i 4 ( Rnd + 1 ),i mod 4 = 0,i mod 4 != 0,+,r(1)=1 r(i)=xi-1 i1,a,b,c,db,c,d,ae,f,g,he XOR r(i),f,g,h,轮密钥选取,轮密钥0 (128bit),轮密钥1,轮密钥2,AES的解密算法,解密算法与加密算法不同 每个阶段均可逆，因此易证解密函授的确可以恢复明文,AES 算法的设计原理,GF(28)中乘法使用的多项式是8次不可约多项式列表中的第一个多项式。 ByteSubstitution（称为S盒）在设计时考虑到抵抗差分密码分析、线性密码分析的要求，应满足以下条件：1. 可逆性； 2. 输入比特的线性组合与输出比特的组合之间的最大非平凡相关性的极小化； 3. 异或差分表中最大非平凡值的极小化； 4. GF(28)中代数表示的复杂性； 5. 描述的简单性。,满足前3条准则的S盒的构造方法已被给出，AES的作者从众多候选构造中选择将x映射到它的逆的S盒。该映射过于简单，为了抵抗插入攻击，加入仿射变换： b(x)=(x7 + x6 + x2 + x) + a(x)(x7 +