密码学第4章(全)

密码学Cryptology计算机学院黄玉划[e-mail]办公室：北门A12号楼11613675155711教学内容第1章引论第2章古典密码学第3章流密码算法与伪随机数产生器第4章分组密码算法第5章分组密码算法的工作模式第6章单向散列(Hash)函数第7章公钥密码算法与数字签名算法第8章认证与密钥交换协议第4章分组密码算法分组密码算法采用密钥将固定长度的明(密)文分组通过加(解)密算法加(解)密成相同长度的密(明)文分组。用分组密码易于构造伪随机数生成器、流密码、消息认证码(MAC)和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。现代对称密码的设计基础是：扩散和混淆。(依赖性)分组密码的特点是加密密钥和解密密钥相同。分组密码的安全性只依赖于密钥，加密算法和解密算法无需保密。第4章分组密码算法——Feistel网络(结构)分组密码设计主要采用两种结构：Feistel和SP网络。Feistel网络是一种代换网络，其输出的每比特密文都和输入的明文及密钥各比特有关。Feistel结构的思想实际上是山农提出的利用乘积密码实现混淆和扩散思想的具体应用。第4章分组密码算法——Feistel网络(续)•加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)•解密:Ri-1=Li;Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)第4章分组密码算法——S盒分组密码一般要采用S盒。对于一个好的S盒，其布尔函数应满足以下9个基本条件：1.平衡性(Balance)。2.严格雪崩准则(StrictAvalancheCriterion)。3.高阶SAC。4.非线性。5.线性结构。6.输出bit独立原则。当一个输入bit取补时，每二个输出bit之间的相关系数变为0。7.完备性。每个输出bit与每个输入bit相关。8.输入/输出差分分布.即差分的最大值尽量小。9.线性近似和抗线性攻击的能力。如果S盒的输出都是其输入的线性或仿射函数，则S盒不能实现较好的混淆。第4章分组密码算法4.1数据加密标准(DES算法)DES算法是美国的第一代分组密码算法标准，也是一个早期的国际标准。它只对小的分组进行标准的算术和逻辑运算，用软硬件实现都比较有效。简单地说，DES算法只不过是加密的两个基本技术——混乱和扩散的组合。其重复特性使得它可非常理想地用在一个专用芯片中。DES算法的出现是密码学史上的一个创举。4.1DES算法——流程输入64位比特明文IP置换表L0R0Li=Ri-1Ri=Li⊕f(Ri-1,Ki)（i=1,2,…16）迭代16次IP逆置换表输出64位比特密文加密方程：L0R0←IP(64位明文)Li←Ri-1Ri←Li-1(Ri-1,Ki)64位密文←IP-1(R16L16)解密方程：R16L16←IP(64位密文)Ri-1←LiLi-1←Ri(Li,Ki)64位明文←IP-1(L0R0)4.1DES算法——初始置换和逆初始置换4.1DES算法——函数f(R,K)的计算过程加密时R=Ri;解密时R=Li;4.1DES算法——扩展运算Ｅ(32位扩展到48位)扩展4.1DES算法——置换P(32位到32位)Ｓ盒的输出（32位）1672021291228171152326518311028241432273919133062211425置换P加密函数的结果（32位）4.1DES算法——S盒(48位压缩到32位)共8个S盒4.1DES算法——S盒(续)S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒84.1DES算法——S盒(续)每个S盒以6位作为输入，而以4位作为输出。假设输入为B=b1b2b3b4b5b6，则b2b3b4b5所代表的数是0到15之间的一个数，记为：k=b2b3b4b5；由b1b6所代表的数是0到3间的一个数，记为h=b1b6。在S的h行，k列找到一个数A，A在0到15之间，它可以用4位二进制表示，为A=a1a2a3a4，这就是S的输出。1234561626234521133911001110019bbbbbbbbSbbbb行：-盒子行列列：值：14=11004.1DES算法——S盒(续)DES中其它算法都是线性的，而S-盒运算则是非线性的,所以S-盒是算法的关键所在S-盒是许多密码算法的唯一非线性部件,因此,它的密码强度决定了整个算法的安全强度提供了密码算法所必须的混乱作用非线性度、差分均匀性、严格雪崩准则、可逆性、没有陷门4.1DES算法——子密钥的生成k1（56位）(48位)ki（56位）（48位）64位密钥置换选择1C0（28位）D0（28位）循环左移循环左移C1（28位）D1（28位）循环左移循环左移Ci（28位）Di（28位）置换选择2置换选择2密钥表的计算逻辑循环左移：1191211023211242122521326214272152821614.1DES算法(续)有趣的是，DES算法是由IBM公司设计的；当时的美国国家标准局(NSA)修改了S-盒设计，以确保IBM没有在算法中嵌入陷门，因为NSA没有理由相信IBM的研究成果，而他们不能绝对确定DES算法没有陷门，如果有陷门，将是他们失职，所以只好修改S-盒；而人们又怀疑NSA在DES算法中强加了弱点。4.1DES算法——设计原理重复交替使用S盒和置换运算P两种变换（confusion+diffusion)；使用Feistel方法。DES的半公开性：S盒的设计原理至今未公布，可能隐含有陷井（Hiddentrapdoors）有报道表明S盒在次序上、内容上是最优的。4.1DES算法——性能在代数结构上，DES算法不是一个群。在安全性方面，DES算法有一些弱密钥、半弱密钥和可能的弱密钥。特别地，DES算法具有互补性。定义EK(P)=C表示用密钥K把明文P加密成密文C，x*表示x的补，则EK*(P*)=C*。这可能DES算法是的一大弱点。DES算法的密钥长度比较短，只有56b。在现在看来，不能抗强力攻击(255次尝试)。另外，频谱测试表明DES算法是非随机的。差分密码分析表明，对DES算法，选择明文攻击比穷举攻击有效。差分密码分析法：247次尝试线性密码分析法：243次尝试(())kkpEEP12()()kkCEPEP4.1DES算法(续)在DES加密过程中，初始变换IP对加密的强度没有影响。DES和CAST算法的S盒为固定S盒，能够较好的防止差分攻击。RC-5采用可变S盒。对于可变S盒，当其输入输出规模很大时不仅能抵抗差分攻击而且能抵抗各种已知攻击。DES算法是一种对合函数加密算法。尽管双重DES不等价于使用一个56位密钥的单重DES，但有一种被称为中途相遇攻击的破译方法会对它构成威胁。分组密码的组合技术不一定能够增强分组密码的安全性。三重DES的有效密钥长度为112位。DES算法有四种工作模式：电子密码本模式、密码分组链接模式、密码反馈模式、输出反馈模式。4.1DES算法——CBC模式和OFB模式64位移位寄存器DESk选取最左边的t位(64位)(64位)(t位)(t位)(t位)xiyi图2X2DESkY2IV=Y0X1DESkY1XnDESkYn图1图1CBC的表达式：Y0＝IV，Yi=DESK(Xi⊕Yi-1),1≤i≤n图2OFB的表达式：Z0=IV,Zi=DESK(Zi-1),Yi=Xi⊕Zi,1≤i≤n4.1DES算法——CBC模式和OFB模式(续)特点：在OFB模式中，一个密文块Yi（或明文块Xi）的改变在解密（或加密）时只会引起相应的明文块Xi（或密文块Yi）的改变，不会引起其他密文块的改变。在CBC模式中，一个密文块Yi的改变在解密时时只会引起相应的相应的明文块Xi和Xi+1.的改变，不会引起其他明文块的改变。而一个明文块Xi的改变，在加密时将会相应的密文块Yi以及其后的所有密文块的改变。第4章分组密码算法4.2高级加密标准(AES算法)DES算法的安全强度越来越满足不了技术发展的需要。为此，美国NIST于1997年开始制定AES(高级加密标准)算法以满足新时代的信息安全需求。1999年，NIST宣布已从15个候选算法中选出5个较好的算法：MARS，RC6，Rijndael，Serpent，Twofish。2000年底，NIST最终确定采纳Rijndael算法作为AES算法。AES算法是由比利时的JoanDaemen和VincentRijmen设计的，经过全世界密码学者3年多的密集评估，被认为是安全的。由于评估过程公开，AES算法会有陷门的可能性很小。4.2AES(Rijndael)算法(续)该算法有3条设计准则：①抗所有已知的攻击；②在多个平台上快速简洁地实现；③设计简单。其分组长度为128位(Rijndael算法本身的分组长度可以是128、192或256位)，密钥长度可以是128、192或256位，分别记为AES-128、AES-192和AES-256。对于AES-128，轮数Rn=44，Nr=10；对于AES-192，Rn=52，Nr=12；对于AES-256，Rn=60，Nr=14。AES算法过程可分为轮密钥编排和加密过程两个独立的部分。明文Xr轮迭代密文Y子密钥K0Xi-1字节代替行移位列混合Ki-1XiAES算法框图一轮AES结构图4.2AES算法——流程4.2AES算法——加密过程的轮变换AES加密算法的分组长度通常为128位，当密钥长度为128位时，其轮变换数目为10次。把一个信息分组State分成四行x列的矩阵形式，一轮AES算法包含4种变换：1.字节代换SubBytes(State)。使用一个S盒πS对State进行非线性变换，其中πS是有限域{0，1}8的一个置换。SubWord(A0，A1，A2，A3)=(B0，B1，B2，B3)，其中Bi=SubBytes(Ai)。2.行移位变换ShiftRow(State)。分组长度为128或192b时，State下三行分别循环左移1、2、3字节。3.列混合变换MixColumn(State)=C*State是有限域GF(28)4上的一个线性变换。4.轮密钥加法变换AddRoundKey(State，RoundKey)。将由函数KeyExpansion(key)生成的轮密钥RoundKey中的一个字与State的每一个列向量进行异或运算。4.2AES算法——1.字节代换SubBytes(State)字节代换是非线性变换，独立地对状态的每个字节进行。代换表（即S-盒）是可逆的，由以下两个变换的合成得到：①首先，将字节看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。A*A-1mod(x8+x4+x3+x+1)=1②其次，对字节做如下页的（GF(2)上的，可逆的）仿射变换。SubBytes的逆变换由代换表的逆表做字节代换，可通过如下两步实现:首先进行仿射变换的逆变换，再求每一字节在GF(28)上逆元。4.2AES算法——1.字节代换SubBytes(续)0011223344556677100011111110001111111000110111100010111110000011111001001111101000111110yxyxyxyxyxyxyxyx4.2AES算法——2.行移位变换ShiftRow(State)行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。第0行不移动，第1行循环左移C1个字节，第2行循环左移C2个字节，第3行循环左移C3个字节。位移量C1、C2、C3的取值与Nb有关，见135页表