1、智能信息安全 Intelligent Information Security孙松林孙松林北京邮电大学北京邮电大学 Email:密码技术 现代密码学n1，密码学简介n2，密码系统模型n3，古典密码n4， 对称密钥（单钥）密码体制对称密钥（单钥）密码体制n5，非对称密钥（公钥）密码体制现代密码学分类n 对称密钥密码(单钥密码)nDES 3DESnFEAL（快速数据加密算法）nIDEAnAESn非对称密钥密码(公钥密码/双钥密码)nRSA古典密码学特点n要求的计算强度小nDES之前n以字母表为主要加密对象n置换置换和代替代替技术n数据安全基于算法的保密n密码分析方法基于明文的可读性以及字母及其组合
2、的频率特性密码系统模型现代密码学中分组密码算法设计指导原则nDiffusion(发散)n小扰动的影响波及到全局n明文或密钥的一位影响密文的多位，密文没有统计特征nConfusion(混淆)n强调密钥的作用n增加密文与明文及密钥之间关系的复杂性n无法从数学上描述，或从统计上去分析n结构简单、易于分析4. 对称密钥密码体制n对称密钥密码的历史对称密钥密码的历史nDESnDES概述nFeistel结构图nS-DESnDESn多重DESnFEALnIDEAnAES对称密钥密码的历史n美国国家标准局 (NBS: National Bureau of Standards) 1973年开始研究除国防部外的其
3、它部门的计算机系统的数据加密标准（DES: Data Encryption Standard）n于1973年5月15日和1974年8月27日先后两次向公众发出了征求加密算法的公告。n1975年3月17日DES首次被公布在联邦记录中。对称密钥密码的历史n1977年1月15日美国政府决定采纳IBM公司设计的方案作为非机密数据的正式数据加密标准DES，被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。n该方案是在1971年，由Horst Feistel领导的IBM密码研究项目组研究出的LUCIFER算法，并已应用于商业领域。对称密钥密码的历史n 规定日后由美国国家保密局
4、（national security agency, NSA）作评估，并重新批准它是否继续作为联邦加密标准。n在1994年1月的评估中，美国决定1998年12月以后将不再使用DES。对称密钥密码的历史n1997年4月15日，美国NIST (National Institute of Standards and Technology)发起征集AES（advanced encryption standard）的活动，并为此成立了AES工作小组。n此次活动的目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，以作为新的数据加密标准。n1997年9月12日，美国联邦登记处公布了正式
5、征集AES候选算法的通告。对称密钥密码的历史n1998年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。对称密钥密码的历史n1999年3月，在第2届AES候选会议（second AES candidate conference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，
6、从15个候选算法中选出了5个：RC6、Rijndael、SERPENT、Twofish和MARS。对称密钥密码的历史n2000年4月13日至14日，召开了第3届AES候选会议（third AES candidate conference），继续对最后5个候选算法进行讨论。n2000年10月2日，NIST宣布Rijndael作为新的AES。对称密钥密码的历史nRijndael 由比利时的Joan Daemen和Vincent Rijmen设计，开发者提出以下几种发音供选择“Reign Dahl”，“Rain doll”和 “Rhine Dahl”。4. 对称密钥密码体制n对称密钥密码的历史nDE
7、SnDES概述概述nFeistel结构图nS-DESnDESn多重DESnFEAL nIDEAnAESDES概述n1973/1974年提出加密算法要达到的目的（通常称为DES 密码算法要求）主要为以下四点： （1）提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的修改； （2）具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握； （3）DES密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础； （4）实现经济，运行有效，并且适用于多种完全不同的应用。 DES概述n1977年由美国的标准化局(NBS，现为NIST)采纳n64位数据分组、56位
8、密钥n历史：nIBM在60年代启动了LUCIFER项目，当时的算法采用128位密钥n改进算法，降低为56位密钥，IBM提交给NBS(NIST)4. 对称密钥密码体制n对称密钥密码的历史nDESnDES概述nFeistel结构图结构图nS-DESnDESn多重DESnFEAL nIDEAnAESFeistel结构图Feistel结构定义u加密加密: Li = Ri-1; Ri = Li-1 F(Ri-1,Ki)u解密解密: Ri-1 = Li Li-1 = Ri F(Ri-1,Ki) = Ri F(Li,Ki)Feistel结构分析n数据分组数据分组Block size(64 128)n密钥长度
9、密钥长度Key size(56 128256)n轮数轮数Number of rounds(16)该结构的关键该结构的关键:n子密钥子密钥Subkey generationn F函数函数Round function(F)Feistel结构优点n易于软硬件实现n结构简单n易于分析4. 对称密钥密码体制n对称密钥密码的历史nDESnDES概述nFeistel结构图nS-DESnDESn多重DESnFEAL nIDEAnAESS-DESnSimplified DES方案，简称S-DES方案。它是一个供教学而非安全的加密算法，它与DES的特性和结构类似，但参数小。 加密加密S-DES方案示意图10bit
10、密钥 解密解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18bit密文8bit密文K2K2K1K1nIP:Initial Permutation 初始置换nSW:交换函数nP10:10bit置换nP8 : 8bit置换nIP-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加密算法的数学表示S-DESn加解密算法涉及五个函数：加解密算法涉及五个函数
11、：(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)=XS-DES IP函数S-DES 复合函数fk复合函数fk，是加密方案中最重要的部分，它可表示为：fk(L,R)=(LF(R,SK),R
12、)其中L、R为8位输入，左右各为4位。F为从4位集到4位集的一个映射，并不要求是单射。SK（SubKey）为子密钥，左图中为K1。IPE/P+S0S1P4+LR4K1844F4fkS-DES加密图IPE/P+S0S1P4+LR4K1844fkF4nIP: Initial Permutation初始置换nE/P：扩张/置换nS0、S1：S盒nP4：4bit置换8bit 明文明文22S-DES加密图(续)E/P+S0S18K2P4+IP-18-bit 密文密文4844fkF44228SWnSW：交换函数S-DES F函数n1，E/P（R）n2，与K1异或运算n3，S0，S1n4，P4E/P+S0S
13、1P4R 4K1844F22S-DES E/P运算输入一个4位数（n1,n2,n3,n4），进行扩张/置换（E/P）运算： 4 1 2 3 2 3 4 1 直观表现形式为：n4, n1, n2, n3n2, n3, n4, n1S-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,0 P0,1 P0,2 P0,3P1,0 P1,1 P1,2 P1,3上述第一行输入进S盒S0，
14、产生2位的输出； 第二行输入进S盒S1，产生2位的输出。S-DES S0、S1运算2313312001232301321032100S3012010331023210321032101SS盒按下述规则运算：将第1和第4的输入比特做为2位数，指示为S盒的一个行；将第2和第3的输入比特做为S盒的一个列，如此确定为S盒矩阵的（i,j）数。n例如：（P0,0, P0,3）=(00), (P0,1,P0,2)=(10)由此确定S0中的第0行2列（0，2） 其系数为3，因此记为（1 1）输出。S-DES P4置换12342431S-DES 密钥的生成设10bit的密钥为（ k1,k2,k10 )置换P10
15、(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)P10LS-1LS-1LS-2LS-2P8P8K18K25555855 加密加密S-DES方案示意图10bit密钥 解密解密8bit明文P108bit明文IP移位IP-1P8fkfkSWSW移位P8fkfkIPIP-18
16、bit密文8bit密文K2K2K1K1课堂练习n用S-DES算法对下列明文数据进行加密：nPlaintext(8bit): 00010111 n密钥10bit，生成规则为班内序号，不足补零！n如：班内序号为10号，则密钥为0000001010n请写出各步步骤！4. 对称密钥密码体制n对称密钥密码的历史nDESnDES概述nFeistel结构图nS-DESnDESn多重DESnFEAL nIDEAnAESDES加密过程如何解密？如何解密？DES轮加密的简图Li=Ri-1Ri = Li-1F(Ri-1,Ki) i=1,2,16Li-1 Ri-1F+Li RiKiDES轮加密S-DES的F函数n1，
17、E/P（R）n2，与K1异或运算n3，S0，S1n4，P4E/P+S0S1P4R 4K1844F22DES的关键/重要技术nIPn密钥nF函数DES算法 IPDES算法 逆IPDES算法 IP & 逆IP58 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 46 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 159 51 43 35 27 19 11 361 53 45 37 29 21 13 563 55 47 39 31 23 15 740 8 48 16 56 24 64 323
18、9 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 2936 4 44 12 52 20 60 2835 3 43 11 51 19 59 2734 2 42 10 50 18 58 2633 1 41 9 49 17 57 25输入的第58位作为第1位输入的第50位作为第2位输入的第42位作为第3位输入的第40位作为第1位输入的第8位作为第2位输入的第48位作为第3位DES算法 IP & 逆IP1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 242
19、5 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 4849 50 51 52 53 54 55 561 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2425 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 4849 50 51 52 53 54 55 5658 50 42 34 26 18 10 260 52 44 36 28 20 12 462 54 4
20、6 38 30 22 14 664 56 48 40 32 24 16 857 49 41 33 25 17 9 161 58 45 37 29 21 13 563 55 47 39 31 23 15 740 8 48 16 56 24 64 32 39 7 47 15 55 23 63 3138 6 46 14 54 22 62 3037 5 45 13 53 21 61 29 36 4 44 12 52 20 60 2834 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25IPIP-1DES算法 密钥KPC-1C0D0LS1LS1C1D1LS2LS2PC-
21、2K1C2D2LS3LS3PC-2K2DES算法 密钥64bit64bit密钥密钥置换选择置换选择1 1（PC1PC1）C C0 0（28bit28bit）D D0 0（28bit28bit）循环左移循环左移1 1位位循环左移循环左移1位位C C1 1（28bit28bit）D D1 1（28bit28bit）循环左移循环左移X X位位循环左移循环左移X X位位置换选择置换选择2 2置换选择置换选择2 2C Ci i（28bit28bit）D Di i（28bit28bit）(56bit)(56bit)(56bit)(56bit)K Ki i K K0 0 (48bit)(48bit)(48b
22、it)(48bit)(56bit)(56bit)PC 置换选择LS 循环左移循环左移位数表循环左移位数表迭代次数迭代次数循环左移位数循环左移位数迭代次数迭代次数循环左移位数循环左移位数119121102321124212252132621427215282161DES算法 密钥DES算法 密钥574941332517915850423426181025951433527191136052443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374
23、755304051453348444939563453464250362932PC-1置换PC-2置换DES算法 密钥n置换选择1工作过程和作用：n1，64位密钥分为8个字节，每个字节的前7位用于加密过程，第8位是奇偶校验位。置换选择1从64位密钥中去掉这8个奇偶校验位。n2，将其余56位数据打乱重排DES算法 密钥n将主密钥K顺序地每7bit归为一组，共计8组，每一组都按奇校验在后面补上一个校验bit：0或1。(奇校验：含奇数个“1”则校验位为“0”，含偶数个“1”则校验位为“1”)n这样，K被扩展为一个长是64的比特串K+，可用16位十六进制数表示。 nK+由安全信道传送，其带上8个校验比
24、特（分别在第8位、16位、64位）就是为了对传输过程中可能出错进行检测和校对。置换选择置换选择1框图框图DES算法 密钥DES算法 密钥取16进制明文X： 0123456789ABCDEF密钥K为： 133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000应用IP，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进行16轮加密。最后对L16, R16使用IP-
25、1得到密文：85E813540F0AB405DES算法 密钥去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000其十六进制表示为0001001100110100010101110111100110011011101111001101111111110001密钥K为： 133457799BBCDFF1DES算法 F函数Li-1 （32 bit）Ri-1 （32 bit）选择扩展运算选择扩展运算 E盒盒48bit寄存器寄存器48bit寄存器寄存器选择压缩运算选择压缩运算 S盒盒32bit寄存器寄存器置
26、换运算置换运算 P盒盒Ri =Li-1 f(Ri-1,ki) （32 bit）（32 bit） Li =Ri-1轮开始：轮开始：64bit分分成左右两成左右两半半子密钥子密钥Ki （48 bit）DES算法 F函数E盒 (Expand Box)n将输入的32bit块扩展到48bit的输出块；n48bit的输出块再分成8个6bit块；01 02 03 0405 06 07 0809 10 11 1213 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 3201 02 03 0405 06 07 0809 10 11 1213 14 15
27、 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 3232040812162024280509131721252901E盒盒扩展位扩展位扩展位扩展位固定位固定位DES算法 F函数S盒 (Substitution Box)n48bit块通过S盒压缩成32bit块48bit寄存器寄存器32bit寄存器寄存器 S1S2S3S4S5S6S7S86bit4bit共共8个个S盒盒DES算法 F函数S1盒14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7 4 14 2 13 1 10 6 12 11 9 5 3 84 1 1
28、4 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S2盒15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 103 13 4 7 15 2 8 14 12 0 1 10 6 9 11 50 14 7 11 10 4 13 1 5 8 12 6 9 3 2 1513 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9DES算法 F函数S3盒10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 813 7 0 9 3 4 6 10 2 8 5 14 12 1
29、1 15 113 6 4 9 8 15 3 0 11 1 2 12 5 10 14 71 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12S4盒7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 1513 8 11 5 6 15 0 3 4 7 2 12 1 10 14 910 6 9 0 12 11 7 13 15 1 3 14 5 2 8 43 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14S5盒2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 914 11 2 12 4 7 13 1 5 0 15 10
30、 3 9 8 64 2 1 11 10 13 7 8 15 9 12 5 6 3 0 1411 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3DES算法 F函数S6盒12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 1110 15 4 2 7 12 9 5 6 1 13 14 0 11 3 89 14 15 5 2 8 12 3 7 0 4 10 1 13 11 64 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13S7盒4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 113 0 11 7 4 9 1 10
31、 14 3 5 12 2 15 8 61 4 11 13 12 3 7 14 10 15 6 8 0 5 9 26 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12S8盒13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 71 15 13 8 10 3 7 4 12 5 6 11 0 14 9 27 11 4 1 9 12 14 2 0 6 10 13 15 3 5 82 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11DES算法 F函数S1盒14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 70 15 7
32、4 14 2 13 1 10 6 12 11 9 5 3 84 1 14 8 13 6 2 11 15 12 9 7 3 10 5 015 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13S2盒15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 103 13 4 7 15 2 8 14 12 0 1 10 6 9 11 50 14 7 11 10 4 13 1 5 8 12 6 9 3 2 1513 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9n作用：将6个输入位映射为4个输出位；n方法：若定义a1a2a3a4a5a6，将a1a6组
33、成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。nS1盒输入为101011的输出是？（11）第）第3行行（0101）第）第5列列表内数据为表内数据为13输出（输出（1101）DES算法 F函数P盒（Permutaion）nP置换的目的是：提供雪崩效应（提高Diffusion发散性能）；n明文或密钥的一点小的变动都引起密文的较大变化。16 07 20 21 29 12 28 1701 15 23 26 05 18 31 1002 08 24 14 32 27 03 0919 13 30 06 22 11 04
34、25DES算法的几点讨论n盒的由来nS盒n密钥盒的由来nShannon在1949 的文章中，介绍了替换-置换网络的思想 (S-P) networks n这种思想形成了现代密码的基础nS-P network 替换-置换乘积密码的现代形式nS-P networks 是基于下列两种最基本的密码运算：n替换（ Substitution ）n置换（ Permutation ）S-BOX S盒n一个二进制字用其它二进制字替换这种替换函数就构成密码可以看作是一个大的查表运算P-BOX P盒n二进制字次序被打乱，重新排序的方法构成密码盒的本质就是空间变换nShannon 把这两种运算组合在一起，即一些 S-b
35、oxes 由 P-box 连接，这种变换叫做混合变换（mixing transformations ）实际实现n实际中，我们需要加密，也需要解密，因此，有两种方法：1，定义每个替换、置换的逆，这样增加了复杂度2，定义一种结构，容易求逆，这样可以使用基本的相同编码或硬件用于加密和解密实际实现n “好的”密码设计具有: 雪崩特性,完备性,不可预料性(avalanche, completeness, unpredictability )n差的密码设计缺乏随机性,具有太大的可预料性n几乎所有现代分组密码用更小的查表（S盒）合并其他变换（线性变换）模仿这样一个大的随机查表。这种做法实际上是安全性和可接受
36、的复杂性的一个折中。DES算法 S盒nDES中S盒运算是非线性的，不易于分析，它提供了更好的安全性；所以S盒是算法的关键所在。n提供了密码算法所必需的混乱作用。S盒的设计原则n1976年，美国NSA披露了S盒的下述几条设计原则：n每个S盒的每一行是整数015的一个全排列；n每个S盒的输出都不是其输入的线性或仿射函数；n改变任一S盒任意1bit的输入，其输出至少有2bit发生变化；n对任一S盒的任意6bit输入x,S(x)与S(x001100)至少有2bit不同；n对任一S盒的任意6bit输入x ，及,0,1，都有S(x)S(x1100) ；n对任一S盒，当它的任一位输入保持不变，其它5位输入随
37、意变化时，所有诸4bit输出中，0与1的总数接近相等。S盒的问题nS盒的设计原理未知n公众仍然不知道S盒的构造中是否还使用了进一步的设计准则。n密钥长度是否足够？n迭代的长度？（8、16、32？）密钥n密钥本身的缺陷n对DES的攻击n差分密码分析n线性密码分析n字典攻击n穷举破译弱密钥与半弱密钥n弱密钥: EKEK = In半弱密钥: EK1 = EK2nDES存在4个弱密钥n至少存在12个半弱密钥差分密码分析n破解DES: 247个选择明文(255个已知明文)n破解Lucifer(18轮128位): 24个选择明文221次计算nDES对差分密码分析的抵抗力很强线性密码分析n破解DES: 24
38、3个已知明文nDES对线性密码分析的抵抗力稍弱字典攻击n考虑选择明文攻击nDES块大小: 64位, 2641020n计算机能力为100MIPS(108)/秒,1万台计算机协同工作一天，计算能力为:108*10000*24*360010171020/1017 = 1000天n适用于任意64位块的加密穷举破译nDES密钥长度: 56位, 2561017n计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为:n108*10000*24*36001017n1017/1017 = 1天nDES算法具有比较高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现
39、更有效的办法。密钥搜索机n而56位长的密钥的穷举空间为256，如果一台计算机的速度是每一秒种检测一百万个密钥，则它搜索完全部密钥就需要将近228.5年的时间。n在对DES安全性的批评意见中，较一致的看法是DES的密钥太短！其长度56bit，致使密钥量仅为2561017，不能抵抗穷搜攻击，事实证明的确如此。n1997年1月28日，美国RSA数据安全公司在RSA安全年会上发布了一项“秘密密钥挑战”竞赛，分别悬赏1000美金、5000美金和10000美金用于攻破不同长度的RC5密码算法；同时还悬赏10000美金破译密钥长度为56bit的DES。nRSA公司发起这场挑战赛是为了调查在Internet上
40、分布式计算的能力，并测试不同密钥长度的RC5算法和密钥长度为56bit的DES算法的相对强度。n结果是：密钥长度为40bit和48bit的RC5算法被攻破；美国克罗拉多州的程序员Verser从1997年3月13日起用了96天的时间，在Internet上数万名志愿者的协同工作下，于1997年6月17日成功地找到了DES的密钥，获得了RSA公司颁发的10000美金的奖励。n这一事件表明，依靠Internet的分布式计算能力，用穷搜方法破译DES已成为可能。因此，随着计算机能力的增强与计算技术的提高，必须相应地增加密码算法的密钥长度。n1977年，Diffe和Hellman曾建议制造每秒能测试106
41、个密钥的VLSI芯片，将这样的100104个芯片并行操作搜索完整个密钥空间大约需1天时间。他们估计制造这样一台机器需耗资大约2000万美金。n1993年，Wiener给出了一个详细的设计密钥搜索机的方案。他建议制造每秒能测试5107个密钥的芯片，基于这种芯片的机器将流水作业，使得16次加密同时发生。目前制造这种芯片每片需耗资10.5美金，耗资10万美金能建造一个由5760个芯片组成的框架，这使得搜索一个密钥平均大约需要1.5天。使用十个这样框架的机器将耗资100万美金，搜索一个密钥平均大约3.5小时。n据新华社1998年7月22日消息,电子边境基金学会(EFF)使用一台25万美金的电脑在56小
42、时内破译了56位密钥的DES。n计算能力（软件和硬件）的提高使得DES变的越来越不安全。Measures of computational efficiencynCould considernNumber of additionsnNumber of multiplicationsnAmount of memory requirednScalability and regularitynFor the present discussion well focus most on number of multiplications as a measure of computational com
43、plexitynMore costly than additions for fixed-point processorsnSame cost as additions for floating-point processors, but number of operations is comparablehttp:/www.top500.orgn1st:nSystem Name: JaguarnSite: Oak Ridge National LaboratorynSystem Family: Cray XTnSystem Computer: Cray XT5-HE Opteron Six
44、Core 2.6 GHznVendor: Cray Inc.nProcessor: AMD x86_64 Opteron Six Core 2600 MHz (10.4 GFlops)nCores: 224162nRpeak(GFlops): 2331000nOperating System: LinuxnRmax(GFlops): 1759000Rpeakna theoretical peak performance.nIt is determined by counting the number of floating-point additions and multiplications
45、 (in full precision) that can be completed during a period of time, usually the cycle time of the machine.nFor 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.曙光星云n2nd:nSystem Name: NebulaenSite: National Superc
46、omputing Centre in Shenzhen (NSCS)nSystem Family: Dawning ClusternSystem Computer: Dawning TC3600 Blade, Intel X5650, NVidia Tesla C2050 GPUnVendor: DawningnProcessor: Intel EM64T Xeon X56xx (Westmere-EP), Six Core 2.6 GHz nCores: 120640nRpeak(GFlops): 2984300nOperating System: LinuxnRmax(GFlops): 1
47、271000天河一号n7th:nSystem Name: TianHe-1nSite: National SuperComputer Center in Tianjin/NUDTnSystem Family: NUDT TH-1 ClusternSystem Computer: NUDT TH-1 Cluster, Xeon E5540/E5450, ATI Radeon HD 4870 2, InfinibandnVendor: NUDTnProcessor: Intel EM64T Xeon E55xx (Nehalem-EP), Four Core 2.53 GHz nCores: 71
48、680nRpeak(GFlops): 1206190nOperating System: LinuxnRmax(GFlops): 563100Sun SonglinBeijing University of Posts and Telecommunications98银河一号n1983年12月22日国防科大，中国第一台每秒钟运算一亿次以上的巨型计算机n1993年，中国第一台10亿次巨型银河计算机型通过鉴定。n1994年，在国家气象局投入正式运行，用于天气中期预报。Chinan24/500n两所高校：吉林大学、南京大学AsianJapan：n18/500nRussia：n11/500nIndia
49、:n5/500nHong Kong、South Korean1/500Euro.nUnited Kingdom:n38/500nGermany：n24/500n5th GermanynFrance:n27/500United Statesn7/10282/500nVendors (10):nIBM:19639.20 % nHP:18637.20 % nCray: 214.20 % nSGI:173.40 % nDell:173.40 % nSun:122.40 %nOS Family:nLinux45591.00 % nUnix224.40 % nWindows51.00 % nProcess
50、or Family:nIntel EM64T40180.20 %nAMD x86_64499.80 % nPower428.40 %Whose Apple？Computationn什么是计算？n根据图灵图灵的研究，直观地说所谓计算就是计算者人或机器对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。nThe purpose of computing is insight，not numbersn -Richard Wesley Hamming4. 对称密钥密码体制n对称密钥密码的历史nDESnDES概述nFei
