密码学03－分组密码体制.ppt

《密码学03－分组密码体制.ppt》由会员分享，可在线阅读，更多相关《密码学03－分组密码体制.ppt（156页珍藏版）》请在三一文库上搜索。

1、本科生学位课：现代密码学,第三章 分组密码体制,主讲教师：董庆宽 研究方向：密码学与信息安全 Email ： 个人主页：http:/ 分组密码概述 3.2 数据加密标准DES 3.3 差分密码分析和线性密码分析 3.4 分组密码的运行模式 3.5 IDEA 3.6 AESRijndael,本章提要,3/155,3.1 分组密码概述,分组密码(Block Cipher) ： 将明文消息分组，逐组加密；对称密码算法，属于代换密码 将明文消息编码表示后的数字序列x0,x1,xi,划分成长为n的组x=(x0,x1,xn-1) 各组（长为n的矢量）分别在密钥k=(k0,k1,kt-1)控制下变换成输出序

2、列y=(y0,y1,ym-1)（长为m的矢量） 其加密函数E：VnKVm，Vn和Vm分别是n维和m维矢量空间，K为密钥空间，如图所示。,4/155,与流密码不同之处： (1)分组加密。在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。 (2)无记忆性。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为m的数字序列的代换密码。 算法的输入长度和输出长度 通常取m=n (用于加密) 若mn，则为有数据扩展的分组密码(用于认证) 若mn，则为有数据压缩的分组密码(用于认证) 在二元情况下

3、，明文x和密文y均为二元数字序列 它们的每个分量xi，yjGF(2)。 本章将主要讨论二元情况。也是当前分组密码研究的主流。,5/155,分组密码的作用 加密(适合软硬件实现) 构成其它密码功能的基本模块 1. 构造伪随机数生成器。用于产生性能良好的随机数 适合产生少量随机数 2. 构造流密码。 速度比移位寄存器慢得多，但软件实现方便 采用适当的分组链接模式(CFB或OFB)可实现 3. 消息认证和数据完整性保护 通过用于构造消息认证码(MAC)和杂凑函数等来实现,6/155,分组密码算法设计的研究发展概况 （一）古典密码学阶段 1）算法保密，出现了代换和置换的方法 2）产生了乘积密码的思想

4、指顺序地执行两个或多个基本密码系统，使最后结果的密码强度高于每个基本密码系统的强度，多轮加密(3.1.3节1段) 3）基尔霍夫准则：早在1883年荷兰密码学家A.Kerckhoffs就在其军事密码学中提出如下密码设计准则： a. 密码系统应该是计算安全的； b. 密钥由通信双方事先约定好，并根据一定协议进行更换； c. 密码系统应该易于使用； d. 密码系统应该精确而有效； e. 除了密钥，密码系统的所有细节都为对手所知。 还提出了一次一密的密码设计方法，直接促进了流密码研究,7/155,（二）近代密码学阶段(1949-1975)-分组密码的酝酿期 1）计算机技术的发展，开始了密码学面向商业应

5、用的设计 2）Shannon的工作：1949年，C. E. Shannon(19162002 )建立了保密系统的通信理论，50-70年代Shannon的工作起着决定性的指导作用。对密码理论的贡献主要有两点 其一，用信息论刻划了密码学中的安全性 提出了语言冗余度和“熵”的概念，论述了破译密码需要多少信息量 定义了“计算安全”与“无条件安全”；前者与破译密码的价值有效性和时间有效性有关。后者是指无论破译者有多少密文也无法解出对应的明文，即使解出也无法验证结果的正确性(One-Time-Pad) 其二，提出了密码设计中的扩散准则和混淆准则 在一次一密无法实现的情况下，这两个准则是设计密码体制的最基本

6、准则。Shannon的思想今天仍然是设计密码体制极其重要的指导准则 3）Smith关于Lucifer密码的设计研究 4）Feistel网络的密码结构,8/155,（三）现代密码学阶段走向成熟 1）密码学由专门应用转向商业应用 美国数据加密标准DES(Data Encryption Standard)是最重大的标志。它和公钥密码体制的提出是现代密码学的开端和密码学发展史上两个重要里程碑。是近代密码学研究重要结晶。 2）DES加密算法的公开及其在商用数据加密中的广泛应用，激发了人们对密码学的研究兴趣，密码学进入了一个新的时期 3）现代分组密码研究的发展 早期的研究基本上是围绕DES进行的，推出了一

