密码学发展史.ppt

1、密码学发展史,周敏超 顾思远 陈濛澈 信息安全工程学院,什么是密码？,密码是一种用来混淆的技术，它希望将正常的、可识别的信息转变为无法识别的信息。 密码学是一个即古老又新兴的学科。密码学(Cryptology)一字源自希腊文kryptos及logos两字，直译即为隐藏及讯息之意,密码的历史几乎跟文字的历史一样长,自从有了文字以来，人们为了某种需要总是想法设法隐藏某些信息，以起到保证信息安全的目的。,在这些诡秘莫测的字符背后，或是隐含着政客那冷酷阴毒的计谋、武士那阴森滴血的剑影，或是携带着智者狡黠的微笑、情人绵绵不绝的秋波可以说，密码是当一种文化在文学、科学和语言发达到一定的复杂程度，当秘密的、

2、符号性的信息交流达到不可或缺的阶段应运而生的一种信息交流的特殊工具。 密码中的秘密,密码学的发展历程大致经历了三个阶段,古典密码（手工、机械阶段 - ） 近代密码（计算机阶段-） 现代密码（-）,古典密码（手工、机械阶段）,古埃及,人类文明刚刚形成的公元前2000年，古埃及就有了密码。贵族克努姆霍特普二世的墓碑上记载了在阿梅连希第二法老王朝供职期间它所建立的功勋。上面的象形文字不同于我们已知的普通埃及象形文字，而是由一位擅长书写的人经过变形处理之后写的，但是具体的使用方法已经失传。人们推测这是为了赋予铭文以庄严和权威。,姓名和头衔的象形文字加密 左：明文 右：密文,中国,阴符 阴书 武经总要,

3、印度,公元前三百年写成的经济论在描述印度密探充斥全国时，介绍了特务机关的官员用密写给密探下达任务。 爱经将密写列为妇女应该学会的64种瑜伽之一,美索不达米亚,在楔形文字时期，巴比伦和亚述的记述者往往用稀奇古怪的楔形文字在泥板上做记号和记日期。一向后世显示自己的学问。在楔形文字后期，偶有记述者把人名变换成数字。,修泽遗迹出土的字碑，记载1-8 与 32-35 的数字,希伯来民族是以色列的祖先。希伯来人开发出了三种加密法，称为“atbah”、“atbash”和“albam”。,“诗的最后一行，”索菲继续说道： “是说埃特巴什将会使真相暴露无遗。埃特巴什？我听过这个词。” “我并不奇怪，”兰登在一边

4、回应：“你可能是从密码学101里听到的。埃特巴什码可能是迄今人们所知最古老的密码了。” 当然喽！有谁不知道赫赫有名的希伯来编码体系？索菲心想。,A B G D H V Z Ch T Y K Th Sh R Q Tz P O S N M L,希伯来,希伯来的三种加密法在希伯来文著作中到处使用，特别是atbash。 希伯来圣经中的加密启示了中世纪的修道士和记述者的字母替代思想。,斯巴达的skytale,长期的战争使得斯巴达人发展出了自己的一套加密方式，公元前5世纪，斯巴达人就使用一种名为scytail的器械，他们把一个带状物，呈螺旋形紧紧地缠在一根权杖或木棍上，之后再沿着棍子的纵轴书写文字，在这条

5、带状物解开后，上面的文字将杂乱无章，收信人需用一根同样直径的棍子重复这个过程，看到明文，这是人类历史上最早的加密器械。,公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法，他使用了一个称为Polybius的校验表，这个表中包含许多后来在加密系统中非常常见的成分。Polybius校验表由一个55的网格组成，网格中包含26个英文字母，其中I和J在同一格中。相应字母用数对表示。在古代，这种棋盘密码被广泛使用。,希腊,恺撒密码 （公元前一世纪）,它是将英文字母向前推移k位。以此字母替代的密表，如k=5，则密文字母与明文与如下对应关系 a b c d e f g h i j

6、k l m n o p q r s t u v w x y z F G H I J K L M N O P Q R S T U V W X Y Z A B C D E k就是最早的文字密钥,被用于高卢战争,密码分析的始祖阿拉伯人,公元8世纪中叶，在阿拔斯王朝，为了统治一个庞大的帝国，行政系统中广泛地使用了密码，比如国家敏感事务、税收。 他们设计并且使用代替和换位加密（单表替换）。 对古兰经的编年启示了字母的字频规律。 公元9世纪，阿拉伯的密码学家阿尔金迪al Kindi (801?873年) 提出解密的频度分析方法，通过分析计算密文字符出现的频率破译密码。,单表替换的克星-频度分析,欧洲的密码

