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

1第2讲密码学基础2密码学的起源和发展三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学3第1阶段－古典密码

密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密4第1阶段－古典密码Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。520世纪早期密码机6第1阶段－古典密码1883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。7

计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“TheCommunicationTheoryofSecretSystems”

1967年DavidKahn的《TheCodebreakers》1971-1973年IBMWatson实验室的HorstFeistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密

第2阶段1949~197581976年：Diffie&Hellman的

“NewDirectionsinCryptography”

提出了不对称密钥；1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能第3阶段1976~91977年DES正式成为标准80年代出现“过渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael成为DES的替代者第3阶段1976~10保密通信11保密通信的功罪100年前，1894年的中日甲午海战，中国惨败，其本质是由于清政府的腐败，但其中一个重要的具体原因，是日方在甲午战争前就破译了清政府使用的密电码。日方破译的电报多达一百余则，对清政府的决策、海军的行踪等了如指掌，因而日方不仅在海战中取得了胜利，还迫使清政府签订“马关条约”，割让辽东半岛、台湾及澎湖列岛，赔偿军费白银2亿两。12保密通信的功罪1917年1月，正当第一次世界大战进入第三个年头时，英国海军破译机关截收到了德国外长齐默尔曼签发的一份密报，经过一个多月的辛勤劳作，终于在2月下旬完全破开了那份密报。密报称，德国将在欧洲进行无限制的潜艇战，意思是说，中立国家的船队也在其打击目标之列，同时指出，若美国不再保持中立，就要求墨西哥与德国结盟，对美宣战。英国外交部在权衡了种种利弊后，到2月22日将此密报交给了美国政府，德国政府的阴谋激怒了开战以来一直保持中立并且在三个月前还声明继续保持中立的美国人，五个星期后美国对德宣战，出兵西线，既避免了在美国本土燃起战火，又加速了协约国的胜利。13保密通信的功罪1941年12月，日本取得了突袭珍珠港、摧毁美国太平洋舰队主力的重大胜利，为了完全控制太平洋，并设法诱出在珍珠港的美国舰队残部予以彻底消灭，日本制定了于1942年6月突然攻击夏威夷前哨中途岛的计划。14保密通信的功罪当时日本海军使用的是日本最高级的密码体制——紫密，它的第二版本JN25b自1940年12月1日启用后应在1942年4月1日内第三版本JN25c替换。但由于舰船分散在广阔的海域不停地转移，给分发新的版本增添许多困难，因此替换工作延期到5月1日，后因同样的原因再延期—个月，到6月1日启用新版本。这就使盟国破译人员有充分的时间更透彻地破解JY25b。5月27日，山本的作战命令已基本上被破译，美国太平洋舰队司令尼米兹海军上将发布作战计划，将3艘航空母舰部署在敌舰不可能侦察到的海域，战斗打响时也以突然攻击的方式打击日军的突击舰队。6月4日，日军4艘巨型航空母舰在一日之内相继被炸沉．从此日本海军由进攻转为防御，最终走向失败。15保密通信的功罪1943年春天，山本五十六为了控制不断恶化的残局，亲自前住所罗门群岛基地巡视，以鼓舞士气。在视察前五天，1943年4月13日，日军第八舰队司令将山本行将视察的行程、时间表，用JN25体制加密后播发给有关基地，以作好迎接的准备，尽管该体制的所用版本在4月1日刚换过，但美国破译人员根据过去的经验，迅速地破译了这份密报，美军决定在空中打掉山本的座机，使日军失去一位战略家，沉重地打击日军士气。经过精心组织，周密安排，终于使山本五十六在飞往视察地途中，被美军飞机击落，葬身于丛林深处。16密码学起源密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为解密变换。１７世纪，英国著名的哲学家弗朗西斯·培根在他所著的《学问的发展》一书中最早给密码下了定义，他说，“所谓密码应具备三个必要的条件，即易于翻译、第三者无法理解、在一定场合下不易引人生疑。”

