《密码学分组密码.ppt》由会员分享，可在线阅读，更多相关《密码学分组密码.ppt（93页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 分组密码体制n分组密码概述n数据加密标准n差分密码分析与线性密码分析n分组密码的运行模式n其他分组密码体制分组密码概述 分组密码因其实现速度较快，在许多密码系统中是一个重要的组成部分。分组密码与流密码在区别在于分组密码将明文的消息编码后划分成长度为n的组，在一个密钥的控制下变换成等长（m）的输出序列。一般情况下，nm。若mn，为由数据扩充的分组密码；若mn，为由数据压缩的分组密码。为了保证一个分组密码算法的有效性安全、易于实施。分组密码算法应满足以下要求：1.分组n足够大，使得明文空间足够大，防止明文穷举攻击法奏效。2.密钥量足够大，尽可能消除弱密钥，使得所有密钥都一样好，防止对密钥的
2、穷举攻击成功。3.由密钥确定的算法要足够的复杂，充分实现明文与密钥的扩散和混乱，使得算法能抵抗各种攻击。4.加密和解密运算简单，易于软件和硬件的高速实现。5.数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引进数据扩展。6.差错传播尽可能小。设计分组密码常用的一些方法介绍设计分组密码常用的一些方法介绍 1.代换 将n长的明文分组变换为唯一n长密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。若分组长度为n，则明文空间M有 个向量，代换的就是给出在该空间上的一个可逆变换 。例如：取n4，2.扩散和混淆 扩散和混淆是Shannon提出的设计密码系统的两个基本的方法，目
3、的是抵抗敌手对密码系统的统计分析。扩散：就是将明文的统计特性散布到密文中，实现的方法是使明文的每一位影响密文的多位，等价于说密文的每一位均受明文中的多位影响。目的是使明文和密文的统计关系变得尽可能的复杂，使敌手无法得到明文（密文）。方法：对数据重复执行某个置换，再对该置换作用一函数，可获得扩散。混淆：是使密文的统计特性和密钥取值的关系变得尽可能的复杂，使敌手无法获得密钥。方法：使用复杂的代换算法，可获得好的混淆结果，而使用简单的线性代换得到的混淆效果不太理想。nFeistel密码结构 很多分组密码的结构本质上都是基于一个Feistel密码结构。Feistel密码结构的思想是利用乘积密码实现扩散
4、和混淆。乘积密码是顺序的执行两个或多个密码系统，使得最后结构的密码强度高于每个基本密码系统产生的结果。加密加密:Li =Ri-1;Ri=Li-1 F(Ri-1,Ki)解密解密:Ri-1=Li Li-1=Ri F(Ri-1,Ki)=Ri F(Li,Ki)Feistel结构定义结构定义Feistel结构图结构图数据加密标准nDES描述n二重DESn两个密钥的三重DESn三个密钥的三重DES64比特明文DES算法加密64比特密文64比特的密钥（内含8比特校验位）DES示意图示意图DES的描述的描述lDES利用56比特长度的密钥K来加密长度为64位的明文，得到长度为64位的密文输入输入64比特明文数据
5、比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据DES算法框图算法框图交换左右交换左右32比特比特 l DES加解密过程令i表示迭代次数，表示逐位模2求和，f为加密函数。DES的加密和解密过程表示如下。加密过程：解密过程：DES 加加密密过过程程：IPmR0L0IP-1DES(m)=mR1=L0 (R0,K1)L1=R0 K1T1R16=L15 (R15,K16)L16=R15 K16T16R15=L14 (R14,K15)L15=R14IPmL16R16IP-1DES(m)=mK16L15=R16 (L1
6、6,K16)R15=L16T16L0=R1 (L1,K1)R0=L1K1T1L1=R2 (L2,K1)R1=L2DES 解解密密过过程程初始置换初始置换IPIP和初始逆置换和初始逆置换IPIP1 1 注：数字表示比特位逆初始置换(IP-1)是简单的比特移位。置 换 码 组1 2 3 64位 63 64逆初始置换密 文1 2 3 64位 63 64逆初始置换87654321403938373635343348474645444342411615141312111095655545352515049242322212019181764636261605958573231302928272625IP
7、-1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2425 26 27 28 29 30 31 3233 34 35 36 37 38 39 4041 42 43 44 45 46 47 4849 50 51 52 53 54 55 5657 58 59 60 61 62 63 64IP IP-1=IP-1 IP=I58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25
8、17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 740 8 48 16 56 24 64 32 39 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25IP-1:IP:L i-1(32比特比特)R i-1(32比特比特)第第 i 次迭代次迭代 R i-1(
9、32比特比特)选择扩展运算E48比特寄存器比特寄存器+K i48比特寄存器比特寄存器选择压缩运算S32比特寄存器比特寄存器置换运算P+L iRi-11 48比特 48 *(Ri-1,Ki)的功能：选择扩展运算选择扩展运算 E E 1 32比特 32置换置换P1 32比特 32(Ri-1,Ki)1 32比特 32+S1S2S3S4S5S6S7S8Ki(48比特比特)选择压缩函数 Si3212345456789891011121312131415161716171819202120212223242524252627282928293031321E:E的作用：将32比特的输入膨胀为48比特。则输出
10、为：B=t32 t1 t2 t32 t1*选择扩展运算的功能：设输入为：T=t1 t2 t3 t32 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 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 1E的作用：将32比特的输入膨胀为48比特。*选择扩展运算：Si 设
11、 Si 盒的 6 个输入端为 b1 b2 b3 b4 b5 b6，在 Si 表中找出 b1 b6 行，b2 b3 b4 b5 列的元素：Si(b1 b6,b2 b3 b4 b5)便是 Si 盒的输出。Si*选择压缩函数Si的功能：E 输出的 48 比特与子密钥异或后，顺序分成 8 组，每组 6 比特，分别通过 S1，S2，,S8 盒后又缩为 32 比特，即每盒输入为 6比特，输出为 4 比特。b1 b6b2 b3 b4 b5二进制输出*选择压缩函数Si的功能：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 012314 4 13 1 2 15 11 8 3 10 6
12、 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 输入到选择函数S11 0 1 1 0 0b1 b6 1 00 0 1 0选择函数S1的输出6S-Box-iS-Box-ii子密钥的产生子密钥的产生置换选择置换选择1 1和置换选择和置换选择2 2DES解密n和Feistel密码一样，DES的解密和加密使用同一算法，只是子密钥的使用顺序相反。n子密钥是独立产生的，可以独立存储。DES中的中的M、K、C明文
13、 m 和密钥 K 的变化对密文的影响：DES的加密结果，每一比特都是明文m和密钥K的每一比特的复杂函数，即明文m和密钥k每改变一个比特都将对密文产生剧烈影响。（明文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 举例
14、：共有4种，如：0101010101010101。(2)半弱密钥：定义：当存在子密钥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 或0101012.DES的安全性：即DES的抗攻击强度如何，或者说密钥长度是否足够了（密钥实际上只有56比特）。(1)理论攻击法：差分分析法和线性逼近法(1990年提出)：前提条件太强：需要已知 243=43981012 对明文密文对。可制造专用装置，用硬件来实
15、现对所有密钥的遍历搜索。早在1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元。在CRYPTO93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥。(2)有实效的攻击法：19971997年1 1月2828日，美国的RSARSA数据安全公司在
16、RSARSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1 1万美元破译密钥长度为5656比特的DESDES。美国克罗拉多洲的程序员VerserVerser从19971997年2月1818日起，用了9696天时间，在InternetInternet上数万名志愿者的协同工作下，成功地找到了DESDES的密钥，赢得了悬赏的1 1万美元。1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES。1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。(3)结论：对DES的成功攻击，说明随着计算机技术的发
17、展，现在完全可以用能够接受的代价破译DES密码，DES已不再安全，数据加密标准面临更新与提高。双重DES(Double DES)lC=EK2(EK1(P)P=DK1(DK2(C)双重DES的讨论l假设对于假设对于 DESDES和所有和所有5656比特密钥，给定任意两个密钥比特密钥，给定任意两个密钥K1K1和和K2K2，都能找到一个密钥都能找到一个密钥K3K3使得使得 EK2EK2(EK1(P)=EK3(P)EK1(P)=EK3(P)。如果如果这个假设是事实，则这个假设是事实，则DESDES的两重加密或者多重加密都将等价的两重加密或者多重加密都将等价于用一个于用一个5656比特密钥的一次加密。比
18、特密钥的一次加密。l从直观上看，上面的假设不可能为真。因为从直观上看，上面的假设不可能为真。因为DESDES的加密事实的加密事实上就是做一个从上就是做一个从6464比特分组到一个比特分组到一个6464分组的置换，分组的置换，而而6464比比特分组共有特分组共有2 26464可能的状态，因而可能的置换个数为可能的状态，因而可能的置换个数为l另一方面，另一方面，DESDES的每个密钥确定了一个置换，因而总的置换的每个密钥确定了一个置换，因而总的置换个数为个数为 。l直到直到19921992年才有人证明了这个结果。年才有人证明了这个结果。中间相遇攻击lC=EK2(EK1(P)X=EK1(P)=DK2
19、(C)l给定明文密文对(P,C)l对所有256个密钥,加密P,对结果排序l对所有256个密钥,解密C,对结果排序l逐个比较,找出K1,K2使得EK1(P)=DK2(C)三重DES三重三重DES四种模型：四种模型：lDES-EEE3：三个不同密钥，顺序使用三三个不同密钥，顺序使用三次加密算法次加密算法lDES-EDE3：三个不同密钥，依次使用加三个不同密钥，依次使用加密密-解密解密-加密算法加密算法lDES-EEE2：K1=K3，同上同上lDES-EDE2：K1=K3，同上同上三重DES C=EK3(DK2(EK1(P)P=DK3(EK2(DK1(C)1.E和D 互换2.K1=K3ED差分密码分
20、析与线性密码分析n差分密码分析 差分密码分析方法是迄今已知的攻击迭代密码最有效的方法之一，其基本思想是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥的比特。本质是一种选择明文攻击。对明文分组为n的r轮迭代密码，两个n比特串 和 的差分定义为为在n比特串集上定义的一个群运算由加密对可得差分序列定义：轮特征 是一个差分序列：其中 是明文对 和 的差分，是第 轮 输出 和 的差分。轮特征 的概率是指在明文 和子密钥 独立、均匀随机时，明文对 和 的差分为 的条件下，第 轮输出的差分为 的概率。对r轮迭代密码的差分密码分析过程可综述为如下的步骤：（1）找出一个（r-1)-轮特征 使得它的概率
21、达到最大或几乎最大。（2）均匀随机地选择明文 并计算 ，使得它们的差分为 ，找出 和 在实际密钥加密下所得的密文 和 。若最后一轮的子密钥 有 个可能取值 ，设置相应的 个计数器，用每个 解密密文得到 和 ，如果 和 的差分是 ，则给相应的计数器加1（3）重复步骤(2)，直到一个或几个计算器的值明显高于其他计数器的值，则输出它们对应的子密钥（或部分比特）。攻击的复杂度：数据复杂度和计算（处理）复杂度。n线性密码分析 线性密码分析是迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡的线性逼近”。设明文分组和密文分组的长度皆为n比特，记明文和密文分组分别为 。记线性密码分析的目标就是找出以
22、下形式的有效线性方程：其中 如果方程成立的概率 ，则称该方程是有效的线性逼近。如果 是最大，则称该方程是最有效的线性逼近。设N表示明文的个数，T表示是方程左边为0的明文数。如果 ，则令如果 ，则令 从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于一组线性方程，从而确定出密钥比特。0和1互换分组密码的操作模式n电子密码本ECB(electronic codebook mode)n密码分组链接CBC(cipher block chaining)n密码反馈CFB(cipher feedback)n输出反馈OFB(output feedback)美国NSB在FIPS PUB
23、 74和81中规定ANSI 在ANSI X3.106中规定ISO和ISO/IEC在ISO 9732 ISO/IEC 10116中规定电子密码本（ECB）Ci=EK(Pi)Pi=DK(Ci)ECB特点简单和有效可以并行实现不能隐藏明文的模式信息相同明文相同密文同样信息多次出现造成泄漏对明文的主动攻击是可能的信息块可被替换、重排、删除、重放误差传递：密文块损坏仅对应明文块损坏适合于传输短信息密码分组链接CBCCi=EK(Ci-1Pi)Pi=EK(Ci)Ci-1CBC特点没有已知的并行实现算法能隐藏明文的模式信息需要共同的初始化向量IV相同明文不同密文初始化向量IV可以用来改变第一块对明文的主动攻击
24、是不容易的信息块不容易被替换、重排、删除、重放误差传递：密文块损坏两明文块损坏n安全性好于ECBn适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec 密码反馈CFBCFB:分组密码流密码 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=(Sij)|Ci CFB解密示意图解密示意图Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|Ci CFB特
25、点分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IVn对于不同的消息，IV必须唯一n误差传递：一个单元损坏影响多个单元 输出反馈OFBOFB:分组密码流密码 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)|(EK(Si)的高的高j位位)OFB解密示意图解密示意图Pi=Ci(EK(Si)的高的高j位位);Si+1=(Si
26、j)|(EK(Si)的高的高j位位)OFB特点nOFB:分组密码流密码没有已知的并行实现算法隐藏了明文模式n需要共同的移位寄存器初始值IVn误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的信息块可被替换、重排、删除、重放安全性较CFB差其他分组密码体制nIDEA1.设计原理2.加密过程国际数据加密IDEA（International Data Encryption Algorithm)算法n1990年瑞士联邦技术学院的来学嘉和Massey提出，PES，91年修订，92公布细节设计目标从两个方面考虑n加密强度n易实现性n强化了抗差分分析的能力，PGP高级加密标准nAES算法Rijnd
27、ael1.数学基础和设计思想2.算法描述AES背景-in1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（Advanced Encryption Standard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。n1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。作为进入AES候选过程的一个条件，开发者承诺放弃被选中算法的知识产权。对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特。AES背景-iin1
28、998年8月12日，在首届AES会议上指定了15个候选算法。n1999年3月22日第二次AES会议上，将候选名单减 少 为 5个，这 5个 算 法 是 RC6，Rijndael，SERPENT，Twofish和MARS。n2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。n2000年10月2日，NIST宣布了获胜者Rijndael算法，2001年11月出版了最终标准FIPS PUB197。Rijndael简介n不属于Feistel结构n加密、解密相似但不对称n支持128/32=Nb数据块大小n支持128/192/256(/32=Nk)密钥长度n有较好的数学理论
29、作为基础n结构简单、速度快AES参数SP网络结构在这种密码的每一轮中，轮输入首先被一个由子密钥控在这种密码的每一轮中，轮输入首先被一个由子密钥控制的可逆函数制的可逆函数S作用，然后再对所得结果用置换（或可逆作用，然后再对所得结果用置换（或可逆线性变换）线性变换）P作用。作用。S和和P分别被称为混乱层和扩散层，主分别被称为混乱层和扩散层，主要起混乱和扩散作用。要起混乱和扩散作用。AES算法结构-inAES算法的轮变换中没有Feistel结构，轮变换是由三个不同的可逆一致变换组成，称之为层，线性混合层：确保多轮之上的高度扩散。非线性层：具有最优最差-情形非线性性的S-盒的并行应用。密钥加层：轮密钥
30、简单地异或到中间状态上。AES算法结构-iiAES-128加解密过程AES算法描述n假设：State表示数据，以及每一轮的中间结果RoundKey表示每一轮对应的子密钥n算法如下：n第一轮之前执行AddRoundKey(State,RoundKey)nRound(State,RoundKey)ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey);nFinalRound(State,RoundKey)ByteSub(State);ShiftRow(State);AddRoundKey(State,R
31、oundKey);状态、密钥状态/密钥的矩阵表示S00S01S02S03S04S05S06S07S08S09S10S11S12S13S14S15k00k01k02k03k10k11k12k13k20k21k22k23k30k31k32k33字节代替(Substitute Bytes)变换n字节代替是一个非线性的字节代替，独立地在每个状态字节上进行运算。代替表（S-盒）是可逆的，是一个1616的矩阵。example行移位(Shift Row)变换简单的置换简单的置换example列混合Mix Column变换n代替操作，将状态的列看作有限域GF（28）上的4维向量并被有限域GF（28）上的一个固
32、定可逆方阵A乘 example轮密钥加（Add Round Key)一个简单地按位异或的操作一个简单地按位异或的操作AES的密钥调度n轮密钥是通过密钥调度算法从密钥中产生，包括两个组成部分：密钥扩展和轮密钥选取。基本原理如下：所有轮密钥比特的总数等于分组长度乘轮数加1。（如128比特的分组长度和10轮迭代，共需要1408比特的密钥）。将种子密钥扩展成一个扩展密钥。轮密钥按下述方式从扩展密钥中选取：第一个轮密钥由开始Nb个字组成，第二个轮密钥由接下来的Nb个字组成，如此继续下去。AES的密钥扩展 G变换nRotword执行一字节循环左移 b0,b1,b2,b3 b1,b2,b3,b0nSubwo
33、rd执行使用S-盒实行字节替换n前两步的结果XOR轮常数RconjexampleRijndael安全性l没有发现弱密钥或补密钥l能有效抵抗目前已知的攻击算法n线性攻击n差分攻击先进对称分组加密算法的特点l可变的密钥长度:RC5l混合的运算 IDEAl数据相关的轮数 RC5l密钥相关的轮数 CAST-128l密钥相关的S盒:Blowfishl冗长密钥调度算法：Blowfishl可变的F：CAST-128l可变长明文/密文块长度l可变轮数l每轮操作作用于全部数据习题nP73:1,2,3,4实验安排：n第十三、十四、十五周停课安排实验。n第十三周：周一下午1：305：30；n地点：信北503n环境：Windows操作系统，C语言编译环境。n2人/组n第十五周：周一下午5-6节，信西503，硬件实验。