Hash函数

基本概念

散列（Hash）函数，又称哈希函数或扎凑函数，是对不定长的输入产生定长输出的一种特殊函数，可以表达为h=H(M)，M为消息，其长度不定，h被称为散列值、hash值、散列值或哈希值，长度一定，一般为128位或160位，如图1所示。

图1哈希函数

常见Hash算法

目前常用的Hash算法一般采用迭代型结构，这种结构的Hash函数已被证明是合理的。迭代型Hash函数的一般结构如图2所示：

图2Hash算法迭代型结构

其中M=Y0+Y1+…+YL-1，b为分组长度，n为输出的hash值长度，CVi是各级输出，CVL为Hash值。

下面介绍几种Hash算法都采用这种迭代型结构。

MD5算法

MD5算法在产生摘要时，输入的信息可任意长，对输入按512位的分组为单位进行处理，处理后输出为128位的Hash值。

算法实例

以明文“TheCaseOfmd5”为例，其16进制ASCII码为：5468652043617365204f66206d6435，转化为二进制为：10101000110100001100101001000000100001101100001011100110110010100100000010011110110011000100000011011010110010000110101，长度为119。

算法过程

第一步消息填充

使消息的长度比512的整数倍少64位。由于消息的长度为119，若要比512的整数倍少64位，则消息长度应为448，故需要填充1个“1”和328个“0”。又因为119<264，故最后附上的64位为：0000000000000000000000000000000000000000000000000000000001110111。最终的消息长度=119位原消息+329位0和1填充内容+64位原消息长度信息=512位

第二步初始化缓冲区

缓冲区用32位的寄存器，初始存数以十六进制表示为：A=0x12345678，B=0x89ABCDEF，C=0xFEDCBA98，D=0x76543210。

第三步 HMD5运算

以分组为单位对消息进行处理。本例中只有一个分组Y0，在Y0组中需要经过压缩函数HMD5，其中包括4轮的处理过程。HMD5每轮的处理过程结构一样，但所用的逻辑函数不同，分别为F、G、H、I。每轮的输入为当前处理的消息分组Y0和缓冲区的当前值A、B、C、D，输出仍放在缓冲区中以产生新的A、B、C、D。每轮又要进行16步迭代运算，4轮共需64步完成。第四轮的输出与第一轮的输入相加得到最后的输出。如下图3、图4所示：

图3一个分组的Hmd5处理

图4一步迭代

表1逻辑函数

轮	基本函数g	g(b,c,d)
1	F(b,c,d)	(bÙc)Ú(b-Ùd)
2	G(b,c,d)	(bÙd)Ú(cÙd-)
3	H(b,c,d)	bÅcÅd
4	I(b,c,d)	cÅ(bÚd-)

表 2 512位分组中x[k]的使用顺序

