《密码学分组密码》PPT课件

1、第三章 分组密码体制,分组密码概述 数据加密标准 差分密码分析与线性密码分析 分组密码的运行模式 其他分组密码体制,分组密码概述,分组密码因其实现速度较快，在许多密码系统中是一个重要的组成部分。分组密码与流密码在区别在于分组密码将明文的消息编码后划分成长度为n的组，在一个密钥的控制下变换成等长（m）的输出序列。一般情况下，nm。若mn，为由数据扩充的分组密码；若mn，为由数据压缩的分组密码,为了保证一个分组密码算法的有效性安全、易于实施。分组密码算法应满足以下要求： 分组n足够大，使得明文空间足够大，防止明文穷举攻击法奏效。 密钥量足够大，尽可能消除弱密钥，使得所有密钥都一样好，防止对密钥的穷

2、举攻击成功。 由密钥确定的算法要足够的复杂，充分实现明文与密钥的扩散和混乱，使得算法能抵抗各种攻击。 加密和解密运算简单，易于软件和硬件的高速实现。 数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引进数据扩展。 差错传播尽可能小,设计分组密码常用的一些方法介绍 1. 代换 将n长的明文分组变换为唯一n长密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。 若分组长度为n，则明文空间M有 个向量，代换的就是给出在该空间上的一个可逆变换 。 例如：取n4,2. 扩散和混淆 扩散和混淆是Shannon提出的设计密码系统的两个基本的方法，目的是抵抗敌手对密码系统的统计分析

3、。 扩散：就是将明文的统计特性散布到密文中，实现的方法是使明文的每一位影响密文的多位，等价于说密文的每一位均受明文中的多位影响。目的是使明文和密文的统计关系变得尽可能的复杂，使敌手无法得到明文（密文）。 方法：对数据重复执行某个置换，再对该置换作用一函数，可获得扩散。 混淆：是使密文的统计特性和密钥取值的关系变得尽可能的复杂，使敌手无法获得密钥。 方法：使用复杂的代换算法，可获得好的混淆结果，而使用简单的线性代换得到的混淆效果不太理想,Feistel密码结构 很多分组密码的结构本质上都是基于一个Feistel密码结构。 Feistel密码结构的思想是利用乘积密码实现扩散和混淆。乘积密码是顺序的

4、执行两个或多个密码系统，使得最后结构的密码强度高于每个基本密码系统产生的结果,加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki) 解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki,Feistel结构定义,Feistel结构图,数据加密标准,DES描述 二重DES 两个密钥的三重DES 三个密钥的三重DES,64比特明文,DES算法加密,64比特密文,64比特的密钥 （内含8比特校验位,DES示意图,DES的描述 DES利用56比特长度的密钥K来加密长度为64位的明文，得到长度为64位的密文,DES加解密过程 令i表示迭代次数，表示逐位

5、模2求和，f为加密函数。DES的加密和解密过程表示如下。 加密过程： 解密过程,DES 加密过程,IP,m,R0,L0,IP,m,L16,R16,DES 解密过程,初始置换IP和初始逆置换IP1,注：数字表示比特位,逆初始置换 (IP-1) 是简单的比特移位,逆初始置换,IP-1,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

6、57 58 59 60 61 62 63 64,IP IP-1 = IP-1 IP = I,58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7,40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37

