md5的简单实现

zan 2014年4月5日 16时0分

#技术#编程#Web开发

好久没写blog，最近也正好想实现一下常见的摘要算法。

md5的背景介绍

md5是一种消息摘要算法，它能够将输入的任何数据经过运算产生128 bit的hash值（这个hash便是这段消息的摘要）一般情况下，md5产生的消息摘要发生碰撞得可能性很低（还是存在的），所以人们常用通过对比经md5运算后摘要来验证一段消息的完整性

md5的算法

md5算法可以描述成下面5个步骤：

step 1.添加填充数据

首先我们要添加1位 1，接着填充n位（n 非负）0到原消息后面，使填充后的数据长度lens满足

lens mod 512=448 //计量单位是bit

这样，我们添加的数据长度范围是 1 bit到 512 bit之间

step 2.添加数据长度

这一步，我们将原始数据的长度用一个64位（小端字节序表示）的整型表示，然后将这64位数据添加到填充之后的数据上这里有几个注意点

这里的消息长度是原数据的长度
当数据长度超过2的64次方时，只使用低64位的数据

经过上面两个步骤，我们的数据长度变成了

lens=512*k+448+64
lens=512*(k+1)

step 3 初始化数据

初始化4个32位的数据 A B C D

    word A: 01 23 45 67  // A = 0x67452301
	word B: 89 ab cd ef  // B = 0xefcdab89
	word C: fe dc ba 98  // C = 0x98badcfe
	word D: 76 54 32 10  // D = 0x10325476

step 4 对消息进行分组运算

将消息分成512位一组,将这一组数据保存在长度为16的unsigned int的数组中，进行四轮的运算。

这里需要定义四种操作

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)))

分别用于四轮运算，其中表达式中的T是个64个元素的unsigned int 数组

其中T[i]是4294967296*abs(sin(i))的整数部分

我们用临时变量保存本组运算结果

AA=A
BB=B
CC=C
DD=D

//第一轮，我们用
[abcd k s i] 表示  a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< 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]

//第二轮，我们用
[abcd k s i] 表示  a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)

//执行下面的运算
[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]

//第三轮，我们用
[abcd k s i] 表示  a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)
[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]

//第四轮，我们用
[abcd k s i] 表示  a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)

//再执行下面的运算
[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]

最后对结果进行暂存，使得