Security-04-密码技术-现代密码学-DES-智能信息安全课件

智能信息安全

IntelligentInformationSecurity孙松林北京邮电大学

Email: slsun@智能信息安全

IntelligentInformatio密码技术–

现代密码学1，密码学简介2，密码系统模型3，古典密码4，对称密钥（单钥）密码体制5，非对称密钥（公钥）密码体制密码技术–现代密码学1，密码学简介现代密码学分类对称密钥密码(单钥密码)DES－3DESFEAL（快速数据加密算法）IDEAAES非对称密钥密码(公钥密码/双钥密码)RSA现代密码学分类对称密钥密码(单钥密码)古典密码学特点要求的计算强度小DES之前以字母表为主要加密对象置换和代替技术数据安全基于算法的保密密码分析方法基于明文的可读性以及字母及其组合的频率特性古典密码学特点要求的计算强度小密码系统模型密码系统模型现代密码学中分组密码算法

设计指导原则Diffusion(发散)小扰动的影响波及到全局明文或密钥的一位影响密文的多位，密文没有统计特征Confusion(混淆)强调密钥的作用增加密文与明文及密钥之间关系的复杂性无法从数学上描述，或从统计上去分析结构简单、易于分析现代密码学中分组密码算法

设计指导原则Diffusion(发4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史对称密钥密码的历史美国国家标准局(NBS:NationalBureauofStandards)1973年开始研究除国防部外的其它部门的计算机系统的数据加密标准（DES:DataEncryptionStandard）于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。1975年3月17日DES首次被公布在联邦记录中。对称密钥密码的历史美国国家标准局(NBS:Nationa对称密钥密码的历史1977年1月15日美国政府决定采纳IBM公司设计的方案作为非机密数据的正式数据加密标准DES，被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。该方案是在1971年，由HorstFeistel领导的IBM密码研究项目组研究出的LUCIFER算法，并已应用于商业领域。对称密钥密码的历史1977年1月15日美国政府决定采纳IBM对称密钥密码的历史规定日后由美国国家保密局（nationalsecurityagency,NSA）作评估，并重新批准它是否继续作为联邦加密标准。在1994年1月的评估中，美国决定1998年12月以后将不再使用DES。对称密钥密码的历史规定日后由美国国家保密局（nationa对称密钥密码的历史1997年4月15日，美国NIST(NationalInstituteofStandardsandTechnology)发起征集AES（advancedencryptionstandard）的活动，并为此成立了AES工作小组。此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。1997年9月12日，美国联邦登记处公布了正式征集AES候选算法的通告。对称密钥密码的历史1997年4月15日，美国NIST(Na对称密钥密码的历史1998年8月12日，在首届AES候选会议（firstAEScandidateconference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。对称密钥密码的历史1998年8月12日，在首届AES候选会议Security_04_密码技术-现代密码学-DES-智能信息安全课件对称密钥密码的历史1999年3月，在第2届AES候选会议（secondAEScandidateconference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个：RC6、Rijndael、SERPENT、Twofish和MARS。对称密钥密码的历史1999年3月，在第2届AES候选会议（s对称密钥密码的历史2000年4月13日至14日，召开了第3届AES候选会议（thirdAEScandidateconference），继续对最后5个候选算法进行讨论。2000年10月2日，NIST宣布Rijndael作为新的AES。对称密钥密码的历史2000年4月13日至14日，召开了第3届对称密钥密码的历史Rijndael由比利时的JoanDaemen和VincentRijmen设计，开发者提出以下几种发音供选择“ReignDahl”，“Raindoll”和“RhineDahl”。对称密钥密码的历史Rijndael由比利时的JoanDa4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史DES概述1973/1974年提出加密算法要达到的目的（通常称为DES密码算法要求）主要为以下四点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）实现经济，运行有效，并且适用于多种完全不同的应用。DES概述1973/1974年提出加密算法要达到的目的（通常DES概述1977年由美国的标准化局(NBS，现为NIST)采纳64位数据分组、56位密钥历史：IBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥改进算法，降低为56位密钥，IBM提交给NBS(NIST)DES概述1977年由美国的标准化局(NBS，现为NIST)4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史Feistel结构图Feistel结构图Feistel结构定义加密:Li=Ri-1;Ri=Li-1F(Ri-1,Ki)解密:Ri-1=LiLi-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel结构定义加密:Li=Ri-1;RiFeistel结构分析数据分组Blocksize(64128)密钥长度Keysize(56128~256)轮数Numberofrounds(16)该结构的关键:子密钥SubkeygenerationF函数Roundfunction(F)Feistel结构分析数据分组Blocksize(64Feistel结构优点易于软硬件实现结构简单易于分析Feistel结构优点易于软硬件实现4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史S-DESSimplifiedDES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。S-DESSimplifiedDES方案，简称S-DES方

加密S-DES方案示意图10bit密钥

解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1IP:InitialPermutation

初始置换SW:交换函数P10:10bit置换P8:8bit置换加密S-DES方案示意图10bit密钥解密8biIP-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加密算法的数学表示IP-1*fk2*SW*fk1*IP

也可写为

密文=IP-S-DES加解密算法涉及五个函数：

(1)初始置换IP(initialpermutation)

(2)复合函数fk1，它由密钥K1确定，具有置换和代换的运算。 (3)交换函数SW

(4)复合函数fk2，它由密钥K2确定，具有置换和代换的运算。 (5)初始置换IP的逆置换IP-1S-DES加解密算法涉及五个函数：

(1)初始置换IP(in初始置换IP函数:IP=12345678 26314857

末端算法的置换为IP的逆置换:

IP-1=1234567841357286

易见IP-1(IP(X))=XS-DES－－IP函数初始置换IP函数:S-DES－－IP函数S-DES－－复合函数fk 复合函数fk，是加密方案中最重要的部分，它可表示为：

fk(L,R)=(LF(R,SK),R)其中

L、R为8位输入，左右各为4位。

F为从4位集到4位集的一个映射，并不要求是单射。

SK（SubKey）为子密钥，左图中为K1。IPE/P+S0S1P4+LR4K1844F4fkS-DES－－复合函数fk 复合函数fk，是加密方案S-DES加密图IPE/P+S0S1P4+LR4K1844fkF4IP:InitialPermutation初始置换E/P：扩张/置换S0、S1：S盒P4：4bit置换8bit明文22S-DES加密图IPE/P+S0S1P4+LR4K1844fS-DES加密图(续)

E/P+S0S18K2P4+IP-18-bit密文4844fkF44228SWSW：交换函数S-DES加密图(续) E/P+S0S18K2P4+IP-S-DES－－F函数1，E/P（R）2，与K1异或运算3，S0，S14，P4E/P+S0S1P4R4K1844F22S-DES－－F函数1，E/P（R）E/P+S0SS-DES－－E/P运算 输入一个4位数（n1,n2,n3,n4），进行扩张/置换（E/P）运算：

41232341

直观表现形式为：

n4,n1,n2,n3 n2,n3,n4,n1S-DES－－E/P运算 输入一个4位数（n1,n2S-DES－－子密钥异或运算

8-bit子密钥K1=(k11,k12,k13,k14,k15,k16,k17,k18)与E/P的结果作异或运算得：n4+k11,n1+k12,n2+k13,n3+k14n2+k15,n3+k16,n4+k17,n1+k18把它们重记为8位：P0,0P0,1P0,2P0,3P1,0P1,1P1,2P1,3

上述第一行输入进S盒S0，产生2位的输出； 第二行输入进S盒S1，产生2位的输出。S-DES－－子密钥异或运算 8-bit子密钥K1=(kS-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，因此记为（11）输出。S-DES－－S0、S1运算S盒按下述规则运算：S-DES－－P4置换1 2 3 42 4 3 1S-DES－－P4置换1 2 3 4S-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=(10100100) K2=(01000011)P10LS-1LS-1LS-2LS-2P8P8K18K25555855S-DES－－密钥的生成设10bit的密钥为（k1

加密S-DES方案示意图10bit密钥

解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1加密S-DES方案示意图10bit密钥课堂练习用S-DES算法对下列明文数据进行加密：Plaintext(8bit):00010111密钥10bit，生成规则为班内序号，不足补零！如：班内序号为10号，则密钥为0000001010请写出各步步骤！课堂练习用S-DES算法对下列明文数据进行加密：4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史DES加密过程如何解密？DES加密过程如何解密？DES轮加密的简图

Li=Ri-1 Ri=Li-1F(Ri-1,Ki) i=1,2,…,16Li-1Ri-1F+LiRiKiDES轮加密的简图 Li=Ri-1Li-1Ri-1DES轮加密DES轮加密S-DES的F函数1，E/P（R）2，与K1异或运算3，S0，S14，P4E/P+S0S1P4R4K1844F22S-DES的F函数1，E/P（R）E/P+S0S1P4R4KDES的关键/重要技术IP密钥F函数DES的关键/重要技术IPDES算法－－IPDES算法－－IPDES算法－－逆IPDES算法－－逆IPDES算法－－IP&逆IP5850423426181026052443628201246254463830221466456484032241685749413325179159514335271911361534537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输入的第58位作为第1位输入的第50位作为第2位输入的第42位作为第3位输入的第40位作为第1位输入的第8位作为第2位输入的第48位作为第3位DES算法－－IP&逆IP585042DES算法－－IP&逆IP123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555612345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565850423426181026052443628201246254463830221466456484032241685749413325179161584537292113563554739312315740848165624643239747155523633138646145422623037545135321612936444125220602834242105018582633141949175725IPIP-1DES算法－－IP&逆IP12DES算法－－密钥KPC-1C0D0LS1LS1C1D1LS2LS2PC-2K1C2D2LS3LS3PC-2K2DES算法－－密钥KPC-1C0D0LS1LS1C1DES算法－－密钥64bit密钥置换选择1（PC1）C0（28bit）D0（28bit）循环左移1位循环左移1位C1（28bit）D1（28bit）循环左移X位循环左移X位置换选择2置换选择2Ci（28bit）Di（28bit）(56bit)(56bit)Ki

K0

(48bit)(48bit)(56bit)PC－－置换选择LS－－循环左移DES算法－－密钥64bit密钥置换选择1（PC1）循环左移位数表迭代次数循环左移位数迭代次数循环左移位数119121102321124212252132621427215282161DES算法－－密钥循环左移位数表迭代次数循环左移位数迭代次数循环左移位数119DES算法－－密钥574941332517915850423426181025951433527191136052443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374755304051453348444939563453464250362932PC-1置换PC-2置换DES算法－－密钥57494133251791585DES算法－－密钥置换选择1工作过程和作用：1，64位密钥分为8个字节，每个字节的前7位用于加密过程，第8位是奇偶校验位。置换选择1从64位密钥中去掉这8个奇偶校验位。2，将其余56位数据打乱重排DES算法－－密钥置换选择1工作过程和作用：DES算法－－密钥将主密钥K顺序地每7bit归为一组，共计8组，每一组都按奇校验在后面补上一个校验bit：0或1。(奇校验：含奇数个“1”则校验位为“0”，含偶数个“1”则校验位为“1”)这样，K被扩展为一个长是64的比特串K+，可用16位十六进制数表示。K+由安全信道传送，其带上8个校验比特（分别在第8位、16位、…、64位）就是为了对传输过程中可能出错进行检测和校对。DES算法－－密钥将主密钥K顺序地每7bit归为一组置换选择1框图DES算法－－密钥置换选择1框图DES算法－－密钥DES算法－－密钥取16进制明文X：0123456789ABCDEF密钥K为：133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000应用IP，我们得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010然后进行16轮加密。最后对L16,R16使用IP-1得到密文：85E813540F0AB405DES算法－－密钥取16进制明文X：01234DES算法－－密钥去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000其十六进制表示为0001001100110100010101110111100110011011101111001101111111110001密钥K为：133457799BBCDFF1DES算法－－密钥去掉奇偶校验位以二进制形式表示的密DES算法－－F函数Li-1

（32bit）Ri-1

（32bit）选择扩展运算E盒48bit寄存器48bit寄存器选择压缩运算S盒32bit寄存器置换运算P盒Ri=Li-1⊕f(Ri-1,ki)

（32bit）（32bit）⊕⊕Li

=Ri-1轮开始：64bit分成左右两半子密钥Ki

（48bit）DES算法－－F函数Li-1（32bit）Ri-1DES算法－－F函数

E盒(ExpandBox)将输入的32bit块扩展到48bit的输出块；48bit的输出块再分成8个6bit块；0102030405060708091011121314151617181920212223242526272829303132010203040506070809101112131415161718192021222324252627282930313232040812162024280509131721252901E盒扩展位扩展位固定位DES算法－－F函数

E盒(ExpandBox)将输DES算法－－F函数

S盒(SubstitutionBox)48bit块通过S盒压缩成32bit块48bit寄存器32bit寄存器

S1S2S3S4S5S6S7S86bit4bit共8个S盒DES算法－－F函数

S盒(SubstitutionDES算法－－F函数S1盒1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S2盒1518146113497213120510313471528141201106911501471110413158126932151381013154211671205149DES算法－－F函数S1盒144131DES算法－－F函数S3盒1009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S4盒7131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S5盒2124171011685315130149141121247131501510398642111101378159125630141181271142136150910453DES算法－－F函数S3盒100914DES算法－－F函数S6盒1211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S7盒4112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S8盒1328461511110931450127115138103741256110149271141912142061013153582114741081315129035611DES算法－－F函数S6盒1211015DES算法－－F函数S1盒1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613S2盒1518146113497213120510313471528141201106911501471110413158126932151381013154211671205149作用：将6个输入位映射为4个输出位；方法：若定义a1a2a3a4a5a6，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。S1盒输入为101011的输出是？？？（11）第3行（0101）第5列表内数据为13输出（1101）DES算法－－F函数S1盒144131DES算法－－F函数

P盒（Permutaion）P置换的目的是：提供雪崩效应（提高Diffusion发散性能）；明文或密钥的一点小的变动都引起密文的较大变化。1607202129122817011523260518311002082414322703091913300622110425DES算法－－F函数

P盒（Permutaion）P置换DES算法的几点讨论盒的由来S盒密钥DES算法的几点讨论盒的由来盒的由来Shannon在1949的文章中，介绍了替换-置换网络的思想(S-P)networks这种思想形成了现代密码的基础S-Pnetwork替换-置换乘积密码的现代形式S-Pnetworks是基于下列两种最基本的密码运算：替换（Substitution）置换（Permutation）盒的由来Shannon在1949的文章中，介绍了替换-置换S-BOXS盒一个二进制字用其它二进制字替换这种替换函数就构成密码可以看作是一个大的查表运算S-BOXS盒一个二进制字用其它二进制字替换这种替换函数P-BOXP盒二进制字次序被打乱，重新排序的方法构成密码P-BOXP盒二进制字次序被打乱，重新排序的方法构成密盒的本质就是空间变换Shannon把这两种运算组合在一起，即一些S-boxes由P-box连接，这种变换叫做混合变换（mixingtransformations）盒的本质就是空间变换Shannon把这两种运算组合在一起，实际实现实际中，我们需要加密，也需要解密，因此，有两种方法：1，定义每个替换、置换的逆，这样增加了复杂度2，定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密实际实现实际中，我们需要加密，也需要解密，因此，有两种方法：实际实现

“好的”密码设计具有:雪崩特性,完备性,不可预料性(avalanche,completeness,unpredictability)差的密码设计缺乏随机性,具有太大的可预料性几乎所有现代分组密码用更小的查表（S盒）合并其他变换（线性变换）模仿这样一个大的随机查表。这种做法实际上是安全性和可接受的复杂性的一个折中。实际实现“好的”密码设计具有:雪崩特性,完备性,不可预料DES算法－－S盒DES中S盒运算是非线性的，不易于分析，它提供了更好的安全性；所以S盒是算法的关键所在。提供了密码算法所必需的混乱作用。DES算法－－S盒DES中S盒运算是非线性的，不易于分析S盒的设计原则1976年，美国NSA披露了S盒的下述几条设计原则：每个S盒的每一行是整数0~15的一个全排列；每个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盒的设计原则1976年，美国NSA披露了S盒的下述几条设计S盒的问题S盒的设计原理未知公众仍然不知道S盒的构造中是否还使用了进一步的设计准则。密钥长度是否足够？迭代的长度？（8、16、32？）S盒的问题S盒的设计原理未知密钥密钥本身的缺陷对DES的攻击差分密码分析线性密码分析字典攻击穷举破译密钥密钥本身的缺陷弱密钥与半弱密钥弱密钥:EKEK=I半弱密钥:EK1=EK2DES存在4个弱密钥至少存在12个半弱密钥弱密钥与半弱密钥差分密码分析破解DES:247个选择明文(255个已知明文)破解Lucifer(18轮128位):24个选择明文＋221次计算DES对差分密码分析的抵抗力很强差分密码分析破解DES:247个选择明文(255个已知明文线性密码分析破解DES:243个已知明文DES对线性密码分析的抵抗力稍弱线性密码分析破解DES:243个已知明文字典攻击考虑选择明文攻击DES块大小:64位,264~1020计算机能力为100MIPS(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*3600~1017 1020/1017=1000天适用于任意64位块的加密字典攻击考虑选择明文攻击穷举破译DES密钥长度:56位,256~1017计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为: 108*10000*24*3600~10171017/1017=1天穷举破译DES密钥长度:56位,256~1017DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。DES算法具有比较高安全性，到目前为止，除了用穷举搜索法对D密钥搜索机而56位长的密钥的穷举空间为256，如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近228.5年的时间。在对DES安全性的批评意见中，较一致的看法是DES的密钥太短！其长度56bit，致使密钥量仅为256≈1017，不能抵抗穷搜攻击，事实证明的确如此。密钥搜索机1997年1月28日，美国RSA数据安全公司在RSA安全年会上发布了一项“秘密密钥挑战”竞赛，分别悬赏1000美金、5000美金和10000美金用于攻破不同长度的RC5密码算法；同时还悬赏10000美金破译密钥长度为56bit的DES。RSA公司发起这场挑战赛是为了调查在Internet上分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为56bit的DES算法的相对强度。1997年1月28日，美国RSA数据安全公司在RSA安全年会结果是：密钥长度为40bit和48bit的RC5算法被攻破；美国克罗拉多州的程序员Verser从1997年3月13日起用了96天的时间，在Internet上数万名志愿者的协同工作下，于1997年6月17日成功地找到了DES的密钥，获得了RSA公司颁发的10000美金的奖励。这一事件表明，依靠Internet的分布式计算能力，用穷搜方法破译DES已成为可能。因此，随着计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度。结果是：密钥长度为40bit和48bit的RC5算法被攻破；1977年，Diffe和Hellman曾建议制造每秒能测试106个密钥的VLSI芯片，将这样的100×104个芯片并行操作搜索完整个密钥空间大约需1天时间。他们估计制造这样一台机器需耗资大约2000万美金。1977年，Diffe和Hellman曾建议制造每秒能测试11993年，Wiener给出了一个详细的设计密钥搜索机的方案。他建议制造每秒能测试5×107个密钥的芯片，基于这种芯片的机器将流水作业，使得16次加密同时发生。目前制造这种芯片每片需耗资10.5美金，耗资10万美金能建造一个由5760个芯片组成的框架，这使得搜索一个密钥平均大约需要1.5天。使用十个这样框架的机器将耗资100万美金，搜索一个密钥平均大约3.5小时。1993年，Wiener给出了一个详细的设计密钥搜索机的方案据新华社1998年7月22日消息,电子边境基金学会(EFF)使用一台25万美金的电脑在56小时内破译了56位密钥的DES。据新华社1998年7月22日消息,电子边境基金学会(EFF)计算能力（软件和硬件）的提高使得DES变的越来越不安全。计算能力（软件和硬件）的提高使得DES变的越来越不安全。MeasuresofcomputationalefficiencyCouldconsiderNumberofadditionsNumberofmultiplicationsAmountofmemoryrequiredScalabilityandregularityForthepresentdiscussionwe’llfocusmostonnumberofmultiplicationsasameasureofcomputationalcomplexityMorecostlythanadditionsforfixed-pointprocessorsSamecostasadditionsforfloating-pointprocessors,butnumberofoperationsiscomparableMeasuresofcomputationaleffi1st:SystemName:JaguarSite:OakRidgeNationalLaboratorySystemFamily:CrayXTSystemComputer:CrayXT5-HEOpteronSixCore2.6GHzVendor:CrayInc.Processor:AMDx86_64OpteronSixCore2600MHz(10.4GFlops)Cores:224162Rpeak(GFlops):2331000OperatingSystem:LinuxRmax(GFlops):17590001st:Rpeakatheoreticalpeakperformance.Itisdeterminedbycountingthenumberoffloating-pointadditionsandmultiplications(infullprecision)thatcanbecompletedduringaperiodoftime,usuallythecycletimeofthemachine.Forexample,anIntelItanium2at1.5GHzcancomplete4floatingpointoperationspercycleoratheoreticalpeakperformanceof6GFlop/s.Rpeakatheoreticalpeakperfor曙光星云2nd:SystemName:NebulaeSite:NationalSupercomputingCentreinShenzhen(NSCS)SystemFamily:DawningClusterSystemComputer:DawningTC3600Blade,IntelX5650,NVidiaTeslaC2050GPUVendor:DawningProcessor:IntelEM64TXeonX56xx(Westmere-EP),SixCore2.6GHz

Cores:120640Rpeak(GFlops):2984300OperatingSystem:LinuxRmax(GFlops):1271000曙光星云2nd:天河一号7th:SystemName:TianHe-1Site:NationalSuperComputerCenterinTianjin/NUDTSystemFamily:NUDTTH-1ClusterSystemComputer:NUDTTH-1Cluster,XeonE5540/E5450,ATIRadeonHD48702,InfinibandVendor:NUDTProcessor:IntelEM64TXeonE55xx(Nehalem-EP),FourCore2.53GHz

Cores:71680Rpeak(GFlops):1206190OperatingSystem:LinuxRmax(GFlops):563100天河一号7th:SunSonglinBeijingUniversityofPostsandTelecommunications98银河一号1983年12月22日国防科大，中国第一台每秒钟运算一亿次以上的巨型计算机1993年，中国第一台10亿次巨型银河计算机Ⅱ型通过鉴定。1994年，在国家气象局投入正式运行，用于天气中期预报。SunSonglinBeijingUniversityChina24/500两所高校：吉林大学、南京大学China24/500AsiaJapan：18/500Russia：11/500India:5/500HongKong、SouthKorea1/500AsiaJapan：Euro.UnitedKingdom:38/500Germany：24/5005thGermanyFrance:27/500Euro.UnitedKingdom:UnitedStates7/10 282/500Vendors(>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%UnitedStates7/10 282/500OSFamily:Linux 455 91.00%Unix 22 4.40%Windows 5 1.00%ProcessorFamily:IntelEM64T 401 80.20%AMDx86_64 49 9.80%Power 42 8.40%OSFamily:WhoseApple？WhoseApple？Computation什么是计算？根据图灵的研究，直观地说所谓计算就是计算者人或机器对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。Thepurposeofcomputingisinsight，notnumbers----RichardWesleyHammingComputation什么是计算？4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史DES危机计算能力（软件和硬件）的提高使得DES变的越来越不安全。如何解决？DES危机计算能力（软件和硬件）的提高使得DES变的越来越不多重DES为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。二重DES（DoubleDES）三重DES（TripleDES）多重DES为了提高DES的安全性，并利用实现DES的现有软硬多重DES 使用三个或两个不同的密钥对数据块进行三次或两次加密，加密一次要比进行普通加密的三次要快，三重DES的强度大约和168bit的密钥强度相当。三重DES有四种模型：1，DES-EEE3使用三个不同密钥顺序进行三次加密变换。2，DES-EDE3使用三个不同密钥依次进行加密-解密-加密变换。3，DES-EEE2其中密钥K1=K3顺序进行三次加密变换。4，DES-EDE2其中密钥K1=K3依次进行加密-解密-加密变换。多重DES 使用三个或两个不同的密钥对数据块进行三次或两次加二重DES二重DES是多重使用DES时最简单的形式。其中明文为P，两个加密密钥为K1和K2，密文为C。解密时，以相反顺序使用两个密钥。二重DES所用密钥长度为112比特，强度极大地增加。二重DES二重DES是多重使用DES时最简单的形式。二重DES加密加密K1K2PC加密加密K2K1CP二重DES加密逻辑二重DES解密逻辑二重DES加密加密K1K2PC加密加密K2K1CP二重DES二重DES加解密DES解密与加密使用相同的算法，但子密钥的使用顺序相反。EEPXC加密EECXP解密二重DES二重DES加解密DES解密与加密使用相同的算法，但子密钥的使二重DES的“BUG”?假设对任意两个密钥K1和K2，能够找出另一密钥K3，使得那么，二重DES以至多重DES都没有意义，因为它们与56比特密钥的单重DES等价。如何解决？二重DES的“BUG”?假设对任意两个密钥K1和K2，能够找！！好在这种假设对DES并不成立！！为什么？如何说明（证明）？－－明文<->密文－－密钥！！好在这种假设对DES并不成立！！为什么？明文与密文的映射空间将DES加密过程64比特分组到64比特分组的映射看作一个置换，如果考虑264个所有可能的输入分组，则密钥给定后，DES的加密将把每个输入分组映射到一个唯一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对264个输入分组，总映射个数为。明文与密文的映射空间将DES加密过程64比特分组到64比特分密钥另一方面，对每个不同的密钥，DES都定义了一个映射，总映射数为256<1017。因此，可验证用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中。这一假定已于1992年被证明。所以使用二重DES产生的映射不会等价于单重DES加密。密钥另一方面，对每个不同的密钥，DES都定义了一个映射，总映二重（多重）DES因此就安全了吗？对二重DES有一种称为中途相遇攻击(meet-in-the-middle)的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下：二重（多重）DES因此就安全了吗？对二重DES有一种称为中途二重DES加解密DES解密与加密使用相同的算法，但子密钥的使用顺序相反。EEPXC加密EECXP解密二重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是所要找的密钥。中途攻击步骤如果已知一个明文密文对(P,C)，攻击的实施可如有了密码,信息就安全了吗?客户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把￥1M转到商家D的有了密码,信息就安全了吗?客户C与银行B的认证：CB:{C,RC}BC:{RB,KCB(RC)}CB:{KCB(RB)}…...有了密码,信息就安全了吗?客户C与银行B的认证：有了密码,信息就安全了吗?客户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)}…...有了密码,信息就安全了吗?客户C与银行B认证的攻击：中途攻击的可能性分析 对已知的明文P，二重DES能产生264个可能的密文，而可能的密钥个数为2112，所以平均来说，对一个已知的明文，有2112/264=248个密钥可产生已知的密文（＝3.55e-15）（误警次数极多）。 再经过另外一对明文密文的检验，误报率将下降到248-64=2-16。所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为1-2-16（＝99.998%）（误警次数极少）。中途攻击的可能性分析 对已知的明文P，二重DES能产生264抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密，从而可使已知明文攻击的代价增加到2112。然而，这样又会使密钥长度增加到56×3=168比特，因而过于笨重。一种实用的方法是仅使用两个密钥做3次加密，实现方式为加密\|解密\|加密，简记为EDE(encryptdecryptencrypt)此方案在密钥管理标准ANSIX.917和ISO8732中被采用抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密，从两个密钥的三重DES两个密钥的三重DES两个密钥的三重DES加密解密K1PC两个密钥的三重DES加密逻辑两个密钥的三重DES解密逻辑K2解密K1BA解密加密K1CPK2解密K1BA两个密钥的三重DES加密解密K1PC两个密钥的三重DES加密三个密钥的三重DES三个密钥的三重DES密钥长度为168比特，加密方式为令K3=K2或K1=K2，则变为一重DES。三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用。三个密钥的三重DES三个密钥的三重DES密钥长度为168比特三个密钥的三重DESEDPAB加密DECBA解密ECDP三个密钥的三重DESEDPAB加密DECBA解密ECDP4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEALIDEAAES4.对称密钥密码体制对称密钥密码的历史FEAL快速数据加密算法由日本学者清水明宏和宫口庄司在DES的基础上提出。FEAL与DES相比的特点：增大了有效密钥长度；增强了密钥的控制作用；增大了加密函数f的复杂性；减少了迭代次数。FEAL快速数据加密算法由日本学者清水明宏和宫口庄司在DESFEAL与DES的技术异同都是单密钥分组密码，分组长度为64位密钥均是64位，但DES密钥中包含8位奇偶校验位，有效密钥为56位，因此FEAL的抗穷举性能大大提高DES的初始置换和逆初始置换与密钥无关，FEAL的初始变换和末尾变换均受密钥控制，从而提高了保密性FEAL与DES的技术异同都是单密钥分组密码，分组长度为64FEAL与DES的技术异同DES使用的变换主要是置换、代替和模2加，非线性由S盒提供；FEAL使用的变换主要是循环移位、模256加和模2加，非线性由S函数提供DES迭代次数为16，FEAL迭代次数为4，因而FEAL软件实现速度更快FEAL不使用置换、代替变换，因此在硬件实现中可省去大量存储器FEAL的密钥长度仍然不够，且迭代次数也少了一些FEAL与DES的技术异同DES使用的变换主要是置换、代替和4.对称密钥密码体制对称密钥密码的历史DESDES概述Feistel结构图S-DESDES多重DESFEAL

IDEAAES4.对称密钥密码体制对称密钥密码的历史IDEA简介XuejiaLai和JamesMassey（瑞士）于1990年在EuroCrypt’90年会上公布了IDEA密码算法第一版，称为PES(ProposedEncryptionStandard)。为抗击差分密码攻击，他们在EuroCrypt’91年会上增强了算法的强度，称为IPES（ImprovedPES)IDEA简介XuejiaLai和JamesMassey（1992年改名为IDEA（InternationalDataEncryptionAlgorithm，国际数据加密算法），并完成了商品化，由瑞士的Ascom公司注册专利，以商业目的使用IDEA算法必须向该公司申请许可。1992年改名为IDEA（InternationalDatIDEA简介IDEA是一个分组长度为64位的分组密码算法，密钥长度为128位（抗强力攻击能力比DES强），同一算法既可加密也可解密。IDEA的“混淆”和“扩散”设计原则来自三种运算，它们易于软、硬件实现（加密速度快）从理论上讲，IDEA属于“强”加密算法，至今还没有出现对该算法的有效攻击算法。IDEA简介IDEA是一个分组长度为64位的分组密码算法，密IDEA简介实现上的考虑使用子分组：16bit的子分组；使用简单操作（易于加法、移位等操作实现）加密解密过程类似；规则的结构（便于VLSI实现）。IDEA简介实现上的考虑IDEA加密和解密框图IDEA加密和解密框图

IDEA加密的总体方案图循环2循环8循环1输出变换64位密文64位明文Z1Z6Z7Z12Z43Z48Z49Z52子密钥生成器128位密钥Z1Z5216IDEA加密的总体方案图循环2循环8循环1输出变换64位

IDEA的密钥

56个16bit的子密钥从128bit的密钥中生成前8个子密钥直接从密钥中取出；对密钥进行25bit的循环左移，接下来的密钥就从中取出；重复进行直到52个子密钥都产生出来。IDEA的密钥 56个16bit的子密钥从128bit的密钥IDEA的解密加密解密实质相同，但使用不同的密钥；解密密钥以如下方法从加密子密钥中导出：解密循环I的头4个子密钥从加密循环10－I的头4个子密钥中导出；解密密钥第1、4个子密钥对应于1、4加密子密钥的乘法逆元；2、3对应2、3的加法逆元；对前8个循环来说，循环I的最后两个子密钥等于加密循环9－I的最后两个子密钥；IDEA的解密加密解密实质相同，但使用不同的密钥；异或运算（）整数模216加（+）整数模216+1乘（）(IDEA的S盒）扩散由称为MA结构的算法基本构件提