7、 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25,IP-1,IP,L i-1(32比特,R i-1(32比特,第 i 次迭代,R i-1(32比特,Ri-1,1 48比特 48,Ri-1,Ki )的功能,选择扩展运算 E,1 32比特 32,E的作用： 将32比特的输入膨胀为48比特,则输出为：B = t32 t1 t2 t32 t1,选择扩展运算的功能,设输入为：T = t1 t2 t3 t32,1 2 3 4 5 6

8、7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32,32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 23 24 25 26 27 28 25 28 29 30 31 32 1,E的作用： 将32比特的输入膨胀为48比特,选择扩展运算,Si,设 Si 盒的 6 个输入端为 b1 b2 b3 b4 b5 b6，在 Si 表中找出 b1 b6 行，b2 b3 b4 b5

9、 列的元素：Si ( b1 b6, b2 b3 b4 b5 ) 便是 Si 盒的输出,选择压缩函数Si的功能,E 输出的 48 比特与子密钥异或后，顺序分成 8 组，每组 6 比特，分别通过 S1，S2，,S8 盒后又缩为 32 比特，即每盒输入为 6比特，输出为 4 比特,b1 b6,b2 b3 b4 b5,二进制输出,选择压缩函数Si的功能,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,0 1 2 3,14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1

10、14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13,输入到选择函数S1,1 0 1 1 0 0,b1 b6 1 0,0 0 1 0,选择函数S1的输出,S-Box-i,S-Box-ii,子密钥的产生,置换选择1和置换选择2,DES解密,和Feistel密码一样，DES的解密和加密使用同一算法，只是子密钥的使用顺序相反。 子密钥是独立产生的，可以独立存储,DES中的M、K、C,明文 m 和密钥 K 的变化对密文的影响： DES的加密结果，每一比特都是明文m和密钥K的每一比特的复杂函数，即明文m和密钥k每改

11、变一个比特都将对密文产生剧烈影响。（明文m和密钥k任意改变一比特，其结果大致有将近一半的位产生了变化。,关于DES的若干问题,1. DES的坏密钥问题： (1)弱密钥： 定义：当密钥K所产生的子密钥满足：K1 = K2 = = K16 则有：DESk ( m ) = DESk -1 ( m ) ， 或：DESk ( DESk ( m ) ) = m 这样的密钥K称为弱密钥。 产生条件：当密钥K满足以下条件时产生弱密钥， k57= k49= k41= = k9= k1=0 或1 k63= k55= k47= = k15= k7=0 或1 举例：共有4种，如：0101010101010101,2)

12、 半弱密钥： 定义：当存在子密钥K和K，使得： DESk ( m ) = DESk -1 ( m ) 或 DESk ( DESk ( m ) ) = m 则K和K成对构成半弱密钥。 产生条件：C0=101010 D0=000 或111 或101010 或010101 C0=010101 D0=000 或111 或101010 或010101,2. DES的安全性： 即DES的抗攻击强度如何，或者说密钥长度是否足够了（密钥实际上只有56比特）。 (1) 理论攻击法： 差分分析法和线性逼近法 (1990年提出)：前提条件太强：需要已知 243 = 43981012 对明文密文对。 可制造专用装置，

13、用硬件来实现对所有密钥的遍历搜索,早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。 在CRYPTO93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥,2) 有实效的攻击法： 1997年1月28日，美国的RSA数据安全公司在RSA安

14、全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。 1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。 1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥,3) 结论： 对DES的成功攻击，说明随着计算机技术的发展，现在完全可以用能够接受的代价破译DES密码，DES已不再安全，数据加密标

