[IT计算机]密码学论文

1、目 录绪 论 2第一章 古代密码学演变历程 4 第一节 古代密码学的产生4 第二节 古代密码学发展6 第二章 现代密码学发展14 第一节 现代密码学产生 14 第二节 现代密码发展 16 第三节 加密算法的分类 18 第三章 md5算法介绍24 第一节 散列算法介绍 25 第二节md5算法 28 第三节md5算法的主要攻击方法. 40 第四节md5结构的缺陷及改进方案 42总结 45参考文献 46序 言密码学是一门古老而深奥的学科,密码研究已有数千年的历史。早在4000多年以前，古埃及人就在墓志铭中使用过类似于象形文字那样奇妙的符号；公元前约50年，凯撒密码一种简单的字符替换被认为是最早的正式

2、算法；中国古代秘密通信的手段，已有一些近于密码的雏形。宋曾公亮、丁度等编撰武经总要“字验”记载，北宋前期，在作战中曾用一首五言律诗的40个汉字，分别代表40种情况或要求，这种方式已具有了密本体制的特点。密码学经历了从古典密码学到现代密码的演变，最新的计算机密码学已广泛的应用到包括军事在内的其他领域，非专业人员都可以利用密码技术去阻止别人，包括政府、军方的安全机构。然而，作为普通的百姓，我们的数据和通信都是私人的、秘密的，与他人无关，也拒绝别人的窥探。密码学是研究信息系统安全的一门学科。它主要包括两个分支，即密码编码学和密码分析学。密码编码学对信息进行编码以实现信息隐藏，其主要目的是寻求保护信息

3、保密性和认证性的方法;密码分析学是研究分析破译密码的学科，其主要目的是研究加密消息的破译和消息的伪造。密码技术的基本思想是对消息做秘密变换，变换的算法即称为密码算法。本文共分三章，主要内容如下：第一章，古代密码学演变历程。主要介绍了古代密码学的产生、演变发展以及主要应用的一些密码加密技术，如隐写术，转轮机，一次一加密密码本，另外也介绍了这些技术的弊端。第二章，现代密码学发展。介绍了现代密码学以函数运算为核心的技术，本章简介了对称算法和非对称算法，重点介绍了公钥加密算法中的散列算法。第三章，md5算法介绍。介绍了散列算法列举了散列算法的实际应用，md5非线性轮函数，md5面临的攻击方式，同时阐述

4、了其优点和缺点。总结中阐述了撰写本文密码学的主要思想和学到的学科内和学科外的知识。第一章 古代密码学发展简介密码学经历了从古典密码学到现代密码学的演变。许多古典密码虽然已经经受不住现代手段的攻击, 但是它们对现代密码学的研究是功不可没的,其思想至今仍然被广泛使用。随着计算机的出现，运用计算机加密和解密技术已经得到广泛的发展和应用，不论是在军事、外交、情报 、商业、还是个人通信方面。第一节 古代密码学的产生在欧洲，公元前405年，斯巴达的将领来山得使用了原始的错乱密码；公元前一世纪，古罗马皇帝凯撒曾使用有序的单表代替密码；之后逐步发展为密本、多表代替及加乱等各种密码体制。 二十世纪初，产生了最初

5、的可以实用的机械式和电动式密码机，同时出现了商业密码机公司和市场。60年代后，电子密码机得到较快的发展和广泛的应用，使密码的发展进入了一个新的阶段。 密码破译是随着密码的使用而逐步产生和发展的。1412年，波斯人卡勒卡尚迪所编的百科全书中载有破译简单代替密码的方法。到16世纪末期，欧洲一些国家设有专职的破译人员，以破译截获的密信。密码破译技术有了相当的发展。1863年普鲁士人卡西斯基所著密码和破译技术，以及1883年法国人克尔克霍夫所著军事密码学等著作，都对密码学的理论和方法做过一些论述和探讨。1949年美国人香农发表了秘密体制的通信理论一文，应用信息论的原理分析了密码学中的一些基本问题。 自

6、19世纪以来，由于电报特别是无线电报的广泛使用，为密码通信和第三者的截收都提供了极为有利的条件。通信保密和侦收破译形成了一条斗争十分激烈的隐蔽战线。1917年，英国破译了德国外长齐默尔曼的电报，促成了美国对德宣战。1942年，美国从破译日本海军密报中，获悉日军对中途岛地区的作战意图和兵力部署，从而能以劣势兵力击破日本海军的主力，扭转了太平洋地区的战局。在保卫英伦三岛和其他许多著名的历史事件中，密码破译的成功都起到了极其重要的作用，这些事例也从反面说明了密码保密的重要地位和意义。第二节 古代密码学的发展2.1历史上的密码术语 历史上，将处理语言单元的密码系统称为密本：字、短语、句子等。例如，单词

