《对称加密算法》PPT课件.ppt

《《对称加密算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《对称加密算法》PPT课件.ppt（74页珍藏版）》请在三一办公上搜索。

1、对称加密算法（1）,胡建斌北京大学信息科学技术学院 http:/,2013-2014年度北京大学本科生课程,目 录DES 加密算法DES加密算法的应用及分析,数据加密标准（Data Encryption Standard,DES),DES的产生(1),1973年5月15日,NBS(National Security Agency)开始公开征集标准加密算法,并公布了它的设计要求:(1)算法必须提供高度的安全性(2)算法必须有详细的说明,并易于理解(3)算法的安全性取决于密钥,不依赖于算法(4)算法适用于所有用户(5)算法适用于不同应用场合(6)算法必须高效、经济(7)算法必须能被证实有效(8)算

2、法必须是可出口的,第三条商用密码技术属于国家秘密。国家对商用密码产品的科研、生产、销售和使用实行专控管理第六条商用密码的科研成果，由国家密码管理机构组织专家按照商用密码技术标准和技术规范审查、鉴定第七条商用密码产品由国家密码管理机构指定的单位生产。未经指定，任何单位或者个人不得生产商用密码产品商用密码管理条例,DES的产生(2),1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在19711972年研制1975年3月17日,NBS公开了全部细节1976年,NBS指派了两个小组进行评价1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种

3、政府机构1977年1月15日,“数据加密标准”FIPS PUB 46发布(DES,Data Encryption Standard),DES的应用,1979年，美国银行协会批准使用1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSI X.392）1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1该标准规定每五年审查一次最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准,分组密码的一般设计原理,分组密码是将明文消息编码表示后的数字（简称明文数字）序列，划分成长度为n的组（可看成长度为n的矢量），每

4、组分别在密钥的控制下变换成等长的输出数字（简称密文数字）序列,设计原则-混淆(confusion),混淆(confusion)：密文的统计特性与密钥的取值之间的关系尽量复杂 密码算法应当保证密钥、明文和密文的依赖关系相当复杂，混淆程度主要用非线性度来度量非线性度的概念最初由Pieprzyk等1988年引入，它是密码安全代换盒的主要设计准则之一，它决定了基于s盒的密码算法抗击Matsul线性分析的能力,设计原则-扩散（Diffusion),扩散（Diffusion):明文的统计结构被扩散消失到密文的长程统计特性,使得明文和密文之间的统计关系尽量复杂 密码算法应保证有语言多余度的明文的统计结构散射

5、到相当长的一段统计中算法应使明文的简单结构和密文的简单结构之间不存在统计关系不同的加密函数之间不存在简单关系扩散程度通常用明文和密钥的雪崩特性（有时用扩散特性）来度量在相同明文条件下，密钥的1比特改变将根本改变密文在相同密钥条件下，明文的1比特改变也将根本改变密文根本改变，一般指改变整个密文块的一半比特,实现原则,软件实现,使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如8、16、32比特等应尽量避免按比特置换，在子块上所进行的密码运算尽量采用易于软件实现的运算最好是用处理器的基本运算，如加法、乘法、移位等,硬件实现,加密和解密的相似性，即加密和解密过程的不同

