《对称密码体制》PPT课件.ppt

第5讲 对称密码体制,主讲：谢 昕,2,课程主要内容,序列密码,数据加密标准DES,分组密码,分组密码运行模式,3,序列密码是一种单钥体制密码，是一种对明文消息字符逐位加密的私钥密码体制。,1 序列密码,4,序列加密变换：ci = mi ki (mod 2)，i 0 序列解密变换: mi = ci ki (mod 2)，i 0,1 序列密码,例：设明文M=(0110010011)2，密钥K=(0111001001)2。在A，B两方通信前，A首先通过安全信道（比如信使）把密钥K送给B，现在要把明文M通过公开信道送给B，加、解密过程如图 。,C=EK(m)=MK=(0110010011)2(0111001001)2=(0001011010) 2,M=DK(C)=CK=(0001011010)2(0111001001)2=(0110010011) 2,5,序列密码体制安全性取决于密钥序列，一个真正具有良好随机特性的密钥序列是设计序列密码的关键。密钥序列依靠秘密信道传送，且最好能与明文序列保持等长。这使得密钥序列的存储、分配和更换变得困难。实际操作中，序列密码是依靠一个短密钥（种子密钥）来产生一个长密钥序列，但此密钥序列不是真正的随机序列，我们称其为伪随机序列。 密钥序列的产生主要是基于移位寄存器。,1 序列密码,6,若t 时刻状态为St =(at , at +1, , at +n 1) 则t +1 时刻状态为St +1 =(at +1 , at +2, , at +n) 其中at +n f (at , at +1, , at +n 1),-线性反馈移位寄存器序列,线性反馈移位寄存器结构模型,7,A5是用于GSM加密的序列密码，它用于加密从电话到基站 的连接，其他部分是不加密的，电话公司很容易窃听用户会话。 A5由三个LFSR组成，寄存器的长度分别是19，22和23。 所有反馈多项式系数都较少，三个LFSR的异或值作为输出。 A5用不同的时针控制。通常，在每一轮中时针驱动两个LFSR。 A5的基本思路很好，效率非常高，能通过所有已知的统计 测试，但因为寄存器太短而不能抗穷举攻击，带较长寄存器和 稠密的反馈多项式的A5变型是安全的。,典型序列密码算法,8,RC4是Ron Rivest在1987年为RSA数据安全公司开发的 可变密钥长度的序列密码。在开始的七年中它有专利，1994年 有人将它的源代码匿名张贴到Cypherpunks邮件列表中。 该代码迅速传到Usenet新闻组，通过互联网传遍了全世界的 ftp站点。RSA数据安全公司试图亡羊补牢，宣称即使代码公开 它仍然是商业秘密，但为时已晚。 RC4描述：密钥序列与明文相互独立。它有一个88的S盒：S0，S1，S255，所有项都是0到255的置换。这个置换是一 个可变长度的密钥的函数。字节k与明文异或得到密文，与密文 异或得到明文。加密速度相当于DES的10倍。,典型序列密码算法,9,根据Rainer Rueppel的理论，可用四种不同的方法来构造 序列密码： 1）系统理论方法。使用一套基本的设计原理和准则，保证 每一个设计对密码分析者来说是一个困难且未知的问题。 2）信息理论方法。使密码分析者不能得到明文。不论密码 分析者做了多少工作，它将永远得不到唯一解。 3）复杂性理论方法。使密码系统基于或等同于一些已知的 难题，比如因式分解或解离散对数。 4）随机性方法。通过迫使密码分析者检测大量无用的数据 来产生一个难于控制的大难题。,序列密码设计的系统理论方法,2 分组密码,分组密码，也称为块密码，它是将明文消息经编码表示后的数字序列划分为若干固定长度的组，每组分别在密钥的控制下转换成等长度的密文分组输出。 分组密码易于构造拟随机数生成器、流密码、消息认证码和杂凑函数等，还可进而成为消息认证技术、数据完整性机构、实体认证协议以及单钥数字签名体制的核心组成部分。,11,2 分组密码,密文仅与给定的密码算法和密钥有关； 与被处理的明文数据段在整个明文（或密文）中所处的位置无关； 总是以大于等于64比特的数据块作为加密单位，给定相同的明文数据块加密后得到相同的密文数据块； 具有代表性的分组加密算法有DES、IDEA 等,分组密码主要特点：,12,2 分组密码,分组密码的设计在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的数字组进行加密变换。,13,（1）要有足够大的分组长度 （2）密钥空间要尽可能大 （3）保证足够强的密码算法复杂度 （4）软件实现尽量采用子块和简单运算 （5）硬件的实现最好加密与解密用相同的结构，以适应用超大规模集成芯片实现,分组密码算法的设计原则,14,置换：设S为一有限集合， 为S到S的一一映射，则 为S上的一个置换。 混淆：将作用于明文的密钥和密文之间的关系复杂化，使明文和密文之间、密文和密钥之间的统计相关性极小化，从而使统计分析攻击法不能奏效。 扩散：将每一位明文及密钥数字的影响尽可能迅速地散布到较多个输出的密文数字中，以便隐蔽明文数字的统计特性。,2 分组密码,15,Feistel结构原理,加密：Li = Ri-1 Ri = Li-1 F(Ri-1，Ki),2 分组密码,16,3 数据加密标准DES,发明人：美国IBM公司W. Tuchman 和 C. Meyer 1971-1972年研制成功。 基础：1967年美国Horst Feistel提出的理论。 产生：美国国家标准局(NBS)于1973年5月到1974年8月两次发布通告，公开征求用于电子计算机的加密算法。经评选从一大批算法中采纳了IBM的LUCIFER方案。 标准化：1975年3月公开发表，1977年1月由NBS颁布为数据加密标准（Data Encryption Standard），于1977年7月15日生效。,DES的背景,17,美国国家安全局（NSA, National Security Agency)参与了美国国家标准局制定数据加密标准的过程。NBS接受了NSA的某些建议，对算法做了修改，并将密钥长度从LUCIFER方案中的128位压缩到56位。 1979年，美国银行协会批准使用DES。 1980年，DES成为美国标准化协会(ANSI)标准。 1984年2月，ISO成立的数据加密技术委员会(SC20)在DES基础上制定数据加密的国际标准工作。,3 数据加密标准DES,18,为二进制编码数据设计的，可以对计算机数据进行密码保护的数学运算。DES算法是对称的，既可用于加密又可用于解密。DES的保密性仅取决于对密钥的保密，而算法是公开的。,64位密钥（56位有效）,3 数据加密标准DES,19,3.1 DES算法基本原理,DES的结构图,20,3.1 DES算法基本原理,Li = Ri-1 Ri = Li-1 F(Ri-1，Ki ),加密：,21,利用传统的换位和置换加密。假定信息空间由0,1组成的 字符串，信息被分成64b的块，密钥是56b。经DES加密的密文也是64比特的块。 明文：m=m1m2m64 mi = 0,1 i = 1,2,64 密钥：k=k1k2k64 ki = 0,1 (i = 1,2,64 ) (其中k8，k16，k64是奇偶校验位，起作用的仅为56位),3.2 DES算法描述,加密算法： Ek(m) = IP-1T16T15T1IP(m) 解密算法： Ek-1 (c) = IP-1T1T2T16IP (c),22,3.2 DES算法描述-初始变换,23,IP 中各列元素位置号数相差为8 ，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后再对各行进行逆序，将阵中元素按行读得的结果。,3.2 DES算法描述-初始变换,1 9 17 25 33 41 49 57 2 10 18 26 34 42 50 58 3 11 19 27 35 43 51 59 4 12 20 28 36 44 52 60 5 13 21 29 37 45 53 61 6 14 22 30 38 46 54 62 7 15 23 31 39 47 55 63 8 16 24 32 40 48 56 64,24,输入64个二进制位明码文数据区组 m= m1m2m64 按初始换位表IP进行换位，得到区组B（0）： B(0)=b1(0)b2(0)b64(0)= m58m50m7 记成L0、R0左右两部分。 逆初始变换用IP-1 表示，它和IP互逆。 例如：第1位经过初始置换后，处于第40位，而通过逆置换，又将第40位换回到第1位,3.2 DES算法描述,25,3.2 DES算法描述-逆初始变换,26,DES迭代过程的核心是非线性F函数的功能，它是每轮实现加密混淆和扩散的主要途径。 每一轮迭代过程都必须经过三个子过程：扩展置换、压缩替换（S盒选择）、P盒排列。,3.2 DES算法描述,27,-迭代过程算法描述,28,- DES 轮函数F的实现原理,扩展置换,子密钥Ki,S盒替代,P盒置换,29,此运算是将数据的右半部分Ri从32b扩展到了48b。由于这个运算改变了位的次序，重复了某些位，故被称为扩展置换。目的：它产生了与密钥同长度的数据以进行异或运算，并提供了更长的结果，使得在替代运算时能进行压缩。,3.2 DES算法描述-扩展置换（E盒）,30,尽管输出分组大于输入分组，但每一个输入分组产生唯一的输出分组。,3.2 DES算法描述-扩展置换（E盒）,扩展置换表,31,每一个S盒都有6位输入，4位输出，且这8个S盒是不同的。48位的输入被分为8个6位的分组，每一分组对应一个S盒替换操作：分组1由S-盒1操作，分组2由S-盒2操作,3.2 DES算法描述-S盒替代,假定将S盒的6位的输入标记为b1b2b3b4b5b6，则 b1b6组合构成了一个2位的数(03)对应表中的一行; b2b3b4b5组合构成了一个4位的数(015) 对应表中的一列。,32,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13,1 0 1 1 0 0,10 2,0 0 1 0,输入6位,输出4位,使用S盒选择的例子,3.2 DES算法描述-S盒替代,33,P盒置换也称直接置换，把每输入位映射到输出位，任意一位不能被映射两次，也不能被略去。,3.2 DES算法描述-P盒置换,最后将P盒置换的结果与最初的64位分组的左半部分异或，然后左、右半部分交换，接着开始另一轮。,34,开始时不考虑每个字节的第8位，DES的密钥由64位减 至56位。每个字节第8位可作为奇偶校验位以确保密钥不发生错误。此过程称为PC-1置换,3.2 DES算法描述-子密钥的生成,压缩置换PC-1表,35,56位密钥被分成两部分(各28位)，然后根据轮数分别循环左移1位或2位。,3.2 DES算法描述-子密钥的生成,循环左移位数表： 轮 位 轮 位 1 1 9 1 2 1 10 2 3 2 11 2 4 2 12 2 5 2 13 2 6 2 14 2 7 2 15 2 8 2 16 1,36,从56位中选出48位。它不仅置换了每位的顺序，同时也选择子密钥，也称这选择置换。删除的8位分别是第9、18、22、25、35、38、43、54位。,3.2 DES算法描述-子密钥的生成,压缩置换PC-2表,37,DES解密过程： 在经过所有的代替、置换、异或和循环移动之后，获得了这样一个非常有用的性质：加密和解密可使用相同的算法。 DES使得用相同的函数来加密或解密每个分组成为可能，二者的唯一不同之处是密钥的次序相反。这就是说，如果各轮的加密密钥分别是K1，K2，K3，K16，那么解密密钥就是K16，K15，K14，K1。,3.2 DES算法描述-解密,38,DES的设计是密码学历史上的一个创新。自从DES问世 至今，对它多次的分析研究，从未发现其算法上的破绽。 利用穷举法搜索攻击，只能说明56位的密钥可能太少，DES的迭代次数可能太少。但直到1998年，电子边境基金会（EFF）动用一台价值25万美元的高速电脑，在56小时内利用穷尽搜索的方法破译56位密钥长度的DES，才证明上述论断。 1982年，已经有办法攻破4次迭代的DES系统了。1985年，对于6次迭代的DES系统也已破译。1990年，以色列学者发明并运用差分分析方法证明，通过已知明文攻击，任何少于16次迭代的DES算法都可以用比穷举法更有效的方法。,3.3 DES的安全性讨论,39,DES的脆弱性： 1）函数构造与作用域 加密强度取决于函数F的复杂度 (S、P)和F的执行次数。 64位固定分组，短组模式，易造成密文重复组块； 有限的函数作用域（ASCII码 0127）； 子密钥只参与异或简单的运算，有可能损害变换精度。 2）迭代问题 无法证明迭代16次最好；在有限的作用域中存在封闭性；迭代次数多不仅费时，还可能被一次简单的变换所代替。,3.3 DES的安全性讨论,40,3）S盒中的重复因子及密钥多值问题 S盒对不同输入可能产生相同输出，使加密、解密变换的密钥具有多值性；子密钥长度48位，只影响32位输出，因此加密强度达不到256，实际只有232x16=236； 4） S盒是精心设计的，其原理至今未公开，其中可能隐藏陷门，它有利于设计者破译密码。 5）提高加密强度（如增加密钥长度），系统开销呈指数增，提高硬件、并行处理外，算法本身和软件技术无法提高加密强度。,3.3 DES的安全性讨论,41,解决密钥长度的问题的办法之一是采用多重DES。 双重DES使用两个长度为56位DES密钥，先用密钥K1进行DES加密，对加密后的密文再使用密钥K2进行DES加密，得到最终密文。双重DES很难抵抗中间相遇攻击。 三重DES使用三个长度为56位DES密钥，先用密钥K1进行DES加密，对加密后的密文再使用密钥K2进行DES解密，最后用密钥K3进行DES加密，得到最终密文。 最常用的三重DES,算法中选取K1 K3 。 （见P34）,3.4 多重DES,42,三重DES是Tuchman提出的，并在1985年成为美国的一个商用加密标准RFC 2420。三重DES使用两个（或三个）密钥，执行三次DES算法。其做法有许多的方式： DES-EEE3、DES-EDE3、DES-EEE2、DES-EDE2,3.4 多重DES-Triple DES,DES-EDE3,43,国际数据加密算法(IDEA)与DES一样，也是一种使用一个 密钥对64位数据块进行加密的单钥加密算法，它是瑞士联邦 技术学院开发的一种面向数据分组块的数据加密标准。 相对于DES的56位密钥，它使用128位密钥，每次加密一个 64位的数据块，这么长的密钥被认为即使在多年后仍是有效的。 IDEA算法通过一系列的加密轮次进行操作，每轮都使用从 完整的加密密钥中生成的一个子密钥，使用一个称为“压码”的 函数在每轮中对数据位进行编码。与DES不同的是IDEA不使用 置换。,3.6 IDEA分组密码,44,IDEA算法简介,IDEA使用128位密钥，在64位明文分组进行加密得到64位密文分组。加密算法的函数在每个分组上运行8个回合。每个回合都包含3个不同运算：异或运算、模加运算和模乘运算。加密与解密也相同，只是密钥各异。 IDEA算法加密速度快，密钥产生方法简单，硬件、软件都能实现。,3.6 IDEA分组密码,45,IDEA算法简介,IDEA的加密运算的回合数虽然比DES的16回合少，但其每一回合的运算复杂度相当于两个回合DES的运算，且其密钥长度为128位，为DES的两倍多，在暴力搜寻攻击法下，其安全性较DES高。但已有研究发现IDEA的2128把密钥中存在有251把的弱密钥，虽然对于整个密钥空间而言还属少数，但在运行时必须小心规避。,3.6 IDEA分组密码,46,IDEA算法的安全性相对DES算法有很大的提高，其密钥是 128位，在穷举攻击的情况下，需要经过2128次加密才能恢复 出密钥。假设一台计算机每秒产生和运行10亿个密钥，它将 检测1013年。 至今IDEA还没有明显的安全漏洞，就连PGP