7、 “ocelot”可能是整个短语“turn left 90 degrees，”的密文，单词“lollipop”可能是“turn right 90 degrees”的密文，而字“bent ear”可能是“howitzer”的密文。这种类型的密本在本书里没有讨论。密本在特殊环境中才有用，而密码在任何情况下都有用；密码本中若没有“anteaters“这一条，那么你就不能提它。但你可以用密码来指代任何东西。2.2 隐写术 隐写术是将秘密消息隐藏在其它消息中，这样，真正存在的秘密被隐藏了。通常发送者写一篇无伤大雅的消息，然后在同一张纸中隐藏秘密消息。历史上的隐写方式有隐形墨水，用小针在选择的字符上刺小的

8、针眼，在手写的字符之间留下细微差别，在打印字符上用铅笔作记号、除了几个字符外，大部分字符用格子盖起来等等。 最近，人们在图象中隐藏秘密消息，用图象的每个字节的最不重要的比特代替消息比特。图象并没有怎么改变大多数图象标准规定的颜色等级比人类眼睛能够觉察得到的要多得多秘密消息却能够在接收端剥离出来。用这种方法可在10241024灰色刻度图片中存储64k字节的消息。能做此类把戏的公开程序已有好几种。 peter wayner的模拟函数也能使消息隐匿，这类函数能修改消息，使它的统计外形与一些其它东西相似：如纽约时报的题录部分、莎士比亚的戏剧、internet网上的新闻组。这类隐写术愚弄不了普通人，但却

9、可以愚弄那些为特定的消息而有目的地扫描internet的大型计算机。2.3 代替密码和换位密码 在计算机出现前，密码学由基于字符的密码算法构成。不同的密码算法是字符之间互相代换或者是互相之间换位，好的密码算法是结合这两种方法，每次进行多次运算。 现在事情变得复杂多了，但原理还是没变。重要的变化是算法对比特而不是对字母进行变换，实际上这只是字母表长度上的改变，从26个元素变为2个元素。大多数好的密码算法仍然是代替和换位的元素组合。2.3.1 代替密码 代替密码就是明文中每一个字符被替换成密文中的另外一个字符。接收者对密文进行逆替换就恢复出明文来。 在经典密码学中，有四种类型的代替密码：（1）简单

10、代替密码，或单字母密码：就是明文的一个字符用相应的一个密文字符代替。报纸中的密报就是简单的代替密码。 （2）多名码代替密码：它与简单代替密码系统相似，唯一的不同是单个字符明文可以映射成密文的几个字符之一，例如a可能对应于5、13、25或56，“b”可能对应于7、19、31或42，等等。 （3）字母代替密码：字符块被成组加密，例如“aba”可能对应于“rtq”，abb可能对应于“sll”等。 （4）多表代替密码：由多个简单的代替密码构成，例如，可能有5个被使用的不同的简单代替密码，单独的一个字符用来改变明文的每个字符的位置。 著名的凯撒密码就是一种简单的代替密码，它的每一个明文字符都由其右边第3

11、个（模26）字符代替（a由d代替，b由e代替w由z代替x由a代替，y由b代替，z由c代替）。它实际上更简单，因为密文字符是明文字符的环移，并且不是任意置换。 rot13是建在unix系统上的简单的加密程序，它也是简单的代替密码。在这种密码中，a被n代替，b被o代替等等，每一个字母是环移13所对应的字母。用rot13加密文件两遍便恢复出原始的文件：p=rot13（rot13（p）； rot13并非为保密而设计的，它经常用在互联网vsenet电子邮件中隐藏特定的内容，以避免泄露一个难题的解答等等。 简单代替密码是很容易破译的，因为它没有把明文的不同字母的出现频率掩盖起来。多名码代替密码早在1401

12、年最早由duchy mantua公司使用，这些密码比简单代替密码更难破译，但仍不能掩盖明文语言的所有统计特性，用已知明文攻击，破译这种密码非常容易，唯密文攻击要难一些，但在计算机上只需几秒钟。 字母代替密码是字母成组加密，普莱费尔在1854年发明了这种密码。在第一次世界大战中英国人就采用这种密码。字母成对加密，它的密码分析在中讨论。希尔密码是多字母代替密码的另一个例子。有时你会把huffman编码用作密码，这是一种不安全的多字母代替密码。 多表代替密码由leon battista在1568年发明，在美国南北战争期间由联军使用。尽管我们容易破译（特别是在计算机的帮助下），许多商用计算机保密产品都

