MD5

MD5
---------------
关键词：Hash MD4 MD5 SHA1
---------------
引言
任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好，任何两段信息的指纹都很难重复，就如同人类的指纹一样。信息指纹在加密、信息压缩和处理中有着广泛的应用。

产生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来的。他的办法非常简单，就是将一个数的平方掐头去尾，取中间的几位数。比如一个四位的二进制数 1001（相当于十进制的9），其平方为 01010001 (十进制的 81）掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息很有可能有同一指纹。现在常用的 MersenneTwister 算法要好得多。

信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,
无法根据信息指纹推出原有信息，这种性质， 正是网络加密传输所需要的。比如说，一个网站可以根据用户的Cookie 识别不同用户，这个 cookie 就是信息指纹。但是网站无法根据信息指纹了解用户的身份，这样就可以保护用户的隐私。在互联网上，加密的可靠性，取决于是否很难人为地找到拥有同一指纹的信息， 比如一个黑客是否能随意产生用户的 cookie。从加密的角度讲 MersenneTwister，算法并不好，因为它产生的随机数有相关性。

互联网上加密要用基于加密伪随机数产生器（csprng)。常用的算法有 MD5 或者 SHA1 等标准，它们可以将不定长的信息变成定长的 128 二进位或者 160 二进位随机数。

1.基于“消息摘要”的算法

“消息摘要”（Message Digest）是一种能产生特殊输出格式的算法，这种加密算法的特点是无论用户输入什么长度的原始数据，经过计算后输出的密文都是固定长度的，这种算法的原理是根据一定的运算规则对原数据进行某种形式的提取，这种提取就是“摘要”，被“摘要”的数据内容与原数据有密切联系，只要原数据稍有改变，输出的“摘要”便完全不同，因此基于这种原理的算法便能对数据完整性提供较为健全的保障。但是，由于输出的密文是提取原数据经过处理的定长值，所以它已经不能还原为原数据，即消息摘要算法是“不可逆”的，理论上无法通过反向运算取得原数据内容，因此它通常只能被用来做数据完整性验证，而不能作为原数据内容的加密方案使用，否则谁也无法还原。尽管如此，“消息摘要”算法还是为密码学提供了健全的防御体系，因为连专家也无法根据拦截到的密文还原出原来的密码内容。因为这个特性，“消息摘要”算法产生的密文被称为“摘要”。

如今常用的“消息摘要”算法经历了多年验证发展而保留下来的强者，分别是MD2、MD4、MD5、SHA、SHA-1/256/383/512等，其中最广泛应用的是基于MD4发展而来的MD5算法。

--------------

Hash函数

Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
如果两个输入串的hash函数的值一样，则称这两个串是一个碰撞(Collision)。既然是把任意长度的字符串变成固定长度的字符串，所以，必有一个输出串对应无穷多个输入串，碰撞是必然存在的。
HASH主要用于信息安全领域中加密算法，他把一些不同长度的信息转化成杂乱的128位的编码里,叫做HASH值. 也可以说，hash就是找到一种数据内容和数据存放地址之间的映射关系
目前在世界上应用最广泛的两大密码算法MD5和SHA-1就是 Hash函数中最重要的两种。两大算法是目前国际电子签名及许多其他密码应用领域的关键技术，广泛应用于金融、证券等电子商务领域。其中SHA-1更被认为是现代网络安全不可动摇的基石。[/color]
--------------

⑴.MD5算法

MD5算法的全称是“消息摘要算法”（Message-Digest Algorithm version.5），它是当前公认的强度最高的加密算法。出现在MD5之前的是MD2和MD4，间隔分别只有一年。虽然三者的算法结构多少有点相似，但是由于MD2诞生于8位计算机的时代，因此它的设计与后来出现的MD4、MD5完全不同，因此不能进行简单的替代。然而，无论是MD2、MD4还是MD5，它们都是在获得一个随机长度信息的基础上产生一个128位信息摘要的算法。

MD2算法是Rivest在1989年开发的，它很慢（因为是为8位机器设计的），但相当安全。在这个算法中，首先要对信息进行数据补位，使信息的字节长度是16的倍数。然后，以一个16位的检验和追加到信息末尾，并且根据这个新产生的信息计算出散列值（Hash），最终运算结果即为类似于 “d41d8cd98f00b204e9800998ecf8427e”的摘要，而且这个值是唯一的。

为了加强算法的安全性，Rivest在1990年又开发出MD4算法。MD4算法同样需要填补信息以确保信息的字节长度加上448后能被512整除（信息字节长度除以512的余数为448）。然后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位Merkle迭代结构的区块，而且每个区块要通过三个不同步骤的处理，最终生成摘要。

