五、分组密码-DES

1、分组密码分组密码主要内容 概述 分组密码的设计原则 分组密码常见的设计方法 数据加密标准DES概述设明文消息编码表示后的二元数字序列为M=x0,x1,xk,分组密码首先将M划分成长为m的块M=B0,B1,Bi,，其中，Bi=(xim,xim+1,xim+m-1)然后分别在密钥K的控制下加密成长度为n的块Ci =(yin,yin+1,yin+n-1)Ci=Ek(Bi)(1)若nm，则为有数据扩展数据扩展的分组密码；(2)若nm，则为有数据压缩数据压缩的分组密码；(3)若n=m，则为无数据扩展也无压缩无数据扩展也无压缩的分组密码。概述 数学模型Ek()为密钥为k时的加密函数，称Dk()解密函数概述

2、 DES加密算法的特点速度快、易于标准化、便于软硬件实现。通常是信息与网络安全中实现数据加密和认证的核心体制，有着广泛的应用。分组密码的设计原则分组密码的设计原则 针对安全性的设计原则 针对实现的设计原则分组密码的设计原则 针对安全性的设计原则（1）分组长度和密钥长度 当明文分组长度为n时，至多需要2n个明文-密文对就彻底破解了密码。同理，当密钥长度为n位时，对一个截获的密文，至多需要试验2n个密钥就破解了该密文。 因此从安全性角度考虑，明文分组长度和密钥明文分组长度和密钥长度尽可能大长度尽可能大。分组密码的设计原则 针对安全性的设计原则（2）扰乱原则 又称混淆（confusion）原则。所设

3、计的密码应使密钥、明文和密文之间的依赖关系相当复杂，掩盖明文和密文之间的关系，以至于这种依赖性对密码分析者来说无法利用。分组密码的设计原则 针对安全性的设计原则（3）扩散原则 所设计的密码应使得密钥的每一位影响密文的许多位以防止对密钥进行逐段破译，而且明文的每一位也应影响密文的许多位以便隐藏明文的统计特性。 小扰动的影响波及到全局 明文中的一位影响到密文的多位，增加密文与明文之间的复杂性 密文没有统计特性分组密码的设计原则 针对安全性的设计原则（4）密码体制必须能抵抗现有的所有攻击方法。分组密码的设计原则 针对实现的设计原则从安全性角度来说，用一个足够大的S-盒盒就能够提供较高的安全性，但这并

4、不利于计算机的软硬件实现，如由64比特明文到64比特密文可构成一个相当安全的加密算法，但是需要1020字节的存储空间来实现。因此，在计算机中灵活有效地实现是一个重要的设计原则。一般实现方式有两种：软件方式和硬件方式。硬件实现的优点是运算快，软件的优点是灵活、代价小。分组密码的设计原则 针对实现的设计原则(1)软件实现的设计原则：使用子块和简单的计算，在将分组划分子块时，一般将子块分为8、16、32比特等。另外，软件实现中按位置换是难于实现的，尽量避免。还有，密码运算应多使用标准处理器的基本指令，如加法、乘法和移位等，以使得提交的算法能在多种平台上运行。分组密码的设计原则 针对实现的设计原则(2

5、)硬件实现的设计原则：为了节约成本，减少硬件逻辑门的数量，一般将算法设计成加解密相似，即同样的器件又可加密也可解密，所在的区别只是密钥的使用方式不同。另外，尽量将密码设计成迭代型，通过使用较为简单的轮函数来达到足够的安全性。分组密码常见的设计方法分组密码常见的设计方法三种结构： S-P网络结构 Feistel（法伊斯特尔）结构 LM结构分组密码常见的设计方法 S-P网络 S-P网络的设计思想于1949年由Shannon提出，是构成现代分组密码的基础。 每一轮中，输入数据先作用于一个由子密钥控制的函数S，然后将所得结果再作用于一个置换P。S是由密钥控制的非线性变换非线性变换；P是与密钥无关的可逆

6、的线性变换线性变换。分组密码常见的设计方法 S-P网络S-也称为代替层代替层，主要起扰乱作用P-也称为置换层置换层，主要起扩散作用S-P网络是基于古典密码学的两个基本操作： 代替substitution(S-box，S盒) 置换permutation(P-box，P盒)S-P网络的一个典型应用。 Feistel分组密码的基本结构1.初始输入：2L位明文和初始密钥K2. 2L位明文分成等长两个部分L0和R03.加密过程分为n轮进行，其中第i轮的输入包括：第i-1轮的输出Li-1和Ri-1以及从初始密钥K产生的子密钥Ki。4.加密分成两步：第一步使用轮函数F对Ri-1和子密钥Ki进行变换，将结果与