7、些类似的算法，例如：LOKI，FEAL，GOST等。,9/155,20世纪90年代，对DES算法研究更加深入，特别是差分密码分析（differential cryptanalysis）和线性密码分析（linear cryptanalysis）的提出，迫使人们不得不研究新的密码结构。 IDEA密码打破了DES类密码的垄断局面 随后出现了SQUARE、SHARK、SAFER-64等采用了结构非常清晰的代替置换（SP）网络 从理论上给出了最大差分特征概率和最佳线性逼近优势的界，证明了密码对差分密码分析和线性密码分析的安全性。 19972000年间美国高级加密标准AES的征集活动以及20002003年

8、间欧洲NESSIE计划的实施，再次掀起了密码研究的新高潮 15个AES候选算法和24个NESSIE终选算法反映了当前密码设计的水平，也可以说是近几年研究成果的一个汇总。,10/155,目前对分组密码安全的讨论主要包括差分密码分析、线性密码分析和强力攻击等 1990年Biham和Shamir差分密码分析方法以及1993年Mitsuru Matsui线性密码分析方法的问世，都极大丰富了密码学的内容 从理论上讲，差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法，而从实际上说，强力攻击是攻击分组密码最可靠的方法,11/155,一些现行的标准 3DES、IDEA、AES 3GPP标准中的算法

9、KASUMI 我国国家标准SMS4，现在改为了SM4 NESSIE分组密码算法(欧) MISTY1，过渡型的标准，日本人Eisaku Takeda设计 Camellia，普通型的标准（AES算法也可用），日本人Shiho Moriai与Mitsuru Matsui设计 SHACAL2，高级型的标准，法国人Helena Handschuh和David Naccache设计 瑞典人Jakob Jonsson和美国人Burt Kaliski设计的RC6,12/155,分组密码领域有待继续研究和完善的理论和实际问题 如何设计可证明安全的密码算法； 如何加强现有算法及其工作模式的安全性； 如何测试密码算

10、法的安全性； 如何设计安全的密码组件，例如S-盒、扩散层及密钥扩散算法等。 分组密码没有非常有效的数学分析工具 需要实践检验 参考资料：对称密码学胡予濮，张玉清等著 密码分析学冯登国,13/155,分组密码算法设计满足的要求： I. 应用要求： 实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有： 运行速度 存储量（程序的长度、数据分组长度、高速缓存大小） 实现平台（硬件、软件、芯片）、 运行模式等限制条件。 这些都需要与安全性要求之间进行适当的折中选择,14/155,II. 算法设计的要求 分组密码设计在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地

11、选出一个置换，用来对当前输入的明文数字组进行加密变换 分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。(需要明文相关性和统计特性) DES、IDEA、FEAL和LOKI等分组密码都采用n=64，在生日攻击下用232组密文成功概率为1/2，同时要求23264b=215MB32GB存贮，故现在采用穷举攻击已经可以实现(时间存储攻击) 生日攻击：(请参考6.2.3节)随机选取n个人，至少有两个人生日相同的概率为 P1365364(365n+1)/365n 当n64时 p0.997近乎于1,15/155, 密钥量要足够大（即置换子集中的元素足够多） 尽可能消除弱密钥

12、并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。 DES采用56比特密钥，太短 IDEA采用128比特密钥，够用 据估计，在今后3040年内采用80比特密钥是足够安全的 由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击 如差分攻击和线性攻击 有高的非线性阶数，实现复杂的密码变换 使对手破译时除了用穷举法外，无其它捷径可循,16/155, 加密和解密运算简单，易于软件和硬件高速实现 使用子块和简单的运算 如将分组n划分为子段，每段长为8、16或者32 在软件实现时，应选用简单的运算，使作用于子段上的密码运算

13、易于以标准处理器的基本运算，如加、乘、移位等实现，避免用软件难于实现的逐比特置换 加解密算法应具有相似性 为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。 设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现 多轮迭代是乘积密码的特例，指同一基本加密结构的多次执行 若以一个简单函数f，进行多次迭代，就称其为迭代密码。 每次迭代称作一轮(Round)。相应函数f 称作轮函数。 每一轮输出都是前一轮输出的函数，即y(i)=fy(i-1), k(i)，其中k(i)是第i轮迭代用的子密钥，由秘密密钥k通过密钥生

