信息安全课件--02-密码学基础课件

1、1第第2讲讲 密码学基础密码学基础2密码学的起源和发展n三个阶段：n1949年之前密码学是一门艺术n19491975年密码学成为科学n1976年以后密码学的新方向公钥密码学 3第第1阶段古典密码阶段古典密码 密码学还不是科学密码学还不是科学, ,而是艺术而是艺术 出现一些密码算法和加密设备出现一些密码算法和加密设备 密码算法的基本手段密码算法的基本手段出现出现，针对的是字符，针对的是字符 简单的密码分析手段出现简单的密码分析手段出现 主要特点：数据的安全基于算法的保密主要特点：数据的安全基于算法的保密4第第1阶段古典密码阶段古典密码Phaistos圆盘，一种直径约为圆盘，一种直径约为160mm

2、的的Cretan-Mnoan粘土圆盘，始于公元前粘土圆盘，始于公元前17世纪。表面有明显世纪。表面有明显字间空格的字母，至今还没有破解。字间空格的字母，至今还没有破解。520世纪早期密码机世纪早期密码机6第第1阶段古典密码阶段古典密码1883年年Kerchoffs第一次明确提出了编码的原则：第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密加密算法应建立在算法的公开不影响明文和密钥的安全。钥的安全。这一原则已得到普遍承认，成为判定密码强度这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密的衡量标准，实际上也成为传统密码和现代密码的分界线。码的分界

3、线。7 计算机使得基于复杂计算的密码成为可能计算机使得基于复杂计算的密码成为可能 相关技术的发展相关技术的发展19491949年年ShannonShannon的的“The Communication Theory of Secret The Communication Theory of Secret SystemsSystems” 19671967年年David KahnDavid Kahn的的The CodebreakersThe Codebreakers1971-19731971-1973年年IBM WatsonIBM Watson实验室实验室的的Horst FeistelHorst F

4、eistel等几篇技术等几篇技术报告报告主要特点：主要特点：数据的安全基于密钥而不是算法的保密数据的安全基于密钥而不是算法的保密 第第2阶段阶段 19491975819761976年：年：Diffie & Hellman Diffie & Hellman 的的 “New Directions in New Directions in CryptographyCryptography” 提出了不对称密钥提出了不对称密钥；19771977年年Rivest,Shamir & AdlemanRivest,Shamir & Adleman提出了提出了RSARSA公钥算法公

5、钥算法9090年代逐步出现椭圆曲线等其他公钥算法年代逐步出现椭圆曲线等其他公钥算法主要特点：主要特点：公钥密码使得发送端和接收端无密钥传输的公钥密码使得发送端和接收端无密钥传输的保密通信成为可能保密通信成为可能第第3阶段阶段 1976919771977年年DESDES正式成为标准正式成为标准8080年代出现年代出现“过渡性过渡性”的的“Post DESPost DES”算法算法, ,如如IDEA,RCx,CASTIDEA,RCx,CAST等等9090年代对称密钥密码进一步成熟年代对称密钥密码进一步成熟 Rijndael,RC6, MARS, Rijndael,RC6, MARS, Twofis

6、h, SerpentTwofish, Serpent等出现等出现20012001年年RijndaelRijndael成为成为DESDES的替代者的替代者第第3阶段阶段 197610保密通信11保密通信的功罪n100年前，1894年的中日甲午海战，中国惨败，其本质是由于清政府的腐败，但其中一个重要的具体原因，是日方在甲午战争前就破译了清政府使用的密电码。日方破译的电报多达一百余则，对清政府的决策、海军的行踪等了如指掌，因而日方不仅在海战中取得了胜利，还迫使清政府签订“马关条约”，割让辽东半岛、台湾及澎湖列岛，赔偿军费白银2亿两。12保密通信的功罪n1917年1月，正当第一次世界大战进入第三个年头

7、时，英国海军破译机关截收到了德国外长齐默尔曼签发的一份密报，经过一个多月的辛勤劳作，终于在2月下旬完全破开了那份密报。密报称，德国将在欧洲进行无限制的潜艇战，意思是说，中立国家的船队也在其打击目标之列，同时指出，若美国不再保持中立，就要求墨西哥与德国结盟，对美宣战。英国外交部在权衡了种种利弊后，到2月22日将此密报交给了美国政府，德国政府的阴谋激怒了开战以来一直保持中立并且在三个月前还声明继续保持中立的美国人，五个星期后美国对德宣战，出兵西线，既避免了在美国本土燃起战火，又加速了协约国的胜利。13保密通信的功罪n1941年年12月，日本取得了突袭珍珠港、摧毁美月，日本取得了突袭珍珠港、摧毁美国

