| « | August 2025 | » | | 日 | 一 | 二 | 三 | 四 | 五 | 六 | | | | | | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | | | | | | | |
|
公告 |
|
| Blog信息 |
|
blog名称:FoxWolf
日志总数:127
评论数量:246
留言数量:0
访问次数:851633
建立时间:2006年5月31日 |
| |
|
 [程序的灵魂-算法]MD5 信息-摘要算法(上)
文章收藏, 软件技术, 科学研究
FoxWolf 发表于 2008/7/16 15:01:04 |
|
英文原文(The MD5 Message-Digest Algorithm RFC 1321)，翻译如下。
可以查看知识库: http://en.wikipedia.org/wiki/MD5
MD5 信息-摘要算法翻译：newlaos[DFCG][CCG]备忘录说明： 这篇备忘录讲述的是因特网通讯方面的内容，并不是定义一个因特网标准，因此传播此文件，将不受任何限制。内容列表：1、总述2、术语及符号3、MD5算法描述4、概要5、MD4与MD5的不同参考附录 A - 执行参考(文件源代码)MD5安全考虑及常用攻击方式(newlaos收集补充)作者地址1、总述 这个篇文章将详细描述 MD5 信息-摘要算法。这种算法可以将任意长度的信息处理成一个128bit(定长)的“指纹”或“信息摘要”。任意两个不同信息不可能处理成同样的信息摘要，同时根据得到的信息摘要也不可能逆推出原始信息。MD5算法主要用于数字签名，出于安全的考虑，任何信息(明文)在用公钥加密系统(例如RSA)加密传送前，都要用MD5算法处理出一个信息摘要。(newlaos: 一个需要传输的明文，先用MD5算法得到一个信息摘要，再用RSA的传送方私钥和接收方公钥对明文进行加密。然后传送方将密文、RSA的传送方公钥及信息摘要传输给接收方。接收方用RSA的接收方私钥和传送方公钥将密文还原成明文，再通过MD5算法得出解密后明文的信息摘要，用它来和传送方发过来的信息摘要对比，如果相同，就说明密文在传送过程中没有被人篡改。) MD5 算法是为32位计算机设计的，它在32位计算机上处理起来非常快，并且MD5算法不需要任何大的替代表，在编程实现方面也十分简洁易行。 MD5 算法是MD4算法的扩展，仅比MD4稍慢一点，但在设计上更为谨慎。MD4虽然快，但是存在一种漏洞，它导致对不同的内容进行加密却可能得到相同的加密后结果，因而促就了MD5的产生。MD5为了获得更好安全性，在运算速度上做了小小的让步。MD5算法作为一个标准，被至于大众领域以吸取各种好的建议，并进行适当的优化和改善。2、术语及符号 在这篇文章里，“word(字)”为32-bit的数值，“byte(字节)”为8-bit的数值。一个bit数据流通常解释为byte数据流，每8 -bit数据被解释为1-byte，且按高位在前的顺序排列。同理，一个byte数据流通常解释为word(字)数据流，每4-byte被解释为1- word，按的是低位在前的顺序排列。 x_i表示"x sub i"，如果写在下方的(下标)是一个表达式，我就用括号将它括起来x_{i+1}。同理，我们用 ^ 代表上标(求幂)，那么x^i代表的就是x的i次方。 "+"代表是word(字)的加法运算。X <<< s表示一个32-bit的数值X向左循环移动s位。not(X)表示对X按bit(位)求反，X v Y表示X与Y按bit(位)做或运算,X xor Y表示X与Y按bit(位)做异或运算，XY表示X与Y按bit(位)做且运算3、MD5算法描述 我们假设有一个b-bit类型的数据，我们希望找到它的信息搞要。在这里b是任意一个无符号整数；b可能为0，不一定是8的倍数，也可能它的数值十分的大。我们设想这个bits(位)型的数据按下面的格式书写：m_0 m_1 ... m_{b-1} (newlaos：还是记得吗,m_0代表的是第1位(bit)的数据，m下标0，类似数组中的第一个单元)接下来的5步就是计算这个数据的信息搞要。 3.1 第1步 按位补充数据(补位) 这个数据按(bit)位补充，要求最终的(bit)位数对512求模的结果为448(newlaos：数据的bit位数 mod 512=448)。也就是说数据补位后，其位数长度只差64(bit)位就是512的整数倍(newlaos：数据的bit位数 + 64 = n*512)。补位的过程必须做，即便是这个数据的位数对512求模的结果正好是448。 补位的实现过程：首先在数据后补一个1(bit),接着在后面补上一堆0(bit)，直到整个数据的位数对512求模的结果正好为448。总之，至少补1位，而最多可能补512位。 3.2 第2步 扩展长度 在完成前1步的补位工作后，又将一个表示数据b原始长度的64-bit数(newlaos:这是对b没有补位前长度的描述，2进制来表示)补在最后。很极少情况下,数据b的长度会大于2^64，所以只用一个64-bit(低位在前顺序)数据来表示数据b长度就可以了。(这些bit值是作为两个32-bit字补充的) 当完成补位及补充数据b的描述后（有些书将这两步合称为：数据填充），得到的结果数据长度正好是512的整数倍。也就是说长度正好是16个(32-bit)字的整数倍(newlaos:也就是64个字节的数据长度)。M[0 ... N-1]代表结果数据中的数组单元，N是16的倍数。 3.3 第3步 初始化 MD Buffer(缓冲) 一个四字(four-word)缓冲(A，B，C，D)被用来计算信息摘要。这里A，B，C，D分别代表一个32-bit寄存器。这些寄存器值初始化为下列的数值：(16进制、低位在前)word A: 01 23 45 67word B: 89 ab cd efword C: fe dc ba 98word D: 76 54 32 10 3.4 第4步 以16*32bit(word)信息块方式处理信息 首先，我们定义四个辅助的函数，每一个函数以三个32-bit数值作为参数，处理输出为一个32-bit数值。F(X,Y,Z) = XY v not(X)Z G(X,Y,Z) = XZ v Y not(Z)H(X,Y,Z) = X xor Y xorZI(X,Y,Z) = Y xor (X v not(Z))*************************newlaos: 用VB表示：F(X,Y,Z) = (X and Y) or ((not X) and Z) G(X,Y,Z) = (X and Z) or (Y and (not Z))H(X,Y,Z) = X xor Y xor ZI(X,Y,Z) = Y xor (X and (not Z)newlaos: 用VC表示：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)))************************* F函数是逐位(bit)函数，即：如果X成立，结果就是Y，否则就是Z。如果 XY 和 not(X)Z 运算在同一bit位上永远都不同为1的话，那么F函数就能被定义为 + ，而不是 v 。这是十分有趣的，即如果X，Y，Z数值的所有bit位独立且平均分布的话(newlaos:1和0在数值各二进制位上分布比较平均),那F(X，Y，Z)函数结果在bit位上的1，0分布也将是独立且平均的。 G，H，I 函数与F函数比较类似，都是根据X，Y，Z的值进行处理，并实现其函数结果在bit位的独立且平均的作用。注意：H函数是bit位的"XOR"或"parity(奇偶)"函数 这一步将用到一个有64个元素的表T[1 ... 64](newlaos:也就是一维数组了)，而这个表又是由正弦函数构造出来的。T[i]表示表内的第i个元素，它的值等于函数abs(sin(i))的4294967296次方，再取整后的值。newlaos:// T[i]=int(abs(sin(i))^4294967296) // 。这里i就代表弧度。数组元素(表元素)将在附录中给出。。(newlaos:4294967296等于2^32) 照着下面去做：/* 处理每一个16*32bit的信息块(512bit) */For i = 0 to N/16-1 do/* 将信息块 i 拷贝入 X */For j = 0 to 15 doSet X[j] to M[i*16+j]. (newlaos: 每一次，把数据原文存放在16个元素的数组X中。等效于 X[j]=M[i*16+j])end /* 循环 *//* 将A存为AA，B存为BB，C存为CC，将D存为DD */AA = ABB = BCC = CDD = D/* 循环 1 *//* [abcd k s i] 代表操作a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). *//* 做接下来的16步操作 */[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4][ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8][ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12][ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]/* 循环 2 *//* [abcd k s i] 代表操作a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). *//* 做接下来的16步操作 */[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20][ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24][ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28][ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]/* 循环 3. *//* [abcd k s t] 代表操作a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). *//* 做接下来的16步操作 */[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36][ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40][ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44][ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]/* 循环 4. *//* [abcd k s t] 代表操作a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). *//* 做接下来的16步操作 */[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52][ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56][ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60][ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]/* 接下就是做下面的加法. (每个寄存器加上初始化时的值） */A = A + AAB = B + BBC = C + CCD = D + DDend /* 大循环结束 */ 3.5 第5步 输出 作息摘要最终处理成以A，B，C，D的形式输出。也就是开始于A的低位在前的顺序字节，结束于D的高位在前的顺序字节。到这里对MD5的算法描述就完了。对于C的执行参考将在附录中给出。4、概要 MD5 信息-摘要算法简便易行，并且能够给出任意长度信息的“指纹”或信息摘要。据猜测MD5的难度就在于每两个信息有同样信息摘要的可能性是2^64分之一，而任意一个给定的信息其得出的信息摘要将是2^128分之一。M5算法针对其弱点是经过十分细致设计的，当然如果相对新一些的算法与进一步的安全性分析，将能对这个排列顺序进行更好的调整。5、MD4 与 MD5 的不同下面列出了 MD4 与 MD5之间的区别：1、增加了第四次循环2、每一步采有唯一不同的加法常数3、在第2次循环中，G函数由(XY v XZ v YZ)改为(XZ v Y not(Z))，以使G函数的平衡性更低4、每一步增加了前一步的计算结果，这导致更快的雪崩效应。5、改变了第二轮和第三轮中访问消息子分组的次序，使得这个模型彼此更不相似。6、在每次循环中的位移量被近似优化，导致更快的雪崩效应。在不同循环中的位移量截然不同。参考：[1] Rivest, R., "MD4 信息摘要算法", RFC 1320, MIT andRSA Data Security, Inc., 1992年四月.[2] Rivest, R., "MD4 信息摘要算法", in A.J. Menezesand S.A. Vanstone, editors, Advances in Cryptology - CRYPTO ‘90Proceedings, pages 303-311, Springer-Verlag, 1991.[3] CCITT Recommendation X.509 (1988), "The Directory -Authentication Framework." |
|
|