搜索
1第2讲密码学基础王庆先qxwang@uestc.edu.cn电子科技大学计算机学院2密码学的起源和发展三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学3第1阶段－古典密码密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段出现，针对的是字符简单的密码分析手段出现主要特点：数据的安全基于算法的保密4Phaistos圆盘，一种直径约为160mm的Cretan-Mnoan粘土圆盘，始于公元前17世纪。表面有明显字间空格的字母，至今还没有破解。第1阶段－古典密码520世纪早期密码机61883年Kerchoffs第一次明确提出了编码的原则：加密算法应建立在算法的公开不影响明文和密钥的安全。这一原则已得到普遍承认，成为判定密码强度的衡量标准，实际上也成为传统密码和现代密码的分界线。第1阶段－古典密码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发表的《密