MD5算法描述
作者：rufi 2004.06.22
当我要写一个MD5算法的程序时，发现中英文的语言描述都有一些不确切的地方，某些个细节
讲得不清楚，或者说很费解。最后不得不拿出C语言的源程序来调试，这对于理解算法是很不
利的。于是就总结了一下我摸索到的一些要点。
1.来历
MD5的全称是message-digest algorithm 5(信息-摘要算法，在90年代初由mit laboratory
for computer science和rsa data security inc的ronald l. rivest开发出来，
经md2、md3和md4发展而来。 http://www.ietf.org/rfc/rfc1321.txt ，是一份最权威的文档，
由ronald l. rivest在1992年8月向ieft提交。
2.用途
MD5的作用是对一段信息(message)生成信息摘要(message-digest)，该摘要对该信息具有
唯一性,可以作为数字签名。用于验证文件的有效性(是否有丢失或损坏的数据),对用户
密码的加密，在哈希函数中计算散列值。
3.特点
输入一个任意长度的字节串，生成一个128位的整数。由于算法的某些不可逆特征，在加密应用
上有较好的安全性。并且，MD5算法的使用不需要支付任何版权费用。
4.说明
唯一性和不可逆性都不是绝对的，从理论上分析是一种多对一的关系，但两个不同的信息产生
相同摘要的概率很小。不可逆是指从输出反推输入所需的运算量和计算时间太大，使用穷搜字
典的方法又需要太多的存储空间。
5.算法描述
算法输入是一个字节串，每个字节是8个bit.
算法的执行分为以下几个步骤：
第一步，补位：
MD5算法先对输入的数据进行补位，使得数据的长度(以byte为单位)对64求余的结果是56。
即数据扩展至LEN=K*64+56个字节，K为整数。
补位方法：补一个1，然后补0至满足上述要求。相当于补一个0x80的字节，再补值
为0的字节。这一步里总共补充的字节数为0～63个。
第二步，附加数据长度：
用一个64位的整数表示数据的原始长度(以bit为单位)，将这个数字的8个字节按低位的在前，
高位在后的顺序附加在补位后的数据后面。这时，数据被填补后的总长度为：
LEN = K*64+56+8=(K+1)*64 Bytes。
※注意那个64位整数是输入数据的原始长度而不是填充字节后的长度,我就在这里栽了跟头.
第三步，初始化MD5参数：
有四个32位整数变量 (A,B,C,D) 用来计算信息摘要，每一个变量被初始化成以下
以十六进制数表示的数值，低位的字节在前面。
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
※注意低位的字节在前面指的是Little Endian平台上内存中字节的排列方式，
而在程序中书写时，要写成：
A=0x67452301
B=0xefcdab89
C=0x98badcfe
D=0x10325476
第四步，定义四个MD5基本的按位操作函数：
X，Y，Z为32位整数。
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 Z
I(X,Y,Z) = Y xor (X or not(Z))
再定义四个分别用于四轮变换的函数。
设Mj表示消息的第j个子分组（从0到15），<<
1<s表示循环左移s位，则四种操作为： ("")="d41d8cd98f00b204e9800998ecf8427e" ("123456789012345678901234567890123456789012345678901234567890123456789="" ("a")="0cc175b9c0f1b6a831c399e269772661" ("abc")="900150983cd24fb0d6963f7d28e17f72" ("abcdefghijklmnopqrstuvwxyz")="c3fcd3d76192e4007dfb496cca67e13b" ("abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz0123456789")="d174ab98d277d9f5a5611c2c9f419d9f" ("message="" ((a="" (x&y)|((~x)&z);="" (x&z)|(y&(~z));="" *="" *每循环一次，把数据原文存放在16个元素的数组x中.="" +="" ...="" ...15]表示。而数组t[1="" 0="" 01234567890")="57edf4a22be3c955ac49da2e2107b67a" 1="" 1,="" 10="" 10]="" 11="" 11]="" 12="" 12]="" 13="" 13]="" 14="" 14]="" 15="" 15]="" 16="" 16-1="" 16]="" 17="" 17]="" 18]="" 19]="" 1]="" 2="" 2,="" 20="" 2004.6.20="" 20]="" 21="" 21]="" 22="" 22]="" 23="" 23]="" 24]="" 25]="" 26]="" 27]="" 28]="" 29]="" 2]="" 3="" 3,="" 30]="" 31]="" 32]="" 33]="" 34]="" 35]="" 36]="" 37]="" 38]="" 39]="" 3]="" 4="" 4.="" 40]="" 41]="" 42]="" 43]="" 44]="" 45]="" 46]="" 47]="" 48]="" 49]="" 4]="" 5="" 50]="" 51]="" 52]="" 53]="" 54]="" 55]="" 56]="" 57]="" 58]="" 59]="" 5]="" 6="" 60]="" 61]="" 62]="" 63]="" 64]="" 64]表示一组常数，="" 6]="" 7="" 7]="" 8="" 8]="" 9="" 9]="" <<="" <<<="" [abcd="" [bcda="" [cdab="" [code]="" [dabc="" a="" a,uint32="" a;="" aa="" aa,="" addition="" alogrithm="" and="" are="" as="" a，b，c，d连续存放，共16个字节，128位。按十六进制依次输出这个16个字节。="" b="B" b,uint32="" b;="" basic="" bb="" bb,="" bits="" by="" c="C" c,uint32="" c;="" cc="" cc,="" class="" const="" d="D" d,uint32="" d;="" dd="" dd.="" digest")="f96b697d7cb7938d525a2f31aaf161d0" do="" end="" f(b,c,d)="" f(uint32="" f(x,y,z)="(X&Y)|((~X)&Z)" f,="" ff(a,b,c,d,mj,s,ti)表示a="b+((a+(F(b,c,d)+Mj+ti)<<<s)" ff(ref="" ff,="" following="" for="" from="" functions.="" g(b,c,d)="" g(uint32="" g(x,y,z)="(X&Z)|(Y&(~Z))" g,="" gg(a,b,c,d,mj,s,ti)表示a="b+((a+(G(b,c,d)+Mj+ti)<<<s)" gg,="" h="" h(b,c,d)="" h(uint32="" h(x,y,z)="X^Y^Z" hh(a,b,c,d,mj,s,ti)表示a="b+((a+(H(b,c,d)+Mj+ti)<<<s)" hh,="" http:="" i="" i(b,c,d)="" i(uint32="" i(x,y,z)="Y^(X|(~Z))" i]表示如下操作="" ii="" ii(a,b,c,d,mj,s,ti)表示a="b+((a+(I(b,c,d)+Mj+ti)<<<s)" in="" int="" is="" j="0" k="" m[i*16+j].="" md5="" md5算法之c#程序="" md5算法比较特别，最适合用汇编语言来写，好多高级语言对之无能无力或效率极低。="" mj="" mj,int="" n="" next="" number="" of="" operations.="" prevent="" private="" public="" recomputation.="" return="" rotate="" rotation="" rounds="" rufi="" rufi.yculblog.com="" s="" s).="" s,uint32="" s11="7;" s12="12;" s13="17;" s14="22;" s21="5;" s22="9;" s23="14;" s24="20;" s31="4;" s32="11;" s33="16;" s34="23;" s41="6;" s42="10;" s43="15;" s44="21;" save="" separate="" set="" state="" static="" system.collections;="" system.io;="" system;="" t[i])="" t[i]为4294967296*abs(sin(i))的32位整数部分，i的单位是弧度,i的取值从1到64。="" the="" ti){="" ti;="" to="" tranforming="" transformations="" uint32="" using="" variables="" void="" x,uint32="" x[j]="" x[k]="" x^y^z;="" y,uint32="" y^(x|(~z));="" z){="" {="" |="" }="" 中新兴的一门.net语言，功能比较全面。花了一晚上的工夫终于用c#最先实现了md5。="" 主要是由于对算法的一些细节不太注意，结果输出总是不对，调试了好长时间。="" 以="" 具体过程如下：="" 四个非线性函数:="" 处理数据，n是总的字节数，以64个字节为一组，每组作一次循环，每次循环进行四轮操作。="" 最后，用程序语言实现算法后，可以输入以下几个信息对程序作一个简单的测试，="" 比如我最开始尝试用python和euphoria编写，发现不太容易。相比而言，c#作为c家簇="" 源文件：md5.cs="" 然后进行如下操作="" 看看程序有没有错误。="" 第1轮*="" 第2轮*="" 第3轮*="" 第4轮*="" 第五步，对输入数据作变换。="" 第六步，输出结果。="" 结束对i的循环*="" 结束对j的循环="" 要变换的64个字节用16个32位的整数数组m[0="" 设置主循环变量="" （&与，|或，~非，^异或）="">> (32-s);
2a += b;
3}
4private static void GG(ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj,int s,UInt32 ti){
5a = a + G(b,c,d) + mj + ti;
6a = a << s | a >> (32-s);
7a += b;
8}
9private static void HH(ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj,int s,UInt32 ti){
10a = a + H(b,c,d) + mj + ti;
11a = a << s | a >> (32-s);
12a += b;
13}
14private static void II(ref UInt32 a,UInt32 b,UInt32 c,UInt32 d,UInt32 mj,int s,UInt32 ti){
15a = a + I(b,c,d) + mj + ti;
16a = a << s | a >> (32-s);
17a += b;
18}
19
20private static void MD5_Init(){
21A=0x67452301; //in memory, this is 0x01234567
22B=0xefcdab89; //in memory, this is 0x89abcdef
23C=0x98badcfe; //in memory, this is 0xfedcba98
24D=0x10325476; //in memory, this is 0x76543210
25}
26
27private static UInt32[] MD5_Append(byte[] input){
28int zeros=0;
29int ones =1;
30int size=0;
31int n = input.Length;
32int m = n%64;
33if( m < 56 ){
34zeros = 55-m;
35size=n-m+64;
36}
37else if (m==56){
38zeros = 0;
39ones = 0;
40size=n+8;
41}
42else{
43zeros = 63-m+56;
44size=n+64-m+64;
45}
46
47ArrayList bs = new ArrayList(input);
48if(ones==1){
49bs.Add( (byte)0x80 ); // 0x80 = $10000000
50}
51for(int i=0;i<zeros;i++){ (byte)0="" );="" *="" 8;="" bs.add(="" byte="" h1="(byte)(N&0xFF);" h2="(byte)((N" n="" uint64="" }="">>8)&0xFF);
52byte h3=(byte)((N>>16)&0xFF);
53byte h4=(byte)((N>>24)&0xFF);
54byte h5=(byte)((N>>32)&0xFF);
55byte h6=(byte)((N>>40)&0xFF);
56byte h7=(byte)((N>>48)&0xFF);
57byte h8=(byte)(N>>56);
58bs.Add(h1);
59bs.Add(h2);
60bs.Add(h3);
61bs.Add(h4);
62bs.Add(h5);
63bs.Add(h6);
64bs.Add(h7);
65bs.Add(h8);
66byte[] ts=(byte[])bs.ToArray(typeof(byte));
67
68/* Decodes input (byte[]) into output (UInt32[]). Assumes len is
69* a multiple of 4.
70*/
71UInt32[] output = new UInt32[size/4];
72for(Int64 i=0,j=0;i<size;j++,i+=4){ &="" (byte[]).="" (ref="" (uint32[])="" *="" 0],="" 0x1fa27cf8);="" 0x21e1cde6);="" 0x242070db);="" 0x2441453);="" 0x265e5a51);="" 0x289b7ec6);="" 0x2ad7d2bb);="" 0x432aff97);="" 0x455a14ed);="" 0x4787c62a);="" 0x4881d05);="" 0x49b40821);="" 0x4bdecfa9);="" 0x4e0811a1);="" 0x655b59c3);="" 0x676f02d9);="" 0x698098d8);="" 0x6b901122);="" 0x6d9d6122);="" 0x6fa87e4f);="" 0x85845dd1);="" 0x8771f681);="" 0x895cd7be);="" 0x8b44f7af);="" 0x8d2a4c8a);="" 0x8f0ccc92);="" 0xa3014314);="" 0xa4beea44);="" 0xa679438e);="" 0xa8304613);="" 0xa9e3e905);="" 0xab9423a7);="" 0xbd3af235);="" 0xbebfbc70);="" 0xc040b340);="" 0xc1bdceee);="" 0xc33707d6);="" 0xc4ac5665);="" 0xd4ef3085);="" 0xd62f105d);="" 0xd76aa478);="" 0xd8a1e681);="" 0xd9d4d039);="" 0xe6db99e5);="" 0xe7d3fbc8);="" 0xe8c7b756);="" 0xe9b6c7aa);="" 0xeaa127fa);="" 0xeb86d391);="" 0xf4292244);="" 0xf4d50d87);="" 0xf57c0faf);="" 0xf61e2562);="" 0xf6bb4b60);="" 0xf7537e82);="" 0xfc93a039);="" 0xfcefa3f8);="" 0xfd469501);="" 0xfd987193);="" 0xfde5380c);="" 0xfe2ce6e0);="" 0xff);="" 0xffeff47d);="" 0xfffa3942);="" 0xffff5bb1);="" 1="" 10="" 11="" 12="" 13="" 14="" 15="" 16="" 17="" 18="" 19="" 1],="" 2="" 20="" 21="" 22="" 23="" 24="" 25="" 26="" 27="" 28="" 29="" 2],="" 3="" 30="" 31="" 32="" 33="" 34="" 35="" 36="" 37="" 38="" 39="" 3],="" 4="" 4.="" 40="" 41="" 42="" 43="" 44="" 45="" 46="" 47="" 48="" 49="" 4],="" 5="" 50="" 51="" 52="" 53="" 54="" 55="" 56="" 57="" 58="" 59="" 5],="" 6="" 60="" 61="" 62="" 63="" 64="" 6],="" 7="" 7],="" 8="" 8],="" 9="" 9],="" a="" a+="a;" a,="" a,b,c,d;="" assumes="" b="B;" b+="b;" b,="" bits="" block="MD5_Append(input);" byte[]="" byte[bits.length*4];="" c="C;" c+="c;" c,="" d="D;" d+="d;" d,="" encodes="" ff="" for(int="" gg="" hh="" i="0,j=0;i<bits.Length;i++,j+=4){" ii="" input){="" into="" is="" k="0;k<x.Length;k+=16){" len="" md5_init();="" md5_trasform(uint32[]="" md5array(byte[]="" multiple="" new="" of="" output="new" output;="" output[j+1]="(byte)((bits[i]" output[j]="(byte)(bits[i]" private="" public="" return="" round="" s11,="" s12,="" s13,="" s14,="" s21,="" s22,="" s23,="" s24,="" s31,="" s32,="" s33,="" s34,="" s41,="" s42,="" s43,="" s44,="" static="" ts[i+1]<<8="" ts[i+2]<<16="" ts[i+3]<<24);="" uint32="" uint32[]="" uint32[]{a,b,c,d};="" x){="" x[k+="" x[k+10],="" x[k+11],="" x[k+12],="" x[k+13],="" x[k+14],="" x[k+15],="" |="" }="">> 8) & 0xff);
73output[j+2] = (byte)((bits[i] >> 16) & 0xff);
74output[j+3] = (byte)((bits[i] >> 24) & 0xff);
75}
76return output;
77}
78
79public static string ArrayToHexString(byte[] array,bool uppercase){
80string hexString="";
81string format="x2";
82if(uppercase){
83format="X2";
84}
85foreach(byte b in array){
86hexString += b.ToString(format);
87}
88return hexString;
89}
90
91public static string MDString(string message){
92char[] c = message.ToCharArray();
93byte[] b = new byte[c.Length];
94for(int i=0;i<c.Length;i++){
95b[i]=(byte)c[i];
96}
97byte[] digest = MD5Array(b);
98return ArrayToHexString(digest,false);
99}
100public static string MDFile(string fileName){
101FileStream fs=File.Open(fileName,FileMode.Open,FileAccess.Read);
102byte[] array=new byte[fs.Length];
103fs.Read(array,0,(int)fs.Length);
104byte[] digest = MD5Array(array);
105fs.Close();
106return ArrayToHexString(digest,false);
107}
108
109public static string Test(string message){
110return "rnMD5 (""+message+"") = " + MD5.MDString(message);
111}
112public static string TestSuite(){
113string s = "";
114s+=Test("");
115s+=Test("a");
116s+=Test("abc");
117s+=Test("message digest");
118s+=Test("abcdefghijklmnopqrstuvwxyz");
119s+=Test("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
120s+=Test("12345678901234567890123456789012345678901234567890123456789012345678901234567890");
121return s;
122}
123}
124[/code]</size;j++,i+=4){></zeros;i++){></s表示循环左移s位，则四种操作为：>