当我要写一个MD算法的程序时，发现中英文的语言描述都有一些不确切的地方，某些个细节
讲得不清楚，或者说很费解。最后不得不拿出C语言的源程序来调试，这对于理解算法是很不
利的。于是就总结了一下我摸索到的一些要点。

.来历
MD的全称是message-digest algorithm (信息-摘要算法，在90年代初由mit laboratory
for computer science和rsa data security inc的ronald l. rivest开发出来，
经md、md和md发展而来。http://www.ietf.org/rfc/rfc.txt，是一份最权威的文档，
由ronald l. rivest在99年8月向ieft提交。

.用途
MD的作用是对一段信息(message)生成信息摘要(message-digest)，该摘要对该信息具有
唯一性,可以作为数字签名。用于验证文件的有效性(是否有丢失或损坏的数据),对用户
密码的加密，在哈希函数中计算散列值。

.特点
输入一个任意长度的字节串，生成一个8位的整数。由于算法的某些不可逆特征，在加密应用
上有较好的安全性。并且，MD算法的使用不需要支付任何版权费用。

.说明
唯一性和不可逆性都不是绝对的，从理论上分析是一种多对一的关系，但两个不同的信息产生
相同摘要的概率很小。不可逆是指从输出反推输入所需的运算量和计算时间太大，使用穷搜字
典的方法又需要太多的存储空间。

.算法描述

算法输入是一个字节串，每个字节是8个bit.
算法的执行分为以下几个步骤：

第一步，补位：
MD算法先对输入的数据进行补位，使得数据的长度(以byte为单位)对6求余的结果是6。
即数据扩展至LEN=K*6+6个字节，K为整数。
补位方法：补一个，然后补0至满足上述要求。相当于补一个0x80的字节，再补值
为0的字节。这一步里总共补充的字节数为0～6个。

第二步，附加数据长度：
用一个6位的整数表示数据的原始长度(以bit为单位)，将这个数字的8个字节按低位的在前，
高位在后的顺序附加在补位后的数据后面。这时，数据被填补后的总长度为：
LEN = K*6+6+8=(K+)*6 Bytes。

※注意那个6位整数是输入数据的原始长度而不是填充字节后的长度,我就在这里栽了跟头.

第三步，初始化MD参数：
有四个位整数变量 (A,B,C,D) 用来计算信息摘要，每一个变量被初始化成以下
以十六进制数表示的数值，低位的字节在前面。
word A: 0 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 0
※注意低位的字节在前面指的是Little Endian平台上内存中字节的排列方式，
而在程序中书写时，要写成：
A=0x670
B=0xefcdab89
C=0x98badcfe
D=0x076

第四步，定义四个MD基本的按位操作函数：
X，Y，Z为位整数。
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到），<<<s表示循环左移s位，则四种操作为：
FF(a,b,c,d,Mj,s,ti)表示a=b+((a+(F(b,c,d)+Mj+ti)<<<s)
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+(G(b,c,d)+Mj+ti)<<<s)
HH(a,b,c,d,Mj,s,ti)表示a=b+((a+(H(b,c,d)+Mj+ti)<<<s)
II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)<<<s)


第五步，对输入数据作变换。
处理数据，N是总的字节数，以6个字节为一组，每组作一次循环，每次循环进行四轮操作。
要变换的6个字节用6个位的整数数组M[0 ...]表示。而数组T[ ... 6]表示一组常数，
T[i]为996796*abs(sin(i))的位整数部分，i的单位是弧度,i的取值从到6。
具体过程如下：

/* 设置主循环变量 */
For i = 0 to N/6- do

/*每循环一次，把数据原文存放在6个元素的数组X中. */
For j = 0 to do
Set X[j] to M[i*6+j].
end /结束对J的循环

/* Save A as AA, B as BB, C as CC, and D as DD.
*/
AA = A
BB = B
CC = C
DD = D

/* 第轮*/
/* 以 [abcd k s i]表示如下操作
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 6 operations. */
[ABCD 0 7 ] [DABC ] [CDAB 7 ] [BCDA ]
[ABCD 7 ] [DABC 6] [CDAB 6 7 7] [BCDA 7 8]
[ABCD 8 7 9] [DABC 9 0] [CDAB 0 7 ] [BCDA ]
[ABCD 7 ] [DABC ] [CDAB 7 ] [BCDA 6]


/* 第轮* */
/* 以 [abcd k s i]表示如下操作
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 6 operations. */
[ABCD 7] [DABC 6 9 8] [CDAB 9] [BCDA 0 0 0]
[ABCD ] [DABC 0 9 ] [CDAB ] [BCDA 0 ]
[ABCD 9 ] [DABC 9 6] [CDAB 7] [BCDA 8 0 8]
[ABCD 9] [DABC 9 0] [CDAB 7 ] [BCDA 0 ]

