哈希函数-MD5、SHA1_md5 sha1

定义

$Hash$,一般译作散列、哈希，就是能把任意长度的输入（又做预映射）通过散列算法，变换成固定长度的输出，这个输出就是散列值。

散列值通常是数字和字母的组合。

性质

1、不可逆性。已知哈希函数$F$和$x$哈希值,无法逆向求出$x$.

2、对于特定的哈希函数，只要输入不变，那么散列值也肯定是唯一不变的.

3、哈希函数产生的映射应当保持均匀，即不要使得映射结果堆积在小区间的某一区域.

4、敏感性。哪怕输入数据只改变$1bit$,得到的哈希值也大不相同.

5、抗碰撞性。理想$Hash$函数是无碰撞的，但实际很难做到这一点。有两种抗碰撞性：弱抗碰撞性、强抗碰撞性.

典型的哈希函数

常见的$Hash$算法有$MD5$和$SHA$系列，目前$MD5$和$SHA1$已被破解，一般推荐使用$SHA2-256$算法.

MD5

输入任意长度的信息，以**$512bit$输入数据块**为单位，输出为$128bit$的信息（数字指纹）。

实现过程

1、补位。使输入信息的长度变为$(N\ast 512+448)bit$，补位内容为$100...0$

​ 那为什么不补为$512bit$的整数倍呢？其实剩余$64bit$是原始信息的长度。也就是说，补位最终结果是$N\ast 512bit$的.

​ 需要注意的是，补位操作必须进行，即使最初信息的长度已经满足$(N\ast 512+448)bit$,但还是要加上$512bit$,然后再补$64bit$记录原始

​ 信息长度. 如下图：

2、分割。把结果分为n组，每一组长度为$512bit$.

3、计算。

$\bullet$ 准备四个标准幻数，每一个数4个字节，总的16字节。其实四个幻数的值定义也很直接，就是32个16进制字面值依次排列。

分别是：

$A=01234567$ $B=89ABCDEF$ $C=FEDCBA98$ $D=76543210$

那么，这四个幻数是用来做什么的呢？

其实不难发现，四个幻数的长度和$MD5$散列值的长度都是$128bit$,四个幻数就是用来做循环初始计算值的。

最终$MD5$散列值就是四个标准幻数经过多轮哈希运算的结果。

需要注意，在程序中，幻数是用小端字节表示的，即

$A=0x67452301$ $B=0xEFCDAB89$ $C=0x98BACDFE$ $D=0x10325476$

准备工作完成，就可以开始计算了。

$\bullet$ 数据被分为n个$512bit$，也就是n个64字节，再把每一个64字节分成16份，每份四个字节。

$\bullet$ 定义四个函数，分别是
$$FF(A,B,C,D,X,S,AC)$$

$$GG(A,B,C,D,X,S,AC)$$

$$HH(A,B,C,D,X,S,AC)$$

$$II(A,B,C,D,X,S,AC)$$

前四个参数分别对应四个标准幻数，第五个参数是每一小份的四个字节数据，第六个和第七个参数都是一些固定常数，执行一些逻辑与、或、非、异或运算，加法运算和移位运算。

$\bullet$ 将四个标准幻数换着顺序作为前四个参数输入，并将16份4字节数据依次作为第五个参数代入，经过这么一轮运算，四个标准幻数的值就变了。

$\bullet$ 将四个标准幻数与一开始的值相加，得到更新后的四个幻数结果。这样就处理完了一个64字节的数据。

$\bullet$ 四个更新后的标准幻数作为第二轮的四个标准幻数输入，并且载入第二个64字节数据中进行运算。

$\bullet$ 重复上述过程，直到n个64字节数据全部计算完成，最终得到的四个标准幻数用十六进制显示出来就是最终$MD5$的散列值。

SHA1(Secure Hash Algorithm)

对于长度小于$2^{64}bit$的消息，将输入流按照每块$512b(64B)$进行分块，并产生$160b(20B)$的信息摘要。

实现过程

大致框图：

1、补位。（与$MD5$补位是一样的）

第一位：补1
其余位：补0
直至满足 L mod 512 = 448

512 - 448 = 64
剩余64bit是初始消息的长度
1
2
3
4
5
6

eg：

2、将信息分为$n$个$512bit$。

3、每个$512b$的运算。

$\bullet$ 把$512b$分为$26$份$32b$,将$16$份扩充到$80$份.