13、使用这种密码形式。维吉尼亚密码（第一次在1586年发表）和博福特密码均是多表代替密码的例子。 多表代替密码有多个单字母密钥，每一个密钥被用来加密一个明文字母。第一个密钥加密明文的第一个字母，第二个密钥加密明文的第二个字母等等。在所有的密钥用完后，密钥又再循环使用，若有20个单个字母密钥，那么每隔20个字母的明文都被同一密钥加密，这叫做密码的周期。在经典密码学中，密码周期越长越难破译，使用计算机就能够轻易破译具有很长周期的代替密码。 滚动密钥密码（有时叫书本密码）是多表代替密码的另一个例子，就是用一个文本去加密另一个文本，即使这种密码的周期与文本一样长，它也是很容易被破译的。换位密码 在换位密码

14、中，明文的字母保持相同，但顺序被打乱了。在简单的纵行换位密码中，明文以固定的宽度水平地写在一张图表纸上，密文按垂直方向读出，解密就是将密文按相同的宽度垂直地写在图表纸上，然后水平地读出明文。在第一次世界大战中，德国人所用的adfgvx密码就是一种换位密码与简单的代替密码的组合。在那个时代它是一个非常复杂的算法，但被法国密码分析家george painvin所破。虽然许多现代密码也使用换位，但由于它对存储要求很大，有时还要求消息为某个特定的长度，因而比较麻烦。代替密码要常用得多。2.3.2 转轮机 在20年代，人们发明各种机械加密设备用来自动处理加密。大多数是基于转轮的概念，机械转轮用线连起来完

15、成通常的密码代替。 转轮机有一个键盘和一系列转轮，它是vigenere 密码的一种实现。每个转轮是字母的任意组合，有26个位置，并且完成一种简单代替。例如：一个转轮可能被用线连起来以完成用“f”代替“a”，用“u”代替“b”，用“l”代替“c”等等，而且转轮的输出栓连接到相邻的输入栓。 例如，在4个转轮的密码机中，第一个转轮可能用“f”代替“a”， 第二个转轮可能用“y”代替“f”， 第三个转轮可能用“e”代替“y”， 第四个转轮可能用“c”代替“e”，“c”应该是输出密文。那么当转轮移动后，下一次代替将不同了。 为使机器更安全，可把几种转轮和移动的齿轮结合起来。因为所有转轮以不同的速度移动，

16、n个转轮的机器的周期是26n。，为进一步阻止密码分析，有些转轮机在每个转轮上还有不同的位置号。 最著名的转轮装置是恩尼格马(enigma)。恩尼格马在第二次世界大战期间由德国人使用。其基本原理由欧洲的arthur scherbius和arvid gerhard damn发明，它由arthur scherbius在美国申请了专利1383，德国人为了战时使用，大大地加强了基本设计。 恩尼格马有三个转轮，从五个转轮中选择。转轮机中有一块稍微改变明文序列的插板，有一个反射轮导致每个转轮对每一个明文字母操作两次。像恩尼格马那样复杂的密码，在第二次世界大战期间都被破译了。波兰密码小组最早破译了德国的恩尼格

17、马，并告诉了英国人。德国人在战争进行过程中修改了我们的密码。但是，古代加密技术，在计算机等现代计算速度加快以后，变得非常不安全，亟待改进，适应现代社会的发展。2.4 一次一密乱码本一次一密乱码本不外乎是一个大的不重复的真随机密钥字母集，这个密钥字母集被写在几张纸上，并一起粘成一个乱码本。它最初的形式是将一次一密乱码本用于电传打字机。发方用乱码本中的每一密钥字母准确地加密一个明文字符。加密是明文字符和一次一密乱码本密钥字符的模26加法。每个密钥仅对一个消息使用一次。发方对所发的消息加密，然后销毁乱码本中用过的一页或用过的磁带部分。收方有一个同样的乱码本，并依次使用乱码本上的每个密钥去解密密文的每