14、成算法产生。,17/155, 数据扩展 一般无数据扩展，在采用同态置换和随机化加密技术时(如公钥密码)可引入数据扩展。 差错传播尽可能地小 1比特的传输错误不会影响更多比特的正确解密 要实现上述几点要求并不容易。 首先，要在理论上研究有效而可靠的设计方法 而后进行严格的安全性检验 并且要易于实现。 下面介绍设计分组密码时的一些常用方法。,18/155,3.1.1代换,为使加密运算可逆(使解密运算可行)，明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的 称明文分组到密文分组的可逆变换为代换(与古典密码中代换表同义) 即代换是输入集A到输出集合A上的双射变换： fk：AA 式中，k是

15、控制输入变量，即密钥 密钥k决定了使用哪一个代换，是代换函数的一部分 双射条件保证在给定k下可从密文惟一恢复明文,19/155,代换的数量 如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值，则不同可逆变换的个数有2n!个。 2n的全排列 代换网络： 实现代换fk的运算网络称作代换网络(由多个运算组件组成)。 常利用一些简单的基本代换，通过组合，实现较复杂的、元素个数较多的代换集，即代换网络,20/155,代换结构 下图表示n=4的代换密码的一般结构 4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特

16、表示。 共有24！=16!种可能置换,21/155,加密映射和解密映射也可由代换表来定义，这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。 表3-1 对应的代换表,加密代换,解密代换,22/155,这种代换结构中分组长度不宜太小 如果分组长度太小，如n=4，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。 这个弱点不是代换结构固有的，只是因为分组长度太小。如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。,23/155,分组长度也不宜很大 会使代换表规模呈几何级数增加 仍以表3.1为例，该表定义了

17、n=4时从明文到密文的一个可逆映射，其中第2列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。 从本质上来说，第2列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥总量需要64比特。 一般地，对n比特的代换结构，密钥的大小是n2n比特。如对64比特的分组，密钥大小应是64264=2701021比特，因此难以处理。如果可用一个函数来描述映射，则密钥量就是n,24/155,解决办法 实际中常将分组n分成较小的段，如可选n=rn0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。 一般n0都不太大，称每个子代换为代换盒，简称为

18、S盒。例如DES中将输入为48比特、输出为32比特的代换用8个S盒来实现，每个S盒的输入端数仅为6比特，输出端数仅为4比特。,25/155,3.1.2 扩散和混淆,扩散和混淆(diffusion and confusion)是由Shannon提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析 如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合,26/155,在Shannon称之为理想密码的密码系统中，密文的所有统计特性