8、太平洋舰队主力的重大胜利，为了完全控制太国太平洋舰队主力的重大胜利，为了完全控制太平洋，并设法诱出在珍珠港的美国舰队残部予以平洋，并设法诱出在珍珠港的美国舰队残部予以彻底消灭，日本制定了于彻底消灭，日本制定了于1942年年6月突然攻击夏月突然攻击夏威夷前哨中途岛的计划。威夷前哨中途岛的计划。14保密通信的功罪n当时日本海军使用的是日本最高级的密码体制紫密，它的第二版本JN25b自1940年12月1日启用后应在1942年4月1日内第三版本JN25c替换。但由于舰船分散在广阔的海域不停地转移，给分发新的版本增添许多困难，因此替换工作延期到5月1日，后因同样的原因再延期个月，到6月1日启用新版本。这

9、就使盟国破译人员有充分的时间更透彻地破解JY25b。5月27日，山本的作战命令已基本上被破译，美国太平洋舰队司令尼米兹海军上将发布作战计划，将3艘航空母舰部署在敌舰不可能侦察到的海域，战斗打响时也以突然攻击的方式打击日军的突击舰队。6月4日，日军4艘巨型航空母舰在一日之内相继被炸沉从此日本海军由进攻转为防御，最终走向失败。15保密通信的功罪n1943年春天，山本五十六为了控制不断恶化的残局，亲自前住所罗门群岛基地巡视，以鼓舞士气。在视察前五天，1943年4月13日，日军第八舰队司令将山本行将视察的行程、时间表，用JN25体制加密后播发给有关基地，以作好迎接的准备，尽管该体制的所用版本在4月1日

10、刚换过，但美国破译人员根据过去的经验，迅速地破译了这份密报，美军决定在空中打掉山本的座机，使日军失去一位战略家，沉重地打击日军士气。经过精心组织，周密安排，终于使山本五十六在飞往视察地途中，被美军飞机击落，葬身于丛林深处。16密码学起源n密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为解密变换。n世纪，英国著名的哲学家弗朗西斯培根在他所著的学问的发展一书中最早给密码下了定义，他说，“所谓密码应具备三个必要的条件，即易于翻译、第三者无法理解、在一定场合下不易引人生疑。” 加密解密明文密文原始明文17密码学起源n谋成于密，败

11、于泄 明 揭暄 兵经百言n古典密码学包含两个互相对立的分支，即密码编码学（Cryptography）和密码分析学（Cryptanalytics）。前者编制密码以保护秘密信息，而后者则研究加密消息的破译以获取信息。二者相反相成，共处于密码学的统一体中。 n现代密码学除了包括密码编码学和密码分析学外，还包括安全管理、安全协议设计、散列函数等内容。18密码学起源n大约在4000年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号(明文)用另一种符号

12、(密文)代替19密码学起源n公元前5世纪，古斯巴达人使用了一种叫做“天书”的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。 20密码学起源n公元前1世纪古罗马凯撒大帝时代曾使用过一种“代替式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种代替式密码直到第二次大战时还被日本海军使用。 n公元前4世纪前后，希腊著名作家艾奈阿斯在其著作城市防卫论中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子

13、的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。21密码学起源n六韬龙韬阴符武王问太公曰：引兵深入诸侯之地，三军猝有缓急，或利或害。吾将以近通远，从中应外，以给三军之用。为之奈何？太公曰：主与将，有阴符。凡八等：有大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；誓众坚守之符，长六寸；请粮益兵之符，长五寸；败军亡将之符，长四寸；失利亡士之符，长三寸。诸奉使行符，稽留者，若符事泄，闻者告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之通识。武王曰：善哉。22密码学起源n六韬龙韬阴书武王问太公曰：引

14、兵深入诸侯之地，主将欲合兵，行无穷之变，图不测之利。其事繁多，符不能明；相去辽远，言语不通。为之奈何？太公曰：诸有阴事大虑，当用书，不用符。主以书遗将，将以书问主。书皆一合而再离，三发而一知。再离者，分书为三部；三发而一知者，言三人，人操一分，相参而不知情也。此谓阴书。敌虽圣智，莫之能识。武王曰：善哉。23密码学起源n在古代还出现过一种被称为“叠痕法”的密码，使用时先把信纸折叠几下（上下及左右），然后铺平信纸，将传递的信息按顺序一个个分开，写在折痕的交叉点上，每一个交叉点写一个字。然后再在空白位置上填上公开的普通信文，普通信文与秘密信文的文字通顺地连贯在一起。为了防止被敌人察觉，使用这种密码需

15、要在编公开信文上下些功夫。如果在秘密信文上再用些暗语式密码，那么敌人就更难看出破绽了。n宋曾公亮、丁度等编撰武经总要“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密码本体制的特点。24密码学起源n暗号。简单地说，暗号就是通过用物件的状态或人的行为来传达事先约定的信息如窗台上的花瓶、手中拿着的报纸、口中昨着的曲子，可分别代表“现在安全”、“我是你要找的人”、“我在找自己人”等明确的信息n隐语。暗号是把信息变换为物件或动作，隐语则是把信息变换成与此信息完全无关的(但有意义的)语言据说，1941年，日本偷袭珍珠港前两星期，美国情报人员曾截获一