6、应仅仅在密钥使用方式上，以便采用同样的器件来实现加密和解密，以节省费用和体积尽量采用标准的组件结构，以便能适应于在超大规模集成电路中实现,简化的DES,Simplified DES方案，简称S-DES方案。加密算法涉及五个函数：(1)初始置换IP(initial permutation)(2)复合(轮)函数fk1，它是由密钥K确定的，具有置换和替代的运算(3)转换函数SW(4)复合(轮)函数fk2(5)初始置换IP的逆置换IP-1,fk1,fk2,fk2,fk1,加密算法的数学表示,加密算法的数学表式IP-1*fk2*SW*fk1*IP 或：密文=IP-1（fk2(SW(fk1(IP(明文)其

7、中 K1=P8(移位(P10(密钥K)K2=P8(移位(移位(P10(密钥K)解密算法的数学表示：明文=IP-1（fk1(SW(fk2(IP(密文),S-DES的密钥生成,设10bit的密钥为（k1,k2,k3,k4,k5,k6,k7,k8,k9,k10)P10=LS-1为循环左移1位LS-2为循环左移左移2位 P8=,S-DES的密钥生成,10bit Key,8bit Key1,8bit 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

8、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)(2 3 4 1)直观表现形式为：,8-bit子密钥：K1=(k11,k12,k13,k14,k15,k16,k17,k18),然后与E/P的结果作异或运算得：把它们重记为8位：,上述第一行输入进S-盒S0，产生2-

9、位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：,F函数,S盒按下述规则运算：将第1/4bit的输入比特做为2-bit数，指示为S盒的一个行；将第2/3bit的输入比特做为2-bit数，指示为S盒的一个列；行列数确定S盒矩阵的（i,j）数；例如：（P0,0,P0,3）=(00),并且(P0,1,P0,2)=(1 0)确定了S0中的第0行2列（0，2）的系数为3，记为（1 1）输出。,由S0,S1输出4-bit经置换它的输出就是F函数的输出。,F函数,Feistel 结构,把任何函数(通常称为F函数，又称轮函数)转化为一个置换，它是由Horst Festiel在设计L

10、ucifer分组密码时发明的，并因DES的使用而流行很多著名的分组密码算法都是基于Feisetl结构的，例如:FEAL、Twosfish和RC5等,Feistel结构定义,对一个分组长度为2n比特的r轮Festiel型密码，它的加解密过程如下:,1)给定明文P(2n比特)，记P=L0R0，L0、R0分别为P的左右n比特2)进行r轮相同的运算，在这里数据和密钥相结合，并根据下述规则计算LiRi 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=R

11、rLr（SW）在加密的最后一轮，为了使算法同时用于加密和解密，略去“左右变换”4)解密 Ri-1=Li Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki),Feistel模型分析,优点,设计容易:F函数不要求可逆,加、解密算法结构相同强度高：如果F函数是随机的,则连续若干圈复合形成的函数与随机置换是无法区分的,缺点,每圈加密时输入有一半没有改变 左右块的加密处理不能并行实施,Feistel模型实现完全性的性能分析,如果对每个密钥k,迭代次数为m的加密变换Ek(x)的每个输入比特的变化都可能会影响到每个输出比特的变化,则称 Ek(x)是完全的意义:实现了Shannon提出的扩散性原则扩散原

12、则(Diffusion)让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响在检验完全性时,无法对所有的密钥都来检验影响的必然性,只好退而求其次,来分析这种可能性,结论,如果Feistel模型的 F函数需要T圈迭代才能实现完全性,则Feistel模型经T+2圈迭代可实现完全性Feistel模型至少需要3圈才可实现完全性DES算法需且只需5圈即可实现完全性,DES特征,分组加密算法：明文和密文为64bit分组长度对称算法：加密和解密除密钥编排不同外，使用同一算法密钥长度：56bit，每个第8位为奇偶校验位，可忽略密钥可为任意的56位数，存在弱密钥，容易避

13、开采用混乱和扩散的组合，每个组合先替代后置换，共16轮只使用了标准的算术和逻辑运算，易于实现,DES示意图,DES的描述,DES加解密过程,令i表示迭代次数，表示逐位模2求和，f为加密函数。,DES中的各种置换、扩展和替代,初始置换IP和初始逆置换IP1,IP和IP1,IP,IP1,DES的一轮迭代,扩展置换-盒32位扩展到48位,扩展,压缩替代S-盒48位压缩到32位,共8个S盒,S-盒1,S-盒2,S-盒3,S-盒4,S-盒5,S-盒6,S-盒7,S-盒8,S-盒的构造,原则：S盒的每一位输出都不是输入的线性或仿射函数,仿射函数 设 f是n元布尔函数,如果则称f 是仿射函数;又若仿射函数满

14、足f(0)=0,则 f 为线性函数.,等价定义:设 f是n元布尔函数,则 f是仿射函数等价于存在常数c1,c2,cn和a使对所有x,都有此时,如果a=0,则 f为线性函数.,仿射函数的缺点:(1)输入与输出之间的代数关系太简单;(2)输入的变化与输出的变化之间的代数关系太简单.仿射函数的优点:实现简单,S-盒,设计标准,S盒的每一位输出都不是输入的线性或仿射函数。S盒的输入发生1比特变化，输出至少有2比特发生变化。当固定S盒的1位输入时，S盒的每一位输出中0和1的个数尽可能平衡。,S-盒的作用,S盒是DES算法中唯一的非线性变换，S盒实现了局部的混乱和扩散；这种局部的混乱和扩散通过E盒和P盒并

15、借助于多次迭代实现了整个密码算法的混乱和扩散 S盒只要稍有改变，其密码强度就会大大降低，因此，不要试图改变一个密码算法中的任何细节,如何全面准确地度量S-盒的密码强度和设计有效的S-盒是分组密码设计和分析中的难题,置换p-盒的构造,P置换的目的是提供雪崩效应,DES中的子密钥的生成,密钥置换算法的构造准则,设计目标：子密钥的统计独立性和灵活性实现简单速度不存在简单关系：给定两个有某种关系的种子密钥,能预测它们轮子密钥之间的关系种子密钥的所有比特对每个子密钥比特的影响大致相同从一些子密钥比特获得其他的子密钥比特在计算上是难的没有弱密钥,目 录DES 加密算法DES加密算法的应用及分析,DES的工

16、作模式,电子密码本 ECB(electronic codebook mode)密码分组链接 CBC(cipher block chaining)密码反馈 CFB(cipher feedback)输出反馈 OFB(output feedback),电子密码本ECB,ECB的特点,简单和有效可以并行实现不能隐藏明文的模式信息 相同明文生成相同密文，同样信息多次出现造成泄漏对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放误差传递：密文块损坏仅对应明文块损坏适合于传输短信息,密码分组链接CBC,对明文施加运算后再加密,CBC的特点,没有已知的并行实现算法能隐藏明文的模式信息 需要共同的初始化

17、向量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,对密钥施加运算后再加密,密码反馈CFB解密,Pi

18、=Ci(EK(Si)的高j位);Si+1=(Sij)|Ci,CFB的特点,没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV误差传递：一个单元损坏影响多个单元,输出反馈OFB,假定：Si 为移位寄存器,传输单位为jbit 加密: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=(Sij)|(EK

19、(Si)的高j位),0FB的特点,没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV误差传递：一个单元损坏只影响对应单元对明文的主动攻击是可能的 信息块可被替换、重排、删除、重放安全性较CFB差,分组密码的强化技术,差分分析（参见实验教程）和线性分析的问世，给DES致命一击，至少从理论上说DES已不再安全为了既不削弱安全性能，又能充分利用现有芯片，密码设计者提出了分组密码的强化思想：密码级联技术多重加密基于单向Hash函数正形置换方法,密码级联技术,本质上说，级联密码是t个相同或不同分组密码的乘积密码，即,其中，是第i 个密码算法的加密函数这里要求各个算法所用的密钥(K1,K2

20、Kt)必须相互独立，这样才能增大密钥长度，进而增强安全性应当指出，某些强度很高的密码体制级联使用，若设计不当很可能使加密效果相互抵消，并且这种级联密码的安全性很难把握，因此我们不提倡使用不同类分组密码进行级联。,多级加密技术,多重加密是密码级联的一种特殊形式，即利用同一算法采用多个相互独立的密钥对明文块依次进行加密，形式上,当t=2时，二重加密易受中间相遇攻击的威胁,三重DES,Tuchman提出了三重加密的思想，在两个不同密钥作用下将加解密算法交叉使用，即,尽管三重加密在二重加密基础上安全性有所改善，但由于仅使用两个密钥，使得攻击的复杂度并没有达到三倍于原算法的效果Merkle和Hellma

21、n提出了一种”时空折衷方法”，可以用2l-1次加密和2l个存贮记录即可破译三重加密，这里l为单个算法的密钥长度,DES的安全性,实际安全性定义,考虑攻击所需的时间和数据量才能准确估计算法的强度，为此可将攻击按计算复杂度进行分类,数据复杂度(Data complexity)即实施攻击所必须的外部输入数据量，以分组长度n为单位，记为Cd处理复杂度(Proceessing complexity)即实施攻击所花费的时间，以加密次数为单位，记为Cp 显然，攻击的复杂度Ca=max(Cd，Cp).,在选择明文攻击下目前对DES的差分攻击的最好结果是,1.强力攻击,在唯密文攻击下，密码分析者依次试用密钥空间

22、中的所有密钥解译一个或多个截获的密文，直至得到一个或多个有意义的明文块在已知(选择)明文攻击下，密码分析者试用密钥空间中的所有可能的密钥对一个已知明文加密，将加密结果同该明文相应的已知密文比较，直至二者相符，然后再用其它几个已知明密文对来验证该密钥的正确性强力攻击适用于任何分组密码,DES密钥攻击,56比特的密钥长度不足以抵御穷举式 256 1017,1977年，Diffie和Hellman已建议制造一个每秒能测试100万个密钥的VLSI芯片。每秒测试100万个密钥的机器大约需要一天就可以搜索整个密钥空间。他们估计制造这样的机器大约需要2000万美元在CRYPTO93上，Session和Wie

23、ner给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。花费10万美元，平均用1.5天左右就可找到DES密钥,美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元1998年7月电子前沿基金会（EFF）使用一台25万美圆的电脑在56小时内破译了56比特密钥的DES1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥,2.差分攻击,也称差分分析，是一种选择明文攻击方法，最早由以色列密

24、码学家Eli Biham和Adi Shamir于1990年提出该方法充分利用了明文对的特殊差分对输出密文对差分的影响，通过分析某个(些)最大概率差分来确定可能密钥的概率并找出最可能的密钥差分分析是目前用于分组密码的最强有力的攻击方法之一，成功地用于攻击DES的复杂度为Ca 247,3.线性攻击,是一种已知明文攻击方法，最早由Matsui在1993年提出该攻击利用了明文、密文和密钥的若干位之间的线性关系。在对DES的线性攻击下，这种线性关系可以通过组合各轮的线性关系而得到(假定各轮子密钥相互独立).此时攻击者希望找到一个等式,使得该等式在密钥空间上成立的概率pl，且|pl-|最大,线性攻击,N个

25、已知明密文对的线性攻击如下:对所有明文p和密文c，令T表示上式左边为0的次数若，猜测，否则猜测 线性分析是攻击分组密码的另一个最强有力的方法，成功地用于攻击DES的复杂度为,4.相关密钥攻击,类似于差分分析，该方法利用密钥差分来攻击分组密码，这是因为Biham证明了许多分组密码的密钥编排算法明显保持了密钥间的关系这种方法与密码体制的轮数和加密函数无关,弱密钥与半弱密钥,弱密钥：若给定的密钥k，k1=k2=k16，则称K为弱密钥半弱密钥：若给定的密钥k,相应的16个子密钥只有两种取值,且每一种都出现8次，则称K为半弱密钥弱密钥:，DES存在4个弱密钥e0e0e0e0f1f1f1f1 fefefefefefefefe半弱密钥:EK1=EK2，至少有12个半弱密钥 即：,5.中间相遇攻击,这是一种适用于多重加密下的已知明文攻击.对DES来说，这种攻击方法需要256次加密，256个存贮记录,作业,完成实验3 DES密码分析实验的课堂实验内容部分给定1个S盒，求它的差分分布矩阵实现DES加密密钥的暴力破解(perl)学习AES加密算法,谢 谢!,