哈希函数-md5实现原理

1.MD5算法

MD:消息摘要算法

输入为任意长，输出为128位

1.1.1、位填充

1.1.1.1MD5每个分组是512，因此必须进行位填充

1. 填充消息使其长度n = 448 mod 512
2. 即使消息长度本身满足条件，也必须填充（例如消息长度位448，也必须填充512）
3. 填充由一个1和其余的0组成
4. 位填充最小为1，最大为512

1.2.长度填充

1. 用64位表示消息位填充前的长度
2. 将该长度附加在位填充的消息后面——最低有效位在前
3. 如果消息长度大于2的64次方，则只使用其低位64位（即消息长度对2的64次方取模）

1.3.初始化缓冲区

• MD5的中间结果CV保存在4个32位的寄存器（A,B,C,D）中
• A,B,C,D的初始值如下（最低有效位存放在低地址字节位置）

——A = 0x01 23 45 67

——B = 0x89 ab cd ef

——C = 0xfe dc ba 98

——D = 0x76 54 32 10

它们称为链接变量

1.4.以512位分组为单位处理消息

1. 4.1、MD5的压缩函数Hmd5 (CVi-1,Yi-1)

1.4.1.1定义四个辅助逻辑函数

——F(X,Y,Z) = XY v not(X) Z

——G(X,Y,Z) = XZ v not(Z)

——H(X,Y,Z) = X xor Y xor Z

——I(X,Y,Z) = Y xor (X v not(Z))

1.4.1.2每个逻辑函数输入是3个32位的字(x ,y , z ),输出是1个32位的字

MD5逻辑函数定义
循环次数对应的逻辑函数C语言描述（&是与，|是或，！是非，^是异或）1F(X,Y,Z)(X & Y) | (X & Z)2G(X,Y,Z)X & Z | Y&(~Z)3H(X,Y,Z)X^Y^Z4I(X,Y,Z)Y^(X | ~Z)
1.4.1.3常数表T

• MD5利用一个常数表T来对压缩过程的每一步增加不同的限制，并且用于消除输入中可能存在的规律。
• 常数表T有64个32位常数构成
• 每个常数利用正弦函数来构成

1.4.2MD5的压缩函数基本描述

——压缩函数用4轮来处理一个512分组

——在每1轮中512分组被进一步分为16个32位的小段：

• X[k], k = 0, 1, 2, ........,15
• X[k]在每1轮中恰好被使用一次：

1. X[0]、X[2]、……，X[15]
2. X[p2(i)]，p2(i) = (1+5i) mod 16
3. X[p3(i)]，p3(i) = (5+3i) mod 16
4. X[p4(i)]，p4(i) = 7i mod 16

——每1轮利用1个逻辑函数对4个寄存器（A , B, C, D）进行16步操作

——每轮操作的结果均存放在A , B, C, D四个寄存器中

——第四轮的输出和第一轮的输入相加（模2的32次方)得到下一轮的输入

1.4.3MD5的压缩函数每一步工作原理

• 每1轮利用1个逻辑函数对4个寄存器（A ,B ,C ,D ）进行16步操作

• 每步操作对A、B、C 和 D 四个存储器中的一个进行一次非线性函数运算，然后将所得结果加上第四个存储器的值、一个数据分块和一个常数值，在将所得结果循环左移一个不定的数。

• 每步操作的通用形式是（记做[abcd f k s i]）

  1. a = b + ((a + f(b,c,d) + X[k] + T[i]) <<< s)
  

——a , b , c , d 是A , B ,C ,D中的一个

——f是逻辑函数F、G 、H和I中的一个

 2. b = a, c = b ,d = c,a = d(循环右移赋值）

• 每步操作的结果均存放在A, B ,C ,D四个寄存器中

MD5的四轮迭代

1.4.3.1MD5的每一步

eg 第一轮第一步

[ABCD F 0 7 1]

A = D

B = B + ((A + F(B,C,D) + X[0] + T[1]) <<< 7)

C = D

D = C

F(B , C , D) = (B & C) | (~B & D)

CLS7 : 循环左移7位

• ： 模2的32次方加运算

一步运算的实质：将（a , b , c , d ）中的字右移一位

1.5.输出128位

——输出位A、B、C、D的值：低字节位A,最高字节位D

MD5安全性

——找到具有Hash值相同的两条消息的代价为： 2的64次方

——找到具有给定摘要的消息的代价为：2的128次方

2.SHA-1算法

2.1位填充

• 填充消息使得长度n = 448 mod 512
• 即使消息长度本身满足条件，也必须填充
• 填充由一个1和其余的0组成
• 位填充最小为1，最大为512

2.2、长度填充

• 用64位表示消息位填充前的长度
• 将该长度附加在位填充的消息后面（最高有效位在前）
• 如果消息大于2的64次方，则只使用其低64位（即消息长度对2的64次方取模）

2.3、初始化缓冲区

• SHA-1的中间结果CV保存在5个32位的寄存器（A,B,C,D,E）中
• A, B, C, D, E的初始值为
• A = 67 45 23 01
• B = ef cd ab 89
• C = 98 ba dc fe
• D = 10 32 54 76
• E = c3 d2 e1 f0

2.4、以512位分组为单位处理消息

2.5、输出

• 输出位A、B、C、D、E的值
• 结果160位

2.6、算法示意图

加法常量K的计算表

2.6.1、四个逻辑函数

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

SHA-1的压缩函数

• 压缩函数用4轮来处理一个512分组
• 每1轮利用1个逻辑函数对5个寄存器（A，B，C，D，E） 进行20步操作
• 每轮操作的结果均存放在A,B,C,D,E五个寄存器中
• 第四轮的输出和第一轮的输入相加（模2的32次方） 得到下一轮的输入

·SHA-1的压缩函数

• 每1轮利用1个逻辑函数对5个寄存器(A，B，C，D，E)进行206操作

-每步操作的通用形式是(记做[abcdfksi):
·ABCDE=(E+f(tBCD)+CLS(A)+W+K)，ACLS(B)CD
-A，B，C，D，E是缓冲区的五个字

            -t:步数
             -f(t,B,C,D):第t步用的逻辑函数

            -CLS(.):循环左移s位
             -W:从当前512位导出的32位字

            - K:第t步的加法常量

            一+:模232加法

-每步操作的结果均存放在A，B，C，D，E五个个寄存器中。

2.7SHA-1的后续修改

• NIST于1981年提出了3个Hash算法

• 

3，MD5&SHA-1