15、准面临更新与提高,双重DES (Double DES,C = EK2(EK1(P) P = DK1(DK2(C,双重DES的讨论,假设对于 DES和所有56比特密钥，给定任意两个密钥K1和K2，都能找到一个密钥K3使得 EK2(EK1(P)=EK3 (P) 。如果这个假设是事实，则DES的两重加密或者多重加密都将等价于用一个56比特密钥的一次加密。 从直观上看，上面的假设不可能为真。因为DES的加密事实上就是做一个从64比特分组到一个64分组的置换， 而64比特分组共有264可能的状态，因而可能的置换个数为 另一方面， DES的每个密钥确定了一个置换，因而总的置换个数为 。 直到1992年才有

16、人证明了这个结果,中间相遇攻击,C = EK2(EK1(P) X = EK1(P) = DK2(C) 给定明文密文对(P,C) 对所有256个密钥,加密P,对结果排序 对所有256个密钥,解密C,对结果排序 逐个比较,找出K1,K2使得EK1(P) = DK2(C,三重DES,三重DES四种模型： DES-EEE3：三个不同密钥，顺序使用三次加密算法 DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法 DES-EEE2：K1=K3，同上 DES-EDE2：K1=K3，同上,三重DES,C=EK3(DK2(EK1(P) P=DK3(EK2( DK1(C,E和D 互换 K1=K3,E,D

17、,差分密码分析与线性密码分析,差分密码分析 差分密码分析方法是迄今已知的攻击迭代密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥的比特。 本质是一种选择明文攻击。 对明文分组为n的r轮迭代密码，两个n比特串 和 的差分定义为,为在n比特串集上定义的一个群运算,由加密对可得差分序列,定义： 轮特征 是一个差分序列： 其中 是明文对 和 的差分， 是第 轮 输出 和 的差分。轮特征 的概率是指在明文 和子密钥 独立、均匀随机时，明文对 和 的差分为 的条件下，第 轮输出的差分为 的概率,对r轮迭代密码的差分密码分析过程可综述为如下的步骤： （1）找出一个（

18、r-1)-轮特征 使得它的概率达到最大或几乎最大。 （2）均匀随机地选择明文 并计算 ，使得它们的差分为 ，找出 和 在实际密钥加密下所得的密文 和 。若最后一轮的子密钥 有 个可能取值 ，设置相应的 个计数器，用每个 解密密文得到 和 ，如果 和 的差分是 ，则给相应的计数器加1,3）重复步骤(2)，直到一个或几个计算器的值明显高于其他计数器的值，则输出它们对应的子密钥（或部分比特,攻击的复杂度：数据复杂度和计算（处理）复杂度,线性密码分析 线性密码分析是迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡的线性逼近”。 设明文分组和密文分组的长度皆为n比特，记明文和密文分组分别为 。

19、记,线性密码分析的目标就是找出以下形式的有效线性方程： 其中,如果方程成立的概率 ，则称该方程是有效的线性逼近。如果 是最大，则称该方程是最有效的线性逼近。 设N表示明文的个数，T表示是方程左边为0的明文数。如果 ，则令 如果 ，则令 从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于一组线性方程，从而确定出密钥比特,0和1互换,分组密码的操作模式,电子密码本ECB (electronic codebook mode) 密码分组链接CBC (cipher block chaining) 密码反馈CFB (cipher feedback) 输出反馈OFB (output

20、 feedback) 美国NSB在FIPS PUB 74和81中规定 ANSI 在ANSI X3.106中规定 ISO和ISO/IEC在ISO 9732 ISO/IEC 10116中规定,电子密码本（ECB,Ci = EK(Pi) Pi = DK(Ci,ECB特点,简单和有效 可以并行实现 不能隐藏明文的模式信息 相同明文相同密文 同样信息多次出现造成泄漏 对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放 误差传递：密文块损坏仅对应明文块损坏 适合于传输短信息,密码分组链接CBC,Ci=EK(Ci-1Pi) Pi=EK(Ci ) Ci-1,CBC特点,没有已知的并行实现算法 能隐藏明

21、文的模式信息 需要共同的初始化向量IV 相同明文不同密文 初始化向量IV可以用来改变第一块 对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏两明文块损坏 安全性好于ECB 适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec,密码反馈CFB,CFB:分组密码流密码 Si 为移位寄存器,j为流单元宽度 加密: Ci =Pi(EK(Si)的高j位) Si+1=(Sij)|Ci 解密: Pi=Ci(EK(Si)的高j位) Si+1=(Sij)|Ci,CFB加密示意图,Ci =Pi(EK(Si)的高j位) ; Si+1=(Si

22、j)|Ci,CFB解密示意图,Pi=Ci(EK(Si)的高j位); Si+1=(Sij)|Ci,CFB特点,分组密码流密码 没有已知的并行实现算法 隐藏了明文模式 需要共同的移位寄存器初始值IV 对于不同的消息，IV必须唯一 误差传递：一个单元损坏影响多个单元,输出反馈OFB,OFB:分组密码流密码 Si 为移位寄存器,j为流单元宽度 加密: Ci =Pi(EK(Si)的高j位) Si+1=(Sij)|(EK(Si)的高j位) 解密: Pi=Ci(EK(Si)的高j位) Si+1=(Sij)|(EK(Si)的高j位,OFB加密示意图,Ci =Pi(EK(Si)的高j位);Si+1=(Sij)|

23、(EK(Si)的高j位,OFB解密示意图,Pi=Ci(EK(Si)的高j位); Si+1=(Sij)|(EK(Si)的高j位,OFB特点,OFB:分组密码流密码 没有已知的并行实现算法 隐藏了明文模式 需要共同的移位寄存器初始值IV 误差传递：一个单元损坏只影响对应单元 对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放 安全性较CFB差,其他分组密码体制,IDEA 设计原理 加密过程,国际数据加密IDEA（International Data Encryption Algorithm)算法,1990年瑞士联邦技术学院的来学嘉和Massey提出，PES，91年修订，92公布细节 设计目

24、标从两个方面考虑 加密强度 易实现性 强化了抗差分分析的能力， PGP,高级加密标准,AES算法Rijndael 数学基础和设计思想 算法描述,AES背景-i,1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（Advanced Encryption Standard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。 1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。 对AES的基本要求是：比三重DES快、至少

25、与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特,AES背景-ii,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算法，2001年11月出版了最终标准FIPS PUB197,Rijndael简介,不属于Feistel结构 加密、解密相似但不对称 支持128/

26、32=Nb数据块大小 支持128/192/256(/32=Nk)密钥长度 有较好的数学理论作为基础 结构简单、速度快,AES参数,SP网络结构,在这种密码的每一轮中，轮输入首先被一个由子密钥控制的可逆函数S作用，然后再对所得结果用置换（或可逆线性变换）P作用。S和P分别被称为混乱层和扩散层，主要起混乱和扩散作用,AES算法结构-i,AES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层， 线性混合层：确保多轮之上的高度扩散。 非线性层：具有最优最差-情形非线性性的S-盒的并行应用。 密钥加层：轮密钥简单地异或到中间状态上,AES算法结构-ii,AES-128加解密过程,AES算法描述,假设：State表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥 算法如下： 第一轮之前执行AddRoundKey(State,RoundKey) Round(State,RoundKey) ByteSub(State); ShiftRow(State); MixColumn(State); AddRoundKey(State,RoundKey); FinalRound(State,RoundKey) ByteSub(State);