[计算机硬件及网络]密码学 154页

1密码学基础\n2密码学的起源和发展三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学\n3第1阶段－古典密码密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密\n4Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。第1阶段－古典密码\n520世纪早期密码机\n61883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。第1阶段－古典密码\n7计算机使得基于复杂计算的密码成为可能相关技术的发展1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-1973年IBMWatson实验室的HorstFeistel等几篇技术报告主要特点：数据的安全基于密钥而不是算法的保密第2阶段1949~1975\n81976年：Diffie&Hellman的“NewDirectionsinCryptography”提出了不对称密钥；1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法主要特点：公钥密码使得发送端和接收端无密钥传输的保密通信成为可能第3阶段1976~\n91977年DES正式成为标准80年代出现“过渡性”的“PostDES”算法,如IDEA,RCx,CAST等90年代对称密钥密码进一步成熟Rijndael,RC6,MARS,Twofish,Serpent等出现2001年Rijndael成为DES的替代者第3阶段1976~\n10保密通信\n11保密通信的功罪100年前，1894年的中日甲午海战，中国惨败，其本质是由于清政府的腐败，但其中一个重要的具体原因，是日方在甲午战争前就破译了清政府使用的密电码。日方破译的电报多达一百余则，对清政府的决策、海军的行踪等了如指掌，因而日方不仅在海战中取得了胜利，还迫使清政府签订“马关条约”，割让辽东半岛、台湾及澎湖列岛，赔偿军费白银2亿两。\n12保密通信的功罪1917年1月，正当第一次世界大战进入第三个年头时，英国海军破译机关截收到了德国外长齐默尔曼签发的一份密报，经过一个多月的辛勤劳作，终于在2月下旬完全破开了那份密报。密报称，德国将在欧洲进行无限制的潜艇战，意思是说，中立国家的船队也在其打击目标之列，同时指出，若美国不再保持中立，就要求墨西哥与德国结盟，对美宣战。英国外交部在权衡了种种利弊后，到2月22日将此密报交给了美国政府，德国政府的阴谋激怒了开战以来一直保持中立并且在三个月前还声明继续保持中立的美国人，五个星期后美国对德宣战，出兵西线，既避免了在美国本土燃起战火，又加速了协约国的胜利。\n13保密通信的功罪1941年12月，日本取得了突袭珍珠港、摧毁美国太平洋舰队主力的重大胜利，为了完全控制太平洋，并设法诱出在珍珠港的美国舰队残部予以彻底消灭，日本制定了于1942年6月突然攻击夏威夷前哨中途岛的计划。\n14保密通信的功罪当时日本海军使用的是日本最高级的密码体制——紫密，它的第二版本JN25b自1940年12月1日启用后应在1942年4月1日内第三版本JN25c替换。但由于舰船分散在广阔的海域不停地转移，给分发新的版本增添许多困难，因此替换工作延期到5月1日，后因同样的原因再延期—个月，到6月1日启用新版本。这就使盟国破译人员有充分的时间更透彻地破解JY25b。5月27日，山本的作战命令已基本上被破译，美国太平洋舰队司令尼米兹海军上将发布作战计划，将3艘航空母舰部署在敌舰不可能侦察到的海域，战斗打响时也以突然攻击的方式打击日军的突击舰队。6月4日，日军4艘巨型航空母舰在一日之内相继被炸沉．从此日本海军由进攻转为防御，最终走向失败。\n15保密通信的功罪1943年春天，山本五十六为了控制不断恶化的残局，亲自前住所罗门群岛基地巡视，以鼓舞士气。在视察前五天，1943年4月13日，日军第八舰队司令将山本行将视察的行程、时间表，用JN25体制加密后播发给有关基地，以作好迎接的准备，尽管该体制的所用版本在4月1日刚换过，但美国破译人员根据过去的经验，迅速地破译了这份密报，美军决定在空中打掉山本的座机，使日军失去一位战略家，沉重地打击日军士气。经过精心组织，周密安排，终于使山本五十六在飞往视察地途中，被美军飞机击落，葬身于丛林深处。\n16密码学起源密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。依照这些法则，变明文为密文，称为加密变换；变密文为明文，称为解密变换。１７世纪，英国著名的哲学家弗朗西斯·培根在他所著的《学问的发展》一书中最早给密码下了定义，他说，“所谓密码应具备三个必要的条件，即易于翻译、第三者无法理解、在一定场合下不易引人生疑。”加密解密明文密文原始明文\n17密码学起源谋成于密，败于泄——明揭暄兵经百言》古典密码学包含两个互相对立的分支，即密码编码学（Cryptography）和密码分析学（Cryptanalytics）。前者编制密码以保护秘密信息，而后者则研究加密消息的破译以获取信息。二者相反相成，共处于密码学的统一体中。现代密码学除了包括密码编码学和密码分析学外，还包括安全管理、安全协议设计、散列函数等内容。\n18密码学起源大约在4000年以前，在古埃及的尼罗河畔，一位擅长书写者在贵族的基碑上书写铭文时有意用加以变形的象形文字而不是普通的象形文字来写铭文，从而揭开了有文字记载的密码史。这篇颇具神秘感的碑文，已具备了密码的基本特征：把一种符号(明文)用另一种符号(密文)代替。\n19密码学起源公元前5世纪，古斯巴达人使用了一种叫做“天书”的器械，这是人类历史上最早使用的密码器械。“天书”是一根用草纸条、皮条或羊皮纸条紧紧缠绕的木棍。密信自上而下写在羊皮纸条上。然后把羊皮纸条解开送出。把羊皮纸条重新缠在一根直径和原木棍相同的木棍上，这样字就一圈圈跳出来。\n20密码学起源公元前1世纪古罗马凯撒大帝时代曾使用过一种“代替式密码”，在这种密码中，每个字母都由其后的第三个字母（按字母顺序）所代替。这种代替式密码直到第二次大战时还被日本海军使用。公元前4世纪前后，希腊著名作家艾奈阿斯在其著作《城市防卫论》中就曾提到一种被称为“艾奈阿斯绳结”的密码。它的作法是从绳子的一端开始，每隔一段距离打一个绳结，而绳结之间距离不等，不同的距离表达不同的字母。\n21密码学起源〈六韬．龙韬．阴符〉武王问太公曰：‘引兵深入诸侯之地，三军猝有缓急，或利或害。吾将以近通远，从中应外，以给三军之用。为之奈何？’太公曰：‘主与将，有阴符。凡八等：有大胜克敌之符，长一尺；破军杀将之符，长九寸；降城得邑之符，长八寸；却敌报远之符，长七寸；誓众坚守之符，长六寸；请粮益兵之符，长五寸；败军亡将之符，长四寸；失利亡士之符，长三寸。诸奉使行符，稽留者，若符事泄，闻者告者，皆诛之。八符者，主将秘闻，所以阴通言语，不泄中外相知之术。敌虽圣智，莫之通识。’武王曰：‘善哉。’\n22密码学起源〈六韬．龙韬．阴书〉武王问太公曰：‘引兵深入诸侯之地，主将欲合兵，行无穷之变，图不测之利。其事繁多，符不能明；相去辽远，言语不通。为之奈何？’太公曰：‘诸有阴事大虑，当用书，不用符。主以书遗将，将以书问主。书皆一合而再离，三发而一知。再离者，分书为三部；三发而一知者，言三人，人操一分，相参而不知情也。此谓阴书。敌虽圣智，莫之能识。’武王曰：‘善哉。’\n23密码学起源在古代还出现过一种被称为“叠痕法”的密码，使用时先把信纸折叠几下（上下及左右），然后铺平信纸，将传递的信息按顺序一个个分开，写在折痕的交叉点上，每一个交叉点写一个字。然后再在空白位置上填上公开的普通信文，普通信文与秘密信文的文字通顺地连贯在一起。为了防止被敌人察觉，使用这种密码需要在编公开信文上下些功夫。如果在秘密信文上再用些暗语式密码，那么敌人就更难看出破绽了。宋曾公亮、丁度等编撰《武经总要》“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密码本体制的特点。\n24密码学起源暗号。简单地说，暗号就是通过用物件的状态或人的行为来传达事先约定的信息．如窗台上的花瓶、手中拿着的报纸、口中昨着的曲子，可分别代表“现在安全”、“我是你要找的人”、“我在找自己人”等明确的信息．隐语。暗号是把信息变换为物件或动作，隐语则是把信息变换成与此信息完全无关的(但有意义的)语言．据说，1941年，日本偷袭珍珠港前两星期，美国情报人员曾截获一次重要的电话对话．那是两名分别在东京和华盛顿的日本高级官员之间的通话．这段对话里“小孩出生”的真正意思是“发动战争”．在华盛顿的日本人：是不是真的有个小孩要出生了?在东京的日本人：是的．而且看来马上就要出生了．在华盛顿的日本人：这个小孩真的要生了吗?是在哪个方向呢?\n25密码学起源16世纪意大利数学家卡尔达诺发明的一种保密通信方法，史称“卡尔达诺漏格板”．漏格板是一张用硬质材料(如硬纸、羊皮、金属等)做成的板，上面挖了一些长方形的孔，即漏格．\n26密码学起源〈兵经百言．衍部．传〉军行无通法，则分者不能合，远者不能应。彼此莫相喻，败道也。然通而不密，反为敌算。故自金、旌、炮、马、令箭、起火、烽烟，报警急外；两军相遇，当诘暗号；千里而遥，宜用素书，为不成字、无形文、非纸简。传者不知，获者无迹，神乎神乎！或其隔敌绝行，远而莫及，则又相机以为之也。”\n27密码学起源大约在1793年，当时的美国总统托马斯杰斐逊发明了一种轮子密码机。转动轮子使明文中的所有字母全排在一条直线上为止．这时圆柱体的其他25行字母也因这一行的固定而被固定了．任选这25行中的一行发出去即为密文．\n28密码学起源“谜”（ENIGMA）密码最初是由一个叫胡戈·科赫的荷兰人发明的。起初主要提供给想保护自己生意秘密的公司使用，但其商界的销路一直不理想。后来德国人将其改装为军用型，使之更为复杂可靠。德国海军于1926年开始使用“ENIGMA”，陆军则于1928年开始使用。1933年，纳粹最高统帅部通信部决定将“ENIGMA”作为德国国防军新式闪击部队的通信装置。德国人在战争期间共生产了大约10多万部“谜”密码机。1940年，经过盟军密码分析学家的不懈努力，“恩尼格玛”密码机被动攻破，盟军掌握了德军的许多机密，而德国军方却对此一无所知。\n29密码学起源传说，古时候有一对夫妻，男的名叫李石匠，女的叫张小花。李石匠靠手艺赚钱，张小花在家纺纱织布。一年，李石匠参加修建石桥，因工程紧张，十一个月也没回家一次。张小花独自在家只有纺车做伴。一天石匠工地回来一个工友路过她家，她托这个工友给丈夫带去一封书信。\n30密码学起源第六十回吴用智赚玉麒麟梁山泊义军头领宋江久慕卢俊义的威名，一心想招取卢俊义上山坐第一把交椅，共图大业，替天行道。智多星吴用扮成一个算命先生，利用卢俊义正为躲避“血光之灾”的惶恐心里，口占四句卦歌，并让他端书在家宅的墙壁上。卢花滩上有扁舟，俊杰黄昏独自游。义到尽头原是命，反躬逃难必无忧。这四句诗写出后，被官府拿到了证据，大兴问罪之师，到处捉拿卢俊义，终于把他逼上梁山。\n31加密与解密现代密码学涉及数学（如数论、有限域、复杂性理论、组合算法、概率算法等）、物理学（如量子力学、现代光学、混沌动力学等）、信息论、计算机科学等学科。1949年，信息论之父C.E.Shannon发表了《保密系统的通信理论》，密码学走上科学和理性之路。1976年W.Diffie和M.E.Hellman发表的《密码学的新方向》，以及1977年美国公布实施的数据加密标准DES，标志着密码学发展的革命。2001年11月美国国家标准技术研究所发布高级数据加密标准AES代表着密码学的最新发展。\n32加密与解密基于密钥的算法通常有两类：对称算法和公开密钥算法。使用一个密钥的加/解密。加密时可以使用一个参数K，称此参数K为加密密钥。K可以是很多数值里的任意值。密钥K的可能值的范围叫做密钥空间。\n33加密与解密使用两个密钥的加/解密。EK1（P）=CDK2（C）=PDK2（EK1（P））=P解密密钥加密密钥原始明文密文加密解密明文\n34加密与解密加密通信的模型信源Mm加密器解密器接收者m非法接入者搭线信道（主动攻击）C’搭线信道（被动攻击）密码分析员m‘密钥源K1k1密钥源K2k2密钥信道\n35加密与解密对称算法就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加/解密密钥是相同的。这些算法也叫秘密密钥算法或单密钥算法。对称算法可分为两类。序列密码（流密码）与分组密码。\n36序列密码（流密码）序列密码主要应用于军事和外交场合。序列密码的优点是错误扩展小、速度快、利于同步、安全程度高。密钥流产生器密钥k明文m密文c异或运算\n37序列密码伪随机序列发生器是指输入真随机的较短的密钥（种子）通过某种复杂的运算产生大量的伪随机位流。真随机序列从真实世界的自然随机性源产生。如自然界中的抛币。伪随机序列用确定的算法产生，不是真正的随机序列。伪随机序列发生器指使用短的真随机序列（称为种子）x扩展成较长的伪随机序列y。随机数是较短的随机位序列。seed(short)PRBS(long)011011010010110....\n38分组密码分组密码是将明文按一定的位长分组，明文组和密钥组的全部经过加密运算得到密文组。数据加密标准DES出自IBM被美国政府正式采纳的数据加密算法（DataEncryptionAlgorithm，DEA）由中国学者来学嘉XuejiaLai和JamesL.Massey在苏黎世的ETH开发的国际数据加密算法IDEA（InternationalDataEncryptionAlgorithm）比利时JoanDaemen和VincentRijmen提交，被美国国家标准和技术研究所（USNationalInstituteofStandardsandTechnology，NIST）选为美国高级加密标准（AES）的Rijndael。\n39分组密码的操作模式电子密码本ECB(electroniccodebookmode)密码分组链接CBC(cipherblockchaining)密码反馈CFB(cipherfeedback)输出反馈OFB(outputfeedback)计数器模式CTR）美国NSB在[FIPSPUB74和81]中规定ANSI在[ANSIX3.106]中规定ISO和ISO/IEC在[ISO9732ISO/IEC10116]中规定\n分组密码的操作模式模式描述典型应用电子密码本ECB用相同的密钥分别对明文分组加密单个数据的安全传输密码分组链接CBC加密算法的输入是上一个密文分组和下一个明文分组的异或普通目的的面向分组的传输密码反馈CFB一次处理J位，上一个分组密文作为产生一个伪随机数输出的加密算法的输入，该输出与明文分组异或，作为下一个分组的输入普通目的的面向分组的传输认证输出反馈OFB与CFB相同，只是加密算法的输入是上一次DES的输出噪声信道上数据流的传输（如卫星传输）计数器模式CTR）每个明文分组是加密的计数器的异或，对每个后续的分组，计数器是累加的。普通目的的面向分组的传输用于高速需求\n41分组密码的分析方法根据攻击者所掌握的信息,可将分组密码的攻击分为以下几类:唯密文攻击已知明文攻击选择明文攻击攻击的复杂度数据复杂度:实施该攻击所需输入的数据量处理复杂度:处理这些数据所需要的计算量\n42分组密码的典型攻击方法最可靠的攻击办法:强力攻击最有效的攻击:差分密码分析,通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特.线性密码分析:本质上是一种已知明文攻击方法,通过寻找一个给定密码算法的有效的线性近似表达式来破译密码系统插值攻击方法密钥相关攻击\n43强力攻击穷尽密钥搜索攻击:唯密文,2k已知(选择)明文,2k,k-密钥长度字典攻击:明密文对编成字典,2n,n-分组长度查表攻击:选择明文攻击,给定明文,用所有的2k个密钥,预计算密文,k-密钥长度时间存储权衡攻击:选择明文攻击,由穷尽密钥搜索和查表攻击混合而成,它在选择明文攻击中以时间换取空间\n44现代常规分组加密算法一种是对DES进行复合，强化它的抗攻击能力；另一种是开辟新的方法，即象DES那样加解密速度快，又具有抗差分攻击和其他方式攻击的能力。\n45现代常规分组加密算法1.TripleDES2.IDEA3.RC54.RC65.AES其他一些较实用的算法，如Blowfish，CAST，以及RC2。\n46双重DES(DoubleDES)C=EK2(EK1(P))P=DK1(DK2(C))\n47Triple-DES的四种模型DES-EEE3：三个不同密钥，顺序使用三次加密算法DES-EDE3：三个不同密钥，依次使用加密-解密-加密算法DES-EEE2：K1=K3，同上DES-EDE2：K1=K3，同上\n481.TRIPLEDES由于已经证明DES不能成为群，见K.W.CampbellandM.J.WienerProofthatDESisnotagroupInAdvancesinCryptology——Crpto’92.Springer-Verlag,NewYork,1993.于是多重DES，尤其是三重DES还在普遍使用。\n49双密钥的三重DES（TripleDESwithTwoKeys)C=EK1(DK2(EK1(P)))P=DK1(EK2(DK1(C)))\n50三密钥的三重DES（TripleDESwithThreeKeys)C=EK3(DK2(EK1(P)))=DK3(EK2(DK1(C)))\n511973年，美国国家标准局(NBS)开始征集联邦数据加密标准的方案。Feistel等人研究了一种128位的对称密钥系统，后IBM改进为56位的密钥系统，并提交NBS。1975年3月17日，NBS公布了IBM公司提供的密码算法，以标准建议的形式在全国范围内征求意见。1977年7月15日，NBS接受这个建议，数据加密标准DES正式颁布，供商业界和非国防性政府部门使用。DES的历史\n52争论：56位够长吗？内部结构公开，设计原理没公开？DES的历史\n53DES的应用1979年，美国银行协会批准使用1980年，美国国家标准局（ANSI）赞同DES作为私人使用的标准,称之为DEA（ANSIX.392）1983年，国际化标准组织ISO赞同DES作为国际标准，称之为DEA-1该标准规定每五年审查一次，计划十年后采用新标准最近的一次评估是在1994年1月，已决定1998年12月以后，DES将不再作为联邦加密标准。\n54DES的描述DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文输入64比特明文数据初始置换IP在密钥控制下16轮迭代初始逆置换IP-1输出64比特密文数据DES算法框图交换左右32比特\n55初始置换IP和初始逆置换IP—1\nLi-1（32比特）Ri-1（32比特）Li（32比特）48比特寄存器扩充/置换运算48比特寄存器子密钥Ki（48比特）32比特寄存器代换/选择运算置换运算PRi（32比特）Li=Ri-1DES的一轮迭代F函数\nDES:FunctionFExpansion:3248（扩充）S-box:64（压缩）Permutation:置换\n扩充/置换运算32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|01\n59代换/选择运算\n60S-Box-i\n61S-Box-ii\n62S-Box对每个盒，6比特输入中的第1和第6比特组成的二进制数确定的行，中间4位二进制数用来确定的列。相应行、列位置的十进制数的4位二进制数表示作为输出。例如的输入为101001，则行数和列数的二进制表示分别是11和0100，即第3行和第4列，的第3行和第4列的十进制数为3，用4位二进制数表示为0011，所以的输出为0011。\n63Permutation1607202129122817011523260518311002082414322703091913300622110425\n子密钥的产生k1（56位）(48位)ki（56位）（48位）64位密钥置换选择1C0（28位）D0（28位）循环左移循环左移C1（28位）D1（28位）循环左移循环左移Ci（28位）Di（28位）置换选择2置换选择2密钥表的计算逻辑循环左移：119121102321124212252132621427215282161\n65置换选择1(PC-1)和置换选择2(PC-2)\n总结－DES示意图\n67DES的安全性分析DES的安全性完全依赖于密钥，与算法本身没有关系。主要研究内容：密钥的互补性；弱密钥与半弱密钥；密文-明文相关性；密文-密钥相关性；S-盒的设计；密钥搜索。\n68弱密钥弱密钥：由密钥k确定的加密函数与解密函数相同，即。DES的弱密钥：如果各轮产生的子密钥一样，则加密函数与解密函数相同。DES至少有4个弱密钥：01010101010101011f1f1f1f0e0e0e0ee0e0e0e0f1f1f1f1fefefefefefefefe\n69半弱密钥半弱密钥：对于密钥k，存在一个不同的密钥，满足。DES的半弱密钥：子密钥生成过程中只能产生两个不同的子密钥或四个不同的子密钥，互为对合。DES至少有12个半弱密钥。\n70S-盒的设计原则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的数目几乎相等。\n71针对DES的攻击方法攻击DES的方法主要有：密钥穷搜索攻击，DES算法总的密钥量为，1998年使用高级计算机的情况下，破译DES只需56小时；差分攻击；线性攻击，较有效的方法；相关密钥攻击等。\n72DES的破译1990年，以色列密码学家EliBiham和AdiShamir提出了差分密码分析法，可对DES进行选择明文攻击。线性密码分析比差分密码分析更有效\n73公钥密码公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。公开密钥算法主要用于加密/解密、数字签名、密钥交换。\n74讨论议题为什么要设计公钥密码算法密钥分配公钥密码体制概述及其应用公钥密码算法的实现Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法椭圆曲线密码算法ECC\n751.为什么要设计公钥密码体制\n76密钥分配（KeyDistribution）保密通信双方需共享密钥共享密钥要经常更换A选择密钥并手工传递给B第三方C选择密钥分别手工传递给A,B用A,B原有共享密钥传送新密钥与A,B分别有共享密钥的第三方C传送新密钥给A和/或BN个用户集需要N(N-1)/2个共享密钥密钥分发中心(KeyDistributionCenter)\n77密钥分发中心（KDC）每个用户与KDC有共享密钥(MasterKey)N个用户,KDC只需分发N个MasterKey两个用户间通信用会话密钥(SessionKey)用户必须信任KDCKDC能解密用户间通信的内容\n78（1）密钥管理量的困难传统密钥管理：两两分别用一对密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。如:n=100时，C(100,2)=4,995n=5000时，C(5000,2)=12,497,500（2）数字签名的问题传统加密算法无法实现抗抵赖的需求。问题的提出\n79起源公钥密码又称为双钥密码和非对称密码，是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-126\n80公开密钥密码的重要特性加密与解密由不同的密钥完成加密:mc:c=EK(m)解密:cm:m=DB(c)=DB(EK(m))知道加密算法,从加密密钥得到解密密钥在计算上是不可行的两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的)m=DB(EK(m))=EK(DB(m))\n812.公钥密码体制的应用概述\n82公钥加密算法传统加密过程加密和解密使用相同密钥明文明文密文\n83公钥加密算法公钥密码算法加密和解密使用不同密钥明文明文密文\n84用公钥密码实现保密\n85基于公开密钥的加密过程\n86用公钥密码实现认证\n87基于公开密钥的认证过程\n88用公钥密码实现保密与认证\n89公钥密钥的应用范围加密/解密数字签名(身份鉴别)密钥交换算法加/解密数字签名密钥交换RSA是是是Dieffie-Hellman否否是DSS否是否\n903.公钥密码算法\n91基本思想和要求涉及到各方：发送方、接收方、攻击者涉及到数据：公钥、私钥、明文、密文公钥算法的条件：产生一对密钥是计算可行的已知公钥和明文，产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者，利用公钥来推断私钥是计算不可行的已知公钥和密文，恢复明文是计算不可行的(可选)加密和解密的顺序可交换\n92陷门单向函数单向陷门函数是满足下列条件的函数f：(1)给定x，计算y=fk(x)是容易的；(2)给定y,计算x使x=fk-1(y)是不可行的。(3)存在k，已知k时,对给定的任何y，若相应的x存在，则计算x使fk-1(y)是容易的。\n93公钥密码基于的数学难题背包问题大整数分解问题（TheIntegerFactorizationProblem,RSA体制）有限域的乘法群上的离散对数问题(TheDiscreteLogarithmProblem,ElGamal体制）椭圆曲线上的离散对数问题（TheEllipticCurveDiscreteLogarithmProblem,类比的ElGamal体制）\n94一、背包问题背包问题：已知一长度为B的背包，及长度分别为a1,a2,...,an的n个物品。假定这些物品的半径和背包相同，若从这n个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？\n95背包问题数学描述\n96背包问题求解\n97超递增序列背包问题求解方法思路：xi取值只可能为0或者1；如果为0，表示不能装入对应的物体，否则可以装入。\n98超递增序列背包问题求解方法\n99Merkle－Hellman背包公钥算法\n100Merkle－Hellman背包公钥算法\n101Merkle－Hellman背包公钥算法问题：如何解密？\n102Merkle－Hellman背包公钥算法MH背包公钥算法是由超递增序列进行变换得到得：\n103Merkle－Hellman背包公钥算法MH背包公钥算法的公钥和私钥\n104Merkle－Hellman背包公钥算法\n105Merkle－Hellman背包公钥算法\n106Merkle－Hellman背包公钥算法\n107Merkle－Hellman背包公钥算法\n108Merkle－Hellman背包公钥算法\n109Merkle－Hellman背包公钥算法\n110Merkle－Hellman背包公钥算法自从最初的Merkle－Hellman背包体制被破译后，又有许多其他的背包被提出，如：多次迭代背包，Graham-Shamir背包、DF背包等。\n111Merkle－Hellman背包公钥算法1988年，Chor与Rivest利用有限域上的算术性质设计了一个背包公钥密码体制，称为Chor-Rivest体制。该体制设计巧妙，一是利用某些情况下计算GF(Pn)上离散对数容易，二是利用有限域GF(P)上多项式分解当p不太大时有有效算法，三是利用了Bose-Chowla定理由一组离散对数经某种变换后作为背包向量。1998年，Vaudenay提出了一种有效的破译方法破译了这种体制。\n112二、RSA密码系统RSA是目前最著名的公钥密码系统，是由三位学者Rivest，Shamir和Adlemen于1978年提出。其安全性是建立在因式分解的困难性上。已知n，求p和q使得n=pq是NP完全问题。\n113RSA算法概要：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)解密。\n114RSA:例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\n115RSA:例1计算d:de=1mod160且d<160，则d=23（因为23×7=161=10×160+1）公布公钥KU={7,187}保存私钥KR={23,17,11}\n116如果待加密的消息M=88(注意：88<187)加密：C=887mod187=11解密:M=1123mod187=88RSA：例1\nRSA：例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。\nRSA：例2Bob已知p和q的值，他用扩展欧几里德算法计算d：de≡1(mod(p-1)(q-1))，得到d=116402471153538991然后Bob计算：cd≡113535859035722866116402471153538991≡30120(modn)由此他可以得到最初的信息。\n119四、ECCECC:EllipticCurveCryptography1985年，N.Koblitz及V.S.Miller分别提出了椭圆曲线密码体制（ECC）。已经开发出的椭圆曲线标准的文档有：IEEEP1363P1363a、ANSIX9.62X9.63、ISO/IEC14888等。近年来，ECC已走向工程实现和实际应用阶段。目前，德国、日本、法国、美国、加拿大等许多西方国家的密码学研究小组和公司已经实现了椭圆曲线密码体制。\n120三、ElGamal密码系统ElGamal是目前著名的公钥密码系统之一，是由ElGamal于1985年提出的。ElGamal可以用于加解密，数字签名其安全性建立在离散对数问题上。即：给定p,q和y=gx(modp)，求x在计算上是不可行的。\n3.6本原根本原根1.指数由欧拉定理知道：如果(g,m)＝1，m>1，则gϕ(n)≡1(modm)也就是说，如果(g,m)＝1，m>1，则存在一个整数γ满足gγ≡1(modm)。定义：若(g,m)＝1，m>1，则使得同余式gγ≡1(modm)成立的最小正整数γ叫做g对模m的指数。\n3.6本原根1.定义设整数m>0,(g,m)=1,如果整数g对m的指数为ϕ(m)，则g叫做m的一个本原根.eg:3是模7的本原根因为3ϕ(7)≡36≡1(mod7)一般说来，当p为素数时，模p本原根是一个数，它的幂构成模p的同余类,比如3(mod7)的幂运算：31≡3,32≡2,33≡6,34≡4,35≡5,36≡1.存在ϕ(p-1)个模p的本原根.本原根\n123加密和解密（1）密钥生成1）任选一个大素数p，使得p-1有大的素因子；2）任选一个modp的本原根g3）公布p和g。使用者任选一私钥x∈Zp，并计算公钥y=gxmodp.\n124加密程序m为明文1）任选一个随机数r∈Zp，满足Gcd(r,p-1)=1并计算c1=grmodp;c2=m×yrmodp密文为（c1，c2）\n125解密程序1）计算w=(c1x)-1modp;2）计算明文m=c2×wmodp。\n126密码学-ECC为什么要提出ECC？\n同等安全强度下各算法的密钥长度RSA主要问题之一：为了保证必要的安全强度，其密钥必须很长ECC的优势：在同等安全强度下，ECC所需密钥比RSA短\n128密码学-ECC椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程所确定的平面曲线。其中，系数（i=1，2，…，6）定义在基域K上（K可以是有理数域、实数域、复数域，还可以是有限域，椭圆曲线密码体制中用到的椭圆曲线都定义在有限域上）。椭圆曲线并非椭圆\n129密码学-ECC群：对于非空集合G，其上的一个二元运算（.）满足：封闭性、结合律、单位元和可逆性环：对于R上的两个二元运算（+，x）满足：关于＋是一个交换群（群的条件＋交换律）对于乘法x满足：封闭性＋结合律＋分配律域：对于F上的两个运算（+，x）满足F是一个整环：交换环＋乘法逆元＋无零因子乘法逆元存在\n2021/9/14例：证明是群，其中n是正整数。分析需要证明4点：封闭性；结合律；幺元存在；逆元存在。证明（1）封闭性：x,y∈n，令k=x+y(modn)，则0≤k＜n1，即k∈n，所以封闭性成立。\n1312021/9/14证明（续）（2）结合律：x,y,z∈n，有(x+ny)+nz=x+y+z(modn)=x+n(y+nz),所以结合律成立。（3）幺元：x∈n，显然有0+nx=x+n0，因此，0是幺元。\n1322021/9/14证明（续）（4）逆元存在：x∈n，如果x=0，显然01=0，如果x≠0，则有nx∈n，显然x+n(nx)=(nx)+nx=0，所以x1=(nx)，因此，x∈n，x有逆元。综上，是群。\n133密码学-ECC\n134密码学ECC椭圆曲线加法运算规则：O是加法的单位元，O＝－O；对于椭圆曲线上的任一点P，有P＋O＝P点P的负元是与P具有现同x坐标和相反y坐标的点，即若P＝（x，y），则-P＝（x，-y）；P＋（P)=O\n135密码学-ECC若P＝（x1，y），Q＝（x2，z），则P＋Q＝-R。其中R是直线PQ与椭圆曲线的第三个交点。若P和Q的x坐标相同，则为无穷远点O若Q＝（x，y），则Q＋Q＝2Q＝－S，其中S为椭圆曲线在Q点的切线与椭圆曲线的另一交点。\n136椭圆曲线密码学有限域上椭圆曲线y2x3+ax+bmodpp是奇素数,且4a3+27b20modp（构成Abel群的条件，证明过程略）y2+xyx3+ax2+bmod2m(Galois域的椭圆曲线）\n有限域上椭圆曲线y2x3+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),如果PQ=(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群。\n138椭圆曲线密码学示例：有限域上椭圆曲线y2x3+ax+bmodp条件：a=1,b=1,x=9,y=7,p=23y2=72mod23=3x3+ax+b=(93+9+1)mod23=3y2x3+ax+bmodp\n139ECC示例示例：有限域上椭圆曲线y2x3+ax+bmodp条件：a=1,b=1,x=9,y=7,p=23问题：求满足上述方程的所有整数对（x，y）以及无穷远点O组成的集合Ep（a，b）＝E23（1，1）？\n椭圆曲线密码学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）\n141ECC示例(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)\n142P＋Q计算过程：x3=2-x1-x2y3=(x1-x3)-y1其中=(y2-y1)/(x2-x1),如果PQ=(3x12+a)/2y1,如果P=Q\n143有限域上椭圆曲线y2+xyx3+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\n144有限域上椭圆曲线y2+xyx3+ax2+bmod2m(Galois域的椭圆曲线）(4)若P=(xP,yP),则R＝2P=(xr,yr)其中：xR=2++ayR=xP2+(+1)xR=xp+yp/xP按照上述定义构成了一个椭圆曲线上的Abel群\n145椭圆曲线上的离散对数“难题”对于方程Q=kP,其中P，Q属于Ep(a,b)。对于给定的k和P，计算Q比较容易，而对于给定的P和Q，计算k比较困难\n146ECC例如：方程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＝9\n147ECC加密/解密实现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形式的点Pm\n148ECC加密/解密实现Step3：Alice随机选择一个正整数r，对Pm产生密文Cm＝{rG，Pm＋rKb}Step4：Bob解密Cm-Kb’(rG)=Pm+rKb-krG=Pm+r(kG)-rkG=Pm\n149ECC加密/解密实现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)}\n150ECC加密/解密实现Step4：Bob解密Kb’(rG)=3(5415,6321)=(673,146)Cm-Kb’(rG)=(6626,3576)-(673,146)=(5,1734)\n151密码学与安全性总结第一阶段80年代第二阶段90年代第三阶段90年代后期信息保密信息保护信息保障密码学保密学加解密技术数据完整性数据可用性数据可控性可信环境可信计算可信存储抗抵赖性++++密码学\n152密码学与安全性总结（续）密码学（数学基础）编码学分析学相辅相成对立统一机密性、完整性、可鉴别性、抗抵赖性信息源目标服务密码学\n153密码实现数学发现密码算法算法论证复杂性密钥配置算法实现密码协议加密解密破译技术密钥技术密码应用领域应用密码系统密码管理密钥管理交叉融合基础过程结果密码学与安全性总结（续）\n154计算复杂性单向函数代数结构密码分析古典密码公钥密码签名模式私钥密码散列函数密码学协议密钥管理操作式抗抵赖机密性密码系统的整体设计与分析数学基础基本工具密码学系统完整性鉴别性密码学与安全性总结（续）