18、个字符。收方在解密消息后销毁乱码本中用过的一页或用过的磁带部分。新的消息则用乱码本的新的密钥加密。值得注意的是，密钥字母必须是随机产生的。对这种方案的攻击将是针对用来产生密钥序列的那种方法。使用伪随机数发生器是不值得考虑的，它们通常具有非随机性。第二章 现代密码学发展密码学经历了从古典密码学到现代密码学的演变，许多古典密码虽然已经经受不住现代手段的攻击。随着计算机的出现，不论是利用计算机加密还是解密技术都得以快速的发展和广泛的应用。第一节 现代密码学的产生当今世界各主要国家的政府都十分重视密码工作，有的设立庞大机构，拨出巨额经费，集中数以万计的专家和科技人员，投入大量高速的电子计算机和其他先进

19、设备进行工作。与此同时，各民间企业和学术界也对密码日益重视，不少数学家、计算机学家和其他有关学科的专家也投身于密码学的研究行列，更加速了密码学的发展。但是，在很多年里这种密码学是军队独家专有的领域。美国国家安全局以及前苏联、英国、法 以色列及其它国家的安全机构已将大量的财力投入到加密自己的通信，同时又千方百计地去破译别人的通信的残酷游戏之中，面对这些政府，个人既无专门知识又无足够财力保护自己的秘密，个人隐秘的信息得不到法律和技术两方面有效的保护。 在这之后，公开的密码学研究开始呈现爆炸性地增长。从二次世界大战以来，当普通公民还在长期使用经典密码时，计算机密码学成为世界军事的独占领域，在军事战争

20、中占据举足轻重的地位。密码学发展到今天，最新的计算机密码学已广泛的应用到除军事以外的其他领域，非专业人员都可以利用密码技术去阻止别人，包括政府、军方的安全机构。然而，作为普通的百姓，我们是否真的需要这种保密？回答是肯定的，我们也可能正设计一件新产品，讨论一种市场策略，或计划接管竞争对手的生意，或者，我们可能生活在一个不尊重个人隐私权的国家，也可能做一些我们自己认为并非违法实际却是非法的事情。不管理由是什么，我们的数据和通信都是私人的、秘密的，与他人无关，也拒绝别人的窥探。 第二节 近代密码学的发展在第一次世界大战以前，密码学中核心的部分极少公开，但事实上它在极为迅速的发展，由william f

21、. friedman在1918年发表的重合指数及其在密码学中的应用，成为二十世纪最有影响的密码分析文章之一。同年，edward h.hebern申请了第一个转轮机专利，这种装置在50年里被作为美军的主要密码设备。 第一次世界大战后，美国陆军和海军的从事秘密工作的机要部门在密码学方面取得重要的进展。同期30、40年代，有几篇基础性的文章出现在公开的文献，但是论文的所显示出来的内容离当时真正的技术水平相差甚远。直到在1967年，david kahn的破译者出现了，虽然它没有新的技术思想，却对以往的密码学历史作了相当完整的记述，包括当时政府认为是秘密的内容。破译者的意义不仅在于它涉及到的相当广泛的领

22、域，更重要的是更多以前对密码一无所知的人开始关注、了解和研究密码学。自此，密码学开始更多的被人关注和重视。 密码学不同于其他学科的是：它需要密码学和密码分析学紧密结合互为促进，这也是密码学的特殊性之一。密码学的中最为矛盾的是：理论系统设计、实际上的程序编译和密码漏洞的分析修补工作特别复杂。提出一个理论上的系统设计原理并不难，但许多学究式的设计就非常复杂，以至于密码分析家不知从何入手，分析这些设计中的漏洞远比原先设计它们更难。在70年代后期和80年代初，当公众在密码学方面的兴趣显示出来时，国家安全局（nsa）即美国官方密码机构曾多次试图平息它。第一次是一名长期在nsa工作的雇员的一封信为密码学的

23、公开时间作了宣传工作。 随着80年代的到来，nsa将重点更多的集中在实际应用上，而不是密码学的研究中。现有的法律授权nsa通过国务院控制密码设备的出口。随着商务活动的日益国际化和世界市场上美国份额的减退，国内外市场上需要单一产品的压力增加了。这种单一产品受到出口控制，于是 nsa不仅对出口什么，而且也对在美国出售什么都施加了相当大的影响。 但是密码学的公开使用面临一种新的挑战，政府建议在可防止涂改的芯片上用一种秘密算法代替广为人知且随处可得的数据加密标准（des），这些芯片将含有政府监控所需的编纂机制。这种“密钥托管”计划的弊病是它潜在地损害了个人隐私权，并且以前的软件加密不得不以高价增用硬件