轮	使用顺序
1	x[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
2	x[1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12]
3	x[5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2]
4	x[0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9]

表 3 从正弦函数构造的表T

0xD76AA478	0xE8C7B756	0x242070DB	0xC1BDCEEE	0xF57C0FAF	0x4787C62A	0xA8304613	0xFD469501
0x698098D8	0x8B44F7AF	0xFFFF5BB1	0x895CD7BE	0x6B901122	0xFD987193	0xA679438E	0x49B40821
0xF61E2562	0xC040B340	0x265E5A51	0xE9B6C7AA	0xD62F105D	0x02441453	0xD8A1E681	0xE7D3FBC8
0x21E1CDE6	0xC33707D6	0xF4D50D87	0x455A14ED	0xA9E3E905	0xFCEFA3F8	0x676F02D9	0x8D2A4C8A
0xFFFA3942	0x8771F681	0x6D9D6122	0xFDE5380C	0xA4BEEA44	0x4BDECFA9	0xF6BB4B60	0xBEBFBC70
0x289B7EC6	0xEAA127FA	0xD4EF3085	0x04881D05	0xD9D4D039	0xE6DB99E5	0x1FA27CF8	0xC4AC5665
0xF4292244	0x432AFF97	0xAB9423A7	0xFC93A039	0x655B59C3	0x8F0CCC92	0xFFEFF47D	0x85845DD1
0x6FA87E4F	0xFE2CE6E0	0xA3014314	0x4E0811A1	0xF7537E82	0xBD3AF235	0x2AD7D2BB	0xEB86D391

（注：从第一行起从左往右读，分别表示T[1，2，…，64]，前两行参与第一轮运算，三四行参与第二轮，以此类推。每两行共16个数据依次对应每轮中16步。）

CLSs规则

轮	1-4步	5-8步	9-12步	13-16步
1	7、12、17、22	7、12、17、22	7、12、17、22	7、12、17、22
2	5、9、14、20	5、9、14、20	5、9、14、20	5、9、14、20
3	4、11、16、23	4、11、16、23	4、11、16、23	4、11、16、23
4	6、10、15、21	6、10、15、21	6、10、15、21	6、10、15、21

根据上述的三个表以及左移规则，就可以开始md5的计算了。首先，将填充结果分成16段每段32位。

X[0]：10101000110100001100101001000000 转为16进制为 0xA8D0CA40

X[1]： 10000110110000101110011011001010

X[2]： 01000000100111101100110001000000
X[3]： 11011010110010000110101100000000
… (注：X[4]-X[13]每段32位上都为0)
X[14]：00000000000000000000000000000000
X[15]：00000000000000000000000001110111

第一轮第一步迭代，如图 5所示：

图5 第一轮第一步迭代带数据

（注：上述演示数据均为16进制）

第一轮之后的15步以及剩余各轮中的16步都类似图5的操作，不再做演示。

第四步输出

最终，经过64步运算后，所得的结果与最初输入的分组进行模232加法（如果两数相加后大于等于232，则结果除以232取余数），见图3。由于本例中只有一个分组，故所得结果即为最终输出，128位的消息摘要（输出位A、B、C、D的值：低字节位A,最高字节位D）。举例如下图5所示：

图 6 最终输出结果举例

SHA算法

算法实例

以明文“TheCaseOfsha-1”为例。其二进制值为101010001101000011001010100001101100001011100110110010101001111011001100111001101101000011000010010110100110001，长度为111。

算法过程

SHA处理消息的过程与MD5算法类似。

第一步消息填充

填充消息使其长度与448模512同余。填充的方法是在消息后附加一个1和若干个0。然后附上填充前的报文长度的64位数据（最高有效位在前）。

本例需要填充1个“1”和337个“0”，最后附上111的长度信息11011110 00000000 00000000 00000000 00000000 00000000 00000000 00000000。

第二步初始化缓冲区

哈希函数的中间结果和最终结果保存于160位的缓冲区中，缓冲区用5个32位的寄存器（A、B、C、D、E）表示，并将寄存器初始化为下列32位的整数：

A=67452301，B=EFCDAB89，C=98BADCFB，D=10325476，E=C3D2E1F0

第三步 HSHA-1算法

图 7 SHA-1算法产生消息摘要

类似MD5算法，SHA-1算法也具有4轮运算模块，但每轮进行20步迭代。每轮输入为消息分组Yq 和缓冲区的160位当前值A、B、C、D、E。输出为新的缓冲区值A、B、C、D、E。每轮的结构相同，但每轮使用一个不同的加法常量Kt 其中t表示步数，0≤t≤79，如表所示，且每轮使用不同的逻辑函数。

图 8 一个分组的HSHA-1 处理

表 4 算法中使用的加法常量

步骤	十六进制
0≤t≤19	Kt =5A827999
20≤t≤39	Kt =6ED9EBA1
40≤t≤59	Kt =8F1BBCDC
60≤t≤76	Kt =CA62C1D6

表 5 各轮中使用的逻辑函数

步骤	Kt的十六进制	取整数部分
0<= t <=19	f1 = f(t,B,C,D)	(B&C)\|((~B)&D)
20<= t <=39	f2 = f(t,B,C,D)	B $\displaystyle \oplus$ C $\displaystyle \oplus$ D
40<=t<=59	f3 = f(t,B,C,D)	(B&C)\|(B&D)\|(C&D)
60<=t<=79	f4 = f(t,B,C,D)	B $\displaystyle \oplus$ C $\displaystyle \oplus$ D