| 枫林在线论坛>>信息安全 [管理模式] [快速回复] [推荐给朋友] |
| [59622] 主题： MD5算法研究 |
| 作者： leaflet |
标题：  MD5算法研究[转载]
|
|
| 昵称： Leaf |
来自： 218.80.*.* 
|
|
| 经验值： 56173 | 发贴时间： 2003年05月25日 16:53:32 | |
| 等级： ☆☆☆☆☆ | 长度： 7385字 | |
|
MD5算法研究(1) [ 作者: 王可 添加时间: 2002-3-29 14:35:31 ] 综述 MD5的全称是Message-Digest Algorithm 5（信息-摘要算法），在90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L. Rivest开发 出来，经MD2、MD3和MD4发展而来。它的作用是让大容量信息在用数字签名软件签署私人 密匙前被"压缩"成一种保密的格式（就是把一个任意长度的字节串变换成一 定长的大整 数）。不管是MD2、MD4还是MD5，它们都需要获得一个随机长度的信息并产生一个128位 的信息摘要。虽然这些算法的结构或多或少有些相似，但MD2的设计与MD4和MD5完全不同 ，那是因为MD2是为8位机器做过设计优化的，而MD4和MD5却是面向32位的电脑。这三个 算法的描述和C语言源代码在Internet RFCs 1321中有详细的描述（http://www.ietf.o r g/rfc/rfc1321.txt），这是一份最权威的文档，由Ronald L. Rivest在1992年8月向IE F T提交。 Rivest在1989年开发出MD2算法。在这个算法中，首先对信息进行数据补位，使信息 的字节长度是16的倍数。然后，以一个16位的检验和追加到信息末尾。并且根据这个新 产生的信息计算出散列值。后来，Rogier和Chauvaud发现如果忽略了检验和将产生MD2冲 突。MD2算法的加密后结果是唯一的--既没有重复。 为了加强算法的安全性，Rivest在1990年又开发出MD4算法。MD4算法同样需要填补 信息以确保信息的字节长度加上448后能被512整除（信息字节长度mod 512 = 448）。然 后，一个以64位二进制表示的信息的最初长度被添加进来。信息被处理成512位Damg?rd / Merkle迭代结构的区块，而且每个区块要通过三个不同步骤的处理。Den Boer和Bossel a ers以及其他人很快的发现了攻击MD4版本中第一步和第三步的漏洞。Dobbertin向大家演 示了如何利用一部普通的个人电脑在几分钟内找到MD4完整版本中的冲突（这个冲突实际 上是一种漏洞，它将导致对不同的内容进行加密却可能得到相同的加密后结果）。毫无 疑问，MD4就此被淘汰掉了。 尽管MD4算法在安全上有个这么大的漏洞，但它对在其后才被开发出来的好几种信息 安全加密算法的出现却有着不可忽视的引导作用。除了MD5以外，其中比较有名的还有S H A-1、RIPE-MD以及HAVAL等。 一年以后，即1991年，Rivest开发出技术上更为趋近成熟的MD5算法。它在MD4的基 础上增加了"安全-带子"（Safety-Belts）的概念。虽然MD5比MD4稍微慢一些 ，但却更为 安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息 - 摘要的大小和填充的必要条件与MD4完全相同。Den Boer和Bosselaers曾发现MD5算法中 的假冲突（Pseudo-Collisions），但除此之外就没有其他被发现的加密后结果了。 Van Oorschot和Wiener曾经考虑过一个在散列中暴力搜寻冲突的函数（Brute-Forc e Hash Function），而且他们猜测一个被设计专门用来搜索MD5冲突的机器（这台机器在 1994年的制造成本大约是一百万美元）可以平均每24天就找到一个冲突。但单从1991年 到2001年这10年间，竟没有出现替代MD5算法的MD6或被叫做其他什么名字的新算法这一 点，我们就可以看出这个瑕疵并没有太多的影响MD5的安全性。上面所有这些都不足以成 为MD5的在实际应用中的问题。并且，由于MD5算法的使用不需要支付任何版权费用的， 所以在一般的情况下（非绝密应用领域。但即便是应用在绝密领域内，MD5也不失为一种 非常优秀的中间技术），MD5怎么都应该算得上是非常安全的了。 算法的应用 MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防 止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名 为.md5的文件，在这个文件中通常只有一行文本，大致结构如： MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d895e269332461 这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通 过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。如果在以后传播这个文 件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线 路不稳定引起的传输错误等），只要你对这个文件重新计算MD5时就会发现信息摘要不相 同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构， 用MD5还可以防止文件作者的"抵赖"，这就是所谓的数字签名应用。 MD5还广泛用于加密和解密技术上。比如在UNIX系统中用户的密码就是以MD5（或其 它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密 码计算成MD5值，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码 是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户 登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而 且还在一定程度上增加了密码被破解的难度。 正是因为这个原因，现在被黑客使用最多的一种破译密码的方法就是一种被称为&q uot;跑 字典"的方法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表，另 一种是 用排列组合方法生成的，先用MD5程序计算出这些字典项的MD5值，然后再用目标的MD5值 在这个字典中检索。我们假设密码的最大长度为8位字节（8 Bytes），同时密码只能是 字母和数字，共26+26+10=62个字符，排列组合出的字典的项数则是P(62,1)+P(62,2)… . +P(62,8)，那也已经是一个很天文的数字了，存储这个字典就需要TB级的磁盘阵列，而 且这种方法还有一个前提，就是能获得目标账户的密码MD5值的情况下才可以。这种加密 技术被广泛的应用于UNIX系统中，这也是为什么UNIX系统比一般操作系统更为坚固一个 重要原因。 算法描述 对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被 划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将 这四个32位分组级联后将生成一个128位散列值。 在MD5算法中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448。 因此，信息的字节长度（Bits Length）将被扩展至N*512+448，即N*64+56个字节（Byt e s），N为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足 上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以64位二进制 表示的填充前信息长度。经过这两步的处理，现在的信息字节长度=N*512+448+64=(N+1 ) *512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求 。 MD5中有四个32位被称作链接变量（Chaining Variable）的整数参数，他们分别为 ：A=0x01234567，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中之一。 以一下是每次操作中用到的四个非线性函数（每轮一个）。 F(X,Y,Z) =(X&Y)|((~X)&Z) G(X,Y,Z) =(X&Z)|(Y&(~Z)) H(X,Y,Z) =X^Y^Z I(X,Y,Z)=Y^(X|(~Z)) 。?是与，|是或，~是非，^是异或） 这四个函数的说明：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应 是独立和均匀的。 F是一个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。 假设Mj表示消息的第j个子分组（从0到15），<< FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<< GG(a,b,c ,d,Mj,s ,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<< HH(a,b,c,d,Mj,s,ti)表示a=b+(( a+(H(b, 这四个函数的说明：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一 *应 是独立和均匀的。 /_\ F是一个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。{~._. ~ } ( Y ) 假设Mj表示消息的第j个子分组（从0到15），<< ()~*~() FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<< GG(a,b,c ,(_)-(_ ) ,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<< HH(a,b,c,d,Mj,s,ti)表示a=b+(( a+(H(b, c,d)+Mj+ti)<< II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)< ;< 这四轮（64步）是： 第一轮 FF(a,b,c,d,M0,7,0xd76aa478) FF(d,a,b,c,M1,12,0xe8c7b756) FF(c,d,a,b,M2,17,0x242070db) |
|
|
========== * * * * * ==========
|
| 作者： metabolism |
标题：  RE:MD5算法研究
|
|
| 昵称： 新陈代谢 |
来自： 218.78.*.*
|
|
| 经验值： 30 | 发贴时间： 2003年07月21日 00:35:47 | |
| 等级： 新手上路 | 长度： 49字 | |
|
这个算法海一般把。算法上面大家要熟练掌握的就是des |
|
|
========== * * * * * ==========
|
 Top
|
||