7、Li-1进行异或，结果作为Ri。（代换过程代换过程）第二步将Ri-1直接作为Li。（置换过程置换过程）分组密码常见的设计方法分组密码常见的设计方法 Feistel（法伊斯特尔）结构第i轮加密过程如下：分组密码常见的设计方法进一步说明：（1）给定明文P=L0R0，运算r轮后加密完成，输出密文C=RrLr。（2）每一轮的运算为：Li=Ri-1，Ri=Li-1 F(Ri-1,Ki)F为轮函数，Ki是子密钥。（3）加密过程具有可逆性，因为：Ri-1=Li，Li-1=Ri F(Li,Ki)分组密码常见的设计方法 Feistel分组密码的解密过程因加密过程具有可逆性，所以Feistel分组密码的解密过程与

8、加密过程完成相同：解密过程将密文作为输入，再进行r论加密运算即得到明文，但是解密过程中使用子密钥的次序与加密过程相反。即第1轮使用Kr，第2轮使用Kr-1，第r轮使用K1。分组密码常见的设计方法 F函数的设计准则轮函数F是分组密码的核心，对消息序列进行混淆操作。1. F函数非线性：非线性程度越强，安全性越高2. 严格雪崩准则：当任何一个输入位i发生改变时，任何输出位j的值发生改变的概率为1/2.3. 独立准则：当任何一个输入位i发生改变时，输出位j和k的值独立地发生改变。分组密码常见的设计方法 Feistel结构的特点1. 分组大小：越大安全性越高，但速度下降，64bit较合理2. 密钥位数：

9、越大安全性越高，但速度下降，64bit广泛使用，但现在不够用。3. Feistel结构中算法至少需要两轮才能改变输入的每一位，因此Feistel型密码的扩散稍慢，要求轮数不少于16次4. 子密钥产生算法：算法越复杂，就越增加密码分析的难度5. 轮函数：函数越复杂，就越增加密码分析的难度6. 能够快速软件实现，包括加密和解密算法7. 易于分析算法的保密强度以及扩展方法分组密码常见的设计方法总结： Feistel（法伊斯特尔）结构的基本思想 （1）交替使用“代替”和“置换” （2）混乱和扩散概念的应用分组密码常见的设计方法 LM结构Xuejia Lai和James Massey提出将明文P分成等长

10、的两个部分L0和R0。第i轮的运算规则：T=F(Li-1 Ri-1，Ki)；Li=Li-1 T；Ri=Ri-1 T。分组密码常见的设计方法 LM结构 特点：MA结构采用的数学运算较多，软件实现的效率将不是太高，但是对算法的分析变得困难。数据加密标准DES历史1972年，美国国家标准局(NBS)制定计划对标准的密码算法进行开发，来规范密码技术应用的混乱局面，用于保护计算机和通信。要求： 算法能够被测试和验证 不同设备间可以互相操作 实现成本低1973年5月15日，NBS在联邦纪事上公布消息公开征集加密算法，提出相关要求：（1）算法具有较高的安全性，安全性仅依赖于密钥，不依赖于算法（2）算法完全确

11、定，易于理解（3）算法对任何用户没有区别，适用于各种用途（4）实现算法的电子器件必须很经济（5）算法必须能够验证、出口历史历史起初，由于公众对密码知识的缺乏，虽响应激烈，但提交的方案并不理想。1974年8月27日，NBS再次发表征集公告，IBM提交良好算法。算法由Host Feistel 1971年设计，是对Luciffer密码算法的改进。1975年3月17日，NBS在联邦纪事上公布算法的细节，随后发表通知，征求公众的评论。1975年11月23日，这一算法被采纳为联邦标准，尽管受到强烈的批评和指责。历史标准的正式文本FIPS PUB48(DES)在1977年1月15日公布。其他文件 FIPS

12、PUB81(DES工作方式) FIPS PUB74(DES实现和使用指南) FIPS PUB112(DES口令加密) FIPS PUB113(DES计算机数据鉴别)相继于80年代初公布。历史1981年，美国国家标准研究所（ANST）批准DES作为私营部门的数据加密标准，称为DEA，有关文件： ANSI X3.92(DEA) ANSI X3.106(DEA工作方式) ANSI X3.105(网络加密标准)等相继公布。 总体结构分组长度为64位循环次数为16密钥长度为64位（包括8位奇偶校验位） 总体描述(1)初始置换IP，将64为明文分成两个部分。IP只进行一次。(2)之后进行16轮加密运算，称