加密解密明文密文原始明文17密码学起源谋成于密，败于泄——明揭暄兵经百言》古典密码学包含两个互相对立的分支，即密码编码学（Cryptography）和密码分析学（Cryptanalytics）。前者编制密码以保护秘密信息，而后者则研究加密消息的破译以获取信息。二者相反相成，共处于密码学的统一体中。现代密码学除了包括密码编码学和密码分析学外，还包括安全管理、安全协议设计、散列函数等内容。18密码学起源大约在4000年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号(明文)用另一种符号(密文)代替19密码学起源公元前5世纪，古斯巴达人使用了一种叫做“天书”的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。20密码学起源公元前1世纪古罗马凯撒大帝时代曾使用过一种“代替式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种代替式密码直到第二次大战时还被日本海军使用。公元前4世纪前后，希腊著名作家艾奈阿斯在其著作《城市防卫论》中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。21密码学起源〈六韬．龙韬．阴符〉武王问太公曰：‘引兵深入诸侯之地，三军猝有缓急，或利或害。吾将以近通远，从中应外，以给三军之用。为之奈何？’太公曰：‘主与将，有阴符。凡八等：有大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；誓众坚守之符，长六寸；请粮益兵之符，长五寸；败军亡将之符，长四寸；失利亡士之符，长三寸。诸奉使行符，稽留者，若符事泄，闻者告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之通识。’武王曰：‘善哉。’22密码学起源〈六韬．龙韬．阴书〉武王问太公曰：‘引兵深入诸侯之地，主将欲合兵，行无穷之变，图不测之利。其事繁多，符不能明；相去辽远，言语不通。为之奈何？’太公曰：‘诸有阴事大虑，当用书，不用符。主以书遗将，将以书问主。书皆一合而再离，三发而一知。再离者，分书为三部；三发而一知者，言三人，人操一分，相参而不知情也。此谓阴书。敌虽圣智，莫之能识。’武王曰：‘善哉。’23密码学起源在古代还出现过一种被称为“叠痕法”的密码，使用时先把信纸折叠几下（上下及左右），然后铺平信纸，将传递的信息按顺序一个个分开，写在折痕的交叉点上，每一个交叉点写一个字。然后再在空白位置上填上公开的普通信文，普通信文与秘密信文的文字通顺地连贯在一起。为了防止被敌人察觉，使用这种密码需要在编公开信文上下些功夫。如果在秘密信文上再用些暗语式密码，那么敌人就更难看出破绽了。宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密码本体制的特点。24密码学起源暗号。简单地说，暗号就是通过用物件的状态或人的行为来传达事先约定的信息．如窗台上的花瓶、手中拿着的报纸、口中昨着的曲子，可分别代表“现在安全”、“我是你要找的人”、“我在找自己人”等明确的信息．隐语。暗号是把信息变换为物件或动作，隐语则是把信息变换成与此信息完全无关的(但有意义的)语言．据说，1941年，日本偷袭珍珠港前两星期，美国情报人员曾截获一次重要的电话对话．那是两名分别在东京和华盛顿的日本高级官员之间的通话．这段对话里“小孩出生”的真正意思是“发动战争”．在华盛顿的日本人：是不是真的有个小孩要出生了?在东京的日本人：是的．而且看来马上就要出生了．在华盛顿的日本人：这个小孩真的要生了吗?是在哪个方向呢?25密码学起源16世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称“卡尔达诺漏格板”．漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格．26密码学起源〈兵经百言．衍部．传〉军行无通法，则分者不能合，远者不能应。彼此莫相喻，败道也。然通而不密，反为敌算。故自金、旌、炮、马、令箭、起火、烽烟，报警急外；两军相遇，当诘暗号；千里而遥，宜用素书，为不成字、无形文、非纸简。传者不知，获者无迹，神乎神乎！或其隔敌绝行，远而莫及，则又相机以为之也。”27密码学起源大约在1793年，当时的美国总统托马斯杰斐逊发明了一种轮子密码机。转动轮子使明文中的所有字母全排在一条直线上为止．这时圆柱体的其他25行字母也因这一行的固定而被固定了．任选这25行中的一行发出去即为密文．28密码学起源“谜”（ENIGMA）密码最初是由一个叫胡戈·科赫的荷兰人发明的。起初主要提供给想保护自己生意秘密的公司使用，但其商界的销路一直不理想。后来德国人将其改装为军用型，使之更为复杂可靠。德国海军于1926年开始使用“ENIGMA”，陆军则于1928年开始使用。1933年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队的通信装置。德国人在战争期间共生产了大约10多万部“谜”密码机。1940年，经过盟军密码分析学家的不懈努力，“恩尼格玛”密码机被动攻破，盟军掌握了德军的许多机密，而德国军方却对此一无所知。29密码学起源传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信。30密码学起源第六十回吴用智赚玉麒麟梁山泊义军头领宋江久慕卢俊义的威名，一心想招取卢俊义上山坐第一把交椅，共图大业，替天行道。智多星吴用扮成一个算命先生，利用卢俊义正为躲避“血光之灾”的惶恐心里，口占四句卦歌，并让他端书在家宅的墙壁上。卢花滩上有扁舟，俊杰黄昏独自游。义到尽头原是命，反躬逃难必无忧。这四句诗写出后，被官府拿到了证据，大兴问罪之师，到处捉拿卢俊义，终于把他逼上梁山。3132加密与解密现代密码学涉及数学（如数论、有限域、复杂性理论、组合算法、概率算法等）、物理学（如量子力学、现代光学、混沌动力学等）、信息论、计算机科学等学科。1949年，信息论之父C.E.Shannon发表了《保密系统的通信理论》，密码学走上科学和理性之路。1976年W.Diffie和M.E.Hellman发表的《密码学的新方向》，以及1977年美国公布实施的数据加密标准DES，标志着密码学发展的革命。2001年11月美国国家标准技术研究所发布高级数据加密标准AES代表着密码学的最新发展。33加密与解密基于密钥的算法通常有两类：对称算法和公开密钥算法。使用一个密钥的加/解密。加密时可以使用一个参数K，称此参数K为加密密钥。K可以是很多数值里的任意值。密钥K的可能值的范围叫做密钥空间。34加密与解密使用两个密钥的加/解密。EK1（P）=CDK2（C）=PDK2