/* 第轮*/
/* 以 [abcd k s i]表示如下操作
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 6 operations. */
[ABCD ] [DABC 8 ] [CDAB 6 ] [BCDA 6]
[ABCD 7] [DABC 8] [CDAB 7 6 9] [BCDA 0 0]
[ABCD ] [DABC 0 ] [CDAB 6 ] [BCDA 6 ]
[ABCD 9 ] [DABC 6] [CDAB 6 7] [BCDA 8]


/* 第轮*/
/* 以 [abcd k s i]表示如下操作
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 6 operations. */
[ABCD 0 6 9] [DABC 7 0 0] [CDAB ] [BCDA ]
[ABCD 6 ] [DABC 0 ] [CDAB 0 ] [BCDA 6]
[ABCD 8 6 7] [DABC 0 8] [CDAB 6 9] [BCDA 60]
[ABCD 6 6] [DABC 0 6] [CDAB 6] [BCDA 9 6]

/* 然后进行如下操作 */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

Next i /* 结束对I的循环*/

第六步，输出结果。
A，B，C，D连续存放，共6个字节，8位。按十六进制依次输出这个6个字节。


最后，用程序语言实现算法后，可以输入以下几个信息对程序作一个简单的测试，
看看程序有没有错误。
　MD ("") = dd8cd98f00b0e9800998ecf87e
　MD ("a") = 0cc7b9c0fb6a8c99e697766
　MD ("abc") = 900098cdfb0d696f7d8e7f7
　MD ("message digest") = f96b697d7cb798dafaaf6d0
　MD ("abcdefghijklmnopqrstuvwxyz") = cfcdd769e007dfb96cca67eb
　MD ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz06789") =
d7ab98d77d9fa6cc9f9d9f
MD ("6789067890678906789067890678906789
067890") = 7edfabec9ac9dae07b67a


MD算法之C#程序

MD算法比较特别，最适合用汇编语言来写，好多高级语言对之无能无力或效率极低。
比如我最开始尝试用Python和Euphoria编写，发现不太容易。相比而言，C#作为C家簇
中新兴的一门.net语言，功能比较全面。花了一晚上的工夫终于用C#最先实现了MD。
主要是由于对算法的一些细节不太注意，结果输出总是不对，调试了好长时间。

[code]
//源文件：md.cs
// MD Alogrithm
// by rufi 00.6.0 http://rufi.yculblog.com/
using System;
using System.Collections;
using System.IO;

public class MD {
//static state variables
private static UInt A;
private static UInt B;
private static UInt C;
private static UInt D;

//number of bits to rotate in tranforming
private const int S = 7;
private const int S = ;
private const int S = 7;
private const int S = ;
private const int S = ;
private const int S = 9;
private const int S = ;
private const int S = 0;
private const int S = ;
private const int S = ;
private const int S = 6;
private const int S = ;
private const int S = 6;
private const int S = 0;
private const int S = ;
private const int S = ;


/* F, G, H and I are basic MD functions.
* 四个非线性函数:
*
* 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))
*
* （&与，|或，~非，^异或）
*/
private static UInt F(UInt x,UInt y,UInt z){
return (x&y)|((~x)&z);
}
private static UInt G(UInt x,UInt y,UInt z){
return (x&z)|(y&(~z));
}
private static UInt H(UInt x,UInt y,UInt z){
return x^y^z;
}
private static UInt I(UInt x,UInt y,UInt z){
return y^(x|(~z));
}

/* FF, GG, HH, and II transformations for rounds , , , and .
* Rotation is separate from addition to prevent recomputation.
*/
private static void FF(ref UInt a,UInt b,UInt c,UInt d,UInt mj,int s,UInt ti){
a = a + F(b,c,d) + mj + ti;
a = a << s | a >> (-s);
a += b;
}
private static void GG(ref UInt a,UInt b,UInt c,UInt d,UInt mj,int s,UInt ti){
a = a + G(b,c,d) + mj + ti;
a = a << s | a >> (-s);
a += b;
}
private static void HH(ref UInt a,UInt b,UInt c,UInt d,UInt mj,int s,UInt ti){
a = a + H(b,c,d) + mj + ti;
a = a << s | a >> (-s);
a += b;
}
private static void II(ref UInt a,UInt b,UInt c,UInt d,UInt mj,int s,UInt ti){
a = a + I(b,c,d) + mj + ti;
a = a << s | a >> (-s);
a += b;
}

private static void MD_Init(){
A=0x670; //in memory, this is 0x067
B=0xefcdab89; //in memory, this is 0x89abcdef
C=0x98badcfe; //in memory, this is 0xfedcba98
D=0x076; //in memory, this is 0x760
}

private static UInt[] MD_Append(byte[] input){
int zeros=0;
int ones =;
int size=0;
int n = input.Length;
int m = n％6;
if( m < 6 ){
zeros = -m;
size=n-m+6;
}
else if (m==6){
zeros = 0;
ones = 0;
size=n+8;
}
else{
zeros = 6-m+6;
size=n+6-m+6;
}

ArrayList bs = new ArrayList(input);
if(ones==){
bs.Add( (byte)0x80 ); // 0x80 = $0000000
}
for(int i=0;i<zeros;i++){
bs.Add( (byte)0 );
}

UInt6 N = (UInt6) n * 8;
byte h=(byte)(N&0xFF);
byte h=(byte)((N>>8)&0xFF);
byte h=(byte)((N>>6)&0xFF);
byte h=(byte)((N>>)&0xFF);
byte h=(byte)((N>>)&0xFF);
byte h6=(byte)((N>>0)&0xFF);
byte h7=(byte)((N>>8)&0xFF);
byte h8=(byte)(N>>6);
bs.Add(h);
bs.Add(h);
bs.Add(h);
bs.Add(h);
bs.Add(h);
bs.Add(h6);
bs.Add(h7);
bs.Add(h8);
byte[] ts=(byte[])bs.ToArray(typeof(byte));

/* Decodes input (byte[]) into output (UInt[]). Assumes len is
* a multiple of .
*/
UInt[] output = new UInt[size/];
for(Int6 i=0,j=0;i<size;j++,i+=){
output[j]=(UInt)(ts[i] | ts[i+]<<8 | ts[i+]<<6 | ts[i+]<<);
}
return output;
}
private static UInt[] MD_Trasform(UInt[] x){

UInt a,b,c,d;

for(int k=0;k<x.Length;k+=6){
a=A;
b=B;
c=C;
d=D;

/* Round */
FF (ref a, b, c, d, x[k+ 0], S, 0xd76aa78); /* */
FF (ref d, a, b, c, x[k+ ], S, 0xe8c7b76); /* */
FF (ref c, d, a, b, x[k+ ], S, 0x070db); /* */
FF (ref b, c, d, a, x[k+ ], S, 0xcbdceee); /* */
FF (ref a, b, c, d, x[k+ ], S, 0xf7c0faf); /* */
FF (ref d, a, b, c, x[k+ ], S, 0x787c6a); /* 6 */
FF (ref c, d, a, b, x[k+ 6], S, 0xa806); /* 7 */
FF (ref b, c, d, a, x[k+ 7], S, 0xfd690); /* 8 */
FF (ref a, b, c, d, x[k+ 8], S, 0x698098d8); /* 9 */
FF (ref d, a, b, c, x[k+ 9], S, 0x8bf7af); /* 0 */
FF (ref c, d, a, b, x[k+0], S, 0xffffbb); /* */
FF (ref b, c, d, a, x[k+], S, 0x89cd7be); /* */
FF (ref a, b, c, d, x[k+], S, 0x6b90); /* */
FF (ref d, a, b, c, x[k+], S, 0xfd9879); /* */
FF (ref c, d, a, b, x[k+], S, 0xa6798e); /* */
FF (ref b, c, d, a, x[k+], S, 0x9b08); /* 6 */

/* Round */
GG (ref a, b, c, d, x[k+ ], S, 0xf6e6); /* 7 */
GG (ref d, a, b, c, x[k+ 6], S, 0xc00b0); /* 8 */
GG (ref c, d, a, b, x[k+], S, 0x6ea); /* 9 */
GG (ref b, c, d, a, x[k+ 0], S, 0xe9b6c7aa); /* 0 */
GG (ref a, b, c, d, x[k+ ], S, 0xd6f0d); /* */
GG (ref d, a, b, c, x[k+0], S, 0x); /* */
GG (ref c, d, a, b, x[k+], S, 0xd8ae68); /* */
GG (ref b, c, d, a, x[k+ ], S, 0xe7dfbc8); /* */
GG (ref a, b, c, d, x[k+ 9], S, 0xecde6); /* */
GG (ref d, a, b, c, x[k+], S, 0xc707d6); /* 6 */
GG (ref c, d, a, b, x[k+ ], S, 0xfd0d87); /* 7 */
GG (ref b, c, d, a, x[k+ 8], S, 0xaed); /* 8 */
GG (ref a, b, c, d, x[k+], S, 0xa9ee90); /* 9 */
GG (ref d, a, b, c, x[k+ ], S, 0xfcefaf8); /* 0 */
GG (ref c, d, a, b, x[k+ 7], S, 0x676f0d9); /* */
GG (ref b, c, d, a, x[k+], S, 0x8dac8a); /* */

/* Round */
HH (ref a, b, c, d, x[k+ ], S, 0xfffa9); /* */
HH (ref d, a, b, c, x[k+ 8], S, 0x877f68); /* */
HH (ref c, d, a, b, x[k+], S, 0x6d9d6); /* */
HH (ref b, c, d, a, x[k+], S, 0xfde80c); /* 6 */
HH (ref a, b, c, d, x[k+ ], S, 0xabeea); /* 7 */
HH (ref d, a, b, c, x[k+ ], S, 0xbdecfa9); /* 8 */
HH (ref c, d, a, b, x[k+ 7], S, 0xf6bbb60); /* 9 */
HH (ref b, c, d, a, x[k+0], S, 0xbebfbc70); /* 0 */
HH (ref a, b, c, d, x[k+], S, 0x89b7ec6); /* */
HH (ref d, a, b, c, x[k+ 0], S, 0xeaa7fa); /* */
HH (ref c, d, a, b, x[k+ ], S, 0xdef08); /* */
HH (ref b, c, d, a, x[k+ 6], S, 0x88d0); /* */
HH (ref a, b, c, d, x[k+ 9], S, 0xd9dd09); /* */
HH (ref d, a, b, c, x[k+], S, 0xe6db99e); /* 6 */
HH (ref c, d, a, b, x[k+], S, 0xfa7cf8); /* 7 */
HH (ref b, c, d, a, x[k+ ], S, 0xcac66); /* 8 */

/* Round */
II (ref a, b, c, d, x[k+ 0], S, 0xf9); /* 9 */
II (ref d, a, b, c, x[k+ 7], S, 0xaff97); /* 0 */
II (ref c, d, a, b, x[k+], S, 0xab9a7); /* */
II (ref b, c, d, a, x[k+ ], S, 0xfc9a09); /* */
II (ref a, b, c, d, x[k+], S, 0x6b9c); /* */
II (ref d, a, b, c, x[k+ ], S, 0x8f0ccc9); /* */
II (ref c, d, a, b, x[k+0], S, 0xffeff7d); /* */
II (ref b, c, d, a, x[k+ ], S, 0x88dd); /* 6 */
II (ref a, b, c, d, x[k+ 8], S, 0x6fa87ef); /* 7 */
II (ref d, a, b, c, x[k+], S, 0xfece6e0); /* 8 */
II (ref c, d, a, b, x[k+ 6], S, 0xa0); /* 9 */
II (ref b, c, d, a, x[k+], S, 0xe08a); /* 60 */
II (ref a, b, c, d, x[k+ ], S, 0xf77e8); /* 6 */
II (ref d, a, b, c, x[k+], S, 0xbdaf); /* 6 */
II (ref c, d, a, b, x[k+ ], S, 0xad7dbb); /* 6 */
II (ref b, c, d, a, x[k+ 9], S, 0xeb86d9); /* 6 */

A+=a;
B+=b;
C+=c;
D+=d;
}
return new UInt[]{A,B,C,D};
}
public static byte[] MDArray(byte[] input){
MD_Init();
UInt[] block = MD_Append(input);
UInt[] bits = MD_Trasform(block);

/* Encodes bits (UInt[]) into output (byte[]). Assumes len is
* a multiple of .
*/
byte[] output=new byte[bits.Length*];
for(int i=0,j=0;i<bits.Length;i++,j+=){
output[j] = (byte)(bits[i] & 0xff);
output[j+] = (byte)((bits[i] >> 8) & 0xff);
output[j+] = (byte)((bits[i] >> 6) & 0xff);
output[j+] = (byte)((bits[i] >> ) & 0xff);
}
return output;
}

public static string ArrayToHexString(byte[] array,bool uppercase){
string hexString="";
string format="x";
if(uppercase){
format="X";
}
foreach(byte b in array){
hexString += b.ToString(format);
}
return hexString;
}

public static string MDString(string message){
char[] c = message.ToCharArray();
byte[] b = new byte[c.Length];
for(int i=0;i<c.Length;i++){
b[i]=(byte)c[i];
}
byte[] digest = MDArray(b);
return ArrayToHexString(digest,false);
}
public static string MDFile(string fileName){
FileStream fs=File.Open(fileName,FileMode.Open,FileAccess.Read);
byte[] array=new byte[fs.Length];
fs.Read(array,0,(int)fs.Length);
byte[] digest = MDArray(array);
fs.Close();
return ArrayToHexString(digest,false);
}

public static string Test(string message){
return "rnMD (""+message+"") = " + MD.MDString(message);
}
public static string TestSuite(){
string s = "";
s+=Test("");
s+=Test("a");
s+=Test("abc");
s+=Test("message digest");
s+=Test("abcdefghijklmnopqrstuvwxyz");
s+=Test("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz06789");
s+=Test("6789067890678906789067890678906789067890");
return s;
}
}
[/code]