13、为函数函数f(3)最后进行末尾置换IP-1，为初始置换的逆置换。 总体描述：函数函数f的运算包括四个部分(1)首先进行密钥序列移位，从移位后的56位密钥序列中选出48位；(2)其次通过扩展置换将输入序列的32位的右半部分扩展成48位，之后与48位的轮密钥进行异或(3)第三步通过8个S-盒将异或运算后获得的48位序列替代成一个32位的序列(4)最后对32位的序列应用P-盒进行置换得到f的32位输出序列。将函数f的输出与输入序列的左半部分进行异或的结果作为新一轮输入序列的右半部分，且输入序列的右半部分作为左半部分。上述过程重复16轮。假设Bi是第i轮计算结果，Li和Ri分别是Bi的左半部分和右半部

14、分，Ki是密钥，f函数为函数为代代换、置换、异或等换、置换、异或等运算的函数运算的函数。加密的具体过程为：Li=Ri-1Ri=Li-1 f(Ri-1,Ki)第i轮的具体过程详细操作过程(1)初始置换IP（Initial Permutation）初始置换如表1所示。58 50 42 34 26 18 10260 52 44 36 28 20 12462 54 46 38 30 22 14664 56 48 40 32 24 16857 49 41 33 25 179159 51 43 35 27 19 11361 53 45 37 29 21 13563 55 47 39 31 23 157详细

15、操作过程(2)密钥置换初始密钥大小为8个字节，共64位，每个字节的第8位为校验位，实际为56位。首先对密钥进行如下置换操作。57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124详细操作过程(2)密钥置换之后，从置换后的密钥中产生子密钥：1.循环左移：先将56位分成长度都是28位的两部分，再根据加密轮数，两部分密钥分别循环左移1位或2位，如下表：轮数12345678位数11222222轮数910111213141516位数1222222157

16、494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124详细操作过程(2)密钥置换2.压缩置换（Compression Permutation）：从56位密钥中选出48位作为当前加密的轮密钥。表格中数字为56位密钥中的位数，表格的位置为48位当前密钥的位置。如原密钥中第33位是当前密钥的35位，原密钥的18位在当前密钥中不出现。1417112415328156211023191242681672720132415231374755304051453

17、34844493956345346425036293249413325179158504234261810259514335271911360524436575547393123157625446383022146615345372921135282012463详细操作过程子密钥生成过程子密钥生成过程子密钥产生过程中，由于每一次进行压缩置换之前都包含一个循环移位操作，因此产生每一个子密钥时，使用了不同的初始密钥子集。初始密钥的所有位在子密钥中出现的次数并不完全相同，每一位大约会被14个子密钥使用详细操作过程(3)扩展变换（Expansion Permutation, E-盒）将64位输入序列的

18、右半部分Ri从32位扩展到48位。不仅改变了32位输入序列中的次序，而且重复了某些位。3212345456789891011121312131415161716171819202120212223242524252627282928293031321详细操作过程(3)扩展变换（Expansion Permutation, E-盒）三个基本目的：1. 产生一个与轮密钥长度相同的48位序列，实现与论密钥的异或运算2. 将32位扩展成48位，使得在接下来的替代运算中进行压缩，从而达到更好的安全性3. 由于输入序列的每一位将影响到两个替换，体现出良好的“雪崩效应”详细操作过程(4)S-盒替代48位轮密

19、钥与扩展后的分组序列进行异或运算，得到48位的结果序列，接下来应用S-盒对该序列进行替代运算 。每个S-盒对应6位输入，得到相应4位输出。8个S-盒各不相同。详细操作过程(4)S-盒替代S-盒1如下：每个S-盒对应一个4行、16列的表，表中的每个项都是16进制的数，相应的对应一个4位的序列。通过S-盒的6个位输入确定S-盒中输出序列所在的行和列。假定将S-盒的6位输入标记为b1、b2、b3、b4、b5、b6，则b1b6组成一个二进制数，对应03的十进制数字，该数表示S-盒的行数。 b2b3b4b5构成一个015之间的十进制数，对应S-盒的列数。根据行和列确定输入项。S-盒为非线性运算，提供了更