16、次重要的电话对话那是两名分别在东京和华盛顿的日本高级官员之间的通话这段对话里“小孩出生”的真正意思是“发动战争” n在华盛顿的日本人：是不是真的有个小孩要出生了?n在东京的日本人：是的而且看来马上就要出生了n在华盛顿的日本人：这个小孩真的要生了吗?是在哪个方向呢?25密码学起源n16世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称“卡尔达诺漏格板”漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格26密码学起源n兵经百言衍部传军行无通法，则分者不能合，远者不能应。彼此莫相喻，败道也。然通而不密，反为敌算。故自金、旌、炮、马、令箭、起火、烽烟，报警急外；两

17、军相遇，当诘暗号；千里而遥，宜用素书，为不成字、无形文、非纸简。传者不知，获者无迹，神乎神乎！或其隔敌绝行，远而莫及，则又相机以为之也。”27密码学起源n大约在1793年，当时的美国总统托马斯杰斐逊发明了一种轮子密码机。转动轮子使明文中的所有字母全排在一条直线上为止这时圆柱体的其他25行字母也因这一行的固定而被固定了任选这25行中的一行发出去即为密文28密码学起源n“谜”（ENIGMA）密码最初是由一个叫胡戈科赫的荷兰人发明的。起初主要提供给想保护自己生意秘密的公司使用，但其商界的销路一直不理想。后来德国人将其改装为军用型，使之更为复杂可靠。德国海军于1926年开始使用“ENIGMA”，陆军则

18、于1928年开始使用。1933年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队的通信装置。德国人在战争期间共生产了大约10多万部“谜”密码机。1940年，经过盟军密码分析学家的不懈努力，“恩尼格玛”密码机被动攻破，盟军掌握了德军的许多机密，而德国军方却对此一无所知。 29密码学起源n传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信。 30密码学起源n第六十回 吴用智赚玉麒麟 梁

19、山泊义军头领宋江久慕卢俊义的威名，一心想招取卢俊义上山坐第一把交椅，共图大业，替天行道。智多星吴用扮成一个算命先生，利用卢俊义正为躲避“血光之灾”的惶恐心里，口占四句卦歌，并让他端书在家宅的墙壁上。n卢花滩上有扁舟，俊杰黄昏独自游。义到尽头原是命，反躬逃难必无忧。 n这四句诗写出后，被官府拿到了证据，大兴问罪之师，到处捉拿卢俊义，终于把他逼上梁山。3132加密与解密n现代密码学涉及数学（如数论、有限域、复杂性理论、组合算法、概率算法等）、物理学（如量子力学、现代光学、混沌动力学等）、信息论、计算机科学等学科。1949年，信息论之父C.E.Shannon发表了保密系统的通信理论，密码学走上科学和

20、理性之路。n1976年W.Diffie和M.E.Hellman发表的密码学的新方向，以及1977年美国公布实施的数据加密标准DES，标志着密码学发展的革命。n2001年11月美国国家标准技术研究所发布高级数据加密标准AES代表着密码学的最新发展。 33加密与解密n基于密钥的算法通常有两类：对称算法和公开密钥算法。n使用一个密钥的加/解密。加密时可以使用一个参数K，称此参数K为加密密钥。K可以是很多数值里的任意值。密钥K的可能值的范围叫做密钥空间。 34加密与解密n使用两个密钥的加/解密。nEK1（P）=CnDK2（C）=PnDK2 （EK1（P）=P解密密钥加密密钥原始明文密文加密解密明文35