24、来实现，迄今，密钥托管产品正值熊市，但这种方案却已经引起了广泛的批评，特别是那些独立的密码学家怨声载道。然而，人们看到的更多是编程技术的未来而不是政治，并且还加倍地努力向世界提供更强的密码，这种密码能够实现对公众的监视。第三节 加密算法分类根据加密和解密的迷药是否相同，可将密码算法分为加密对称算法和非对称加密算法。 2.3.1对称加密算法des（数据加密标准）是最通用的计算机加密算法。des是美国和国际标准，它是对称算法，加密和解密的密钥是相同的。 对称加密算法有时又叫传统加密算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。在大多数对称算法中，加密解密密钥是相同的。这些算法也叫秘密密

25、钥算法或单密钥算法，它要求发送者和接收者在安全通信之前，商定一个密钥。对称算法的安全性依赖于密钥，泄漏密钥就意味着任何人都能对消息进行加密解密。只要通信需要保密，密钥就必须保密 对称加密算法的优点和缺点其优点在于效率高（加解密速度能达到数十兆秒或更多），算法简单，系统开销小，适合加密大量数据。 尽管对称密码术有一些很好的特性，但它也存在着明显的缺陷，包括：（l）进行安全通信前需要以安全方式进行密钥交换。这一步骤，在某种情况下是可行的，但在某些情况下会非常困难，甚至无法实现。（2)规模复杂。举例来说，a与b两人之间的密钥必须不同于a和c两人之间的密钥，否则给b的消息的安全性就会受到威胁。在有10

26、00个用户的团体中，a需要保持至少999个密钥（更确切的说是1000个，如果她需要留一个密钥给他自己加密数据）。对于该团体中的其它用户，此种倩况同样存在。这样，这个团体一共需要将近50万个不同的密钥！推而广之，n个用户的团体需要n2/2个不同的密钥。 通过应用基于对称密码的中心服务结构，上述问题有所缓解。在这个体系中，团体中的任何一个用户与中心服务器（通常称作密钥分配中心）共享一个密钥。因而，需要存储的密钥数量基本上和团体的人数差不多，而且中心服务器也可以为以前互相不认识的用户充当“介绍人”。但是，这个与安全密切相关的中心服务器必须随时都是在线的，因为只要服务器一掉线，用户间的通信将不可能进行

27、。这就意味着中心服务器是整个通信成败的关键和受攻击的焦点，也意味着它还是一个庞大组织通信服务的“瓶颈” 2.3.2公开密钥算法 rsa（根据它的发明者命名的，即rivest，shamir 和adleman）是最流行的公开密钥算法，它能用作加密和数字签名。 公开密钥密码体制是现代密码学的最重要的发明和进展。一般理解密码学(cryptography)就是保护信息传递的机密性。但这仅仅是当今密码学主题的一个方面。对信息发送与接收人的真实身份的验证、对所发出/接收信息在事后的不可抵赖以及保障数据的完整性是现代密码学主题的另一方面。 公开密钥密码体制对这两方面的问题都给出了出色的解答，并正在继续产生许多

28、新的思想和方案。在公钥体制中，加密密钥不同于解密密钥。人们将加密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。迄今为止的所有公钥密码体系中，rsa系统是最著名、使用最广泛的一种。 。密钥对在基于公钥体系的安全系统中，密钥是成对生成的，每对密钥由一个公钥和一个私钥组成。在实际应用中，私钥由拥有者自己保存，而公钥则需要公布于众。为了使基于公钥体系的业务（如电子商务等）能够广泛应用，一个基础性关键的问题就是公钥的分发与管理。 对称算法可看成保险柜，密钥就是保险柜的号码组合。知道号码组合的人能够打开保险柜，放入文件，再关闭它。持有号码组合的其他人可以打开保险柜，取出文件来，而不知道保险柜号

29、码组合的人就必须去摸索打开保险柜的方法。 1976年，whitfield diffie和martin hellman永远改变 了密码学的范例（nsa宣称早在1966年就有这种概念的知识，但没有提供证据）。他们提出了公开密钥密码学。他们使用两个不同的密钥：一个是公开的，另一个是秘密的。持有公钥的任何人都可加密信息，但却不能解密。只有持有私钥的人才能解密。就好像有人把密码保险柜变成一个信箱，把邮件投进邮箱相当于用公开密钥加密，任何人都可以做，只要打开窗口，把它投进去。取出邮件相当于用私钥解密。一般情况下，打开它是很难的，你需要焊接机和火把。然而，如果你拥有私钥（开信箱的钥匙），就很容易从邮箱中取出