20、好的安全性。1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613详细操作过程(4)S-盒替代例如：假设对应第1个S-盒的输入序列为110011。第1位和最后一位组合构成11，对应十进制3，对应S-盒的第3行。中间4位为1001，对应十进制9，对应S-盒的第9列。S-盒第3行第9列对应的十六进制数是11，对应二进制1011。即输入110011，输出1011。14413121511831061259070157414213110612119538411481362111512

21、97310501512824917511314100613详细操作过程(4)S-盒替代S-盒的设计是关键步骤，其他运算都是线性的，而S-盒的运算是非线性的，比其他的任何操作都能提供更好的安全性。详细操作过程(5)P-盒置换（P-boxes Permutation）经S-盒代替运算后的32位输出依照P-盒进行置换，如下：表中数字为输入序列的位，表格的位置为输出序列的位置。1672021291228171152326518311028241432273919133062211425详细操作过程(5)P-盒置换（ P-boxes Permutation ）将P-盒置换的结果与该轮输入的64位分组的左

22、半部分进行异或运算后，得到本轮加密输出序列的右半部分，本轮加密输入序列的右半部分直接输出，作为本轮加密输出序列的左半部分，相应得到64位的输出序列。详细操作过程(6)逆初始置换（末尾置换）初始置换的逆过程(IP-1)。 末尾置换IP-1如下： 初始置换IP如下：4081816562464323974715552363313864614542262303754513532161293644412522060283534311511959273424210501858263314194917572558504234261810260524436282012462544638302214664564

23、840322416857494133251791595143352719113615345372921135635547393123157详细操作过程(6)逆初始置换（末尾置换）初始置换IP和对应的逆初始置换IP-1操作的目的：IP置换将原来明文的检验位变成IP输出的一个字节；打乱原来输入的ASCII码字划分的关系；可使算法同时用于加密和解密；更容易地将明文和密文数据以字节大小放入DES芯片中。详细操作过程(7)DES解密DES算法经过精心选择各种操作而获得一个非常好的性质：加密和解密可使用相同的算法，即解密过程将密文作为输入序列进行相应的DES加密，与加密过程不同之处是解密过程使用的轮密钥与

24、加密过程使用的次序相反。解密过程产生各轮子密钥的算法与加密过程生成轮密钥的算法相同，不同的是解密过程进行循环右移操作。例1 已知明文m=computer，密钥k=program，相应的ASCII表示为m=01100011 01101111 01101101 01110000 01110101 01110100 01100101 01110010k=01110000 01110010 01101111 01100111 01110010 01100001 01101101k只有56位，不包括8位的奇偶校验位。例1m经过IP置换得到L0=11111111 10111000 01110110 010

25、10111R0=00000000 11111111 00000110 10000011密钥k经过置换后得到C0=11101100 10011001 00011011 1011D0=10110100 01011000 10001110 0110循环左移一位，得到48位的子密钥k1：k1 =00111101 10001111 11001101 00110100 00111111 01001000例1 R0经过扩展变换得到的48为序列为10000000 00010111 1111111010000000 11010100 00000110结果再和k1进行异或运算，得到的结果为10111101 100

26、11000 0011001110110111 11101011 01111110将得到的结果分成8组：101111 011001 100000 110011101101 111110 101101 001110例1通过8个S-盒得到32序列为01110110 00110100 00100110 10100001对S-盒的输出序列进行P-置换，得到01000100 00100000 10011110 10011111经过以上操作，得到经过第1轮加密的结果序列为00000000 11111111 00000110 1000001110111011 10011000 11101000 1100100

27、0以上加密过程进行16轮，得到最终密文为01011000 10101000 01000001 1011100001101001 11111110 10101110 00110011总结：DES的加密结果可以看做是明文m和密钥k之间的一种复杂函数，即使是对明文和密钥的微小改变，产生的密文序列都将会发生很大的变化。DES运用了置换、替代、代数等多种密码技术，算法结构紧凑，条理清楚，而且加密和解密算法类似，便于工程实现。DES的出现是密码学史上的一个创举，具有划时代的意义，在此之前任何设计者对于密码算法的细节都是严格保密的，而DES公开发表后由任何人进行研究和分析，DES的安全性完全依赖于所用的密钥