（EK1（P））=P解密密钥加密密钥原始明文密文加密解密明文35加密与解密加密通信的模型信源Mm加密器解密器接收者m非法接入者搭线信道（主动攻击）C’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道36加密与解密对称算法就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法。对称算法可分为两类。序列密码（流密码）与分组密码。37序列密码（流密码）序列密码主要应用于军事和外交场合。序列密码的优点是错误扩展小、速度快、利于同步、安全程度高。密钥流产生器密钥k明文m密文c异或运算38序列密码伪随机序列发生器是指输入真随机的较短的密钥（种子）通过某种复杂的运算产生大量的伪随机位流。真随机序列从真实世界的自然随机性源产生。如自然界中的抛币。伪随机序列用确定的算法产生，不是真正的随机序列。伪随机序列发生器指使用短的真随机序列（称为种子）x扩展成较长的伪随机序列y。随机数是较短的随机位序列。seed(short)PRBS(long)011011010010110....39分组密码分组密码是将明文按一定的位长分组，明文组和密钥组的全部经过加密运算得到密文组。数据加密标准DES出自IBM被美国政府正式采纳的数据加密算法（DataEncryptionAlgorithm，DEA）由中国学者来学嘉XuejiaLai和JamesL.Massey在苏黎世的ETH开发的国际数据加密算法IDEA（InternationalDataEncryptionAlgorithm）比利时JoanDaemen和VincentRijmen提交，被美国国家标准和技术研究所（USNationalInstituteofStandardsandTechnology，NIST）选为美国高级加密标准（AES）的Rijndael。40分组密码的操作模式电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数器模式CTR）美国NSB在[FIPSPUB74和81]中规定ANSI在[ANSIX3.106]中规定

ISO和ISO/IEC在[ISO9732ISO/IEC10116]中规定分组密码的操作模式模式描述典型应用电子密码本ECB用相同的密钥分别对明文分组加密单个数据的安全传输密码分组链接CBC加密算法的输入是上一个密文分组和下一个明文分组的异或普通目的的面向分组的传输密码反馈CFB一次处理J位，上一个分组密文作为产生一个伪随机数输出的加密算法的输入，该输出与明文分组异或，作为下一个分组的输入普通目的的面向分组的传输认证输出反馈OFB与CFB相同，只是加密算法的输入是上一次DES的输出噪声信道上数据流的传输（如卫星传输）计数器模式CTR）每个明文分组是加密的计数器的异或，对每个后续的分组，计数器是累加的。普通目的的面向分组的传输用于高速需求42分组密码的分析方法根据攻击者所掌握的信息,可将分组密码的攻击分为以下几类:唯密文攻击已知明文攻击选择明文攻击攻击的复杂度数据复杂度:实施该攻击所需输入的数据量处理复杂度:处理这些数据所需要的计算量43分组密码的典型攻击方法最可靠的攻击办法:强力攻击最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特.线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统插值攻击方法密钥相关攻击44强力攻击穷尽密钥搜索攻击:唯密文,2k已知(选择)明文,2k,k-密钥长度字典攻击:明密文对编成字典,2n,n-分组长度查表攻击:选择明文攻击,给定明文,用所有的2k个密钥,预计算密文,k-密钥长度时间存储权衡攻击:选择明文攻击,由穷尽密钥搜索和查表攻击混合而成,它在选择明文攻击中以时间换取空间45现代常规分组加密算法

一种是对DES进行复合，强化它的抗攻击能力；另一种是开辟新的方法，即象DES那样加解密速度快，又具有抗差分攻击和其他方式攻击的能力。46现代常规分组加密算法1.TripleDES2.IDEA3.RC54.RC65.AES其他一些较实用的算法，如Blowfish，CAST，以及RC2。47双重DES(DoubleDES)C=EK2(EK1(P))P=DK1(DK2(C))

48Triple-DES的四种模型DES-EEE3：三个不同密钥，顺序使用三次加密算法DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法DES-EEE2：K1=K3，同上DES-EDE2：K1=K3，同上491.TRIPLEDES由于已经证明DES不能成为群，见

K.W.CampbellandM.J.WienerProofthatDESisnotagroupInAdvancesinCryptology——Crpto’92.Springer-Verlag,NewYork,1993.于是多重DES，尤其是三重DES还在普遍使用。50双密钥的三重DES

（TripleDESwithTwoKeys)C=EK1(DK2(EK1(P)))P=DK1(EK2(DK1(C)))51三密钥的三重DES

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

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

56初始置换IP和初始逆置换IP—1

Li-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器扩充/置换运算48比特寄存器子密钥Ki（48比特）32比特寄存器代换/选择运算置换运算PRi（32比特）Li=Ri-1DES的一轮迭代F函数DES:FunctionFExpansion:3248（扩充）S-box:64（压缩）Permutation:置换

扩充/置换运算32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|0160代换/选择运算61S-Box-i62S-Box-ii

63S-Box对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。相应行、列位置的十进制数的4位二进制数表示作为输出。例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。

64

Permutation1607202129122817011523260518311002082414322703091913300622110425子密钥的产生

k1

（56位）(48位)

ki

（56位）

（48位）64位密钥置换选择1

C0（28位）

D0（28位）

循环左移循环左移

C1（28位）

D1（28位）

循环左移循环左移

Ci（28位）

Di（28位）置换选择2置换选择2密钥表的计算逻辑循环左移：11912110232112421225213262142721528

216166置换选择1(PC-1)和置换选择2(PC-2)

总结－DES示意图68DES的安全性分析DES的安全性完全依赖于密钥，与算法本身没有关系。主要研究内容：密钥的互补性；弱密钥与半弱密钥；密文-明文相关性；密文-密钥相关性；S-盒的设计；密钥搜索。69弱密钥弱密钥：由密钥k确定的加密函数与解密函数相同，即。DES的弱密钥：如果各轮产生的子密钥一样，则加密函数与解密函数相同。DES至少有4个弱密钥：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe70半弱密钥半弱密钥：对于密钥k，存在一个不同的密钥，满足。DES的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密钥，互为对合。DES至少有12个半弱密钥。71S-盒的设计原则S-盒的设计原理没有公开，一些原则如下：所有S-盒的每一行是0,1,…,15的一个置换；所有S-盒的输出都不是输入的线性函数或仿射函数；S-盒的输入改变任意一位都会引起输出中至少两位发生变化；对于任何输入x（6位），S(x)与S(x⊕001100)至少有两位不同；对于任何输入x（6位），S(x)与S(x⊕00ef00)不相等，e,f取0或1；对于任意一个输入位保持不变而其他五位变化时，输出中0和1的数目几乎相等。72针对DES的攻击方法攻击DES的方法主要有：密钥穷搜索攻击，DES算法总的密钥量为，1998年使用高级计算机的情况下，破译DES只需56小时；差分攻击；线性攻击，较有效的方法；相关密钥攻击等。73DES的破译1990年，以色列密码学家EliBiham和AdiShamir提出了差分密码分析法，可对DES进行选择明文攻击。线性密码分析比差分密码分析更有效

74公钥密码公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。公开密钥算法主要用于加密/解密、数字签名、密钥交换。75讨论议题为什么要设计公钥密码算法密钥分配公钥密码体制概述及其应用公钥密码算法的实现Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC761.为什么要设计公钥密码体制77密钥分配（KeyDistribution）保密通信双方需共享密钥共享密钥要经常更换A选择密钥并手工传递给B第三方C选择密钥分别手工传递给A,B用A,B原有共享密钥传送新密钥与A,B分别有共享密钥的第三方C传送新密钥给A和/或BN个用户集需要N(N-1)/2个共享密钥密钥分发中心(KeyDistributionCenter)78密钥分发中心（KDC）每个用户与KDC有共享密钥(MasterKey)N个用户,KDC只需分发N个MasterKey两个用户间通信用会话密钥(SessionKey)用户必须信任KDCKDC能解密用户间通信的内容79

（1）密钥管理量的困难传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500

（2）数字签名的问题传统加密算法无法实现抗抵赖的需求。问题的提出80起源公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献：

W.DiffieandM.E.Hellman,NewDirectrionsinCryptography,IEEETransactiononInformationTheory,V.IT-22.No.6,Nov1976,PP.644-654RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的,见

CommunitionsoftheACM.Vol.21.No.2.Feb.1978,PP.120-12681公开密钥密码的重要特性加密与解密由不同的密钥完成 加密:mc:c=EK(m)

解密:cm:m=DB(c)=DB(EK(m))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) m=DB(EK(m))=EK(DB(m))822.公钥密码体制的应用概述83公钥加密算法传统加密过程加密和解密使用相同密钥明文明文密文84公钥加密算法公钥密码算法加密和解密使用不同密钥明文明文密文85

用公钥密码实现保密86基于公开密钥的加密过程87

用公钥密码实现认证88基于公开密钥的认证过程89

用公钥密码实现保密与认证90

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

公钥密码基于的数学难题背包问题大整数分解问题（TheIntegerFactorizationProblem,RSA体制）有限域的乘法群上的离散对数问题

