密码技术现代密码学des智能信息安全课件

智能信息安全 Intelligent Information Security,孙松林 北京邮电大学 Email: ,密码技术 现代密码学,1，密码学简介 2，密码系统模型 3，古典密码 4， 对称密钥（单钥）密码体制 5，非对称密钥（公钥）密码体制,现代密码学分类,对称密钥密码(单钥密码) DES 3DES FEAL（快速数据加密算法） IDEA AES 非对称密钥密码(公钥密码/双钥密码) RSA,古典密码学特点,要求的计算强度小 DES之前 以字母表为主要加密对象 置换和代替技术 数据安全基于算法的保密 密码分析方法基于明文的可读性以及字母及其组合的频率特性,密码系统模型,现代密码学中分组密码算法 设计指导原则,Diffusion(发散) 小扰动的影响波及到全局 明文或密钥的一位影响密文的多位，密文没有统计特征 Confusion(混淆) 强调密钥的作用 增加密文与明文及密钥之间关系的复杂性 无法从数学上描述，或从统计上去分析 结构简单、易于分析,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,对称密钥密码的历史,美国国家标准局 (NBS: National Bureau of Standards) 1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准（DES: Data Encryption Standard） 于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。 1975年3月17日DES首次被公布在联邦记录中。,对称密钥密码的历史,1977年1月15日美国政府决定采纳IBM公司设计的方案作为非机密数据的正式数据加密标准DES，被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。 该方案是在1971年，由Horst Feistel领导的IBM密码研究项目组研究出的LUCIFER算法，并已应用于商业领域。,对称密钥密码的历史,规定日后由美国国家保密局（national security agency, NSA）作评估，并重新批准它是否继续作为联邦加密标准。 在1994年1月的评估中，美国决定1998年12月以后将不再使用DES。,对称密钥密码的历史,1997年4月15日，美国NIST (National Institute of Standards and Technology)发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。 此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。 1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。,对称密钥密码的历史,1998年8月12日，在首届AES候选会议（first AES candidate conference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。,对称密钥密码的历史,1999年3月，在第2届AES候选会议（second AES candidate conference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个：RC6、Rijndael、SERPENT、Twofish和MARS。,对称密钥密码的历史,2000年4月13日至14日，召开了第3届AES候选会议（third AES candidate conference），继续对最后5个候选算法进行讨论。 2000年10月2日，NIST宣布Rijndael作为新的AES。,对称密钥密码的历史,Rijndael 由比利时的Joan Daemen和Vincent Rijmen设计，开发者提出以下几种发音供选择“Reign Dahl”，“Rain doll”和 “Rhine Dahl”。,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,DES概述,1973/1974年提出加密算法要达到的目的（通常称为DES 密码算法要求）主要为以下四点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）实现经济，运行有效，并且适用于多种完全不同的应用。,DES概述,1977年由美国的标准化局(NBS，现为NIST)采纳 64位数据分组、56位密钥 历史： IBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥 改进算法，降低为56位密钥，IBM提交给NBS(NIST),4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,Feistel结构图,Feistel结构定义,加密: Li = Ri-1; Ri = Li-1F(Ri-1,Ki) 解密: Ri-1 = Li Li-1 = RiF(Ri-1,Ki) = RiF(Li,Ki),Feistel结构分析,数据分组Block size(64 128) 密钥长度Key size(56 128256) 轮数Number of rounds(16) 该结构的关键: 子密钥Subkey generation F函数Round function(F),Feistel结构优点,易于软硬件实现 结构简单 易于分析,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,S-DES,Simplified DES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。,加密,S-DES方案示意图,IP:Initial Permutation 初始置换 SW:交换函数 P10:10bit置换 P8 : 8bit置换,IP-1*fk2*SW*fk1*IP 也可写为 密文=IP-1（fk2(SW(fk1(IP(明文) 其中 K1=P8(移位(P10(密钥K) K2=P8(移位(移位(P10(密钥K) 解密算法的数学表示： 明文=IP-1（fk1(SW(fk2(IP(密文),S-DES加密算法的数学表示,S-DES,加解密算法涉及五个函数： (1)初始置换IP(initial permutation) (2)复合函数fk1，它由密钥K1确定，具有置换和代换的运算。 (3)交换函数SW (4)复合函数fk2，它由密钥K2确定，具有置换和代换的运算。 (5)初始置换IP的逆置换IP-1,初始置换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,S-DES IP函数,S-DES 复合函数fk,复合函数fk，是加密方案中最重要的部分，它可表示为： fk(L,R)=(LF(R,SK),R) 其中 L、R为8位输入，左右各为4位。 F为从4位集到4位集的一个映射，并不要求是单射。 SK（SubKey）为子密钥，左图中为K1。,IP,E/P,+,S0,S1,P4,+,L,R,4,K1,8,4,4,F,4,fk,S-DES加密图,IP,E/P,+,S0,S1,P4,+,L,R,4,K1,8,4,4,fk,F,4,IP: Initial Permutation初始置换 E/P：扩张/置换 S0、S1：S盒 P4：4bit置换,8bit 明文,2,2,S-DES加密图(续),E/P,+,S0,S1,8,K2,P4,+,IP-1,8-bit 密文,4,8,4,4,fk,F,4,4,2,2,8,SW,SW：交换函数,S-DES F函数,1，E/P（R） 2，与K1异或运算 3，S0，S1 4，P4,E/P,+,S0,S1,P4,R,4,K1,8,4,4,F,2,2,S-DES E/P运算,输入一个4位数（n1,n2,n3,n4），进行扩张/置换（E/P）运算： 4 1 2 3 2 3 4 1 直观表现形式为： n4, n1, n2, n3 n2, n3, n4, n1,S-DES 子密钥异或运算,8-bit子密钥K1=(k11,k12,k13,k14,k15,k16,k17,k18) 与E/P的结果作异或运算得： n4+k11,n1+k12,n2+k13,n3+k14 n2+k15,n3+k16,n4+k17,n1+k18 把它们重记为8位： P0,0 P0,1 P0,2 P0,3 P1,0 P1,1 P1,2 P1,3 上述第一行输入进S盒S0，产生2位的输出； 第二行输入进S盒S1，产生2位的输出。,S-DES S0、S1运算,S盒按下述规则运算： 将第1和第4的输入比特做为2位数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列，如此确定为S盒矩阵的（i,j）数。 例如： （P0,0, P0,3）=(00), (P0,1,P0,2)=(10) 由此确定S0中的第0行2列（0，2） 其系数为3，因此记为（1 1）输出。,S-DES P4置换,1 2 3 4 2 4 3 1,S-DES 密钥的生成,设10bit的密钥为（ k1,k2,k10 ) 置换P10(k1,k2,k10) =(k3,k5,k2,k7,k4,k10,k1,k9,k8,k6) 置换P8 (k1,k2,k10) =(k6,k3,k7,k4,k8,k5,k10,k9 ) LS-1为循环左移1位， LS-2为循环左移2位 例： 按照上述条件，若K选为(1010000010)， 产生的两个子密钥分别为 K1=(1 0 1 0 0 1 0 0) K2=(0 1 0 0 0 0 1 1),5,5,加密,S-DES方案示意图,课堂练习,用S-DES算法对下列明文数据进行加密： Plaintext(8bit): 00010111 密钥10bit，生成规则为班内序号，不足补零！ 如：班内序号为10号，则密钥为0000001010 请写出各步步骤！,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,DES加密过程,如何解密？,DES轮加密的简图,Li=Ri-1 Ri = Li-1F(Ri-1,Ki) i=1,2,16,DES轮加密,S-DES的F函数,1，E/P（R） 2，与K1异或运算 3，S0，S1 4，P4,E/P,+,S0,S1,P4,R,4,K1,8,4,4,F,2,2,DES的关键/重要技术,IP 密钥 F函数,DES算法 IP,DES算法 逆IP,DES算法 IP & 逆IP,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 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,DES算法 IP & 逆IP,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,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,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,61 58 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 5 45 13 53 21 61 29,36 4 44 12 52 20 60 28,34 2 42 10 50 18 58 26,33 1 41 9 49 17 57 25,IP,IP-1,DES算法 密钥,DES算法 密钥,64bit密钥,C0（28bit）,D0（28bit）,循环左移1位,循环左移1位,C1（28bit）,D1（28bit）,循环左移X位,循环左移X位,置换选择2,Ci（28bit）,Di（28bit）,(56bit),(56bit),Ki,K0,(48bit),(48bit),(56bit),PC 置换选择 LS 循环左移,循环左移位数表,DES算法 密钥,DES算法 密钥,PC-1置换,PC-2置换,DES算法 密钥,置换选择1工作过程和作用： 1，64位密钥分为8个字节，每个字节的前7位用于加密过程，第8位是奇偶校验位。置换选择1从64位密钥中去掉这8个奇偶校验位。 2，将其余56位数据打乱重排,DES算法 密钥,将主密钥K顺序地每7bit归为一组，共计8组，每一组都按奇校验在后面补上一个校验bit：0或1。(奇校验：含奇数个“1”则校验位为“0”，含偶数个“1”则校验位为“1”) 这样，K被扩展为一个长是64的比特串K+，可用16位十六进制数表示。 K+由安全信道传送，其带上8个校验比特（分别在第8位、16位、64位）就是为了对传输过程中可能出错进行检测和校对。,置换选择1框图,DES算法 密钥,DES算法 密钥,取16进制明文X： 0123456789ABCDEF 密钥K为： 133457799BBCDFF1 去掉奇偶校验位以二进制形式表示的密钥是 00010010011010010101101111001001101101111011011111111000 应用IP，我们得到： L0=11001100000000001100110011111111 L1=R0=11110000101010101111000010101010 然后进行16轮加密。最后对L16, R16使用IP-1得到密文：85E813540F0AB405,DES算法 密钥,去掉奇偶校验位以二进制形式表示的密钥是 0001001 0011010 0101011 0111100 1001101 1011110 1101111 1111000,其十六进制表示为 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001,密钥K为： 133457799BBCDFF1,DES算法 F函数,Li-1 （32 bit）,Ri-1 （32 bit）,选择扩展运算 E盒,48bit寄存器,48bit寄存器,选择压缩运算 S盒,32bit寄存器,置换运算 P盒,Ri =Li-1f(Ri-1,ki) （32 bit）,（32 bit）,Li =Ri-1,轮开始：64bit分成左右两半,子密钥Ki （48 bit）,DES算法 F函数 E盒 (Expand Box),将输入的32bit块扩展到48bit的输出块； 48bit的输出块再分成8个6bit块；,01 02 03 04,05 06 07 08,09 10 11 12,13 14 15 16,17 18 19 20,21 22 23 24,25 26 27 28,29 30 31 32,01 02 03 04,05 06 07 08,09 10 11 12,13 14 15 16,17 18 19 20,21 22 23 24,25 26 27 28,29 30 31 32,32,04,08,12,16,20,24,28,05,09,13,17,21,25,29,01,E盒,扩展位,扩展位,固定位,DES算法 F函数 S盒 (Substitution Box),48bit块通过S盒压缩成32bit块,48bit寄存器,32bit寄存器,6bit,4bit,共8个S盒,DES算法 F函数,DES算法 F函数,DES算法 F函数,DES算法 F函数,作用：将6个输入位映射为4个输出位； 方法：若定义a1a2a3a4a5a6，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。 S1盒输入为101011的输出是？,（11）第3行 （0101）第5列 表内数据为13 输出（1101）,DES算法 F函数 P盒（Permutaion）,P置换的目的是：提供雪崩效应（提高Diffusion发散性能）； 明文或密钥的一点小的变动都引起密文的较大变化。,DES算法的几点讨论,盒的由来 S盒 密钥,盒的由来,Shannon在1949 的文章中，介绍了替换-置换网络的思想 (S-P) networks 这种思想形成了现代密码的基础 S-P network 替换-置换乘积密码的现代形式 S-P networks 是基于下列两种最基本的密码运算： 替换（ Substitution ） 置换（ Permutation ）,S-BOX S盒,一个二进制字用其它二进制字替换这种替换函数就构成密码可以看作是一个大的查表运算,P-BOX P盒,二进制字次序被打乱，重新排序的方法构成密码,盒的本质就是空间变换,Shannon 把这两种运算组合在一起，即一些 S-boxes 由 P-box 连接，这种变换叫做混合变换（mixing transformations ）,实际实现,实际中，我们需要加密，也需要解密，因此，有两种方法： 1，定义每个替换、置换的逆，这样增加了复杂度 2，定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密,实际实现,“好的”密码设计具有: 雪崩特性,完备性,不可预料性(avalanche, completeness, unpredictability ) 差的密码设计缺乏随机性,具有太大的可预料性 几乎所有现代分组密码用更小的查表（S盒）合并其他变换（线性变换）模仿这样一个大的随机查表。这种做法实际上是安全性和可接受的复杂性的一个折中。,DES算法 S盒,DES中S盒运算是非线性的，不易于分析，它提供了更好的安全性；所以S盒是算法的关键所在。 提供了密码算法所必需的混乱作用。,S盒的设计原则,1976年，美国NSA披露了S盒的下述几条设计原则： 每个S盒的每一行是整数015的一个全排列； 每个S盒的输出都不是其输入的线性或仿射函数； 改变任一S盒任意1bit的输入，其输出至少有2bit发生变化； 对任一S盒的任意6bit输入x,S(x)与S(x001100)至少有2bit不同； 对任一S盒的任意6bit输入x ，及,0,1，都有S(x)S(x1100) ； 对任一S盒，当它的任一位输入保持不变，其它5位输入随意变化时，所有诸4bit输出中，0与1的总数接近相等。,S盒的问题,S盒的设计原理未知 公众仍然不知道S盒的构造中是否还使用了进一步的设计准则。 密钥长度是否足够？ 迭代的长度？（8、16、32？）,密钥,密钥本身的缺陷 对DES的攻击 差分密码分析 线性密码分析 字典攻击 穷举破译,弱密钥与半弱密钥,弱密钥: EKEK = I 半弱密钥: EK1 = EK2 DES存在4个弱密钥 至少存在12个半弱密钥,差分密码分析,破解DES: 247个选择明文(255个已知明文) 破解Lucifer(18轮128位): 24个选择明文221次计算 DES对差分密码分析的抵抗力很强,线性密码分析,破解DES: 243个已知明文 DES对线性密码分析的抵抗力稍弱,字典攻击,考虑选择明文攻击 DES块大小: 64位, 2641020 计算机能力为100MIPS(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*36001017 1020/1017 = 1000天 适用于任意64位块的加密,穷举破译,DES密钥长度: 56位, 2561017 计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*36001017 1017/1017 = 1天,DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。,密钥搜索机,而56位长的密钥的穷举空间为256，如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近228.5年的时间。 在对DES安全性的批评意见中，较一致的看法是DES的密钥太短！其长度56bit，致使密钥量仅为2561017，不能抵抗穷搜攻击，事实证明的确如此。,1997年1月28日，美国RSA数据安全公司在RSA安全年会上发布了一项“秘密密钥挑战”竞赛，分别悬赏1000美金、5000美金和10000美金用于攻破不同长度的RC5密码算法；同时还悬赏10000美金破译密钥长度为56bit的DES。 RSA公司发起这场挑战赛是为了调查在Internet上分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为56bit的DES算法的相对强度。,结果是：密钥长度为40bit和48bit的RC5算法被攻破；美国克罗拉多州的程序员Verser从1997年3月13日起用了96天的时间，在Internet上数万名志愿者的协同工作下，于1997年6月17日成功地找到了DES的密钥，获得了RSA公司颁发的10000美金的奖励。 这一事件表明，依靠Internet的分布式计算能力，用穷搜方法破译DES已成为可能。因此，随着计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度。,1977年，Diffe和Hellman曾建议制造每秒能测试106个密钥的VLSI芯片，将这样的100104个芯片并行操作搜索完整个密钥空间大约需1天时间。他们估计制造这样一台机器需耗资大约2000万美金。,1993年，Wiener给出了一个详细的设计密钥搜索机的方案。他建议制造每秒能测试5107个密钥的芯片，基于这种芯片的机器将流水作业，使得16次加密同时发生。目前制造这种芯片每片需耗资10.5美金，耗资10万美金能建造一个由5760个芯片组成的框架，这使得搜索一个密钥平均大约需要1.5天。使用十个这样框架的机器将耗资100万美金，搜索一个密钥平均大约3.5小时。,据新华社1998年7月22日消息,电子边境基金学会(EFF)使用一台25万美金的电脑在56小时内破译了56位密钥的DES。,计算能力（软件和硬件）的提高使得DES变的越来越不安全。,Measures of computational efficiency,Could consider Number of additions Number of multiplications Amount of memory required Scalability and regularity For the present discussion well focus most on number of multiplications as a measure of computational complexity More costly than additions for fixed-point processors Same cost as additions for floating-point processors, but number of operations is comparable,,1st: System Name: Jaguar Site: Oak Ridge National Laboratory System Family: Cray XT System Computer: Cray XT5-HE Opteron Six Core 2.6 GHz Vendor: Cray Inc. Processor: AMD x86_64 Opteron Six Core 2600 MHz (10.4 GFlops) Cores: 224162 Rpeak(GFlops): 2331000 Operating System: Linux Rmax(GFlops): 1759000,Rpeak,a theoretical peak performance. It is determined by counting the number of floating-point additions and multiplications (in full precision) that can be completed during a period of time, usually the cycle time of the machine. For example, an Intel Itanium 2 at 1.5 GHz can complete 4 floating point operations per cycle or a theoretical peak performance of 6 GFlop/s.,曙光星云,2nd: System Name: Nebulae Site: National Supercomputing Centre in Shenzhen (NSCS) System Family: Dawning Cluster System Computer: Dawning TC3600 Blade, Intel X5650, NVidia Tesla C2050 GPU Vendor: Dawning Processor: Intel EM64T Xeon X56xx (Westmere-EP), Six Core 2.6 GHz Cores: 120640 Rpeak(GFlops): 2984300 Operating System: Linux Rmax(GFlops): 1271000,天河一号,7th: System Name: TianHe-1 Site: National SuperComputer Center in Tianjin/NUDT System Family: NUDT TH-1 Cluster System Computer: NUDT TH-1 Cluster, Xeon E5540/E5450, ATI Radeon HD 4870 2, Infiniband Vendor: NUDT Processor: Intel EM64T Xeon E55xx (Nehalem-EP), Four Core 2.53 GHz Cores: 71680 Rpeak(GFlops): 1206190 Operating System: Linux Rmax(GFlops): 563100,Sun Songlin,Beijing University of Posts and Telecommunications,98,银河一号,1983年12月22日国防科大，中国第一台每秒钟运算一亿次以上的巨型计算机 1993年，中国第一台10亿次巨型银河计算机型通过鉴定。 1994年，在国家气象局投入正式运行，用于天气中期预报。,China,24/500 两所高校：吉林大学、南京大学,Asia,Japan： 18/500 Russia： 11/500 India: 5/500 Hong Kong、South Korea 1/500,Euro.,United Kingdom: 38/500 Germany： 24/500 5th Germany France: 27/500,United States,7/10 282/500 Vendors (10): IBM: 196 39.20 % HP: 186 37.20 % Cray: 21 4.20 % SGI: 17 3.40 % Dell: 17 3.40 % Sun: 12 2.40 %,OS Family: Linux 455 91.00 % Unix 22 4.40 % Windows 5 1.00 % Processor Family: Intel EM64T 401 80.20 % AMD x86_64 49 9.80 % Power 42 8.40 %,Whose Apple？,Computation,什么是计算？ 根据图灵的研究，直观地说所谓计算就是计算者人或机器对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。 The purpose of computing is insight，not numbers -Richard Wesley Hamming,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,DES危机,计算能力（软件和硬件）的提高使得DES变的越来越不安全。 如何解决？,多重DES,为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。 二重DES（Double DES） 三重DES（Triple DES）,多重DES,使用三个或两个不同的密钥对数据块进行三次或两次加密，加密一次要比进行普通加密的三次要快，三重DES的强度大约和168bit的密钥强度相当。 三重DES有四种模型： 1，DES-EEE3 使用三个不同密钥顺序进行三次加密变换。 2，DES-EDE3 使用三个不同密钥依次进行加密-解密-加密变换。 3，DES-EEE2 其中密钥K1=K3 顺序进行三次加密变换。 4，DES-EDE2 其中密钥K1=K3 依次进行加密-解密-加密变换。,二重DES,二重DES是多重使用DES时最简单的形式。 其中明文为P，两个加密密钥为K1和K2，密文为C。 解密时，以相反顺序使用两个密钥。 二重DES所用密钥长度为112比特，强度极大地增加。,二重DES,二重DES加密逻辑,二重DES解密逻辑,二重DES加解密,DES解密与加密使用相同的算法，但子密钥的使用顺序相反。,二重DES,二重DES的“BUG”?,假设对任意两个密钥K1和K2，能够找出另一密钥K3，使得 那么，二重DES以至多重DES都没有意义，因为它们与56比特密钥的单重DES等价。,如何解决？,！好在这种假设对DES并不成立！,为什么？ 如何说明（证明）？ 明文密文 密钥,明文与密文的映射空间,将DES加密过程64比特分组到64比特分组的映射看作一个置换，如果考虑264个所有可能的输入分组，则密钥给定后，DES的加密将把每个输入分组映射到一个唯一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对264个输入分组，总映射个数为 。,密钥,另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为2561017。 因此，可验证用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中。 这一假定已于1992年被证明。所以使用二重DES产生的映射不会等价于单重DES加密。,二重（多重）DES因此就安全了吗？,对二重DES有一种称为中途相遇攻击(meet-in-the-middle)的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下：,二重DES加解密,DES解密与加密使用相同的算法，但子密钥的使用顺序相反。,二重DES,二重DES的中途攻击,如果有 那么,中途攻击步骤,如果已知一个明文密文对(P,C)，攻击的实施可如下进行： （1）首先，用256个所有可能的K1对P加密，将加密结果存入一表并对表按X排序； （2）然后用256个所有可能的K2对C解密，在上述表中查找与C解密结果相匹配的项； （3）如果找到，则记下相应的K1和K2。 （4）最后再用一新的明文密文对(P,C)检验上面找到的K1和K2，用K1和K2对P两次加密，若结果等于C，就可确定K1和K2是所要找的密钥。,有了密码,信息就安全了吗?,客户C要银行B把￥1M转到商家D的账上,假定C与B之间使用加密算法足够安全,共享密钥KCB只有双方知道, C信任B,转账过程为： CB: KCB(Hi,我是C) BC: KCB(Hi,我是银行) CB: KCB(我要转账到D) BC: KCB(OK,转多少?) CB: KCB(￥1M) BC: KCB(OK,已经转账完毕) 上述方案是否有漏洞？,有了密码,信息就安全了吗?,客户C与银行B的认证： CB: C,RC BC: RB,KCB(RC) CB: KCB(RB) .,有了密码,信息就安全了吗?,客户C与银行B认证的攻击： AB: C,RA BA: RB,KCB(RA) AB: KCB(RB) A=B: C,RB B=A: RB2,KCB(RB) A=B: KCB(RB) .,中途攻击的可能性分析,对已知的明文P，二重DES能产生264个可能的密文，而可能的密钥个数为2112，所以平均来说，对一个已知的明文，有2112/264=248个密钥可产生已知的密文（3.55e-15）（误警次数极多）。 再经过另外一对明文密文的检验，误报率将下降到248-64=2-16。所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为1-2-16（99.998%）（误警次数极少） 。,抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密，从而可使已知明文攻击的代价增加到2112。 然而，这样又会使密钥长度增加到563=168比特，因而过于笨重。 一种实用的方法是仅使用两个密钥做3次加密，实现方式为加密|解密|加密，简记为EDE( encryptdecryptencrypt) 此方案在密钥管理标准ANSI X.917和ISO 8732中被采用,两个密钥的三重DES,两个密钥的三重DES,加密,解密,K1,P,C,两个密钥的三重DES加密逻辑,两个密钥的三重DES解密逻辑,K2,解密,K1,B,A,解密,加密,K1,C,P,K2,解密,K1,B,A,三个密钥的三重DES,三个密钥的三重DES密钥长度为168比特，加密方式为 令K3=K2或K1=K2，则变为一重DES。 三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用。,三个密钥的三重DES,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,FEAL快速数据加密算法,由日本学者清水明宏和宫口庄司在DES的基础上提出。 FEAL与DES相比的特点： 增大了有效密钥长度； 增强了密钥的控制作用； 增大了加密函数f的复杂性； 减少了迭代次数。,FEAL与DES的技术异同,都是单密钥分组密码，分组长度为64位 密钥均是64位，但DES密钥中包含8位奇偶校验位，有效密钥为56位，因此FEAL的抗穷举性能大大提高 DES的初始置换和逆初始置换与密钥无关，FEAL的初始变换和末尾变换均受密钥控制，从而提高了保密性,FEAL与DES的技术异同,DES使用的变换主要是置换、代替和模2加，非线性由S盒提供；FEAL使用的变换主要是循环移位、模256加和模2加，非线性由S函数提供 DES迭代次数为16，FEAL迭代次数为4，因而FEAL软件实现速度更快 FEAL不使用置换、代替变换，因此在硬件实现中可省去大量存储器 FEAL的密钥长度仍然不够，且迭代次数也少了一些,4. 对称密钥密码体制,对称密钥密码的历史 DES DES概述 Feistel结构图 S-DES DES 多重DES FEAL IDEA AES,IDEA简介,Xuejia Lai和James Massey（瑞士）于1990年在EuroCrypt90年会上公布了IDEA密码算法第一版，称为PES(Proposed Encryption Standard)。 为抗击差分密码攻击，他们在EuroCrypt91年会上增强了算法的强度，称为IPES（Improved PES),1992年改名为IDEA（International Data Encryption Algorithm，国际数据加密算法），并完成了商品化，由瑞士的Ascom公司注册专利，以商业目的使用IDEA算法必须向该公司申请许可。,IDEA简介,IDEA是一个分组长度为64位的分组密码算法，密钥长度为128位（抗强力攻击能力比DES强），同一算法既可加密也可解密。 IDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快） 从理论上讲，IDEA属于“强”加密算法，至今还没有出现对该算法的有效攻击算法。,IDEA简介,实现上的考虑 使用子分组：16bit的子分组； 使用简单操作（易于加法、移位等操作实现） 加密解密过程类似； 规则的结构（便于VLSI实现）。,IDEA加密和解密框图,IDEA加密的总体方案图,循环2,循环8,循环1,输出变换,64位密文,64位明文,Z1,Z6,Z7,Z12,Z43,Z48,Z49,Z52,子密钥生成器,128位密钥,Z1,Z52,16,IDEA的密钥,56个16bit的子密钥从128bit的密钥中生成 前8个子密钥直接从密钥中取出； 对密钥进行25bit的循环左移，接下来的密钥就从中取出； 重复进行直到52个子密钥都产生出来。,IDEA的解密,加密解密实质相同，但使用不同的密钥； 解密密钥以如下方法从加密子密钥中导出： 解密循环I的头4个子密钥从加密循环10I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元； 对前8个循环来说，循环I的最后两个子密钥等于加密循环9I的最后两个子密钥；,异或运算（ ） 整数模216加（ + ） 整数模216+1乘（ ）(IDEA的S盒） 扩散由称为MA结构的算法基本构件提供。,F2,F1,Z5,G1,G2,IDEA运算,IDEA算法的扩散主要是由乘加结构的基本单元实现的。,IDEA的MA结构,IDEA分组密码的特点,可变密钥长度 混合操作 依赖数据的循环移位 依赖于密钥的循环移位 依赖S盒子 冗长的密钥调度算法 可变的F函数和可变的明文/密文长度 可变的循环次数 在每次循环中都对两半数据进行操作,4. 对称密钥密码体制,对称密钥密码的历史 DES FEAL IDEA AES AES的产生 Rijndael简介,从各方面来看，DES已走到了它生命的尽头。其56比特密钥实在太小，虽然三重DES可以解决密钥长度的问题，但是DES的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这种情况下，它的效率相对较低。 鉴于此，1997年4月15日美国国家标准和技术研究所（NIST）发起征集AES（AESAdvanced Encryption Standard）算法的活动，并成立了AES工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。,AES的产生背景,AES的产生,对AES的基本技术要求是： 比三重DES快 至少与三重DES一样安全 数据分组长度为128比特 密钥长度为128/192/256比特。,AES的评选方法 1.用量化的或定性的尺度作为选择的标准； 2.选择一种以上的算法； 3.选择一个备用算法； 4.考虑公众的建议以改进算法。,AES的产生,AES的产生,AES评选历程 1997年NIST宣布征集AES算法 1998年确定第一轮15个候选者 1999年确定第二轮五个候选者: MARS, RC6, Rijndael, Serpent, Twofish 2000年底Rijndael胜出,NIST主任Ray Kammer在马里兰召开的新闻发布会上说之所以选中Rijndael，是因为它