30、邮件。 数学上，这个过程是基于前面讨论过的单向陷门函数。加密是容易的，加密指令就是公开密钥，任何人都能加密信息。解密是困难的，它做得非常困难，以致于不知道这个秘密，即使用cray计算机和几百万年的时间都不能解开这个信息。这个秘密或陷门就是私钥。持有这个秘密，解密就和加密一样容易。对称算法与公钥算法的比较：在实际的世界中，公开密钥算法不会代替对称算法。公开密钥算法不用来加密消息，而用来加密密钥。这样做有两个理由： （1）公钥算法比对称算法慢，对称算法一般比公钥算法快一千倍。是的，计算机变得越来越快，在15年后计算机运行公开密钥密码算法的速度比得上现在计算机运行对称密码的速度。但是，带宽需求也在增

31、加，总有比公开密钥密码处理更快的加密数据要求。（2）公开密钥密码系统对选择明文攻击是脆弱的。如果c=e（p），当p是n个可能明文集中的一个明文，那么密码分析者只需要加密所有n个可能的明文，并能与c比较结果（记住，加密密钥是公开的）。用这种方法，他不可能恢复解密密钥，但他能够确定p。如果持有少量几个可能加了密的明文消息，那么采用选择明文攻击可能特别有效。例如，如果p是比1百万美圆少的某个美圆值，密码分析家尝试所有1百万个可能的美圆值，即使p不很明确，这种攻击也是非常有效的。单是知道密文与某个特殊的明文不相符，就可能是有用的信息。对称密码系统不易受这种攻击，因为密码分析家不可能用未知的密钥来完成加

32、密的尝试。 第三章 散列算法和md5算法散列函数（也称散列算法）提供了这样的一种服务：它对不同长度的输入消息，产生固定的长度的输出。这个固定长度的输出称之为原输入消息的“散列”或“消息摘要”。对于一个安全的散列函数，这个消息摘要通常可以直接作为消息的认证标签。目前已经研制出适合于各种用途的散列算法，这些算法都是伪随机函数，任何散列值都是等可能的。输出并不可辨别的方式依赖于输入。任何输入串中单个比特的变化，将会导致输出比特串中大约一半的比特发生变化。mdx系列hash函数主要有md2，md4，md5，以及在设计上略为改变的haval，ripemd. ripemd一160。这些hash函数最新、最

33、有效的攻击方法见，这证明了它们是不安全的。md4是ronrivest设计的单向散列函数，md表示消息摘，对输入消息，算法产生128一位散列值(或消息摘要)。该hash函数的设计没有基于任何假设和密码体制，而是一种直接构造法，所以计算速度快，特别适合32位计算机软件实现，对于长的信息签名很实用。第一节 散列算法介绍3.1.1散列函数散列函数又称hash函数，hash函数(也称杂凑函数或杂凑算法)就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一般用于产生消息摘要，密钥加密等.一个安全的杂凑函数应该至少满足以下几个条件:输入长度是任意的;输出长度是固定的,根据

34、目前的计算技术应至少取128bits长,以便抵抗生日攻击;对每一个给定的输入,计算输出即杂凑值是很容易的给定杂凑函数的描述,找到两个不同的输入消息杂凑到同一个值是计算上不可行的,或给定杂凑函数的描述和一个随机选择的消息,找到另一个与该消息不同的消息使得它们杂凑到同一个值是计算上不可行的。hash函数主要用于完整性校验和提高数字签名的有效性,目前已有很多方案。这些算法都是伪随机函数,任何杂凑值都是等可能的。输出并不以可辨别的方式依赖于输入;在任何输入串中单个比特的变化,将会导致输出比特串中大约一半的比特发生变化。3.1.2常见散列函数(hash函数)（1）md5（message digest a

35、lgorithm 5）：是rsa数据安全公司开发的一种单向散列算法，md5被广泛使用，可以用来把不同长度的数据块进行暗码运算成一个128位的数值； （2）sha（secure hash algorithm）这是一种较新的散列算法，可以对任意长度的数据运算生成一个160位的数值； （3）mac（message authentication code）：消息认证代码，是一种使用密钥的单向函数，可以用它们在系统上或用户之间认证文件或消息。hmac（用于消息认证的密钥散列法）就是这种函数的一个例子。 （4）crc（cyclic redundancy check）：循环冗余校验码，crc校验由于实现简单