(TheDiscreteLogarithmProblem,ElGamal体制）椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,

类比的ElGamal体制）95背包问题背包问题：已知一长度为B的背包，及长度分别为a1,a2,...,an的n个物品。假定这些物品的半径和背包相同，若从这n个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？96背包问题数学描述97背包问题求解98超递增序列背包问题求解方法思路：xi取值只可能为0或者1；如果为0，表示不能装入对应的物体，否则可以装入。99超递增序列背包问题求解方法100Merkle－Hellman背包公钥算法101Merkle－Hellman背包公钥算法102Merkle－Hellman背包公钥算法问题：如何解密？103Merkle－Hellman背包公钥算法

MH背包公钥算法是由超递增序列进行变换得到得：104Merkle－Hellman背包公钥算法

MH背包公钥算法的公钥和私钥105Merkle－Hellman背包公钥算法

106Merkle－Hellman背包公钥算法

107Merkle－Hellman背包公钥算法

108Merkle－Hellman背包公钥算法

109Merkle－Hellman背包公钥算法

110Merkle－Hellman背包公钥算法

111RSA算法概要：Bob选择保密的素数p和q，并计算n=pq；Bob通过gcd(e,(p-1)(q-1))=1来选择e；Bob通过de≡1(mod(p-1)(q-1))来计算d；Bob将n和e设为公开的，p、q、d设为秘密的；Alice将m加密为c≡me(modn)，并将c发送给Bob；Bob通过计算m≡cd(modn)解密。112密码学RSA:例1选择两个素数:p=17&q=11计算

n=pq=17×11=187计算ø(n)=(p–1)(q-1)=16×10=160选择e:gcd(e,160)=1;其中e=7计算d:de=1mod160

且d<160

，则

d=23

（因为23×7=161=10×160+1）公布公钥KU={7,187}保存私钥KR={23,17,11}113密码学RSA：例1如果待加密的消息M=88(注意：88<187)加密：C=887mod187=11

解密:M=1123mod187=88

密码学RSA：例2Bob选择p=885320693，q=238855417，则可以计算

n=p*q=211463707796206571，设加密系数为e=9007，将n和e发送给Alice。假设Alice传递的信息是cat。令a=01c=03t=20，则cat=030120=30120。

Alice计算：c≡me≡301209007≡113535859035722866(modn)

她将c传给Bob。Bob已知p和q的值，他用扩展欧几里德算法计算d：

de≡1(mod(p-1)(q-1))，得到

d=116402471153538991

然后Bob计算：

cd≡113535859035722866116402471153538991≡30120(modn)

由此他可以得到最初的信息。115密码学ECCECC:EllipticCurveCryptography1985年，N.Koblitz及V.S.Miller分别提出了椭圆曲线密码体制（ECC）。已经开发出的椭圆曲线标准的文档有：IEEEP1363P1363a、ANSIX9.62X9.63、ISO/IEC14888等。近年来，ECC已走向工程实现和实际应用阶段。目前，德国、日本、法国、美国、加拿大等许多西方国家的密码学研究小组和公司已经实现了椭圆曲线密码体制。116密码学ECC为什么要提出ECC？RSA主要问题之一：为了保证必要的安全强度，其密钥必须很长ECC的优势：在同等安全强度下，ECC所需密钥比RSA短117密码学ECC椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程所确定的平面曲线。其中，系数（i=1，2，…，6）定义在基域K上（K可以是有理数域、实数域、复数域，还可以是有限域，椭圆曲线密码体制中用到的椭圆曲线都定义在有限域上）。椭圆曲线并非椭圆118密码学ECC群：对于非空集合G，其上的一个二元运算（.）满足：封闭性、结合率、单位元和可逆性环：对于R上的两个二元运算（+，x）满足：关于＋是一个交换群（群的条件＋交换率）对于乘法x满足：封闭性＋结合率＋分配率域：对于F上的两个运算（+，x）满足F是一个整环：交换环＋乘法逆元＋无零因子乘法逆元存在119密码学ECC120密码学ECC椭圆曲线加法运算规则：O是加法的单位元，O＝－O；对于椭圆曲线上的任一点P，有P＋O＝P点P的负元是与P具有现同x坐标和相反y坐标的点，即若P＝（x，y），则-P＝（x，-y）；P＋（P)=O若P＝（x1，y），Q＝（x2，z），则P＋Q＝-R。其中R是直线PQ与椭圆曲线的第三个交点。若P和Q的x坐标相同，则为无穷远点O若Q＝（x，y），则Q＋Q＝2Q＝－S，其中S为椭圆曲线在Q点的切线与椭圆曲线的另一交点。121椭圆曲线密码学ECC有限域上椭圆曲线 y2x3+ax+bmodpp是奇素数,且4a3+27b20modp（构成Abel群的条件，证明过程略） y2+xyx3+ax2+bmod2m(Galois域的椭圆曲线）122椭圆曲线密码学ECC有限域上椭圆曲线 y2x3+ax+bmodp

（3）加法公式:P=(xp,yp),Q=(xQ,yQ)若xP=xQ且yP=-yQ则P+Q=O否则P+Q=(xR,yR)xR=2-xP-xQyR=(xP-xR)-yP其中

=(yQ-yP)/(xQ-xP),如果PQ=(3xP2+a)/（2yP），如果P=Q（1）P+O=P（2）P=(x,y)P＋(x,-y)=O其中（x,-y)是P的负元－P(4)重复相加：nP=P+…+P按照上述定义构成了一个椭圆曲线上的Abel群123椭圆曲线密码学ECC示例：有限域上椭圆曲线

y2x3+ax+bmodp条件：a=1,b=1,x=9,y=7,p=23y2

=72mod23=3x3+ax+b=(93+9+1)mod23=3y2x3+ax+bmodp124椭圆曲线密码学ECC示例示例：有限域上椭圆曲线

y2x3+ax+bmodp条件：a=1,b=1,x=9,y=7,p=23问题：求满足上述方程的所有整数对（x，y）以及无穷远点O组成的集合Ep（a，b）＝E23（1，1）？125椭圆曲线密码学ECC示例(0,1)(6,4)(12,19)(0,22)(6,19)(13,7)(1,7)(7,11)(13,16)(1,16)(7,12)(17,3)(3,10)(9,7)(17,20)(3,13)(9,16)(18,3)(4,0)(11,3)(18,20)(5,4)(11,20)(19,5)(5,19)(12,4)(19,18)E23（1，1）126椭圆曲线密码学ECC示例(0,1)(6,4)(12,19)(0,22)(6,19)(13,7)(1,7)(7,11)(13,16)(1,16)(7,12)(17,3)(3,10)(9,7)(17,20)(3,13)(9,16)(18,3)(4,0)(11,3)(18,20)(5,4)(11,20)(19,5)(5,19)(12,4)(19,18)E23（1，1）1）P＝（0，1），P+O＝（0，1）2）P＝（13，7）

