《密码分析的艺术》由会员分享,可在线阅读,更多相关《密码分析的艺术(18页珍藏版)》请在金锄头文库上搜索。
1、1目目录录密码分析的艺术.3一、什么是密码分析.3二、密码分析的历史.3(一)第一阶段:古代-1949 年.3(二)第二阶段:1949 年-1975 年.6(三)第三阶段:1976 年至今.7三、密码分析的方法.7(一)穷举法攻击.8(二)统计分析攻击.8(三)数学分析攻击.9四、密码分析的案例:MD5 算法及其破解.10(一)关于 MD5 算法.101.MD5 算法简介.102.MD5 应用.113.MD5 算法原理.134.MD5 算法的优势.16(二)MD5 算法的破解.17(五)总结.182密码分析的艺术密码分析的艺术一、什么是密码分析一、什么是密码分析密码学是保密学的一部分。保密学是
2、研究密码系统或通信安全的科学,它包含两个分支,即密码学(cryptology)和密码分析学(cryptanalytics) 。密码学是对信息进行编码实现隐蔽信息的一门学问, 而密码分析学是研究分析破译密码的学问,两者相互对立而又相互促进。密码分析这个词有时也被用来指广义上的绕开某个密码学算法或密码协议的尝试,而不仅仅是针对加密算法。但是,密码分析通常不包括并非主要针对密码算法或协议的攻击,如贿赂、拷打、入室抢劫、键盘记录器,等等。尽管这些攻击方式是计算机安全领域里的重要考虑因素, 而且通常比传统的密码分析更加有效。虽然密码分析的目标在密码学的历史上从古至今都一样, 但是实际使用的方法和技巧则随
3、着密码学变得越来越复杂而日新月异。 密码学算法和协议从古代只利用纸笔等工具,发展到第二次世界大战时的恩尼格玛密码机(又称谜,德语:Enigma) ,直到目前的基于电子计算机的方案。而密码分析也随之改变了。无限制地成功破解密码已经不再可能。事实上,只有很少的攻击是实际可行的。在上个世纪 70 年代中期,公钥密码学作为一个新兴的密码学分支发展起来了。而用来破解这些公钥系统的方法则和以住完全不同, 通常需要解决精心构造出来的纯数学问题。其中最著名的就是大数的质因子分解。二、密码分析的历史二、密码分析的历史密码学有一个奇妙的发展历程,当然,密而不宣总是扮演主要角色。一般认为密码学的发展可以划分为三个阶
4、段:(一)第一阶段:古代(一)第一阶段:古代-1949-1949 年年这一时期可以看作是科学密码学的前夜时期, 这阶段的密码技术可以说是一种艺术,而不是一种科学,密码学专家常常是凭知觉和信念来进行密码设计和分析,而不是推理和证明。早在古埃及就已经开始使用密码技术,但是用于军事目的,不公开。31844 年,萨米尔莫尔斯发明了莫尔斯电码:用一系列的电子点划来进行电报通讯。电报的出现第一次使远距离快速传递信息成为可能,事实上,它增强了西方各国的通讯能力。20 世纪初,意大利物理学家奎里亚摩马可尼发明了无线电报,让无线电波成为新的通讯手段,它实现了远距离通讯的即时传输。马可尼的发明永远地改变了密码世界
5、。由于通过无线电波送出的每条信息不仅传给了己方,也传送给了敌方,这就意味着必须给每条信息加密。随着第一次世界大战的爆发,对密码和解码人员的需求急剧上升,一场秘密通讯的全球战役打响了。在第一次世界大战之初,隐文术与密码术同时在发挥着作用。在索姆河前线德法交界处,尽管法军哨兵林立,对过往行人严加盘查,德军还是对协约国的驻防情况了如指掌, 并不断发动攻势使其陷入被动, 法国情报人员都感到莫名其妙。一天, 有位提篮子的德国农妇在过边界时受到了盘查。 哨兵打开农妇提着的篮子,见里头都是煮熟的鸡蛋,亳无可疑之处,便无意识地拿起一个抛向空中,农妇慌忙把它接住。哨兵们觉得这很可疑,他们将鸡蛋剥开,发现蛋白上布
6、满了字迹,都是英军的详细布防图,还有各师旅的番号。原来,这种传递情报的方法是德国一位化学家提供的,其作法并不复杂:用醋酸在蛋壳上写字,等醋酸干了后, 再将鸡蛋煮熟,字迹便透过蛋壳印在蛋白上,外面却没有任何痕迹。1914 年 8 月 5 日,英国“泰尔哥尼亚”号船上的潜水员割断了德国在北大西洋海下的电缆。他们的目的很简单,就是想让德国的日子更难过,没想到这却使德方大量的通讯从电缆转向了无线电。结果,英方截取了大量原本无法得到的情报。情报一旦截获,就被送往 40 号房间英国海军部的密件分析部门。40 号房间可以说是现代密件分析组织的原型,这里聚集了数学家、语言学家、棋类大师等任何善于解谜的人。19
7、14 年 9 月,英国人收到了一份“珍贵”的礼物:同盟者俄国人在波罗的海截获了一艘德国巡洋舰“玛格德伯格”号,得到一本德国海军的密码本。他们立即将密码本送至 40 号房间,允许英国破译德国海军的密件,并在战争期间围困德军战船。能够如此直接、顺利且经常差不多是同时读取德国海军情报的情况, 在以往的战事中几乎从未发生过。4密码学历史上最伟大的密码破译事件开始于 1917 年 1 月 17 日。 当时英军截获了一份以德国最高外交密码 0075 加密的电报,这个令人无法想象的系统由一万个词和词组组成,与一千个数字码群对应。密电来自德国外交部长阿瑟齐麦曼,传送给他的驻华盛顿大使约翰冯贝伦朵尔夫,然后继续
8、传给德国驻墨西哥大使亨尼希冯艾克哈尔特,电文将在那里解密,然后交给墨西哥总统瓦律斯提阿诺加汉扎。密件从柏林经美国海底电缆送到了华盛顿, 英军在那里将其截获并意识到了它的重要性。但是,同样接到密件的约翰冯贝伦朵尔夫却在他的华盛顿办公室里犯了个致命的错误:他们将电报用新的 0075 密件本译出,然后又用老的密件本加密后用电报传送到墨西哥城。大使先生没有意识到,他已经犯下了一个密码使用者所能犯的最愚蠢的、最可悲的错误。此时, 已经破译了老密码的英方正对着这个未曾破译的新外交密码系统一筹莫展, 不过没过多久,他们便从大使先生的糊涂操作中获得了新旧密码的比较版本。随着齐麦曼的密件逐渐清晰起来,其重要性令
9、人吃惊。尽管 1915 年美国的远洋客轮“露斯塔尼亚”号被德军击沉,但只要德国对其潜艇的行动加以限制,美国仍将一直保持中立。齐麦曼的电文概括了德国要在1917 年 2 月 1 日重新开始无限制海战以抑制英国的企图。为了让美国原地不动,齐麦曼建议墨西哥入侵美国,重新宣布得克萨斯州、新墨西哥州和亚里桑纳州归其所有。德国还要墨西哥说服日本进攻美国,德国将提供军事和资金援助。英国海军部急于将破译的情报通知美国而又不能让德国知道他们的密码已被破译。于是,英国的一个特工成功地渗入了墨西哥电报局,得到了送往墨西哥总统的解了密的文件拷贝。这样,秘密就可能是由墨西哥方泄露的,他们以此为掩护将情报透露给了美国。美
10、国愤怒了。每个人都被激怒了,原先只是东海岸的人在关心,现在,整个中西部都担心墨西哥的举动。电文破译后六个星期,美国对德国宣战。当总统伍德罗威尔逊要求对德宣战时,站在他背后的,是一个团结起来的愤怒的国家,它时刻准备对德作战。这可能是密码破译史上,当然也是情报史上最著名的事件。齐麦曼的电文使整个美国相信德国是国家的敌人。德国利用密码破译击败了俄军,反过来又因自5己的密码被破译而加速走向了灭亡。第一次世界大战前,重要的密码学进展很少出现在公开文献中。直到 1918年, 二十世纪最有影响的密码分析文章之一William F. Friedman 的专题论文 重合指数及其在密码学中的应用作为私立的“河岸(
11、Riverbank)实验室”的一份研究报告问世了,其实,这篇著作涉及的工作是在战时完成的。一战后,完全处于秘密工作状态的美国陆军和海军的机要部门开始在密码学方面取得根本性的进展。但是公开的文献几乎没有。然而技术却在飞速的发展, 简单的明文字母替换法已经被频率分析法毫无难度地破解了,曾经认为是完美的维吉耐尔(Vigenere)密码和它的变种也被英国人Charles Babbage 破解了。顺便说一句,这个 Charles Babbage 可不是凡人,他设计了差分机 Difference Engine 和分析机 Analytical Engine,而这东西就是现在计算机的先驱。这个事实给了人们两个启示:第一,没有哪种“绝对安全”的密码是不会被攻破的,这只是个时间问题;第二,破译密码看来只要够聪明就成。在二次大战中