19、都与所使用的密钥独立。下图的代换密码就是这样的一个密码系统，然而它是不实用的。,27/155,扩散：就是将明文的统计特性散布到密文中去 实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。 例如对英文消息M=m1m2m3的加密操作 yn=chr(i=1,2,kord(mn+i)(mod 26) 其中ord(mi)是求字母mi对应的序号，chr(i)是求序号i对应的字母 这时明文的统计特性将被散布到密文中 因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。 在二元分组密码中，可对数据重复执行某个置换，再对这一

20、置换作用于一函数(代换)，可获得扩散。(置换+代换) 扩散的目的是使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥,28/155,混淆 是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。 即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥。 使用复杂的代换算法可以得到预期的混淆效果 简单的线性代换函数得到的混淆效果则不够理想 扩散和混淆成功地实现分组密码本质属性，因而成为设计现代分组密码的基础,29/155,3.1.3 Feistel 密码结构,分组密码的结构： 是指实现密码算法的组件结构 主要基于两种运算：代换（ Subst

21、itution ）和置换（ Permutation ） 实际中，需要加密，也需要解密，因此，有两种方法： 1. 定义每个代换、置换的逆，这样增加了复杂度 2. 定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密，比如S-P网络 S-P网络：是代换-置换乘积密码的现代形式 在Shannon 1949 的文章中，介绍了代换-置换网络(SPN)的思想 ，这种思想形成了现代密码的基础 SPN主要基于代换和置换两种最基本的密码运算 Shannon 把这两种运算组合在一起，将一些 S-boxes 由 P-box 连接，这种变换叫做混合变换（mixing transformations）

22、,30/155,目前分组密码所采用的整体结构可分为： S-P网络（最基本的结构） SP的网络结构非常清晰，例如Safer+、Serpent、IDEA、AES等 S一般被称为混淆层，主要起混淆作用 P一般被称为扩散层，主要起扩散作用。 在明确S和P的某些密码指标后，设计者能估计SP型密码抵抗差分密码分析和线性密码分析的能力。SP网络和Feistel网络相比，可以得到更快速的扩散，但是SP密码的加/解密通常不相似。 Feistel结构（一种特殊的S-P结构） 例如DES、CAST-256、DEAL、DFC、E2等 加解密相似是Feistel型密码的一个实现优点，但它在密码的扩散似乎有些慢，例如需要

23、两轮才能改变输入的每一个比特。不过在实用中似乎并不会形成较大的影响，只要轮数足够多。 其他密码结构（例如Frog和HPC）。采用非正规结构，安全性不好,31/155,Feistel结构 早期，很多成功的分组密码的结构从本质上说都是基于一个称为Feistel网络的结构 Feistel提出利用乘积密码可获得简单代换密码 乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生结果 乘积密码的特例是迭代密码，采用多个相同的基本密码系统顺次执行(如Feistel结构) Feistel还提出了实现代换和置换的方法。 其思想实际上是Shannon提出的利用乘积密码实现混淆

24、和扩散思想的具体应用。,32/155,1Feistel 加密结构 Horst Feistel, （working at IBM Thomas J Watson Research Labs ） 70年代初设计了这样的结构，我们现在叫做Feistel cipher 图3-3是Feistel网络示意图,33/155,Feistel结构描述 1)加密算法的输入：是分组长为2w的明文和一个密钥K 2)将每组明文分成左右两半L0和R0 3)在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。 4)其第i 轮迭代的输入为前一轮输出的函数： LiRi1 RiLi1F(Ri1, Ki) 其中Ki是第i 轮用

25、的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。,34/155,Festal网络中的代换： Festal网络中每轮结构都相同，每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。 每轮的轮函数的结构都相同，但以不同的子密钥Ki作为参数。 可起到混淆等效果 Festal网络中的置换： 代换过程完成后，再交换左、右两半数据，这一过程称为置换。 这种结构是Shannon提出的代换置换网络（substitution-permutation network, SPN）的特有形式。 在代换中也包含一些置换运算 可起到扩散等效果,35/155,Fei

26、stel网络的实现与以下参数和特性有关： 分组大小 分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比特。128比特 密钥大小 密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。 轮数 单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。 子密钥产生算法 该算法的复杂性越大，则密码分析的困难性就越大。 轮函数 轮函数的复杂性越大，密码分析的困难性也越大。,36/155,在设计Feistel网络时，还有以下两个方面需要考虑 快速的软件实现 在很多情况中，算法是被镶嵌在

27、应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键 算法容易分析 如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法,37/155,2. Feistel 解密结构 Feistel解密过程本质上和加密过程是一样的 算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，最后一轮使用K1。 这一特性保证了解密和加密可采用同一算法。,38/155,加密过程由上而下，每轮的左右两半用LEi和REi表示 解密过程由下而上，每轮的左右两半用LDi和RDi表示 图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值

28、的对应关系 即加密过程第i轮的输出是LEiREi（表示链接） 解密过程第17-i轮相应的输入是RDiLDi,39/155,加密过程的最后一轮执行完后，两半输出再经交换，因此密文是RE16LE16。解密过程取以上密文作为同一算法的输入，即第1轮输入是RE16LE16，等于加密过程第16轮两半输出交换后的结果 下面证明解密过程第1轮的输出等于加密过程第16轮输入左右两半交换值 在加密过程中： LE16RE15 RE16LE15F(RE15, K16) 在解密过程中 LD1RD0=LE16RE15 RD1LD0F(RD0, K16)RE16F(RE15, K16) LE15F(RE15, K16)