7、学,大约在1379年，欧洲第一本关于密码学的手册由Gabriela de Lavinde编写，由几个加密算法组成，并且为罗马教皇Clement七世服务。这个手册包括一套用于通信的密钥，并且用符号取代字母和空格，形成了第一个简要的编码字符表（称为Nomenclators）。该编码字符表后来被逐渐扩展，并且流行了几个世纪，成为当时欧洲政府外交通信的主流方法。,欧洲的密码学,15世纪密码技术被广泛用于欧洲的政治、经济及文化领域里。特别是政治上的尔虞我诈、明争暗斗，对密码的加密和解密技术提出了更高的要求。 到16世纪末期，密码学更趋重要，以致大多数国家设立专职的密码秘书从事编制新密钥，加、脱密信件和破

8、译截获的书信。准密本的代码表也在这一时期得以完善，与此同时还出现了多名码（多个明文对应密文）和多义码（有两三个对应明文的密文）。 到18世纪,有些准密本已发展到两千至三千个组码。 18世纪,黑屋非常普遍，在维也纳，十人的密码组平均每天能处理80到100封信件（上至拿破仑等高官，下至平民百姓），加密信件经常遭到坚持不懈的密码分析。,密码的影响力,公元16世纪晚期，英国的菲利普斯(Philips)利用频度分析法成功破解苏格兰女王玛丽的密码信，信中策划暗杀英国女王伊丽莎白，这次解密将玛丽送上了断头台。 1628年4月,由于一个年轻人破开了雨格诺教徒的密码,亨利二世孔戴亲王,攻占了久攻不克的雷阿尔蒙特

9、城。 1781年，美军破译了克林顿将军与康华利将军的通讯信件，使英国舰队增援约克敦的计划失败，并迫使康华利投降，确定了独立战争的胜利。,多表替代,1466年或1467年初，利昂巴蒂斯塔艾伯蒂第一个提出，后来又为许多人逐步发展成当今大多数密码体制所属的一种密码类型。,艾伯蒂密码圆盘,多表替代,修道院院长约翰内斯特里特米乌斯在1508年初从事写作一本专讲密码学的书，使多表代替又向前跨出了一大步，书名为“多种写法”，此书在他死后一年半出版，是密码学第一本印刷书籍。 书中第五章出现方表： Military-Mjnl。,A B C D E F G H I J K L M N O P Q R S T U

10、V W X Y Z A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A C- C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D- D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 。 Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y,多表替代,乔范巴蒂斯塔贝拉

11、索曾是红衣主教卡皮的随从，1553年，他出版了一本名为乔范巴蒂斯塔贝拉索先生的密码，提出文字密钥的应用。即根据密钥来决定用哪一行的密表来进行替换，,对如下明文加密： TO BE OR NOT TO BE THAT IS THE QUESTION 当选定RELATIONS作为密钥时，加密过程是：明文一个字母为T，第一个密钥字母为R，因此可以找到在R行中代替T的为K，依此类推,A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z B -B

12、C D E F G H I J K L M N O P Q R S T U V W X Y Z A C- C D E F G H I J K L M N O P Q R S T U V W X Y Z A B D- D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 。 R- RS T U V W X Y Z A B C D E F G H I J K L M NO P Q 。 Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y,多表替代,乔瓦尼巴蒂斯塔波他是自然科学家（1535-16

13、15），将艾伯蒂乱序密表与特里特米乌斯和贝拉索的见解融合在一起，使之成为现代多表代替的概念。 他还首先阐明了密码分析技术的第二个主要方式可能字猜译法。,“不可破译”的维吉尼亚密码（？）,法国外交官维吉尼亚Blaise de Vigenere(1523-1596)在1585年写成了论密码集中了当时密码学的很多精华（密码分析除外）。 对贝拉索密码，他采用自身密钥体制，即以一个共同约定的字母为起始密钥，以之对第一个密文脱密，得到第一个明文，以第一个明文为密钥对第二个密文脱密，以此类推。如此不会重复使用密钥。 然而他的自身密钥体制被后世遗忘，而他着力改进的原来的贝拉索密码却被人当作他的发明，于是贝拉索

14、密码被称为维吉尼亚密码。,维吉尼亚密码的破译,公元1863，普鲁士少校卡西斯基（Kasiski）首次从关键词的长度着手将它破解。1854年，英国的巴贝奇（Charles Babbage)通过仔细分析编码字母的结构也将维吉尼亚密码破解。,估计密钥长度。找出隶属于同一凯撒表的字母，对其进行频度分析（卡西斯基试验）,查尔斯巴贝奇,自动化计算机研制的先驱 分析机,“任何人不惜步我的后尘，而能成功地建造一个包括了数学分析的全部执行部门的机器，我就敢把我的声誉交给他去评价，因为只有他才能充分鉴赏我努力的实质及其成果的价值。”,其他古典密码,栅栏密码 明文：THERE IS A CIPHER 去掉空格后变为