21、加密与解密n加密通信的模型信源Mm加密器)(1mEck解密器)(2cDmk接收者m非法接入者搭线信道（主动攻击）C 搭线信道（被动攻击）密码分析员m密钥源K1k1密钥源K2k2密钥信道36加密与解密n对称算法就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法。n对称算法可分为两类。序列密码（流密码）与分组密码。37序列密码（流密码）n序列密码主要应用于军事和外交场合。n序列密码的优点是错误扩展小、速度快、利于同步、安全程度高。密钥流密钥流产生器产生器密钥密钥k明文明文m密文密文c异或运算38序列密码n伪随机序列发生

22、器是指输入真随机的较短的密钥（种子）通过某种复杂的运算产生大量的伪随机位流。 n真随机序列从真实世界的自然随机性源产生。如自然界中的抛币。 n伪随机序列用确定的算法产生，不是真正的随机序列。伪随机序列发生器指使用短的真随机序列（称为种子）x扩展成较长的伪随机序列y。 n随机数是较短的随机位序列。 seed(short)PRBS(long)011011010010110.39分组密码n分组密码是将明文按一定的位长分组，明文组和密钥组的全部经过加密运算得到密文组。n数据加密标准DES出自IBM被美国政府正式采纳的数据加密算法（Data Encryption Algorithm，DEA）n由中国学者

23、来学嘉Xuejia Lai和 James L. Massey 在苏黎世的ETH开发的国际数据加密算法IDEA（International Data Encryption Algorithm）n比利时Joan Daemen 和 Vincent Rijmen 提交，被美国国家标准和技术研究所（US National Institute of Standards and Technology，NIST）选为美国高级加密标准（AES）的Rijndael。 40分组密码的操作模式n电子密码本ECB (electronic codebook mode)n密码分组链接CBC (cipher block ch

24、aining)n密码反馈CFB (cipher feedback)n输出反馈OFB (output feedback)n计数器模式CTR）美国NSB在FIPS PUB 74和81中规定ANSI 在ANSI X3.106中规定 ISO和ISO/IEC在ISO 9732 ISO/IEC 10116中规定分组密码的操作模式模式描述典型应用电子密码本ECB用相同的密钥分别对明文分组加密单个数据的安全传输密码分组链接CBC加密算法的输入是上一个密文分组和下一个明文分组的异或普通目的的面向分组的传输密码反馈CFB一次处理J位，上一个分组密文作为产生一个伪随机数输出的加密算法的输入，该输出与明文分组异或，作

25、为下一个分组的输入普通目的的面向分组的传输认证输出反馈OFB与CFB相同，只是加密算法的输入是上一次DES的输出噪声信道上数据流的传输（如卫星传输）计数器模式CTR）每个明文分组是加密的计数器的异或，对每个后续的分组，计数器是累加的。普通目的的面向分组的传输用于高速需求42分组密码的分析方法n根据攻击者所掌握的信息,可将分组密码的攻击分为以下几类:唯密文攻击已知明文攻击选择明文攻击n攻击的复杂度数据复杂度:实施该攻击所需输入的数据量处理复杂度:处理这些数据所需要的计算量43分组密码的典型攻击方法n最可靠的攻击办法:强力攻击n最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来

26、恢复某些密钥比特.n线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统n插值攻击方法n密钥相关攻击44强力攻击n穷尽密钥搜索攻击:n唯密文,2kn已知(选择)明文, 2k, k-密钥长度n字典攻击:n明密文对编成字典, 2n,n-分组长度n查表攻击:n选择明文攻击, 给定明文,用所有的2k个密钥,预计算密文, k-密钥长度n时间存储权衡攻击:n选择明文攻击,由穷尽密钥搜索和查表攻击混合而成,它在选择明文攻击中以时间换取空间45现代常规分组加密算法 一种是对DES进行复合，强化它的抗攻击能力；另一种是开辟新的方法，即象DES那样加解密速度快，

27、又具有抗差分攻击和其他方式攻击的能力。46现代常规分组加密算法n1. Triple DESn2. IDEAn3. RC5n4. RC6n5. AESn其他一些较实用的算法，如Blowfish，CAST，以及RC2。47双重DES (Double DES) nC = EK2(EK1(P) P = DK1(DK2(C)48Triple-DES的四种模型nDES-EEE3：三个不同密钥，顺序使用三次加密算法nDES-EDE3：三个不同密钥，依次使用加密-解密-加密算法nDES-EEE2：K1=K3，同上nDES-EDE2：K1=K3，同上491 . TRIPLE DESn由于已经证明，见 K.W.C

28、ampbell and M.J.Wiener Proof that DES is not a group In Advances in CryptologyCrpto92. Springer-Verlag , New York,1993.于是多重DES，尤其是三重DES还在普遍使用。50双密钥的三重DES（Triple DES with Two Keys)nC=EK1(DK2(EK1(P) P=DK1(EK2( DK1(C)51三密钥的三重DES（Triple DES with Three Keys)nC=EK3(DK2(EK1(P) =DK3(EK2( DK1(C)52n1973年，美国国家

29、标准局(NBS) 开始征集联邦数据加密标准的方案。nFeistel等人研究了一种128位的对称密钥系统，n后IBM改进为56位的密钥系统，并提交NBS。n1975年3月17日，NBS公布了IBM公司提供的密码算法，以标准建议的形式在全国范围内征求意见。n1977年7月15日，NBS接受这个建议，数据加密标准DES正式颁布，供商业界和非国防性政府部门使用。DES 的历史53n争论：争论：n56位够长吗？位够长吗？n内部结构公开，设计原理没公开？内部结构公开，设计原理没公开？DES 的历史54DES的应用n1979年，美国银行协会批准使用n1980年，美国国家标准局（ANSI）赞同DES作为私人使

30、用的标准,称之为DEA（ANSI X.392） 1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1n该标准规定每五年审查一次，计划十年后采用新标准n最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。55DES的描述nDES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文输入输入64比特明文数据比特明文数据初始置换初始置换IP在密钥控制下在密钥控制下16轮迭代轮迭代初始逆置换初始逆置换IP-1输出输出64比特密文数据比特密文数据DES算法框图算法框图交换左右交换左右32比特比特 56初始置换IP和初始逆置换

31、IP1 Li-1（32比特）比特）Ri-1（32比特）比特）Li（32比特）比特）48比特寄存器比特寄存器扩充扩充/置换运算置换运算48比特寄存器比特寄存器子密钥子密钥Ki（48比特）比特）32比特寄存器比特寄存器代换代换/选择运算选择运算置换运算置换运算PRi（32比特）比特）Li=Ri-1DES的一轮迭代的一轮迭代F函数函数DES: Function FExpansion: 32 48（扩充）（扩充）S-box: 6 4（压缩）（压缩）Permutation:置换置换 扩充扩充/置换运算置换运算32 | 01 02 03 04 | 0504 | 05 06 07 08 | 0908 | 0

32、9 10 11 12 | 1312 | 13 14 15 16 | 1716 | 17 18 19 20 | 2120 | 21 22 23 24 | 2524 | 25 26 27 28 | 2928 | 29 30 31 32 | 0160代换/选择运算61S-Box-i62S-Box-ii 63S-Boxn对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。相应行、列位置的十进制数的4位二进制数表示作为输出。例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，的第3行和第4列的十进制数为3，用4位二进制数表示为

33、0011，所以的输出为0011。 64 Permutation16 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 25子密钥的产生 k1 （ 56位） (48位 ) ki （ 56位） （ 48位） 64位密钥置换选择1 C0（ 28位） D0（ 28位） 循环左移循环左移 C1（ 28位） D1（ 28位） 循环左移循环左移 Ci（ 28位） Di（ 28位）置换选择2置换选择2密钥表的计算逻辑循环左移：1 1 9 12 1 10 23 2 11 24 2 12 2

34、5 2 13 26 2 14 27 2 15 28 2 16 166置换选择1(PC-1)和置换选择2(PC-2) 总结DES示意图68DES的安全性分析 nDES的安全性完全依赖于密钥，与算法本身没有关系。 n主要研究内容：n密钥的互补性；n弱密钥与半弱密钥；n密文-明文相关性；n密文-密钥相关性；nS-盒的设计；n密钥搜索。 69弱密钥n弱密钥：由密钥 k 确定的加密函数与解密函数相同 ，即 。nDES的弱密钥： 如果各轮产生的子密钥一样，则加密函数与解密函数相同。 nDES至少有4个弱密钥 ：n0101010101010101n1f1f1f1f0e0e0e0ene0e0e0e0f1f1f

35、1f1nfefefefefefefefe)()(1kkDESDES70半弱密钥 n半弱密钥：对于密钥 k ，存在一个不同的密钥 ，满足 。 nDES的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密钥，互为对合。 nDES至少有12个半弱密钥。 *k)()(*kkDESDES71S -盒的设计原则 S -盒的设计原理没有公开，一些原则如下：n所有S-盒的每一行是0,1,15的一个置换；n所有S-盒的输出都不是输入的线性函数或仿射函数；nS-盒的输入改变任意一位都会引起输出中至少两位发生变化；n对于任何输入x（6位），S(x)与S(x 001100)至少有两位不同；n对于任何输

36、入x（6位），S(x)与S(x 00ef00)不相等，e, f取0或1；n对于任意一个输入位保持不变而其他五位变化时，输出中0和1的数目几乎相等。 72针对DES的攻击方法攻击DES的方法主要有：n密钥穷搜索攻击，DES算法总的密钥量为 ，1998年使用高级计算机的情况下，破译DES只需56小时； n差分攻击；n线性攻击，较有效的方法；n相关密钥攻击等。175610273DES的破译n1990年，以色列密码学家Eli Biham和Adi Shamir提出了差分密码分析法，可对DES进行选择明文攻击。n线性密码分析比差分密码分析更有效 74公钥密码n公开密钥算法中用作加密的密钥不同于用作解密的密

37、钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。n在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。n公开密钥算法主要用于加密/解密、数字签名、密钥交换。 75讨论议题讨论议题n为什么要设计公钥密码算法n密钥分配n公钥密码体制概述及其应用n公钥密码算法的实现nDiffie-Hellman密钥交换算法n背包算法nRSA算法nEIGamal算法n椭圆曲线密码算法ECC761. 为什么要设计公钥密码体制77密钥分配（Key Distribut

38、ion）保密通信双方需共享密钥共享密钥要经常更换A选择密钥并手工传递给B第三方C选择密钥分别手工传递给A,B用A,B原有共享密钥传送新密钥与A,B分别有共享密钥的第三方C传送新密钥给A和/或BN个用户集需要N(N-1)/2个共享密钥密钥分发中心(Key Distribution Center)78密钥分发中心（KDC）l每个用户与KDC有共享密钥(Master Key)lN个用户,KDC只需分发N个Master Keyl两个用户间通信用会话密钥(Session Key)用户必须信任KDCKDC能解密用户间通信的内容79 （1）密钥管理量的困难）密钥管理量的困难 传统密钥管理：两两分别用一对密钥

39、时，则传统密钥管理：两两分别用一对密钥时，则n个用个用户需要户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密个密钥，当用户量增大时，密钥空间急剧增大。如钥空间急剧增大。如: n=100 时，时， C(100,2)=4,995 n=5000时，时， C(5000,2)=12,497,500 （2）数字签名的问题）数字签名的问题 传统加密算法无法实现抗抵赖的需求。传统加密算法无法实现抗抵赖的需求。问题的提出问题的提出80起源n公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献： W.Diffie and M.

40、E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654nRSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-12681公开密钥密码的重要特性加密与解密由不同的密钥完成加密: mc: c = EK(m)解密: cm: m = DB(c) = DB(EK(m)知道加密算法,

41、从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)m = DB(EK(m) = EK(DB(m)822. 公钥密码体制的应用概述83公钥加密算法n传统加密过程加密和解密使用相同密钥加密和解密使用相同密钥明文明文明文明文密文密文84公钥加密算法n公钥密码算法加密和解密使用加密和解密使用不同密钥不同密钥明文明文明文明文密文密文85 用公钥密码实现保密用公钥密码实现保密BBBBkkkkk )kkAliceBobcEmBobDcDEmm用户拥有密钥对（k,公钥 公开，私钥 保密： （ ）： （ ）（ ）86基于公开密钥的加密过程87 用公钥密码实现用

42、公钥密码实现认证认证AAAAkkkkk )kkAliceBobcEmBobDcDEmm用户拥有密钥对（k,公钥 公开，私钥 保密： （ ）： （ ）（ ）88基于公开密钥的认证过程89 用公钥密码实现用公钥密码实现保密与认证保密与认证BAABABABBAkkkkkkkkkkk )kkAliceBobcEDmBobDDDEDmm用户拥有密钥对（k,公钥 公开，私钥 保密： （ ）： （E (c)） （E (c)） （E (（ ）)） 90 公钥密钥的应用范围加密加密/解密解密数字签名数字签名(身份鉴别身份鉴别)密钥交换密钥交换算法加/解密数字签名密钥交换RSA是是是Dieffie-Hellman

43、否否是DSS否是否913. 公钥密码算法92基本思想和要求n涉及到各方：发送方、接收方、攻击者n涉及到数据：公钥、私钥、明文、密文n公钥算法的条件：n产生一对密钥是计算可行的n已知公钥和明文，产生密文是计算可行的n接收方利用私钥来解密密文是计算可行的n对于攻击者，利用公钥来推断私钥是计算不可行的n已知公钥和密文，恢复明文是计算不可行的n(可选)加密和解密的顺序可交换93陷门单向函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y, 计算x使x=fk-1(y)是不可行的。(3)存在k，已知k 时,对给定的任何y，若相应的x存在，则计算x使fk-1(y)是

44、容易的。94 公钥密码基于的数学难题公钥密码基于的数学难题 背包问题背包问题 大 整 数 分 解 问 题 （大 整 数 分 解 问 题 （ T h e I n t e g e r T h e I n t e g e r Factorization Problem,RSAFactorization Problem,RSA体制）体制） 有限域的乘法群上的离散对数问题有限域的乘法群上的离散对数问题 (The Discrete Logarithm Problem,(The Discrete Logarithm Problem, ElGamal ElGamal体制）体制） 椭圆曲线上的离散对数问题（椭圆

45、曲线上的离散对数问题（The EllipticThe Elliptic Curve Discrete Logarithm Problem, Curve Discrete Logarithm Problem, 类比的类比的ElGamalElGamal体制）体制）95背包问题n背包问题：n已知一长度为B的背包，及长度分别为a1,a2,.,an的n个物品。假定这些物品的半径和背包相同，若从这n个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？96背包问题数学描述ii112x011,2,., ,a,.,bniininxba aa求 或 ，使其满足：其中和 都是整数97背包问题求解NPN

46、P背包问题属于完备类（问题中难度最大的一类）对这一问题没有有效算法11(2,3,., )ijja in12ni但是，如果序列a ,a ,.,a 是超递增序列：a背包问题有多项式解法98超递增序列背包问题求解方法123456248163243xxxxxxn12n例:已知序列a ,a ,.,a 是超递增序列：1,2,4,8,.,2求 背包问题的解思路：思路：xi取值只可能为取值只可能为0或者或者1；如果为；如果为0，表示不，表示不能装入对应的物体，否则可以装入。能装入对应的物体，否则可以装入。99超递增序列背包问题求解方法123456123452481632432481611xxxxxxxxxxx

47、（2）带入：1116,05（3）因为所以有x（不能选）123451234248161124811xxxxxxxxx（4）带入：16(1)对于体积为32的物体，因为4332，所以x（可以选）1246121xxxxxx（ 5 ） 继 续 上 述 过 程 ， 可 得 ： 0100MerkleHellman背包公钥算法122c.nnma ma m1（ 2 ） 利 用 公 钥 加 密 如 下 ： a1212a ,.,.nnaamm mm（1）选取一组正整数作为公钥予以公布是n位0，1明文符号串。12c.nm mm（3）从密文 求明文等价于背包问题101MerkleHellman背包公钥算法12明文： m

48、 10110110，m 11001001123456782832aaaaaaa例如：已知: a ， ， 11， 08 71， 51， 43， 6712分别加密得到密文： c2 8 + 1 1 + 8 + 5 1 + 4 3 1 4 1 c2 8 + 3 2 + 7 1 + 4 7 = 1 9 8102MerkleHellman背包公钥算法n问题：n如何解密？103MerkleHellman背包公钥算法nMH背包公钥算法是由超递增序列进行变换得到得：31(m o d)mm （ ）和互 素 ， 满 足11(2,3,., )ijjbb in12ni（1）设序列b ,b ,.,b 是超递增序列：H(m

49、 o d),1, 2,.,kkM erkleellm a nabmkn( 4 ) 做 变 换 （变 化 ） ：2nmb（2）选取作为模数104MerkleHellman背包公钥算法nMH背包公钥算法的公钥和私钥i（ 1 ） 得 到 的 新 序 列a作 为 公 钥1(mod)m （ 2） 满 足的作 为 私 钥105MerkleHellman背包公钥算法.bbb112233nn112233nna mamamamb mmmm1212.,.,01nnccmm mmm mmnc112233nn(5)假设已知：a ma ma ma m为的密文，其中是位 ， 符号串，则：这是超递增序列的背包问题。106M

50、erkleHellman背包公钥算法28130761mod523例如：1，3，7，13，26，65，119，267是超递增序列取：m=523, =467, 107MerkleHellman背包公钥算法12345678467 1467mod523467 3355mod523467 7131mod523437 13318mod523467 26113mod523467 6521mod523467 119135mod523467 267215mod523aaaaaaaa 108MerkleHellman背包公钥算法(467,355,131,318,113,21,135,215)变换后得到的序列作为公

51、钥予以公布28作为私钥保密109MerkleHellman背包公钥算法356c732aaa1发送方：对于明文m=10101100加密得到密文：a110MerkleHellman背包公钥算法73228mod523c732 28 20496 99mod523接收方：得到密文后，乘以 得：23456781356246737132665119267c991010101100mmmmmmmmmmmmmmmm1解超递增序列背包问题：即得明文：111RSAn算法概要：Bob选择保密的素数p和q，并计算n=pq；Bob通过gcd(e,(p-1)(q-1)=1来选择e；Bob通过de1(mod(p-1)(q-1

52、)来计算d；Bob将n和e设为公开的，p、q、d设为秘密的；Alice将m加密为c me(mod n)，并将c发送给Bob；Bob通过计算m cd(mod n)解密。112密码学RSA: 例例1选择两个素数: p=17&q=11计算n =pq =1711=187计算(n)=(p1)(q-1)=1610=160选择 e : gcd(e,160)=1;其中e=7计算d: de=1mod160 且d 160 ，则 d=23 （因为237=161=10160+1）公布公钥KU=7,187保存私钥KR=23,17,11113密码学RSA：例：例1n如果待加密的消息 M=88 (注意： 88Bob

53、nStep 1：Bob选择Ep(a，b)的元素G，使得G的阶n是一个大素数,秘密选择整数k.计算P=kG,公开(p，a，b，G，P)，保密k。其中KbkG为Bob公钥，Kbk为Bob私钥nStep 2：将消息m编码为x-y形式的点PmnStep 3：Alice随机选择一个正整数r，对Pm产生密文CmrG，PmrKbnStep 4：Bob解密nCm-Kb(rG)n=Pm+rKb-krGn=Pm+r(kG)-rkG=Pm131椭圆曲线密码学ECC加密加密/解密实现解密实现nAlice-Bob(示例）nStep 1：Bob选择E88331(3，45)，G(4,11), Bob私钥KbK=3, Bob

54、公布公钥Kb(413,1808) nStep 2： Pm=(5,1734) nStep 3：Alice随机选择一个正整数r=8，对Pm产生密文:CmrG，PmrKb=(5415,6321),(6626,3576)nStep 4：Bob解密nKb(rG)=3(5415,6321)=(673,146)nCm -Kb(rG)=(6626,3576)-(673,146)=(5,1734)132密码学序列密码序列密码n按位处理消息n一般具有一个伪随机密钥流发生器n对明文按位进行异或运算 (XOR)n以随机的密钥流来破坏消息的统计特征nCi=MiXORStreamKeyi133密码学序列密码序列密码同步流

55、密码原理密钥流生成器密钥流生成器密钥流生成器密钥流生成器加密变换加密变换解密变换解密变换安全信道安全信道公开信道种子密钥种子密钥k种子密钥种子密钥k密钥流密钥流Ki密钥流密钥流Ki明文明文m密文密文c密文密文c明文明文m134密码学序列密码序列密码自同步流密码原理密钥流生成器密钥流生成器密钥流生成器密钥流生成器加密变换加密变换解密变换解密变换安全信道安全信道公开信道种子密钥种子密钥k种子密钥种子密钥k密钥流密钥流Ki密钥流密钥流Ki明文明文m密文密文c密文密文c明文明文m135密码学序列密码：序列密码：RC4nRC： “RC” is Rons Code or Rivest Ciphern198

56、7年Ron Rivest 为RSA公司所设计的流密码算法n可变密钥长度的、面向字节操作的流密码：82048位可变n1994年算法才公开n在SSL/TLS和IEEE 802.11无线网络中有广泛应用：WEP协议136密码学序列密码：序列密码：RC4n用从1到256个字节的可变长度密钥初始化矢量S：0.255 ，S0,S1,S255nS 形成了算法的内部状态n密钥流字节K由S中255个元素按照一定方式选出一个元素来生成n每生成一个K，S中的元素就被重新置换一次RC4初始化初始化137密码学序列密码：序列密码：RC4n初始化Sn初始条件：密钥种子 Key ,密钥初始化向量Sn初始化S：S中元素被置为

57、按升序从0到255：nS0=0,S1=1,S255=255n建立一个临时矢量Kn如果密钥种子Key的长度为256字节，则将Key赋值给K；n否则将K的值赋给K的前N个元素（N为密钥长度），n循环重复用Key的值赋给K剩下的元素,直到K的所有元素都被赋值n然后用K产生S的初始置换n从S0到S255，对每个Si，根据由Ki确定的方案，将Si置换为S中的另外一个字节n由于对S的操作仅是交换（即置换），因此S仍然包含所有值为0到255的元素密钥生成密钥生成Input ：Key , N=len(key)Output: S /*密钥流初始值*/*Array “key” contains N bytes o

58、f key*/*Array “S” always has a permutation of 0,1,255*/for i = 0 to 255Si = iKi = keyi (mod N)next ij = 0for i = 0 to 255j = (j + Si + Ki) mod 256swap(Si, Sj)next i138密码学序列密码：序列密码：RC4n密钥流KeyStramByte的生成是从S0到S255，对每个Si，根据当前S的值，将Si与S中另外一个字节置换n当S255完成置换后，操作继续重复n加密：n将KeyStreamByte值与下一个明文字节异或n解密：n将KeyStr

59、eamByte值与下一个密文字节异或加密与解密加密与解密Input ：M, S Output: Cij0foreachmessagebyteMii=(i+1)mod256j=(j+Si)mod256swap(Si,Sj)t=(Si+Sj)mod256KeyStreamByte=StCi=MiXORKeyStreamByteNextC=C1|C2|Cn139密码学序列密码：序列密码：RC4n对已知的密码分析很安全n有很多攻击分析，但不是很实际n结果非线性n绝对不能重复使用密钥n在无线保密协议（ WEP）中使用，但是有潜在的安全问题RC4安全性安全性对于对于WEP协议，后续内容将进一步讨论协议，后

60、续内容将进一步讨论140n硬件加密n采用电路、器件等对硬件本身的加密n采用硬件对软件和数据的加密n加密包括：隐藏、防护，防破译、防窃听等n芯片技术n将软件算法由硬件芯片实现n压缩解压芯片n将算法固化在存储芯片中硬件加解密技术硬件加解密技术其他密码学知识141n采用软件方法的加解密技术n程序、数据结构、数据变换、循环、迭代循环、嵌套循环、迷宫程序等。n软件压缩还原技术n用于数据压缩、文本压缩、存储单元压缩、影象压缩技术等应用算法，压缩加密。n压缩文本成为攻击对象，还原问题成为安全的关键研究。软件加解密技术软件加解密技术其他密码学知识142n不知道密码，可能入侵密码系统n不知道密钥，仍然可能入侵密码系统n被动攻击：截获密文，分析推断