29、F(RE15, K16)LE15 所以解密过程第1轮的输出为LE15RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。,40/155,一般地，加密过程的第i轮有 LEiREi-1 REiLEi-1F(REi-1, Ki) 因此 REi-1LEi LEi-1REi F(REi-1, Ki)=REi F(LEi, Ki) 以上两式描述了加密过程中第i轮的输入与第i轮输出的函数关系，由此关系可得图3-4右边显示的LDi和RDi的取值关系。 最后可以看到，解密过程第16轮的输出是RE0LE0，左右两半再经一次交换后即得最初的明文。,41/155,3.2

30、数据加密标准DES,DES的产生 美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准 于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的（通常称为DES 密码算法要求）主要为以下四点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）计算安全性：具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）基尔霍夫准则：DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）可行性：实现经济，运行有效，并且适用于多种完全不同的应用

31、。,42/155,DES在1975年3月17日首次被公布在联邦记录中 经过大量的公开讨论后，1977年1月15日美国政府颁布：采纳美国IBM公司设计的方案作为非机密数据的正式数据加密标准（DES, Data Encryption Standard），DES被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。 它的分组长度为64比特，密钥长度为56比特，是早期的称作Lucifer密码的一种发展和修改。 DES是迄今为止世界上最为广泛使用和流行的一种分组密码算法 1996年以后，主要是3DES,43/155,3.2.1 DES描述,图4.5是DES加密算法的框图 其中明

32、文分组长为64比特，密钥长为56比特。图的左边是明文的处理过程，有3个阶段:,2)具有相同功能的16轮变换，每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并被交换次序。 3)最后再经过一个逆初始置换IP-1（为IP的逆）从而产生64比特的密文,1)初始置换IP，用于重排明文分组的64比特数据。,除初始置换和逆初始置换外，DES的结构和图4.3 所示的Feistel密码结构完全相同,44/155,图4.5的右边是使用56比特密钥的方法 密钥首先通过一个置换函数PC-1， 然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，