15、：THEREISACIPHER T E E S C P E H R I A I H R TEESCPE HRIAIHR,其他古典密码,Playfair密码 一种替换密码，1854年由查尔斯惠斯通发明。经莱昂普莱费尔提倡在英国军地和政府使用。它使用方便而且可以让频度分析法变成瞎子，在1854到1855年的克里米亚战争和1899年的布尔战争中有广泛应用。但在1915年的一战中被破译了。,S C I E N A B D F G H J K L M O P Q R T U V W X Y,SCIENCE为密钥,SK-HI SC-CI CN-IS SA-AH,其他古典密码,博福特密码 一次性便笺密码,1

16、844年，萨米尔莫尔斯发明了莫尔斯电码：用一系列的电子点划来进行电报通讯。电报的出现第一次使远距离快速传递信息成为可能，事实上，它增强了西方各国的通讯能力。 20世纪初，意大利物理学家奎里亚摩马可尼发明了无线电报，让无线电波成为新的通讯手段，它实现了远距离通讯的即时传输。由于通过无线电波送出的每条信息不仅传给了己方，也传送给了敌方，这就意味着必须给每条信息加密。 随着第一次世界大战的爆发，对密码和解码人员的需求急剧上升，一场秘密通讯的全球战役打响了。,有线电报产生了现代编码学无线电报产生了现代密码分析学,齐默尔曼电报,公元20世纪初，第一次世界大战进行到关键时刻，英国破译密码的专门机构“40号

17、房间”利用缴获的德国密码本破译了著名的“齐默尔曼电报”，促使美国放弃中立参战，改变了战争进程。,受计算机科学蓬勃发展刺激和推动的结果。快速电子计算机（转轮密码）和现代数学方法(应用矩阵的Hill密码)一方面为加密技术提供了新的概念和工具，另一方面也给破译者提供了有力武器。计算机和电子学时代的到来给密码设计者带来了前所未有的自由，他们可以轻易地摆脱原先用铅笔和纸进行手工设计时易犯的错误，也不用再面对用电子机械方式实现的密码机的高额费用。总之，利用电子计算机可以设计出更为复杂的密码系统。,Enigma （隐匿之王）,德国的Arthur Scherbius于1919年发明的一种加密电子器件，结合了机

18、械系统与电子系统。它被证明是有史以来最可靠的加密系统之一。二战期间令德军保密通讯技术处于领先地位。,转子,机械系统包括了一个包含了字母与数字的键盘，相邻地排列在一个轴上的一系列名为“转子”的旋转圆盘,在每次按键后最右边的转子都会旋转，并且有些时候与它相邻的一些转子也会旋转。转子持续的旋转会造成每次按键后得到的加密字母都会不一样。,反射器,反射器是恩尼格玛机与当时其它转子机械之间最显著的区别。它将最后一个转子的其中两个触点连接起来，并将电流沿一个不同的路线导回。这就使加密过程与解密过程变得一致。 加密后得到的字母与输入的字母永远不会相同。这在概念上和密码学上都是一个严重的错误，这个错误最终被盟军

19、解码人员利用。,接线板,接线板上的每条线都会连接一对字母。这些线的作用就是在电流进入转子前改变它的方向。,密钥的可能性,三个转子不同的方向组成了26262617576种可能性； 三个转子间不同的相对位置为6种可能性； 连接板上两两交换6对字母的可能性则是异常庞大，有100391791500种； 于是一共有175766100391791500 这样庞大的可能性，换言之，即便能动员大量的人力物力，要想靠“暴力破译法”来逐一试验可能性，那几乎是不可能的。而收发双方，则只要按照约定的转子方向、位置和连接板连线状况，就可以非常轻松简单地进行通讯了。这就是“恩尼格玛”密码机的保密原理。,Enigma破译,

20、第二次世界大战中，在破译德国著名的“Enigma”密码机密码过程中，原本是以语言学家和人文学者为主的解码团队中加入了数学家和科学家。电脑之父亚伦图灵就是在这个时候加入了解码队伍，发明了一套更高明的解码方法。同时，这支优秀的队伍设计了人类的第一部电脑（“炸弹”）来协助破解工作。,计算机和电子学时代的到来使得美国在1942年制造出了世界上第一台计算机.美国利用计算机轻松地破译了日本的紫密密码,使日本在中途岛海战中一败涂地,日本海军的主力损失殆尽. 1943年,在获悉山本五十六将于4月18日乘中型轰炸机，由6架战斗机护航，到 中途岛视察时,罗斯福总统亲自做出决定截击山本,山本乘坐的飞机在去往中途岛的