36、，检错能力强，被广泛使用在各种数据校验应用中。占用系统资源少，用软硬件均能实现，是进行数据传输差错检测地一种很好的手段（crc 并不是严格意义上的散列算法，但它的作用与散列算法大致相同，所以归于此类）。 3.1.3 散列算法的典型应用（1）用md5校验和实现文件的完整性保护 较常用的有奇偶校验和crc校验，但是这两种并没有抗数据传该的能力，能检测到数据传输的错误，但却不能防止数据被破坏。md5是目前最广泛的一种文件完整性算法可以。（2）文件系统完整性保护 散列算法可以保存二进制文件系统的数字指纹，目的是检测文件系统是否未经允许的被修改。可以定期或者根据需要再次计算文件系统的校验和，一旦发现与原

37、来保存的值不匹配，说明文件已经被非法修改或是感染病毒。 （3）身份鉴别 例如unix系统中用户密码就是经过md5加密后存储在文件系统中，当用户登陆时，系统把用具输入的密码计算成md5值，然后再与文件系统中的md5比较，就可验证密码的合法性。 （4）网页自动恢复系统 网页保护是专门用于对页面进行保护的系统。其基本任务是在网页文件被篡改后，能够及时发现发现、产生报警、自动恢复。第二节 md5算法3.2.1 md5算法原理md5算法的核心是hash函数。密码学hash函数又称杂凑函数，是在信息安全领域有广泛和重要应用的密码算法，主要作用是数据完整性验证和消息认证。它有一种类似于指纹的应用，所以有时候

38、也把它叫做“数字指纹”。因为它具有以下特性:原始信息只要改变一点点，哪怕是几比特，对应的消息摘要也会改变很大。hash函数把任意有限长的输入行映射到固定长的行。hash函数的值域与定义域相比规模要小得多，它是“多对一”的映射，因此可能会发生碰撞。所谓碰撞是指定义域的两个不同元素xl、x2映射到同一个消息摘要，即h(xl)=h(x2)，也就是存在不同的消息具有相同的消息摘要对md5算法简要的叙述可以为：md5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。 在md5算法

