📄 md5信息-摘要加算法(翻译).html
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>MD5 信息摘要加密算法</title>
</head>
<body bgcolor="#000000" text="#FFFFFF">
<script language="vbscript"></script>
<p align="center"><br>
<br>
<b><font color="#FF0000"><font size="5"> MD5 信息-摘要算法 </font></font></b></p>
<p align="center"><font size="2" color="#00FF00">翻译：newlaos[DFCG][CCG]</font></p>
<p align="left" style="line-height: 150%"><br>
<br>
<font size="2">备忘录说明：<br>
这篇备忘录讲述的是因特网通讯方面的内容，并不是定义一个因特网标准，因此传播此文件，将不受任何限制。<br>
<br>
内容列表：<br>
<a href="#1、总述">1、总述<br></a>
<a href="#2、术语及符号">2、术语及符号</a><br>
<a href="#3、MD5算法描述">3、MD5算法描述</a><br>
<a href="#4、概要">4、概要</a><br>
<a href="#5、MD4 与 MD5 的不同">5、MD4与MD5的不同</a><br>
<a href="#参考：">参考</a><br>
<a href="#附录A - 执行参考">附录 A - 执行参考</a>(文件源代码)<br>
<a href="#安全考虑">MD5安全考虑及常用攻击方式</a>(<font color="#00FF00">newlaos</font><font color="#FFFFFF">收集补充)</font><font color="#0000FF"><br>
<a href="#作者通讯地址">作者地址</a></font><font color="#00FF00"><br>
</font>
<br>
<b><font color="#FFFF00" size="4"><a name="1、总述">1、总述</a></font></b><br>
<br>
这个篇文章将详细描述 MD5 信息-摘要算法。这种算法可以将任意长度的信息处理成一个128bit(定长)的“指纹”或“信息摘要”。任意两个不同信息不可能处理成同样的信息摘要，同时根据得到的信息摘要也不可能逆推出原始信息。MD5算法主要用于数字签名，出于安全的考虑，任何信息(明文)在用公钥加密系统(例如RSA)加密传送前，都要用MD5算法处理出一个信息摘要。(<font color="#00FF00">newlaos</font>:一个需要传输的明文，先用MD5算法得到一个信息摘要，再用RSA的传送方私钥和接收方公钥对明文进行加密。然后传送方将密文、RSA的传送方公钥及信息摘要传输给接收方。接收方用RSA的接收方私钥和传送方公钥将密文还原成明文，再通过MD5算法得出解密后明文的信息摘要，用它来和传送方发过来的信息摘要对比，如果相同，就说明密文在传送过程中没有被人篡改。)<br>
<br>
MD5 算法是为32位计算机设计的，它在32位计算机上处理起来非常快，并且MD5算法不需要任何大的替代表，在编程实现方面也十分简洁易行。<br>
<br>
MD5 算法是MD4算法的扩展，仅比MD4稍慢一点，但在设计上更为谨慎。MD4虽然快，但是存在一种漏洞，它导致对不同的内容进行加密却可能得到相同的加密后结果，因而促就了MD5的产生。MD5为了获得更好安全性，在运算速度上做了小小的让步。MD5算法作为一个标准，被至于大众领域以吸取各种好的建议，并进行适当的优化和改善。<br>
<br>
<b><font size="4" color="#FFFF00"><a name="2、术语及符号">2、术语及符号</a></font></b><br>
<br>
在这篇文章里，“word(字)”为32-bit的数值，“byte(字节)”为8-bit的数值。一个bit数据流通常解释为byte数据流，每8-bit数据被解释为1-byte，且按高位在前的顺序排列。同理，一个byte数据流通常解释为word(字)数据流，每4-byte被解释为1-word，按的是低位在前的顺序排列。<br>
<br>
x_i表示"x sub i"，如果写在下方的(下标)是一个表达式，我就用括号将它括起来x_{i+1}。同理，我们用 ^ 代表上标(求幂)，那么x^i代表的就是x的i次方。<br>
<br>
"+"代表是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(位)做且运算<br>
<br>
<font color="#FFFF00" size="4"><b><a name="3、MD5算法描述">3、MD5算法描述</a></b></font><br>
<br>
我们假设有一个b-bit类型的数据，我们希望找到它的信息搞要。在这里b是任意一个无符号整数；b可能为0，不一定是8的倍数，也可能它的数值十分的大。我们设想这个bits(位)型的数据按下面的格式书写：<br>
m_0 m_1 ... m_{b-1} (<font color="#00FF00">newlaos</font>：还是记得吗,m_0代表的是第1位(bit)的数据，m下标0，类似数组中的第一个单元)<br>
<br>
接下来的5步就是计算这个数据的信息搞要。<br>
<br>
<a name="3.1 第1步 按位补充数据(补位)"><font color="#FF0000">3.1 第1步 按位补充数据(补位)</font></a><br>
<br>
这个数据按(bit)位补充，要求最终的(bit)位数对512求模的结果为448(<font color="#00FF00">newlaos</font>：数据的bit位数 mod 512=448)。也就是说数据补位后，其位数长度只差64(bit)位就是512的整数倍(<font color="#00FF00">newlaos</font>：数据的bit位数 + 64 = n*512)。补位的过程必须做，即便是这个数据的位数对512求模的结果正好是448。<br>
<br>
补位的实现过程：首先在数据后补一个1(bit),接着在后面补上一堆0(bit)，直到整个数据的位数对512求模的结果正好为448。总之，至少补1位，而最多可能补512位。<br>
<br>
<a name="3.2 第2步 扩展长度"><font color="#FF0000">3.2 第2步 扩展长度</font></a><br>
<br>
在完成前1步的补位工作后，又将一个表示数据b原始长度的64-bit数(<font color="#00FF00">newlaos</font>:这是对b没有补位前长度的描述，2进制来表示)补在最后。很极少情况下,数据b的长度会大于2^64，所以只用一个64-bit(低位在前顺序)数据来表示数据b长度就可以了。(这些bit值是作为两个32-bit字补充的)<br>
<br>
当完成补位及补充数据b的描述后（有些书将这两步合称为：数据填充），得到的结果数据长度正好是512的整数倍。也就是说长度正好是16个(32-bit)字的整数倍(<font color="#00FF00">newlaos</font>:也就是64个字节的数据长度)。M[0 ... N-1]代表结果数据中的数组单元，N是16的倍数。<br>
<br>
<font color="#FF0000"><a name="3.3 第3步 初始化 MD Buffer(缓冲)">3.3 第3步 初始化 MD Buffer(缓冲)</a></font><br>
<br>
一个四字(four-word)缓冲(A，B，C，D)被用来计算信息摘要。这里A，B，C，D分别代表一个32-bit寄存器。这些寄存器值初始化为下列的数值：(16进制、低位在前)<br>
<br>
word A: 01 23 45 67<br>
word B: 89 ab cd ef<br>
word C: fe dc ba 98<br>
word D: 76 54 32 10<br>
<br>
<a name="3.4 第4步 以16*32bit(word)信息块方式处理信息"><font color="#FF0000">3.4 第4步 以16*32bit(word)信息块方式处理信息</font></a><br>
首先，我们定义四个辅助的函数，每一个函数以三个32-bit数值作为参数，处理输出为一个32-bit数值。<br>
F(X,Y,Z) = XY v not(X)Z <br>
G(X,Y,Z) = XZ v Y not(Z)<br>
H(X,Y,Z) = X xor Y xorZ<br>
I(X,Y,Z) = Y xor (X v not(Z))<br>
*************************<br>
<font color="#00FF00">newlaos</font>: 用VB表示：<br>
F(X,Y,Z) = (X and Y) or ((not X) and Z) <br>
G(X,Y,Z) = (X and Z) or (Y and (not Z))<br>
H(X,Y,Z) = X xor Y xor Z<br>
I(X,Y,Z) = Y xor (X and (not Z)</font>
</p>
<p align="left" style="line-height: 150%"><font size="2"><font color="#00FF00">newlaos</font>:
用VC表示：<br>
F(x, y, z) = (((x) & (y)) | ((~x) & (z)))<br>
G(x, y, z) = (((x) & (z)) | ((y) & (~z)))<br>
H(x, y, z) = ((x) ^ (y) ^ (z))<br>
I(x, y, z) = ((y) ^ ((x) | (~z)))<br>
*************************</font>
</p>
<p align="left" style="line-height: 150%"><font size="2"> F函数是逐位(bit)函数，即：如果X成立，结果就是Y，否则就是Z。如果 XY 和 not(X)Z 运算在同一bit位上永远都不同为1的话，那么F函数就能被定义为 + ，而不是 v 。这是十分有趣的，即如果X，Y，Z数值的所有bit位独立且平均分布的话(<font color="#00FF00">newlaos</font>:1和0在数值各二进制位上分布比较平均),那F(X，Y，Z)函数结果在bit位上的1，0分布也将是独立且平均的。<br>
<br>
G，H，I 函数与F函数比较类似，都是根据X，Y，Z的值进行处理，并实现其函数结果在bit位的独立且平均的作用。注意：H函数是bit位的"XOR"或"parity(奇偶)"函数<br>
<br>
这一步将用到一个有64个元素的表T[1 ... 64](<font color="#00FF00">newlaos</font>:也就是一维数组了)，而这个表又是由正弦函数构造出来的。T[i]表示表内的第i个元素，它的值等于函数abs(sin(i))的4294967296次方，再取整后的值。<font color="#00FF00">newlaos://</font> T[i]=int(abs(sin(i))^4294967296)
<font color="#00FF00"> //</font> 。这里i就代表弧度。数组元素(表元素)将在附录中给出。。(<font color="#00FF00">newlaos</font>:4294967296等于2^32)<br>
<br>
<br>
照着下面去做：<br>
<br>
/* 处理每一个16*32bit的信息块(512bit) */<br>
For i = 0 to N/16-1 do<br>
<br>
/* 将信息块 i 拷贝入 X */<br>
For j = 0 to 15 do<br>
Set X[j] to M[i*16+j]. (<font color="#00FF00">newlaos</font>: 每一次，把数据原文存放在16个元素的数组X中。等效于 X[j]=M[i*16+j])<br>
end /* 循环 */<br>
<br>
/* 将A存为AA，B存为BB，C存为CC，将D存为DD */<br>
AA = A<br>
BB = B<br>
CC = C<br>
DD = D<br>
<br>
/* 循环 1 */<br>
/* [abcd k s i] 代表操作<br>
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */<br>
/* 做接下来的16步操作 */<br>
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]<br>
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]<br>
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]<br>
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]<br>
<br>
/* 循环 2 */<br>
/* [abcd k s i] 代表操作<br>
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */<br>
/* 做接下来的16步操作 */<br>
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]<br>
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]<br>
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]<br>
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]<br>
<br>
/* 循环 3. */<br>
/* [abcd k s t] 代表操作<br>
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */<br>
/* 做接下来的16步操作 */<br>
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]<br>
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]<br>
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]<br>
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]<br>
<br>
/* 循环 4. */<br>
/* [abcd k s t] 代表操作<br>
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */<br>
/* 做接下来的16步操作 */<br>
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]<br>
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]<br>
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]<br>
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]<br>
<br>
/* 接下就是做下面的加法. (每个寄存器加上初始化时的值） */<br>
A = A + AA<br>
B = B + BB<br>
C = C + CC<br>
D = D + DD<br>
<br>
end /* 大循环结束 */<br>
<br>
<font color="#FF0000"><a name="3.5 第5步 输出">3.5 第5步 输出</a></font><br>
作息摘要最终处理成以A，B，C，D的形式输出。也就是开始于A的低位在前的顺序字节，结束于D的高位在前的顺序字节。<br>
到这里对MD5的算法描述就完了。对于C的执行参考将在附录中给出。<br>
<br>
<font color="#FFFF00" size="4"><b><a name="4、概要">4、概要</a></b></font><br>
<br>
MD5 信息-摘要 算法简便易行，并且能够给出任意长度信息的“指纹”或信息摘要。据猜测MD5的难度就在于每两个信息有同样信息摘要的可能性是2^64分之一，而任意一个给定的信息其得出的信息摘要将是2^128分之一。M5算法针对其弱点是经过十分细致设计的，当然如果相对新一些的算法与进一步的安全性分析，将能对这个排列顺序进行更好的调整。<br>
<br>
<font color="#FFFF00" size="4"><b><a name="5、MD4 与 MD5 的不同">5、MD4 与 MD5 的不同</a></b></font><br>
<br>
下面列出了 MD4 与 MD5之间的区别：<br>
1、增加了第四次循环<br>
2、每一步采有唯一不同的加法常数<br>
3、在第2次循环中，G函数由(XY v XZ v YZ)改为(XZ v Y not(Z))，以使G函数的平衡性更低<br>
4、每一步增加了前一步的计算结果，这导致更快的雪崩效应。<br>
5、改变了第二轮和第三轮中访问消息子分组的次序，使得这个模型彼此更不相似。<br>
6、在每次循环中的位移量被近似优化，导致更快的雪崩效应。在不同循环中的位移量截然不同。<br>
<br>
<a name="参考："><font color="#FFFF00" size="4"><b>参考：</b></font></a><br>
<br>
[1] Rivest, R., "MD4 信息摘要算法", RFC 1320, MIT and<br>
RSA Data Security, Inc., 1992年四月.<br>
<br>
[2] Rivest, R., "MD4 信息摘要算法", in A.J. Menezes<br>
and S.A. Vanstone, editors, Advances in Cryptology - CRYPTO '90<br>
Proceedings, pages 303-311, Springer-Verlag, 1991.<br>
<br>
[3] CCITT Recommendation X.509 (1988), "The Directory -<br>
Authentication Framework."<br>
<br>
<b>
<font color="#FFFF00" size="4"><a name="附录A - 执行参考">附录A - 执行参考</a></font></b></font><b><font color="#FFFF00" size="4">(文件源代码)</font></b><font size="2"><br>
<br>
附录中包括取自RSAREF的文件：一个保护私人邮件的加密工具<br>
<br>
<font color="#FF00FF"> <a href="md5(C)/Global.h"> global.h</a></font> -- 通用头文件<br>
<br>
<font color="#FF00FF"> <a href="md5(C)/Md5.h"> md5.h</a></font> -- MD5头文件<br>
<br>
<font color="#FF00FF"> <a href="md5(C)/Md5c.c"> md5c.c</a></font> -- MD5源代码<br>
<br>
如果想得到更详细的信息，可以发电子邮件到 rsaref@rsa.com<br>
<br>
附录中还包括：<br>
<font color="#FF00FF"> <a href="md5(C)/Mddriver.c"> mddriver.c</a></font> -- MD2, MD4 及 MD5 的测试驱动引擎<br>
此引擎默认是为测试MD5编译使用的，但也可以将MD标志中对C函数编译命令行修改成2或4，来支持对MD2或MD4的测试编译。<br>
<br>
这种执行具有可移植性，能够在很多不同的平台上实现。当然根据特定平台，对这个执行进行优化设计也不难，这个工作可以留给读者来完成。例如：在"little-endian"平台上，在一个32-bit的字中位于最内存地址最前的字节，其意义性最小，也没有严格的约束，因此对MD5传输解码的调用完全可以用一个典型的模型来取代。(<font color="#00FF00">newlaos</font>:不明白)<br>
<br>
<a name="A.1 global.h"><font color="#FF0000">A.1 global.h</font></a><br>
<br>
/* GLOBAL.H - RSAREF 类型及常数<br>
*/<br>
<br>
/* PROTOTYPES should be set to one if and only if the compiler supports<br>
function argument prototyping.<br>
如果使PROTOTYPES没有被C语言编译器定义的话，就默认为0<br>
*/<br>
#ifndef PROTOTYPES<br>
#define PROTOTYPES 0<br>
#endif<br>
<br>
/* POINTER 用来定义通用的指针类型 */<br>
typedef unsigned char *POINTER;<br>
<br>
/* UINT2 定义一个双字节的字 */<br>
typedef unsigned short int UINT2;<br>
<br>
/* UINT4 定义一个四字节的字 */<br>
typedef unsigned long int UINT4;<br>
<br>
/* PROTO_LIST 的定义依据上面对PROTOTYPE的定义.<br>
如果用 PROTOTYPES, 那么 PROTO_LIST 返回就列表，否则返回一个空列表<br>
*/<br>
#if PROTOTYPES<br>
#define PROTO_LIST(list) list<br>
#else<br>
#define PROTO_LIST(list) ()<br>
#endif<br>
<br>
<font color="#FF0000"><a name="A.2 md5.h">A.2 md5.h</a></font><br>
<br>
/* MD5.H - MD5C.C 的头文件<br>
*/<br>
<br>
/* Copyright (C) 1991-2, RSA 数据安全公司版权所有. 1991年<br>
<br>
MD5使用授权声明(略)<br>
/* MD5 context. */<br>
typedef struct {<br>
UINT4 state[4]; /* state (ABCD) */<br>
UINT4 count[2]; /* bit数, modulo 2^64 (lsb first) */<br>
unsigned char buffer[64]; /* 输入缓冲 */<br>
} MD5_CTX;<br>
<br>
void MD5Init PROTO_LIST ((MD5_CTX *));<br>
void MD5Update PROTO_LIST<br>
((MD5_CTX *, unsigned char *, unsigned int));<br>
void MD5Final PROTO_LIST ((unsigned char [16], MD5_CTX *));<br>
<br>
<a name="A.3 md5c.c MD5的源代码"><font color="#FF0000">A.3 md5c.c MD5的源代码</font></a><br>
#include "global.h"<br>
#include "md5.h"<br>
<br>
/* 定义MD5变换过程用到的常量<br>
*/<br>
#define S11 7<br>
#define S12 12<br>
#define S13 17<br>
#define S14 22<br>
#define S21 5<br>
#define S22 9<br>
#define S23 14<br>
#define S24 20<br>
#define S31 4<br>
#define S32 11<br>
#define S33 16<br>
#define S34 23<br>
#define S41 6<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -