md5加密算法

[参考文章]
rfc1321
http://c.chinaitlab.com/cckaifa/database/200808/759396.html
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.org/rfc/rfc1321.txt）/*在本文下面是这篇文章*/，这是一份最权威的文档，由ronald l. rivest在1992年8月向ieft提交。
MD5算法应用
md5的典型应用是对一段信息（message）产生信息摘要（message-digest），以防止被篡改。比如，在unix下有很多软件在下载的时候都有一个文件名相同，文件扩展名为。md5的文件，在这个文件中通常只有一行文本，大致结构如：
md5 （tanajiya.tar.gz） = 0ca175b9c0f726a831d895e269332461
这就是tanajiya.tar.gz文件的数字签名。md5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的md5信息摘要。如果在以后传播这个文件的过程中，无论文件的内容发生了任何形式的改变（包括人为修改或者下载过程中线路不稳定引起的传输错误等），只要你对这个文件重新计算md5时就会发现信息摘要不相同，由此可以确定你得到的只是一个不正确的文件。如果再有一个第三方的认证机构，用md5还可以防止文件作者的"抵赖"，这就是所谓的数字签名应用。
md5还广泛用于加密和解密技术上。比如在unix系统中用户的密码就是以md5（或其它类似的算法）经加密后存储在文件系统中。当用户登录的时候，系统把用户输入的密码计算成md5值，然后再去和保存在文件系统中的md5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这不但可以避免用户的密码被具有系统管理员权限的用户知道，而且还在一定程度上增加了密码被破解的难度。
MD5算法描述
对md5算法简要的叙述可以为：md5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。
在md5算法中，首先需要对信息进行填充，使其字节长度对512求余的结果等于448.因此，信息的字节长度（bits length）将被扩展至n*512+448，即n*64+56个字节（bytes），n为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以64位二进制表示的填充前信息长度。经过这两步的处理，现在的信息字节长度=n*512+448+64=（n+1）*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。
MD5算法实现
md5中有四个32位被称作链接变量（chaining variable）的整数参数，用来计算信息摘要，每一个变量被初始化成为以下以十六进制表示的数值：
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
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），<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,c,d)+Mj+ti)<II(a,b,c,d,Mj,s,ti)表示a=b+((a+(I(b,c,d)+Mj+ti)<处理数据，N是总的字节数，以64个字节为一组，每组作一次循环，每次循环进行四轮操作。要变换的64个字节用16个32位的整数数组M[0 ...15]表示。而数组T[1 ... 64]表示一组常数，T为4294967296*abs(sin(i))的32位整数部分，i的单位是弧度,i的取值从1到64。具体过程如下：
/* 设置主循环变量 */
For (i = 0；i< =N/16-1;i++ )
{
/*每循环一次，把数据原文存放在16个元素的数组X中. */
For( j = 0;j<=15 ;j++)
Set X[j] to M[i*16+j].
AA = A
BB = B
CC = C
DD = D
/* 第1轮*/
/* 以 [abcd k s i]表示如下操作
a = b + ((a + F(b,c,d) + X[k] + T) << s) */
/*做以下运算*/
[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 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 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 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 + AA
B = B + BB
C = C + CC
D = D + DD
}