39、中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448。因此，信息的字节长度（bits length）将被扩展至n*512+448，即n*64+56个字节（bytes），n为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度=n*512+448+64=(n+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。 md5中有四个32位被称作链接变量的整数参数，他们分别为：a=0x012345

40、67，b=0x89abcdef，c=0xfedcba98，d=0x76543210。当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。将上面四个链接变量复制到另外四个变量中：a到a，b到b，c到c，d到d。主循环有四轮（md4只有三轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。每次操作如下图3-1、图 3-2所示。 图 3-1 md5

41、主循环图 3-2 md5轮循环中的对32bit消息字的一次处理过程以一下是每次操作中用到的四个非线性函数（每轮一个）。f(x,y,z) =(x&y)|(x)&z) g(x,y,z) =(x&z)|(y&(z) h(x,y,z) =xyz i(x,y,z)=y(x|(z) （&是与，|是或，是非，是异或） 这四个函数的说明：如果x、y和z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。f是一个逐位运算的函数。即，如果x，那么y，否则z。函数h是逐位奇偶操作符。 47md5的四个非线性轮函数分别如下第一轮 ff(a,b,c,d,m0,7,0xd76aa478) ff(d,a,b,c,m

42、1,12,0xe8c7b756) ff(c,d,a,b,m2,17,0x242070db) ff(b,c,d,a,m3,22,0xc1bdceee) ff(a,b,c,d,m4,7,0xf57c0faf) ff(d,a,b,c,m5,12,0x4787c62a) ff(c,d,a,b,m6,17,0xa8304613) ff(b,c,d,a,m7,22,0xfd469501) ff(a,b,c,d,m8,7,0x698098d8) ff(d,a,b,c,m9,12,0x8b44f7af) ff(c,d,a,b,m10,17,0xffff5bb1) ff(b,c,d,a,m11,22,0x895

43、cd7be) ff(a,b,c,d,m12,7,0x6b901122) ff(d,a,b,c,m13,12,0xfd987193) ff(c,d,a,b,m14,17,0xa679438e) ff(b,c,d,a,m15,22,0x49b40821) 第二轮 gg(a,b,c,d,m1,5,0xf61e2562) gg(d,a,b,c,m6,9,0xc040b340) gg(c,d,a,b,m11,14,0x265e5a51) gg(b,c,d,a,m0,20,0xe9b6c7aa) gg(a,b,c,d,m5,5,0xd62f105d) gg(d,a,b,c,m10,9,0x02441453

44、) gg(c,d,a,b,m15,14,0xd8a1e681) gg(b,c,d,a,m4,20,0xe7d3fbc8) gg(a,b,c,d,m9,5,0x21e1cde6) gg(d,a,b,c,m14,9,0xc33707d6) gg(c,d,a,b,m3,14,0xf4d50d87) gg(b,c,d,a,m8,20,0x455a14ed) gg(a,b,c,d,m13,5,0xa9e3e905) gg(d,a,b,c,m2,9,0xfcefa3f8) gg(c,d,a,b,m7,14,0x676f02d9) gg(b,c,d,a,m12,20,0x8d2a4c8a) 第三轮 hh(a

45、,b,c,d,m5,4,0xfffa3942) hh(d,a,b,c,m8,11,0x8771f681) hh(c,d,a,b,m11,16,0x6d9d6122) hh(b,c,d,a,m14,23,0xfde5380c) hh(a,b,c,d,m1,4,0xa4beea44) hh(d,a,b,c,m4,11,0x4bdecfa9) hh(c,d,a,b,m7,16,0xf6bb4b60) hh(b,c,d,a,m10,23,0xbebfbc70) hh(a,b,c,d,m13,4,0x289b7ec6) hh(d,a,b,c,m0,11,0xeaa127fa) hh(c,d,a,b,m3

46、,16,0xd4ef3085) hh(b,c,d,a,m6,23,0x04881d05) hh(a,b,c,d,m9,4,0xd9d4d039) hh(d,a,b,c,m12,11,0xe6db99e5) hh(c,d,a,b,m15,16,0x1fa27cf8) hh(b,c,d,a,m2,23,0xc4ac5665) 第四轮ii(a,b,c,d,m0,6,0xf4292244) ii(d,a,b,c,m7,10,0x432aff97) ii(c,d,a,b,m14,15,0xab9423a7) ii(b,c,d,a,m5,21,0xfc93a039) ii(a,b,c,d,m12,6,0x

47、655b59c3) ii(d,a,b,c,m3,10,0x8f0ccc92) ii(c,d,a,b,m10,15,0xffeff47d) ii(b,c,d,a,m1,21,0x85845dd1) ii(a,b,c,d,m8,6,0x6fa87e4f) ii(d,a,b,c,m15,10,0xfe2ce6e0) ii(c,d,a,b,m6,15,0xa3014314) ii(b,c,d,a,m13,21,0x4e0811a1) ii(a,b,c,d,m4,6,0xf7537e82) ii(d,a,b,c,m11,10,0xbd3af235) ii(c,d,a,b,m2,15,0x2ad7d2bb

48、) ii(b,c,d,a,m9,21,0xeb86d391) 常数ti可以如下选择： 在第i步中，ti是4294967296 abs(sin(i)的整数部分，i的单位是弧度。 (4294967296等于2的32次方) 所有这些完成之后，将a、b、c、d分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是a、b、c和d的级联。 3.2.2 md5算法的伪代码实现#define s11 7#define s12 12#define s13 17#define s14 22#define s21 5#define s22 9#define s23 14#define s24 20#d

49、efine s31 4#define s32 11#define s33 16#define s34 23#define s41 6#define s42 10#define s43 15#define s44 21static void md5transform proto_list (uint4 4, unsigned char 64);static void encode proto_list (unsigned char *, uint4 *, unsigned int);static void decode proto_list (uint4 *, unsigned char *,

50、unsigned int);static void md5_memcpy proto_list (pointer, pointer, unsigned int);static void md5_memset proto_list (pointer, int, unsigned int);static unsigned char padding64 = 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

51、0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;#define f(x, y, z) (x) & (y) | (x) & (z)#define g(x, y, z) (x) & (z) | (y) & (z)#define h(x, y, z) (x) (y) (z)#define i(x, y, z) (y) (x) | (z)#define rotate_left(x, n) (x) (32-(n)#define ff(a, b, c, d, x, s, ac) (a) += f (b), (c)

52、, (d) + (x) + (uint4)(ac); (a) = rotate_left (a), (s); (a) += (b); #define gg(a, b, c, d, x, s, ac) (a) += g (b), (c), (d) + (x) + (uint4)(ac); (a) = rotate_left (a), (s); (a) += (b); #define hh(a, b, c, d, x, s, ac) (a) += h (b), (c), (d) + (x) + (uint4)(ac); (a) = rotate_left (a), (s); (a) += (b); #define ii(a, b, c, d, x, s, ac) (a) += i (b), (c), (d) + (x) + (uint4)(ac); (a) = rotate_left (a), (s); (a) += (b); void md5init (context)md5_ctx *context; context-count0 = context-count1 = 0; co