-P=（13，-7）=(13,16)3）P＝（3，10），Q＝（9，7）

P+Q=(17,20)4）P＝（3，10）

2P=(7,12)127椭圆曲线密码学ECCP＋Q计算过程：x3=2-x1-x2y3=(x1-x3)-y1其中=(y2-y1)/(x2-x1),如果PQ=(3x12+a)/2y1,如果P=Q128椭圆曲线密码学ECC有限域上椭圆曲线y2+xyx3+ax2+bmod2m(Galois域的椭圆曲线）（3）加法公式:P=(xP,yP),Q=(xQ,yQ),且P≠-Q,P≠Q则P+Q=(xR,yR)xR=2++xP+xQ+ayR=(xP+xR)+xR+yP其中

=(yQ+yP)/(xQ+xP)（1）P+O=P（2）P=(x,y)P＋(x,-y)=O其中（x,-y)是P的负元－P(4)若P=(xP,yP),则R＝2P=(xr,yr)其中：xR=2++ayR=xP2+(+1)xR=xp+yp/xP按照上述定义构成了一个椭圆曲线上的Abel群129椭圆曲线密码学ECC椭圆曲线上的离散对数“难题”对于方程Q=kP,其中P，Q属于Ep(a,b)。对于给定的k和P，计算Q比较容易，而对于给定的P和Q，计算k比较困难例如：方程y2=(x3+9x+17)mod23所定义的群E23(9,17)。求：P＝（16，5）和Q＝（4，5）的离散对数k？穷举计算：P＝（16，5），2P＝(20,20),3P=(14,14)，4P＝（19，20），5P＝13，10）；6P＝（7，3），7P＝（8，7），8P＝（12，17），9P＝（4，5）因此k＝9130椭圆曲线密码学ECC加密/解密实现Alice->BobStep1：Bob选择Ep(a，b)的元素G，使得G的阶n是一个大素数,秘密选择整数k.计算P=kG,公开(p，a，b，G，P)，保密k。其中Kb＝kG为Bob公钥，Kb‘＝k为Bob私钥Step2：将消息m编码为x-y形式的点PmStep3：Alice随机选择一个正整数r，对Pm产生密文Cm＝{rG，Pm＋rKb}Step4：Bob解密Cm-Kb’(rG)=Pm+rKb-krG=Pm+r(kG)-rkG=Pm131椭圆曲线密码学ECC加密/解密实现Alice->Bob(示例）Step1：Bob选择E88331(3，45)，G＝(4,11),Bob私钥Kb‘＝K=3,Bob公布公钥Kb＝(413,1808)Step2：Pm=(5,1734)

Step3：Alice随机选择一个正整数r=8，对Pm产生密文:Cm＝{rG，Pm＋rKb}={(5415,6321),(6626,3576)}Step4：Bob解密Kb’(rG)=3(5415,6321)=(673,146)Cm-Kb’(rG)=(6626,3576)-(673,146)=(5,1734)132密码学序列密码按位处理消息一般具有一个伪随机密钥流发生器对明文按位进行异或运算(XOR)以随机的密钥流来破坏消息的统计特征Ci=MiXORStreamKeyi

133密码学序列密码同步流密码原理密钥流生成器密钥流生成器加密变换解密变换安全信道公开信道种子密钥k种子密钥k密钥流Ki密钥流Ki明文m密文c密文c明文m134密码学序列密码自同步流密码原理密钥流生成器密钥流生成器加密变换解密变换安全信道公开信道种子密钥k种子密钥k密钥流Ki密钥流Ki明文m密文c密文c明文m135密码学序列密码：RC4RC：“RC”isRon’sCodeorRivestCipher1987年RonRivest为RSA公司所设计的流密码算法可变密钥长度的、面向字节操作的流密码：8～2048位可变1994年算法才公开在SSL/TLS和IEEE802.11无线网络中有广泛应用：WEP协议136密码学序列密码：RC4用从1到256个字节的可变长度密钥初始化矢量S：0..255，S[0],S[1],…,S[255]S形成了算法的内部状态密钥流字节K由S中255个元素按照一定方式选出一个元素来生成每生成一个K，S中的元素就被重新置换一次RC4初始化137密码学序列密码：RC4初始化S初始条件：密钥种子Key[],密钥初始化向量S初始化S：S中元素被置为按升序从0到255：S[0]=0,S[1]=1,…,S[255]=255建立一个临时矢量K如果密钥种子Key的长度为256字节，则将Key赋值给K；否则将K的值赋给K的前N个元素（N为密钥长度），循环重复用Key的值赋给K剩下的元素,直到K的所有元素都被赋值然后用K产生S的初始置换从S[0]到S[255]，对每个S[i]，根据由K[i]确定的方案，将S[i]置换为S中的另外一个字节由于对S的操作仅是交换（即置换），因此S仍然包含所有值为0到255的元素密钥生成Input：Key[],N=len(key)Output:S[]/*密钥流初始值*//*Array“key”containsNbytesofkey*//*Array“S”alwayshasapermutationof0,1,…,255*/ fori=0to255 S[i]=i K[i]=key[i(modN)] nexti j=0 fori=0to255 j=(j+S[i]+K[i])mod256 swap(S[i],S[j]) nexti138密码学序列密码：RC4密钥流KeyStramByte的生成是从S[0]到S[255]，对每个S[i]，根据当前S的值，将S[i]与S中另外一个字节置换当S[255]完成置换后，操作继续重复加密：将KeyStreamByte值与下一个明文字节异或解密：将KeyStreamByte值与下一个密文字节异或加密与解密Input：M,S[]Output:Ci＝j＝0foreachmessagebyteMii=(i+1)mod256j=(j+S[i])mod256swap(S[i],S[j])t=(S[i]+S[j])mod256KeyStreamByte=S[t]Ci=MiXORKeyStreamByteNextC=C1|C2|…|Cn

139密码学序列密码：RC4对已知的密码分析很安全有很多攻击分析，但不是很实际结果非线性绝对不能重复使用密钥在无线保密协议（WEP）中使用，但是有潜在的安全问题RC4安全性对于WEP协议，后续内容将进一步讨论140硬件加密采用电路、器件等对硬件本身的加密采用硬件对软件和数据的加密加密包括：隐藏、防护，防破译、防窃听等芯片技术将软件算法由硬件芯片实现压缩解压芯片将算法固化在存储芯片中硬件加解密技术其他密码学知识141采用软件方法的加解密技术程序、数据结构、数据变换、循环、迭代循环、嵌套循环、迷宫程序等。软件压缩还原技术用于数据压缩、文本压缩、存储单元压缩、影象压缩技术等应用算法，压缩加密。压缩文本成为攻击对象，还原问题成为安全的关键研究。软件加解密技术其他密码学知识142不知道密码，可能入侵密码系统不知道密钥，仍然可能入侵密码系统被动攻击：截获密文，分析推断出明文的攻击。主动攻击：向系统注入假信息（串扰、删除、增添、篡改、伪造等）手段的攻击。密码破译与窃取其他密码学知识143唯密文攻击已知明文攻击选择明文攻击选择密文攻击密码分析其他密码学知识144密码学与安全性总结第一阶段80年代第二阶段90年代第三阶段90年代后期信息保密信息保护信息保障密码学保密学加解密技术数据完整性数据可用性数据可控性可信环境可信计算可信存储抗抵赖性++++密码学145密码学与安全性总结（续）密码学（数学基础）编码学分析学相辅相成对立统一机密性、完整性、可鉴别性、抗抵赖性信息源目标服务密码学146密码学密码实现数学发现密码算法算法论证复杂性密钥配置算法实现密码协议加密解密破译技术密钥技术密码应用领域应用密码系统密码管理密钥管理交叉融合基础过程结果密码学与安全性总结（续）密码学147计算复杂性单向函数代数结构密码分析古典密码公钥密码签名模式私钥密码散列函数密码学协议密钥管理操作式抗抵赖机密性密码系统的整体设计与分析数学基础基本工具密码学系统完整性鉴别性密码学与安全性总结（续）密码学148信息安全理论与技术Topic1:信息安全基础InformationSecurityFoundations密码学（Cryptography）消息认证（MessageAuthentication）数字签名（DigitalSignature）身份认证（IdentificationAuthentication）访问控制（AccessControl）密钥管理（KeyManagement）计算机系统与网络安全（ComputerSystemandNetworkFoundation）……信息安全法律法规与标准化信息安全与法律法规基本原理国内外主要信息安全法律法规标准化与标准化组织149信息安全基础

MessageAuthenticationMessageAuthentication：报文鉴别（消息认证，消息鉴别）Message：消息、报文。Authentication：鉴别、认证。认证：消息的接收者对消息进行的验证真实性：消息确实来自于其真正的发送者，而非假冒；完整性：消息的内容没有被篡改。是一个证实收到的消息来自可信的源点且未被篡改的过程。它也可以验证消息的顺序和及时性150消息认证概念三元组（K,T,V)密钥生成算法K标签算法T验证算法V攻击者信宿信源认证编码器认证译码器信道安全信道密钥源TVK151消息认证认证函数鉴别编码器和鉴别译码器可抽象为认证函数认证函数产生一个鉴别标识（AuthenticationIdentification）给出合理的认证协议(AuthenticationProtocol)接收者完成消息的鉴别（Authentication）152消息认证认证函数分类认证的函数分为三类：消息加密函数(Messageencryption)用完整信息的密文作为对信息的认证。消息认证码MAC(MessageAuthenticationCode)是对信源消息的一个编码函数。散列函数