21、路上被美军击毁,山本坠机身亡,日本海军从此一蹶不振.密码学的发展直接影响了二战的战局。,密码本质上是另一种语言,在二次世界大战中，印第安纳瓦霍土著语言被美军用作密码，美国二战时候特别征摹使用印第安纳瓦约(Navajo)通信兵。在二次世界大战日美的太平洋战场上，美国海军军部让北墨西哥和亚历桑那印第安纳瓦约族人使用约瓦纳语进行情报传递。纳瓦约语的语法、音调及词汇都极为独特，不为世人所知道，当时纳瓦约族以外的美国人中，能听懂这种语言的也就一二十人。这是密码学和语言学的成功结合，纳瓦霍语密码成为历史上从未被破译的密码。,有人说密码学至少使二战的时间缩短了一年。,克劳德香农(Claude Elwood

22、Shannon,1916-2001),1948年香农发表了A Mathematical Theory of Communication 。 香农理论的重要特征是熵(entropy)的概念，他证明熵与信息内容的不确定程度有等价关系。,近现代密码学,Enigma的破译历程表示，真正保证密码安全的不是算法，而是密钥。即使算法外泄，有密钥的存在，密码也不会失效。,著名的“柯克霍夫原则” 荷兰密码学家Kerckhoffs于1883年在其名著军事密码学中提出的密码学的基本假设：密码系统中的算法即使为密码分析者所知，也对推导出明文或密钥没有帮助。也就是说，密码系统的安全性不应取决于不易被改变的事物（算法），

23、而应只取决于可随时改变的密钥。,DES,1975年1月15日，对计算机系统和网络进行加密的DES（Data Encryption Standard数据加密标准）由美国国家标准局颁布为国家标准。,DES的出现，推动了密码分析理论和技术的快速发展，出现了差分分析、线性分析等多种新型有效的密码分析方法。 DES的出现而引起的讨论及附带的标准化工作确立了安全使用分组密码的若干准则，是密码学领域中的一个里程碑。,S盒运算-密钥变换-S盒运算- -密钥变换。16次,公钥密码体系,1976年，当时在美国斯坦福大学的迪菲（Diffie）和赫尔曼(Hellman)两人提出了公开密钥密码的新思想（论文New Di

24、rection in Cryptography），把密钥分为加密的公钥和解密的私钥，这是密码学的一场革命。,公钥密码体系,不对称密码学中使用到一对公钥(public key)和私钥(private key)组合。用公钥加密的密文只能用对应私钥解密，反之，用私钥加密的密文只能用对应公钥解密。在操作过程中，人们把公钥向外界发布，让外界都知道，自己保存私钥，只有自己才能知道。如果A要发一份秘密信息给B，则A只需要得到B的公钥，然后用B的公钥加密秘密信息，此加密的信息只有B能用其保密的私钥解密。反之，B也可以用A的公钥加密保密信息给A。信息在传送过程中，即使被第三方截取，也不可能解密其内容。,RSA算

25、法,1977年，美国MIT的里维斯特(Ronald Rivest)、沙米尔(Adi Shamir)和阿德勒曼(Len Adleman)提出第一个较完善的公钥密码体制RSA体制，这是一种建立在大数因子分解基础上的算法。 RSA是被研究得最广泛的公钥算法，从1978年提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。通常认为破译RSA的难度与大数分解难度等价。,RSA算法,密钥产生 取某一个整数n，n可分解为两素数p和q的乘积，任取 e（与欧拉函数(n)=(p-1)(q-1)互素）且e(p-1)(q-1)，寻找一个正整数d，使ed1(mod(p-1)(

26、q-1),即ed除(p-1)(q-1)的余数为1。将e，n作为公钥，d，n作为私钥,将信息转化成数字 明文m 密文c 加密 c=me mod n 解密 cd mod n = (me) d mod n = m(ed) mod n=m (欧拉定理),公钥密码基于的数学难题,RSA加、解密算法，是一个可逆的公钥密码体制,该体制利用了:寻找大素数是相对容易的,而分解两个大素数的积是计算上不可行的。 背包问题 有限域的乘法群上的离散对数问题(如ElGamal公钥系统、 Massey-Omura公钥系统） 椭圆曲线上的离散对数问题(类比的ElGamal系统）,现代密码学与计算机技术、电子通信技术紧密相关。在这一阶段，密码理论蓬勃发展，密码算法设计与分析互相促进，出现了大量的密码算法和各种攻击方法。另外，密码