然而MD4存在一个严重漏洞，那就是“冲突”（Collisions）。“冲突”是所有基于“摘要”的算法都要面对的最大问题，由于它们是根据“不完整”的数据内容产生的密文，如果运算过程存在暇癖，就会在处理某些不同数据时产生相同的摘要，这后果可是致命的，因为“摘要”算法的原则是原数据不可还原，因此验证的过程并不同于简单加密运算里的“数据还原匹配”，验证端同样要根据原数据（甚至连原数据都没有，而仅仅是最初保存的摘要）进行运算得到的摘要作为凭据与客户端发来的摘要进行匹配检验，如果两段字符串完全相同，即视为验证通过。这是在“摘要算法”理论上“不可逆且唯一”的基础上采用的安全检验方法，验证方可以不需要索取原数据，而只要拥有一个有效的摘要即可完成对客户端的身份确认，大大减少了原数据被入侵者掌握的几率。

但是这样的验证的方式就产生了一个“看似不可能”的缺陷：假如入侵者能伪造出一段数据，使之能在通过“摘要”计算后产生的摘要与真正的原数据产生的摘要一样，那么入侵者便能冒充原数据持有者通过身份验证。这在理论上是不可能的，然而现实总是不会让人那么愉快，由于算法不可避免的出现了漏洞，使得这个设想成为了事实，这就是“冲突”的来源：某两个或多个数据产生的摘要出现了完全雷同的现象，使得用户能在输入了即使不是原数据的密码后能顺利通过验证，因为身份检验程序发现原本储存的用户信息的签名数据与接收到的数据的运算结果完全一致，于是认为请求方为合法用户，就给予通过了。这种运算结果相同的现象，就是“冲突”。

“冲突”会造成非常危险的后果，因此MD4被无情的抛弃了，取而代之的是在MD4基础上加强了算法的MD5，它在MD4的基础上增加了“安全带”（Safety Belts）的概念，虽然MD5比MD4稍微慢一些，但却大大减小了冲突的发生率，虽然很早以前就有专家发现MD5算法在专门用于寻找“冲突”的机器上平均每24天就会产生一个“冲突”，但是对于一般应用来说，这种几率已经非常低微，因此MD5至今仍然是最强健的加密算法。

有读者也许会问，既然MD5是不可逆的，那么网络上存在的那些“MD5密码破解工具”又是什么回事？其实，那并不是破解，至今MD5还没能被完全破解过。网络上流传的那些工具纯粹是依赖于“运气+机器性能+耐心”的产品而已，它们的原理是“穷举”，即程序在一定的数据范围内产生一系列数据组合进行MD5运算，再把运算结果与获取的摘要进行比较，如果两者相同，就被定义为“破解”了。这只是一种穷举法而已，实际意义不大，要知道在不产生冲突的前提下生成一个与原数据完全相同的字符串要有多少运气的成分，更何况它还完全依赖于你的机器性能，如果对方密码简单如123456这样的形式，我们还可能侥幸在1分钟 ——1天内运算出来，但是如果对方密码是 0e1WeTru9t@MD5 这样的组合呢？MD5的高强度使得它如此难以破解，因此成为大众首选，许多入侵者在辛苦取得目标网站数据库后，一看password字段都是0ca175b9c0f726a831d895e269332461的形式，第一反应都会是“MD！白干了！”

⑵.SHA算法

世界的发展是多元化的，尽管MD5性能如此出众，但它并不能代表唯一，世界上还同时存在着许多其它方式的高强度算法，SHA系列算法就是其中一个。

SHA的中文是“安全哈希算法”（Safe-Hash Algorithm），它有多个改进版本，也属于“摘要”算法，它能产生高达160位的摘要，SHA-1是改进了SHA算法缺陷而产生的升级版本，除此之外还有SHA-256、SHA-383、SHA-512等，提供了最高达到512位的摘要。

SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。SHA-1是由美国标准技术局（NIST）颁布的国家标准，是一种应用最为广泛的hash函数算法，也是目前最先进的加密技术，被政府部门和私营业主用来处理敏感的信息。而SHA-1基于MD5，MD5又基于MD4。

3) 什么是CRC
CRC的全称为Cyclic Redundancy Check，中文名称为循环冗余校验。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。实际上，除数据通信外，CRC在其它很多领域也是大有用武之地的。例如我们读软盘上的文件，以及解压一个ZIP文件时，偶尔会碰到“Bad CRC”错误，由此它在数据存储方面的应用可略见一斑。

2.Hash算法在信息安全方面应用的主要体现
1) 文件校验
我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。
MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。
2) 数字签名
Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。 对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。
3) 鉴权协议
如下的鉴权协议又被称作"挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

当然，hash函数并不是完全可靠，不同文件产生相同MD5和SHA1的几率还是有的，只是不高，在我们论坛里提供的系统光盘，你想对这么几个文件存在相同HASH的不同文件根本是不可能的。

===============
总结：理论上，对任意一段数据，必存在另外一段不同的数据，使得他们的MD5相同
===============
参考文献：
《MD5算法研究》
《DES算法实现过程分析》
《RSA算法基础》
《RC4加密算法》
《加密和 Microsoft 公钥基础结构》

**********

2007年11月15日 19时17分  发布   百度空间：http://hi.baidu.com/sys0/