33、所以产生的每轮子密钥不相同。,45/155,1.初始置换 DES的初始置换见表3-2 表3-2(a)和3-2(b)分别给出了初始置换和逆初始置换的定义，这两个置换是互逆的。 64比特的明文M以8比特为一行，共8行以行顺序编号 由表3-2(a)得X=IP(M)，由3-2(b)得 YIP-1(X)=IP-1(IP(M)=M,46/155,和Feistel网络一样，每轮变换可由以下公式表示： LiRi1 RiLi1F(Ri1, Ki) 其中轮密钥Ki为48比特。,2.轮结构 图3-6是DES加密算法的轮结构 首先看图的左半部分。将64比特的轮输入分成各为32比特的左、右两半，分别记为L和R。,47/

34、155,函数F(R,K)的计算过程 如图4.7所示。轮输入的右半部分R为32比特，R首先被扩展成48比特，扩展过程由表3.2(c)定义，其中将R的16个比特各重复一次。,扩展后的48比特再与子密钥Ki异或，然后再通过一个S盒，产生32比特的输出。 该输出再经过一个由表3.2(d)定义的置换P，产生的结果即为函数F(R,K)的输出。,48/155,扩展置换E和置换P,49/155,代换盒 S (substitution box) F中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为4比特，其变换关系由表3.3定义，每个S盒给出了4个代换（由一个表的4行给出）。（见42页表3.3） DES

35、的S盒定义,50/155,对每个盒Si 其6比特输入中，第1个和第6个比特形成一个2位二进制数，用来选择Si的4个代换中的一个 中间4位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。 例如，S1 的输入为011001 则行选为01（即第1行），列选为1100（即第12列） 行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。 S盒的每一行定义了一个可逆代换 图3-2（在3.1.1节）表示S1第0行所定义的代换,51/155,3密钥的产生 实际上，K是长度为64的位串，其中56位是密钥，8位是奇偶校验位（为了检错），在密

36、钥编排的计算中，这些校验位可略去。 DES密钥编排算法结构图 LSi表示循环左移一个或两个位置 其中i为1，2，9，16循环移1位，其余循环移两位,52/155,过程： (1) 给定64位的密钥K，放弃奇偶校验位（8，16，64）形成连续的56比特的密钥 (2)再看图3-5和图3-6，输入算法的56比特密钥首先经过一个置换运算PC-1，该置换由表3.4(a)给出 然后将置换后的56比特分为各为28比特的左、右两半，分别记为C0和D0 (3)在第i 轮分别对Ci-1和Di-1进行左循环移位，所移位数由表3.4(c)给出。 移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择2 PC-2的输入

37、。通过置换选择2产生的48比特的Ki，即为本轮的子密钥，作为函数F(Ri-1,Ki)的输入。其中置换选择2由表3.4(b)定义,53/155,DES密钥编排中使用的表（表3-4） (a) 置换选择1 (b) 置换选择2 (c) 左循环移位位数 注. 对i=1,2,16， Ci、Di分别是由C0、D0左旋若干比特而得到，至i=16，刚好左旋了28比特位而回复当初，即:C16=C0，D16=D0。,54/155,4解密 和Feistel密码一样，DES的解密和加密算法使用同一算法，但子密钥使用的顺序相反 解密时子密钥的产生有两种方式： 1）是先由K产生16个子密钥，再逆续使用 2）反序产生。(在前

38、面讲过的密钥扩展过程中若改LSi为 则也就可以依次产生这逆序的子密钥。,55/155,DES加密实例 取16进制明文X：0123456789ABCDEF 密钥K为： 133457799BBCDFF1 去掉奇偶校验位以二进制形式表示的密钥是 00010010011010010101101111001001101101111011011111111000 应用初始置换IP，我们得到： L0=11001100000000001100110011111111 R0=11110000101010101111000010101010 然后进行16轮加密。最后对L16, R16 使用IP-1得到密文：85E

39、813540F0AB405,56/155,DES的设计特色： 在DES算法中，函数是最基本的关键环节， 其中 用S-盒实现小块的非线性变换，达到混乱目的； 用置换P实现大块的非线性变换，达到扩散目的。 置换P的设计使每层S-盒的4bit输出进入到下一层的4个不同S-盒 每个S-盒的输入由分属上一层中4个不同S-盒的输出构成。 DES的核心是S盒，除此之外的计算是属线性的。 S盒作为该密码体制的非线性组件对安全性至关重要。 S-盒的设计准则还没有完全公开。一些密码学家怀疑美国NSA(the National Security Agency)设计S-盒时隐藏了“陷门”，使得只有他们才知道破译算法，

40、但没有证据能表明这一点。,57/155,1976年，美国NSA披露了S-盒的下述几条设计原则： 每个S-盒的每一行是整数015的一个全排列； 每个S-盒的输出都不是其输入的线性或仿射函数； 改变任一S-盒任意1bit的输入，其输出至少有2bit发生变化； 对任一S-盒的任意6bit输入x，S(x)与S(x001100)至少有2bit不同； 对任一S-盒的任意6bit输入x，及, 0,1，都有S(x)S(x1100)； 对任一S-盒，当它的任一位输入保持不变，其它5位输入尽情变化时，所有诸4bit输出中，0与1的总数接近相等。 S盒的争论： 公众仍然不知道S盒的构造中是否还使用了进一步的设计准则

41、（有陷门？） 密钥长度是否足够？（已经证明密钥长度不够） 迭代的长度？（8、16、32？）,58/155,DES的安全性问题 完全依赖于所用的密钥，即算法是公开的。 1）取反特性： 对于明文组M，密文组C和主密钥K，若C=DESK(M)， 则 ，其中 、 和 ,分别为M，C和K的逐位取反。 证明： 置换本身的取反特性可以保持 (1)若以K为主密钥扩展的16个加密子密钥记为K1,K2,K16，则以 为主密钥扩展的16个加密子密钥为 (2)由 (1a) (1b)=ab，可得 =F(Ri-1,Ki) (3)由 b1a b= ，可得 ，由此得证。 由此DES在选择明文攻击时工作量会减少一半。攻击者破译

42、所使用的密钥，选取两个明密文对(M,C1)和( ,C2)，并对于可能密钥K计算出，DESK(M)=C，若C=C1或 C2，则说明密钥为K或 。 其中C2=,59/155,2）弱密钥与半弱密钥. 对合 大多数密码体制都有某些明显的“坏密钥”，对于K和K 若由K扩展出来的加密子密钥为：K1, K2, , K15, K16 而由K扩展出来的加密子密钥却是：K16, K15, , K2, K1 即有DESK-1=DESK ，则称K与K互为对合 在F256中的对合对： 在DES的主密钥扩展中，C0与D0各自独立地循环移位来产生加(解)密子密钥。 若C0与D0分别是00,11,10,01中任意一个的14次

43、重复，则因这样的C0与D0都对环移(无论左或右)偶数位具有自封闭性,60/155,若PC-1-1(C0D0)=K,则由K扩展出来的加密子密钥为： K1, K2, K2, K2, K2, K2, K2, K2, K1, K1, K1, K1, K1, K1, K1, K2 把C0与D0各自左环移一位得C1与D1，设PC-1-1 (C1D1)=K，则由K扩展出来的加密子密钥为： K2, K1, K1, K1, K1, K1, K1, K1, K2, K2, K2, K2, K2, K2, K2, K1 因此，由上述C0与D0导致的K与K互为对合；K中只有这些对合对 对于K，若K是自己的对合，则称K

44、为DES的一个弱密钥 若K存在异于自己的对合，则称K为DES的一个半弱密钥,61/155,显然，C0与D0分别是00,11,10,01中任意一个的14次重复的情况共有42=16种 其中C0与D0分别是00,11中任意一个的14次重复的情况(计22=4种)对应弱密钥； 剩下的(16-4=12种)对应半弱密钥。 弱密钥与半弱密钥直接引起的“危险”是在多重使用DES加密中，第二次加密有可能使第一次加密复原；另外，弱密钥与半弱密钥使得扩展出来的诸加密子密钥至多有两种差异，如此导致原本多轮迭代的复杂结构简化和容易分析。 所幸在总数256个可选密钥中，弱密钥与半弱密钥所占的比例极小，如果是随机选择，(半)

45、弱密钥出现的概率很小，因而其存在性并不会危及DES的安全。,62/155,3)密文与明文、密文与密钥的相关性. 人们的研究结果表明：DES的编码过程可使每个密文比特都是所有明文比特和所有密钥比特的复杂混合函数，而要达到这一要求至少需要DES的迭代：5轮。人们也用2-检验证明：DES迭代8轮以后，就可认为输出和输入不相关了。 4）密钥搜索机. 在对DES安全性的批评意见中，较一致的看法是DES的密钥太短！其长度56bit，致使密钥量仅为2561017，不能抵抗穷搜攻击，事实证明的确如此。 1997年1月28日，美国RSA数据安全公司在RSA安全年会上发布了一项“秘密密钥挑战”竞赛，分别悬赏100

46、0美金、5000美金和10000美金用于攻破不同长度的RC5密码算法，同时还悬赏10000美金破译密钥长度为56bit的DES。RSA公司发起这场挑战赛是为了调查在Internet上分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为56bit的DES算法的相对强度。,63/155,结果是：密钥长度为40bit和48bit的RC5算法被攻破；美国克罗拉多州的程序员Verser从1997年3月13日起用了96天的时间，在Internet上数万名志愿者的协同工作下，于1997年6月17日成功地找到了DES的密钥，获得了RSA公司颁发的10000美金的奖励。这一事件表明，依靠Internet

47、的分布式计算能力，用穷搜方法破译DES已成为可能。因此，随着计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度。 5）DES的攻击方法 目前攻击DES的主要方法有时间-空间权衡攻击、差分攻击、线性攻击和相关密钥攻击等方法，在这些攻击方法中，线性攻击方法是最有效的一种方法。本章将对差分和线性分析方法进行介绍,64/155,DES的评估 规定每隔5年由美国国家保密局（national security agency, NSA）作出评估，并重新批准它是否继续作为联邦加密标准。最近的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。 一些强力攻击的案例： 19

48、97年DESCHALL小组经过近4个月的努力，通过Internet搜索了31016个密钥，找出了DES的密钥，恢复出了明文。 1998年5月美国EFF(electronics frontier foundation)宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56 比特密钥的DES。 美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之为AES(advanced encryption standard) 的新加密标准。 尽管如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值。,65/155,3.2.2 二重DES,为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。 二重DES是多重使用DES时最简单的形式，如图4.8所示。其中明文为P，两个加密密钥为K1和K2 密文为：C=EK2(EK1P)， 解密时，以相反顺序使用两个密钥： P=DK1(DK2C) 二重DES所用密钥长度为112比特，强度极大地增加。,66/155,是否与单重DES等价？ 假设对任意两个密钥K