那么，如何扩充呢？
W t = { M t i    0 ⩽ t ⩽ 15 R O T L 1 ( W t − 3 ⨁ W t − 8 ⨁ W t − 14 ⨁ W t − 16 )    16 ⩽ t ⩽ 79 W_{t}=\left\{

$$\begin{matrix} M_{t}^{i}\textbf{ }\textbf{ }0\leqslant t\leqslant15\\ ROTL^{1}(W_{t-3}\bigoplus W_{t-8}\bigoplus W_{t-14}\bigoplus W_{t-16})\textbf{ }\textbf{ }16\leqslant t\leqslant79 \end{matrix}$$ \right. Wt​={Mti​  0⩽t⩽15ROTL1(Wt−3​⨁Wt−8​⨁Wt−14​⨁Wt−16​)  16⩽t⩽79​
$ROT{L}^1$表示左移一位.

eg:
$$W_{16}=(W_{13}⨁W_8⨁W_2⨁W_0)<<1$$
$\bullet$ 设置$5$个初始量，
$$H_0^{(0)}=67452301$$

$$H_1^{(0)}=efcdab89$$

$$H_2^{(0)}=98badcfe$$

$$H_3^{(0)}=10325476$$

$$H_4^{(0)}=c3d2e1f0$$

$\bullet$ 将初始量的值分别赋给$a,b,c,d,e$
$$a=H_0^{(0)}$$

$$b=H_1^{(0)}$$

$$c=H_2^{(0)}$$

$$d=H_3^{(0)}$$

$$e=H_4^{(0)}$$

$\bullet$ 进行$80$轮运算.

​ $fort=0to79:$
{ \left \{ \right. {
​ $T=ROT{L}^5(a)+f_t(b,c,d)+e+K_t+W_t$

​ $e=d$

​ $d=c$

​ $c=ROL{T}^{30}(b)$

​ $b=a$

​ $a=T$
$$\}$$
其中，
K t = { 5 a 827999    0 ⩽ t ⩽ 19 6 e d 9 e b a 1    20 ⩽ t ⩽ 39 8 f 1 b b c d c    40 ⩽ t ⩽ 59 c a 62 c 1 d 6    60 ⩽ t ⩽ 79 K_{t}=\left\{

$$\begin{matrix} 5a827999\textbf{ }\textbf{ }0\leqslant t\leqslant19\\ 6ed9eba1\textbf{ }\textbf{ }20\leqslant t\leqslant39\\ 8f1bbcdc\textbf{ }\textbf{ }40\leqslant t\leqslant59\\ ca62c1d6\textbf{ }\textbf{ }60\leqslant t\leqslant79 \end{matrix}$$ \right. Kt​=⎩⎪⎪⎨⎪⎪⎧​5a827999  0⩽t⩽196ed9eba1  20⩽t⩽398f1bbcdc  40⩽t⩽59ca62c1d6  60⩽t⩽79​

f t ( x , y , z ) = { C h ( x , y , z ) = ( x ∧ y ) ⨁ ( x ∧ z ) ,    0 ⩽ t ⩽ 19 P a r i t y ( x , y , z ) = x ⨁ y ⨁ z ,    20 ⩽ t ⩽ 39 M a j ( x , y , z ) = ( x ∧ y ) ⨁ ( x ∧ z ) ⨁ ( y ∧ z ) ,    40 ⩽ t ⩽ 59 P a r i t y ( x , y , z ) = x ⨁ y ⨁ z ,    60 ⩽ t ⩽ 79 f_{t}(x,y,z)=\left\{

$$\begin{matrix} Ch(x,y,z)=(x\wedge y)\bigoplus(x\wedge z),\textbf{ }\textbf{ }0\leqslant t\leqslant19\\ Parity(x,y,z)=x\bigoplus y\bigoplus z,\textbf{ }\textbf{ }20\leqslant t\leqslant39\\ Maj(x,y,z)=(x\wedge y)\bigoplus(x\wedge z)\bigoplus(y\wedge z),\textbf{ }\textbf{ }40\leqslant t\leqslant59\\ Parity(x,y,z)=x\bigoplus y\bigoplus z,\textbf{ }\textbf{ }60\leqslant t\leqslant79 \end{matrix}$$ \right. ft​(x,y,z)=⎩⎪⎪⎨⎪⎪⎧​Ch(x,y,z)=(x∧y)⨁(x∧z),  0⩽t⩽19Parity(x,y,z)=x⨁y⨁z,  20⩽t⩽39Maj(x,y,z)=(x∧y)⨁(x∧z)⨁(y∧z),  40⩽t⩽59Parity(x,y,z)=x⨁y⨁z,  60⩽t⩽79​

$\bullet$ 将$80$轮运算之后得到的$a,b,c,d,e$分别与初始量相加.

$\bullet$ 将上述结果作为第二个$512b$的初始量进行循环计算。

$\bullet$ 重复上述过程，直到$n$个$512b$数据全部计算完成，最终得到的$a,b,c,d,e$就是$SHA1$的最终结果。