(HashFunction)是一个公开的函数，它将任意长的信息映射成一个固定长度的信息。153消息认证认证函数：加密函数MEKEK(M)DMK提供保密提供认证不提供签名BobAlice对称加密：保密性与认证154消息认证认证函数：加密函数公钥加密：保密性MEKaEKa(M)DMK’a提供保密不提供认证BobAlice155消息认证认证函数：加密函数公钥加密：认证与签名MDK’bEK’b(M)EMKb提供认证BobAlice156消息认证认证函数：加密函数公钥加密：保密、认证与签名MDKaEKa(Dk’b(M))DK’a提供认证提供保密性EK’bDk’b(M)Dk’b(M)EKbMBobAlice157消息认证认证函数：加密函数公钥加密：保密、认证与签名??MEK’bEK’b(Eka(M))EKb提供认证提供保密性DKaEa(M)Eka(M)DK’aMBobAlice158消息认证认证函数：消息认证码消息认证码：使用一个密钥生成一个固定大小的短数据块，并将该数据块加载到消息后面，称MAC（或密码校验和）

MAC＝Ck（M）MAC函数类似于加密函数，但不需要可逆性。因此在数学上比加密算法被攻击的弱点要少159消息认证认证函数：消息认证码MAC的基本用法：消息认证AliceBobM||KCK(M)CKCM比较提供认证160消息认证认证函数：消息认证码MAC的基本用法：与明文有关的认证M||K1CK(M)CK2CM比较EK2MDK1MAliceBob提供认证提供保密161消息认证认证函数：消息认证码MAC的基本用法：与密文有关的认证M||K1CK1(Ek2(M))CCM比较EK2K1提供认证提供保密MMDK2BobAliceEk2(M)162消息认证认证函数：Hash函数HashFunction哈希函数、摘要函数输入：任意长度的消息报文M输出：一个固定长度的散列码值H(M)是报文中所有比特的函数值单向函数根据是否使用密钥带秘密密钥的Hash函数:消息的散列值由只有通信双方知道的秘密密钥K来控制。此时，散列值称作MAC。不带秘密密钥的Hash函数：消息的散列值的产生无需使用密钥。此时，散列值称作MDC。Hash函数需满足以下条件：输入x可以为任意长度，输出为固定长度正向计算容易，反向计算困难抗冲突性(无冲突性）163消息认证认证函数：Hash函数成熟的HashFunctionMD5：输入：消息长度任意输出：128位SHA-1:输入：消息长度<264输出：160位164比较认证函数：Hash函数比较项MD5SHA-1MD长度128位160位抗穷举攻击能力给定消息的摘要：2128产生两个具有相同摘要的消息:264给定消息的摘要：2160产生两个具有相同摘要的消息:280抗密码分析能力对已知的密码分析能力弱未知速度64步，缓冲区128位，快80步，缓冲区160位，较MD5慢很多简单性简单，软件易实现简单，软件易实现低位结构于高位结构低位结构高位结构165消息认证认证函数：Hash函数哈希函数的基本用法（a）M||H(M)HKHM比较EKMDMBobAlice提供认证提供保密EK(M|H(M))166消息认证认证函数：Hash函数哈希函数的基本用法（b）M||KEK(H(M))HHM比较EDBobAlice提供认证K167消息认证认证函数：Hash函数哈希函数的基本用法（c）M||K’bDK’b(H(M))HHM比较DEBobAlice提供认证Kb168消息认证认证函数：Hash函数哈希函数的基本用法(d)M||KDK’b(H(M))HHM比较EDBobAlice提供认证提供保密KMMDK’bEKbEk(M|DK’b(H(M))169消息认证认证函数：Hash函数哈希函数的基本用法（e）M||H(M||S)||HM比较BobAlice提供认证SS||H170消息认证认证函数：Hash函数哈希函数的基本用法（f）M||H(M||S)||KHM比较EKMDMBobAlice提供认证提供保密EK(M||H(M||S)SS||H171信息安全规范与标准－概述Topic1:信息安全基础InformationSecurityFoundations密码学（Cryptography）消息认证（MessageAuthentication）数字签名（DigitalSignature）身份认证（IdentificationAuthentication）访问控制（AccessControl）计算机系统与网络安全（ComputerSystemandNetworkFoundation）密钥管理（KeyManagement）计算机系统与网络安全（ComputerSystemandNetworkFoundation）

……信息安全法律法规与标准化信息安全与法律法规基本原理国内外主要信息安全法律法规标准化与标准化组织172信息安全基础

数字签名数字签名：DigitalSignature传统签名的基本特点签名是可信的：能与被签的文件在物理上不可分割签名是不可抵赖的：签名者不能否认自己的签名签名不能被伪造：除了合法者外，其他任何人不能伪造其签名签名是不可复制的：对一个消息的签名不能通过复制的方式变为另外一个消息的签名签名是不可改变的：经签名的消息不能被篡改容易被验证数字签名是传统签名的数字化能与所签文件“绑定”签名者不能否认自己的签名容易被自动验证签名不能被伪造173信息安全基础

数字签名五元组(P,A,K,S,V)P是所有消息组成的有限集A是所有可能的签名组成的有限集K是所有可能的密钥组成的有限集S签名算法D验证算法174信息安全基础

数字签名可分为两类：直接数字签名方案（directdigitalsignature）；基于仲裁的数字签名方案（arbitrateddigitalsignature）。175数字签名直接数字签名Sa（M）Eb(Sa(M))M，Sa(H(M))Eb(M，Sa(H(M)))MMSH（M）Ek（H）MDk（H）HHH比较Alice(A)Bob(B)直接签名Alice(A)Bob(B)加密＋签名Alice(A)Bob(B)Hash＋签名Alice(A)Bob(B)加密＋签名＋HashHash＋签名176数字签名仲裁数字签名Alice(A)Bob(B)Trent(T)M,Eat(IDa,H（M))Ebt(IDa,M,Eat(Ida,H(M)),T))对称密码＋明文传送177数字签名仲裁数字签名Alice(A)Bob(B)Trent(T)Eab(M),Eat(IDa,Eab(H(M)))Ebt(IDa,Eab(M),Ea