28、。DES的分析DES的分析1.DES的雪崩效应雪崩效应定义为：明文或密钥的一点小的变动应该使密文发生一个大的变化。右边实例中明文改变1bit，密钥不变。DES的分析1.DES的雪崩效应右边实例中密钥改变1bit，明文不变。DES的分析2.S-盒的设计准则问题涉及美国国家安全局（NSA）， NSA修改了IBM最初设计的S-盒，虽然仍然满足最初的S-盒设计原则。人们怀疑NSA在S-盒中嵌入陷门，使得NSA借助于这个陷门及56位的短密钥可以解密。DES的分析2.S-盒的设计准则在1990年以前，S-盒的设计准则一直没有公布，直到差分密码分析方法发表后才公布，公布的S-盒设计准则为如下几个：P1:S-

29、盒的每一行是整数0,15的一个置换P2:没有一个S-盒是输入的线性或仿射函数P3:改变S-盒的一个输入比特至少要引起两个输出比特的改变P4:如果固定输入的最左边和最右边的2个比特，变换中间4个比特（S-盒只有6个输入），每个可能的4比特输出只能得到一次（S-盒只有4个输出）P5:如果两个输入仅中间2个比特不同，则输出至少有2个比特不同DES的分析2.S-盒的设计准则P6:对于任何一个S-盒，如果两个输入的前两不同，而最后两位相同，两个输出必须不同。P7:对任何一个S-盒，如果固定一个输入比特保持不变，而其他5比特输入变换，观察一个固定输出比特的值，使这个输出比特为D的输入的数目与使这个输出比特

30、位I的输入的数目总数接近相等。P8:在有相同且非零的差分的32对输入中，至多有8对具有相同的输出差分。DES的分析3.56位有效密钥太短在IBM最初向NSA提交的方案当中，密钥的长度为112位，但在DES成为标准时，被消减到56位。56位密钥确实太短： 分布式穷举攻击1997年1月28日，美国RSA数据安全公司在互联网上开展一项竞赛，悬赏1万美元来破解一段DES密文。科罗拉多州的程序员R. Verser设计了一个通过互联网分段运行的密钥搜索程序，组织了一个称为DESCHALL的搜索行动，成千上万的志愿者加入到计划中。DES的分析3.56位有效密钥太短(1)1997年6月17日晚上，美国盐湖城的

31、M.Sanders成功找到密钥解除明文，历时96天，仅搜索24.6%的密钥空间。竞赛公布后的140天。(2)专用搜索机：1998年7月，美国电子前沿基金会（Electronic Frontier Foundation, EFF）宣布，他们用一台价值25万美元的计算机改装成专用设备，56小时就破译了DES。(3)1999年1月，RSA数据安全会议期间，EFF用22小时15分钟破解DES的一个密钥。更加直接地说明了56位密钥太短，宣布DES的终结。DES的分析4.弱密钥和半弱密钥如果对于初始密钥，所产生的子密钥都是一样，这样的密钥称为弱密钥。初始密钥被分两部分，每部分都单独做移位，如果密钥的每一个

32、部分都是0或1，则每一圈的子密钥都相同，则存在4个弱密钥：0000000 00000000000000 FFFFFFF FFFFFFF 0000000 FFFFFFF FFFFFFF弱密钥的存在使得DES在遭受选择明文攻击时的搜索量减半DES的分析4.弱密钥和半弱密钥若给定密钥k，相应的16个子密钥只有两种，且每种都出现8次，称为半弱密钥。至少有12个半弱密钥，组成6对。半半弱密钥：有些密钥只产生4种密钥，每种出现4次，称为半半弱密钥，共48个。01 FE 01 FE 01 FE 01 FEFE 01 FE 01 FE 01 FE 011F E0 1F E0 1F E0 1F E0E0 1F

33、E0 1F E0 1F E0 1F01 E0 01 E0 01 E0 01 E0E0 01 E0 01 E0 01 E0 011F FE 1F FE 1F FE 1F FEFE 1F FE 1F FE 1F FE 1F01 1F 01 1F 01 1F 01 1F1F 01 1F 01 1F 01 1F 01E0 FE E0 FE E0 FE E0 FEFE E0 FE E0 FE E0 FE e0DES的分析4.弱密钥和半弱密钥弱密钥和半弱密钥以及半半弱密钥的数量与密钥总量相比很少，随机选中的概率可以忽略不计，另外，在产生密钥时，可以人为进行检查进行过滤。DES的分析5.互补对称性由DES中函数f的结构可知再考虑DES的结构，有称为互补对称性。由于互补对称性，穷举攻击时仅需试验所有256个密钥的一半。iiiiKRfKRf,11 MDESMDESKKDES的攻击 攻击方法1. 穷举攻击（1）尝试所有的可能情况（2）字典攻击：明密文对编成字典，尝试字典中所有