《《对称加密算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《对称加密算法》PPT课件.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对称加密算法（对称加密算法（1）胡建斌胡建斌北京大学信息科学技术学院北京大学信息科学技术学院 http:/ 2013-2014年度北京大学本科生课程目目 录录1.DES 加密算法加密算法2.DES加密算法的应用及分析加密算法的应用及分析数据加密标准数据加密标准（Data Encryption Standard,DES)DES的产生(1)n1973年5月15日,NBS(National Security Agency)开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用
2、户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算法必须是可出口的第三条商用密码技术属于国家秘密。国家对商用密码产品的科研、生产、销售和使用实行专控管理第六条商用密码的科研成果，由国家密码管理机构组织专家按照商用密码技术标准和技术规范审查、鉴定第七条商用密码产品由国家密码管理机构指定的单位生产。未经指定，任何单位或者个人不得生产商用密码产品商用密码管理条例商用密码管理条例DES的产生(2)n1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在19711972年研制n1975年3月17日,NBS公开了全部细节n
3、1976年,NBS指派了两个小组进行评价n1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构n1977年1月15日,“数据加密标准”FIPS PUB 46发布 (DES,Data Encryption Standard)DES的应用n1979年，美国银行协会批准使用n1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSI X.392）n1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1n该标准规定每五年审查一次n最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准分组密码的一般
4、设计原理n分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列设计原则-混淆(confusion)n混淆(confusion)：密文的统计特性与密钥的取值密文的统计特性与密钥的取值之间的关系尽量复杂 n密码算法应当保证密钥、明文和密文的依赖关系相当复杂，混淆程度主要用非线性度来度量n非线性度的概念最初由Pieprzyk等1988年引入，它是密码安全代换盒的主要设计准则之一，它决定了基于s盒的密码算法抗击Matsul线性分析的能力设计原则-扩散（Diffusion)n扩散（Diffus
5、ion):明文的统计结构被扩散消失到密文的长程统计特性明文的统计结构被扩散消失到密文的长程统计特性,使得明文和密文之间的统计关系尽量复杂 n密码算法应保证有语言多余度的明文的统计结构散射到相当长的一段统计中n算法应使明文的简单结构和密文的简单结构之间不存在统计关系n不同的加密函数之间不存在简单关系n扩散程度通常用明文和密钥的雪崩特性（有时用扩散特性）来度量n在相同明文条件下，密钥的1比特改变将根本改变密文n在相同密钥条件下，明文的1比特改变也将根本改变密文n根本改变，一般指改变整个密文块的一半比特实现原则软件实现软件实现n使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软
6、件编程，如8、16、32比特等n应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算n最好是用处理器的基本运算，如加法、乘法、移位等硬件实现硬件实现n加密和解密的相似性，即加密和解密过程的不同应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积n尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现简化的DESnSimplified DES方案，简称S-DES方案。n加密算法涉及五个函数：(1)初始置换IP(initial permutation)(2)复合(轮)函数fk1，它是由密钥K确定的，具有置换和替代的运算 (3)转换函数SW (4)复
7、合(轮)函数fk2 (5)初始置换IP的逆置换IP-1 fk1fk2fk2fk1加密算法的数学表示 n加密算法的数学表式IP-1*fk2*SW*fk1*IP 或：密文=IP-1（fk2(SW(fk1(IP(明文)其中 K1=P8(移位(P10(密钥K)K2=P8(移位(移位(P10(密钥K)n解密算法的数学表示：明文=IP-1（fk1(SW(fk2(IP(密文)S-DES的密钥生成设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)nP10=nLS-1为循环左移1位nLS-2为循环左移左移2位 nP8=S-DES的密钥生成10bit Key8bit Key18b
8、it Key2(2)S-DES的加密运算:初始置换用IP函数:IP=1 2 3 4 5 6 7 8 2 6 3 1 4 8 5 7末端算法的置换为IP的逆置换:IP-1=1 2 3 4 5 6 7 8 4 1 3 5 7 2 8 6易见IP-1(IP(X)=X F函数函数函数fk:加 密方案中的最重要部分，它可表示为：fk(L,R)=(LF(R,SK),R)其中L，R为8位输入,左右各为4位,F为从4位集到4位集的一个映射,并不要求是1:1的。SK为子密钥映映射射F：首先输入是一个4bit数（n1,n2,n3,n4），第一步运算是扩展/置换（E/P）运算：(E/P)=LR=(4 1 2 3)(
9、2 3 4 1)直观表现形式为：8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：把它们重记为8位：上述第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：F函数S盒按下述规则运算：n 将第1/4bit的输入比特做为2-bit数，指示为S盒的一个行；n 将第2/3bit的输入比特做为2-bit数，指示为S盒的一个列；n 行列数确定S盒矩阵的（i,j）数；例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(1 0)确定了S0中的第0行2列（0，2）的
10、系数为3，记为（1 1）输出。由S0,S1输出4-bit经置换它的输出就是F函数的输出。F函数Feistel 结构结构n把任何函数(通常称为F函数，又称轮函数)转化为一个置换，它是由Horst Festiel在设计Lucifer分组密码时发明的，并因DES的使用而流行n很多著名的分组密码算法都是基于Feisetl结构的，例如:FEAL、Twosfish和RC5等Feistel结构定义对一个分组长度为2n比特的r轮Festiel型密码，它的加解密过程如下:1)给定明文P(2n比特)，记P=L0R0，L0、R0分别为P的左右n比特2)进行r轮相同的运算，在这里数据和密钥相结合，并根据下述规则计算L
11、iRi Li =Ri-1;Ri=Li-1F(Ri-1,Ki)F:GF(2)nxGF(2)NGF(2)n为轮函数(有限域上的运算)K1，k2，Kr由种子密钥K生成的子密钥 n为组长度，N为子密钥长度3)输出密文C=RrLr （SW）在加密的最后一轮，为了使算法同时用于加密和解密，略去“左右变换”4)解密 Ri-1=Li Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel模型分析优点优点n 设计容易设计容易:F F函数不要求可逆函数不要求可逆,加、解密算法结构相同加、解密算法结构相同n强度高：如果强度高：如果F F函数是随机的函数是随机的,则连续若干圈复合形成的函则连续若干圈复
12、合形成的函数与随机置换是数与随机置换是无法无法区分的区分的缺点缺点n每圈加密时输入有一半没有每圈加密时输入有一半没有改变改变n 左右块的加密处理不能并行左右块的加密处理不能并行实施实施 Feistel模型实现完全性的性能分析模型实现完全性的性能分析n如果对每个密钥k,迭代次数为m的加密变换Ek(x)的每个输入比特的变化都可能会影响到每个输出比特的变化,则称 Ek(x)是完全的n意义意义:实现了Shannon提出的扩散性原则n扩散原则扩散原则(Diffusion)n让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响n在检验完全性时,无法对所有的密钥都来
13、检验影响的必然性,只好退而求其次,来分析这种可能性 结论结论n如果Feistel模型的 F函数需要T圈迭代才能实现完全性,则Feistel模型经T+2圈迭代可实现完全性nFeistel模型至少需要3圈才可实现完全性nDES算法需且只需5圈即可实现完全性DES特征特征分组加密算法：明文和密文为分组加密算法：明文和密文为64bit分组长度分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：密钥长度：56bit，每个第，每个第8位为奇偶校验位，可忽略位为奇偶校验位，可忽略密钥可为任意的密钥可为任意的56位数，存在弱密钥，容易避开位数，
14、存在弱密钥，容易避开采用混乱和扩散的组合，每个组合先替代后置换，共采用混乱和扩散的组合，每个组合先替代后置换，共16轮轮只使用了标准的算术和逻辑运算，易于实现只使用了标准的算术和逻辑运算，易于实现DES示意图DES的描述输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据DES算法框图交换左右32比特 DES加解密过程令i表示迭代次数，表示逐位模2求和，f为加密函数。DES中的各种置换、扩展和替代中的各种置换、扩展和替代初始置换初始置换IP和初始逆置换和初始逆置换IP1 IP和和IP1IPIP1Li-1（32比特）比特）Ri-1（32比特）比特）Li（3
15、2比特）比特）48比特寄存器比特寄存器选择扩展运算选择扩展运算E48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器选择压缩运算选择压缩运算S置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的的一轮迭代一轮迭代扩展置换扩展置换-盒盒32位扩展到位扩展到48位位扩展扩展压缩替代压缩替代S-盒盒48位压缩到位压缩到32位位共共8个个S盒盒S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8S-盒的构造盒的构造 原则：原则：S盒的每一位输出都不是输入的线性或仿射函数盒的每一位输出都不是输入的线性或仿射函数 仿射函数仿射函数 设设 f是是n元布尔函
16、数元布尔函数,如果如果则称则称f 是仿射函数是仿射函数;又若仿射函数满足又若仿射函数满足f(0)=0,则则 f 为线性函数为线性函数.等价定义等价定义:设设 f是是n元布尔函数元布尔函数,则则 f是仿射函数等价于是仿射函数等价于存在常数存在常数c1,c2,cn和和a使对所有使对所有x,都有都有此时此时,如果如果a=0,则则 f为线性函数为线性函数.仿射函数的缺点仿射函数的缺点:(1)输入与输出之间的代数关系太简单输入与输出之间的代数关系太简单;(2)输入的变化与输出的变化之间的代数关系太简单输入的变化与输出的变化之间的代数关系太简单.仿射函数的优点仿射函数的优点:实现简单实现简单 S-盒盒设计
17、标准设计标准nS盒的每一位输出都不是输入的线性或仿射函数。nS盒的输入发生1比特变化，输出至少有2比特发生变化。n当固定S盒的1位输入时，S盒的每一位输出中0和1的个数尽可能平衡。S-盒的作用盒的作用n S盒是DES算法中唯一的非线性唯一的非线性变换变换，nS盒实现了局部的混乱和扩散；这种局部的混乱和扩散通过E盒和P盒并借助于多次迭代实现了整个密码算法的混乱和扩散n S盒只要稍有改变，其密码强度就会大大降低，因此，不要试图改变一个密码算法中的任何细节 如何全面准确地度量如何全面准确地度量S-盒的密码强度和设计有效的盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题盒是分组密码设计和分析
18、中的难题置换置换p-盒的构造盒的构造P置换的目的是提供雪崩效应置换的目的是提供雪崩效应DES中的子密钥的生成中的子密钥的生成密钥置换算法的构造准则密钥置换算法的构造准则设计目标：子密钥的统计独立性和灵活性设计目标：子密钥的统计独立性和灵活性实现简单实现简单速度速度不存在简单关系：给定两个有某种关系的种子密钥不存在简单关系：给定两个有某种关系的种子密钥,能预测它们轮子密钥能预测它们轮子密钥之间的关系之间的关系种子密钥的所有比特对每个子密钥比特的影响大致相同种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的从一些子密钥比特获得其他的子密钥比特在计算上
19、是难的没有弱密钥没有弱密钥目目 录录1.DES 加密算法加密算法2.DES加密算法的应用及分析加密算法的应用及分析DES的工作模式的工作模式电子密码本电子密码本 ECB(electronic codebook ECB(electronic codebook mode)mode)密码分组链接密码分组链接 CBC(cipher block chaining)CBC(cipher block chaining)密码反馈密码反馈 CFB(cipher feedback)CFB(cipher feedback)输出反馈输出反馈 OFB(output feedback)OFB(output feedbac
20、k)电子密码本电子密码本ECBECB的特点的特点简单和有效简单和有效可以并行实现可以并行实现不能隐藏明文的模式信息不能隐藏明文的模式信息 相同明文相同明文生成生成相同密文，相同密文，同样信息多次出现造成泄漏同样信息多次出现造成泄漏对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放误差传递：密文块损坏误差传递：密文块损坏仅仅对应明文块损坏对应明文块损坏适合于传输短信息适合于传输短信息密码分组链接密码分组链接CBC对明文施加运算后再加密对明文施加运算后再加密CBC的特点的特点没有已知的并行实现算法能隐藏明文的模式信息 需要共同的初始化
21、向量IV 相同明文生成不同密文 初始化向量IV可以用来改变第一块对明文的主动攻击是不容易的 信息块不容易被替换、重排、删除、重放 误差传递：密文块损坏两明文块损坏安全性好于ECB适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如 SSL、IPSec密码反馈密码反馈CFB 假定：Si 为移位寄存器,传输单位为jbit 加密: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 对密钥施加运算后再加密对密钥
22、施加运算后再加密密码反馈密码反馈CFB解密解密Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|Ci CFB的特点的特点没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位寄存器初始值需要共同的移位寄存器初始值IVIV误差传递：一个单元损坏影响多个单元误差传递：一个单元损坏影响多个单元输出反馈输出反馈OFB 假定：假定：Si Si 为移位寄存器为移位寄存器,传输单位为传输单位为jbitbit 加密加密:C Ci i=P=Pi i(E EK K(S(Si i)的高的高j j位位)S Si+1i+1=(S=(Si ij)|j)|(E EK K(S(S
23、i i)的高的高j j位位)解密解密:P:Pi i=C=Ci i(E EK K(S(Si i)的高的高j j位位)S Si+1i+1=(S=(Si ij)|j)|(E EK K(S(Si i)的高的高j j位位)输出反馈输出反馈OFB加密加密Ci=Pi(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)输出反馈输出反馈OFB解密解密Pi=Ci(EK(Si)的高的高j位位);Si+1=(Sij)|(EK(Si)的高的高j位位)0FB的特点的特点没有已知的并行实现算法没有已知的并行实现算法隐藏了明文模式隐藏了明文模式需要共同的移位寄存器初始值需要共同的移位寄存器初始
24、值IVIV误差传递：一个单元损坏只影响对应单元误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放信息块可被替换、重排、删除、重放安全性较安全性较CFBCFB差差分组密码的强化技术分组密码的强化技术n差分分析（参见实验教程）和线性分析的问世，给DES致命一击，至少从理论上说DES已不再安全n为了既不削弱安全性能，又能充分利用现有芯片，密码设计者提出了分组密码的强化思想：n密码级联技术n多重加密n基于单向Hash函数n正形置换方法密码级联技术本质上说，级联密码是t个相同或不同分组密码的乘积密码，即其中，是第i 个密码算法的加密函数
25、n这里要求各个算法所用的密钥(K1,K2Kt)必须相互独立，这样才能增大密钥长度，进而增强安全性n应当指出，某些强度很高的密码体制级联使用，若设计不当很可能使加密效果相互抵消，并且这种级联密码的安全性很难把握，因此我们不提倡使用不同类分组密码进行级联。多级加密技术n多重加密是密码级联的一种特殊形式，即利用同一算法采用多个相互独立的密钥对明文块依次进行加密，形式上n当t=2时，n二重加密易受中间相遇攻击的威胁三重三重DESTuchman提出了三重加密的思想，在两个不同密钥作用下将加解密算法交叉使用，即n尽管三重加密在二重加密基础上安全性有所改善，但由于仅使用两个密钥，使得攻击的复杂度并没有达到三
26、倍于原算法的效果nMerkle和Hellman提出了一种”时空折衷方法”，可以用2l l-1次加密和2l l个存贮记录即可破译三重加密，这里l为单个算法的密钥长度DES的安全性的安全性实际安全性定义n考虑攻击所需的时间和数据量才能准确估计算法的强度，为此可将攻击按计算复杂度进行分类p数据复杂度(Data complexity)即实施攻击所必须的外部输入数据量，以分组长度n为单位，记为Cdp处理复杂度(Proceessing complexity)即实施攻击所花费的时间，以加密次数为单位，记为Cp 显然，攻击的复杂度Ca=max(Cd，Cp).在选择明文攻击下目前对DES的差分攻击的最好结果是1
27、.强力攻击n在唯密文攻击唯密文攻击下，密码分析者依次试用密钥空间中的所有密钥解译一个或多个截获的密文，直至得到一个或多个有意义的明文块n在已知已知(选择选择)明文明文攻击下，密码分析者试用密钥空间中的所有可能的密钥对一个已知明文加密，将加密结果同该明文相应的已知密文比较，直至二者相符，然后再用其它几个已知明密文对已知明密文对来验证该密钥的正确性n强力攻击适用于任何分组密码DES密钥攻击密钥攻击 56比特的密钥长度不足以抵御穷举式比特的密钥长度不足以抵御穷举式 2 256 56 101017171.1977年，年，Diffie和和Hellman已建议制造一个每已建议制造一个每秒能测试秒能测试10
28、0100万个密钥的万个密钥的VLSI芯片。每秒测芯片。每秒测试试100100万个密钥的机器大约需要一天就可以万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机搜索整个密钥空间。他们估计制造这样的机器大约需要器大约需要2000万万美元美元2.2.在在CRYPTO93上，上，Session和和Wiener给出了给出了一个非常详细的密钥搜索机器的设计方案，一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所这个机器基于并行运算的密钥搜索芯片，所以以16次加密能同时完成。花费次加密能同时完成。花费10万万美元，平美元，平均用均用1.5天左右就可找到天左右就可
29、找到DES密钥密钥3.3.美国克罗拉多洲的程序员美国克罗拉多洲的程序员Verser从从1997年年2 2月月18日起，用了日起，用了96天时间，在天时间，在Internet上数万上数万名志愿者的协同工作下，成功地找到了名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的的密钥，赢得了悬赏的1万美元万美元4.4.19981998年年7 7月电子前沿基金会（月电子前沿基金会（EFFEFF）使用一台）使用一台2525万美圆的电脑在万美圆的电脑在5656小时内破译了小时内破译了5656比特密比特密钥的钥的DESDES5.5.19991999年年1 1月月RSARSA数据安全会议期间，电子前沿数
30、据安全会议期间，电子前沿基金会用基金会用2222小时小时1515分钟就宣告破解了一个分钟就宣告破解了一个DESDES的密钥的密钥2.差分攻击n也称差分分析，是一种选择明文攻击方法，最早由以色列密码学家Eli Biham和Adi Shamir于1990年提出n该方法充分利用了明文对的特殊差分对输出密文对差分的影响，通过分析某个(些)最大概率差分来确定可能密钥的概率并找出最可能的密钥n差分分析是目前用于分组密码的最强有力的攻击方法之一，成功地用于攻击DES的复杂度为Ca 2473.线性攻击n是一种已知明文攻击方法，最早由Matsui在1993年提出n该攻击利用了明文、密文和密钥的若干位之间的线性关
31、系。在对DES的线性攻击下，这种线性关系可以通过组合各轮的线性关系而得到(假定各轮子密钥相互独立).此时攻击者希望找到一个等式使得该等式在密钥空间上成立的概率pl ，且|pl-|最大线性攻击N个已知明密文对的线性攻击如下:1.对所有明文p和密文c，令T表示上式左边为0的次数2.若 ，猜测 ，否则猜测 线性分析是攻击分组密码的另一个最强有力的方法，成功地用于攻击DES的复杂度为4.相关密钥攻击n类似于差分分析，该方法利用密钥差分来攻击分组密码，这是因为Biham证明了许多分组密码的密钥编排算法明显保许多分组密码的密钥编排算法明显保持了密钥间的关系持了密钥间的关系n这种方法与密码体制的轮数和加密函
32、数无关弱密钥与半弱密钥弱密钥与半弱密钥弱密钥弱密钥：若给定的密钥k，k1=k2=k16，则称K为弱密钥半弱密钥半弱密钥：若给定的密钥k,相应的16个子密钥只有两种取值,且每一种都出现8次，则称K为半弱密钥弱密钥:，DES存在4个弱密钥e0e0e0e0f1f1f1f1 fefefefefefefefe半弱密钥:EK1=EK2，至少有12个半弱密钥 即：5.中间相遇攻击n这是一种适用于多重加密下的已知明文已知明文攻击.n对DES来说，这种攻击方法需要256次加密，256个存贮记录作业作业n完成实验3 DES密码分析实验的课堂实验内容部分n给定1个S盒，求它的差分分布矩阵n实现DES加密密钥的暴力破解(perl)n学习AES加密算法谢谢 谢谢!