HASH算法学习

MD5算法

MD5发展历程

Message Digest Algorithm MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。

MD5于90年代初由MIT Laboratory for Computer Science和RSA Data Security Ic,的Ronald L. Rivest开发出来，是从MD2、MD3和MD4发展过来的。起作用是让大容量信息在用数字签名软件签署私人密钥前被"压缩"成一种保密的格式（就是把一个任意长度的字节串变换成一定长的大整数）。

这些算法的结构相似，但MD2是为8位机器做设计优化的，而MD4和MD5却是面向32位的电脑。这三个算法的描述和c语言源代码在Internet RFC 1321中有详细的描述。

Rivest在19年开发出MD2算法。在这个算法中，首先对信息进行数据补位，使信息的字节长度是16的倍数。然后，以一个16位的检验和追加到信息末尾，并且根据这个新产生的信息计算出散列值。

1990年开发出MD4算法，MD4算法同样需要填补信息以确保信息的比特位长度加上448后能被512整除（信息比特位长度mod 512 = 448）。然后，一个以位二进制表示的信息的最初长度被添加进来。信息被处理成512位迭代结构的区块，而且每个区块要通过三个不同步骤的处理。

1991年，Rivest开发出技术上更为趋近成熟的md5算法。它在MD4的基础上增加了"安全-带子"（safety-belts）的概念。虽然MD5比MD4稍微慢一些，但却更为安全。这个算法很明显的由四个和MD4设计有少许不同的步骤组成。在MD5算法中，信息-摘要的大小和填充的必要条件与MD4完全相同。

MD5应用

MD5用的是哈希函数,在计算机网络中应用较多的不可逆加密算法有RSA公司发明的MD5算法和由美国国家技术标准研究所建议的安全散列算法SHA。 

其典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防止被篡改。比如，在UNIX下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如： 

MD5 (tanajiya.tar.gz) = 0ca175b9c0f726a831d5e269332461 

这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。

MD5算法简介

对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。 

在MD5算法中，首先需要对信息进行填充，使其位长对512求余的结果等于448。因此，信息的位长（Bits Length）将被扩展至N*512+448，即N*+56个字节（Bytes），N为一个正整数。填充的方法如下，在信息的后面填充一个1和无数个0，直到满足上面的条件时才停止用0对信息的填充。然后，在在这个结果后面附加一个以位二进制表示的填充前信息长度。经过这两步的处理，现在的信息的位长=N*512+448+=(N+1)*512，即长度恰好是512的整数倍。这样做的原因是为满足后面处理中对信息长度的要求。 

MD5中有四个32位被称作链接变量（Chaining Variable）的整数参数，他们分别为：A=0x01234567，B=0xabcdef，C=0xfedcba98，D=0x76543210。 

当设置好这四个链接变量后，就开始进入算法的四轮循环运算。循环的次数是信息中512位信息分组的数目。 

将上面四个链接变量复制到另外四个变量中：A到a，B到b，C到c，D到d。 

主循环有四轮（MD4只有三轮），每轮循环都很相似。第一轮进行16次操作。每次操作对a、b、c和d中的其中三个作一次非线性函数运算，然后将所得结果加上第四个变量，文本的一个子分组和一个常数。再将所得结果向右环移一个不定的数，并加上a、b、c或d中之一。最后用该结果取代a、b、c或d中之一。 

以一下是每次操作中用到的四个非线性函数（每轮一个）。 

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

 （&是与，|是或，~是非，^是异或） 

这四个函数的说明：如果X、Y和Z的对应位是和均匀的，那么结果的每一位也应是和均匀的。 

F是一个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。 

假设Mj表示消息的第j个子分组（从0到15），<<

　　FF(a, b, c, d, Mj, s, ti)表示 a = b + ((a + F(b, c, d) + Mj + ti) << s)

　　GG(a, b, c, d, Mj, s, ti)表示 a = b + ((a + G(b, c, d) + Mj + ti) << s)

　　HH(a, b, c, d, Mj, s, ti)表示 a = b + ((a + H(b, c, d) + Mj + ti) << s)

　　II(a, b, c, d, Mj, s, ti)表示 a = b + ((a + I(b, c, d) + Mj + ti) << s)

这四轮（步）是： 

第一轮 

　　FF(a, b, c, d, M0, 7, 0xd76aa478) 

　　FF(d, a, b, c, M1, 12, 0xe8c7b756) 

　　FF(c, d, a, b, M2, 17, 0x242070db) 

　　FF(b, c, d, a, M3, 22, 0xc1bdceee) 

　　FF(a, b, c, d, M4, 7, 0xf57c0faf) 

　　FF(d, a, b, c, M5, 12, 0x4787c62a) 

　　FF(c, d, a, b, M6, 17, 0xa8304613) 

　　FF(b, c, d, a, M7, 22, 0xfd469501) 

　　FF(a, b, c, d, M8, 7, 0x698098d8) 

　　FF(d, a, b, c, M9, 12, 0x8b44f7af) 

　　FF(c, d, a, b, M10, 17, 0xffff5bb1) 

　　FF(b, c, d, a, M11, 22, 0x5cd7be) 

　　FF(a, b, c, d, M12, 7, 0x6b901122) 

　　FF(d, a, b, c, M13, 12, 0xfd987193) 

　　FF(c, d, a, b, M14, 17, 0xa679438e) 

　　FF(b, c, d, a, M15, 22, 0x49b40821) 

第二轮 

　　GG(a, b, c, d, M1, 5, 0xf61e2562) 

　　GG(d, a, b, c, M6, 9, 0xc040b340) 

　　GG(c, d, a, b, M11, 14, 0x265e5a51) 

　　GG(b, c, d, a, M0, 20, 0xe9b6c7aa) 

　　GG(a, b, c, d, M5, 5, 0xd62f105d) 

　　GG(d, a, b, c, M10, 9, 0x02441453) 

　　GG(c, d, a, b, M15, 14, 0xd8a1e681) 

　　GG(b, c, d, a, M4, 20, 0xe7d3fbc8) 

　　GG(a, b, c, d, M9, 5, 0x21e1cde6) 

　　GG(d, a, b, c, M14, 9, 0xc33707d6) 

　　GG(c, d, a, b, M3, 14, 0xf4d50d87) 

　　GG(b, c, d, a, M8, 20, 0x455a14ed) 

　　GG(a, b, c, d, M13, 5, 0xa9e3e905) 

　　GG(d, a, b, c, M2, 9, 0xfcefa3f8) 

　　GG(c, d, a, b, M7, 14, 0x676f02d9) 

　　GG(b, c, d, a, M12, 20, 0x8d2a4c8a) 

第三轮 

　　HH(a, b, c, d, M5, 4, 0xfffa3942) 

　　HH(d, a, b, c, M8, 11, 0x8771f681) 

　　HH(c, d, a, b, M11, 16, 0x6d9d6122) 

　　HH(b, c, d, a, M14, 23, 0xfde5380c) 

　　HH(a, b, c, d, M1, 4, 0xa4beea44) 

　　HH(d, a, b, c, M4, 11, 0x4bdecfa9) 

　　HH(c, d, a, b, M7, 16, 0xf6bb4b60) 

　　HH(b, c, d, a, M10, 23, 0xbebfbc70) 

　　HH(a, b, c, d, M13, 4, 0x2b7ec6) 

　　HH(d, a, b, c, M0, 11, 0xeaa127fa) 

　　HH(c, d, a, b, M3, 16, 0xd4ef3085) 

　　HH(b, c, d, a, M6, 23, 0x04881d05) 

　　HH(a, b, c, d, M9, 4, 0xd9d4d039) 

　　HH(d, a, b, c, M12, 11, 0xe6db99e5) 

　　HH(c, d, a, b, M15, 16, 0x1fa27cf8) 

　　HH(b, c, d, a, M2, 23, 0xc4ac5665) 

第四轮 

　　II(a, b, c, d, M0, 6, 0xf4292244) 

　　II(d, a, b, c, M7, 10, 0x432aff97) 

　　II(c, d, a, b, M14, 15, 0xab9423a7) 

　　II(b, c, d, a, M5, 21, 0xfc93a039) 

　　II(a, b, c, d, M12, 6, 0x655b59c3) 

　　II(d, a, b, c, M3, 10, 0x8f0ccc92) 

　　II(c, d, a, b, M10, 15, 0xffeff47d) 

　　II(b, c, d, a, M1, 21, 0x85845dd1) 

　　II(a, b, c, d, M8, 6, 0x6fa87e4f) 

　　II(d, a, b, c, M15, 10, 0xfe2ce6e0) 

　　II(c, d, a, b, M6, 15, 0xa3014314) 

　　II(b, c, d, a, M13, 21, 0x4e0811a1) 

　　II(a, b, c, d, M4, 6, 0xf7537e82) 

　　II(d, a, b, c, M11, 10, 0xbd3af235) 

　　II(c, d, a, b, M2, 15, 0x2ad7d2bb) 

　　II(b, c, d, a, M9, 21, 0xeb86d391) 

常数ti可以如下选择： 

在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。(4294967296等于2的32次方) 

所有这些完成之后，将A、B、C、D分别加上a、b、c、d。然后用下一分组数据继续运行算法，最后的输出是A、B、C和D的级联。 

当你按照我上面所说的方法实现MD5算法以后，你可以用以下几个信息对你做出来的程序作一个简单的测试，看看程序有没有错误。 

　　MD5 ("") = d41d8cd98f00b204e9800998ecf8427e 

　　MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661 

　　MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72 

　　MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0 

　　MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b 

　　MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") = 

　　d174ab98d277d9f5a5611c2c9f419d9f 

SHA-1算法

在1993年，安全散列算法（SHA）由美国国家标准和技术协会(NIST)提出，并作为联邦信息处理标准（FIPS PUB 180）公布；1995年又发布了一个修订版FIPS PUB 180-1，通常称之为SHA-1。SHA-1是基于MD4算法的，并且它的设计在很大程度上是模仿MD4的。现在已成为公认的最安全的散列算法之一，并被广泛使用。

SHA-1与MD5差异

SHA1对任意长度明文的预处理和MD5的过程是一样的，也即预处理完后的明文长度是512位的整数倍，但是有一点不同，那就是SHA1的原始报文长度不能超过2的次方，然后SHA1生成160位的报文摘要。SHA1算法简单而且紧凑，容易在计算机上实现。

表1列出了对MD5及SHA的比较差异之处。让我们根据各项特性，简要说明其不同。

表1  MD5与SHA1的比较

安全性：SHA所产生的摘要比MD5长32位。若两种散列函数在结构上没有任何问题的话，SHA比MD5更安全。

速度：两种方法都是主要考虑以32位处理器为基础的系统结构。但SHA的运算步骤比MD5多了16步，而且SHA记录单元的长度比MD5多了32位。因此若是以硬件来实现SHA，其速度大约比MD5慢了25％。

简易性：两种方法都是相当的简单，在实现上不需要很复杂的程序或是大量存储空间。然而总体上来讲，SHA对每一步骤的操作描述比MD5简单。

SHA-1哈希算法流程 

对于任意长度的明文，SHA1首先对其进行分组，使得每一组的长度为512位，然后对这些明文分组反复重复处理。

对于每个明文分组的摘要生成过程如下：

    （1）将512位的明文分组划分为16个子明文分组，每个子明文分组为32位。

    （2）申请5个32位的链接变量，记为A、B、C、D、E。

    （3）16份子明文分组扩展为80份。

    （4）80份子明文分组进行4轮运算。

    （5）链接变量与初始链接变量进行求和运算。

    （6）链接变量作为下一个明文分组的输入重复进行以上操作。

    （7）最后，5个链接变量里面的数据就是MD5摘要。

SHA-1算法详解

一。分组过程

对于任意长度的明文，SHA1的明文分组过程与MD5相类似，首先需要对明文添加位数，使明文总长度为448（mod512）。在明文后添加位的方法是第一个添加位是l，其余都是0。然后将真正明文的长度（没有添加位以前）以位表示，附加于前面已添加过位的明文后，此时的明文长度正好是512位的倍数。有一点与MD5不同，那就是SHA1的原始报文长度不能超过2的次方。

经过添加处理的明文，其长度正好为512位的整数倍，然后按512位的长度进行分组（block），可以划分成L份明文分组，我们用Y0，Y1，……YL－1表示这些明文分组。对于每一个明文分组，都要重复反复的处理，这些与MD5是相同的。

对于512位的明文分组，SHA1将其再分成16份子明文分组（sub-block），每份子明文分组为32位，我们使用M[k]（k= 0, 1,……15）来表示这16份子明文分组。之后还要将这16份子明文分组扩充到80子明文分组份，我们记为W[k]（k= 0, 1,……79），扩充的方法如下。

    W t = M t , 当0≤t≤15

    W t = W t-3⊕ W t-8⊕W t-14⊕ W t-16, 当16≤t≤79

    SHA1有4轮运算，每一轮包括20个步骤（一共80步），最后产生160位摘要，这160位摘要存放在5个32位的链接变量中，分别标记为A、B、C、D、E。这5个链接变量的初始值以16进位制表示如下。

    A=0x 67452301

    B=0x EFCDAB

    C=0x 98BADCFE

    D=0x 10325476

    E=0x C3D2E1F0

二。SHA1的4轮运算

    SHA1有4轮运算，每一轮包括20个步骤,一共80步，当第1轮运算中的第1步骤开始处理时，A、B、C、D、E五个链接变量中的值先赋值到另外5个记录单元A′，B′，C′，D′，E′中。这5个值将保留，用于在第4轮的最后一个步骤完成之后与链接变量A，B，C，D，E进行异或操作。

    SHA1的4轮运算，共80个步骤使用同一个操作程序，如下：

其中为逻辑函数，为子明文分组W[t]，为固定常数。这个操作程序的意义为：

将的结果赋值给链接变量A

将链接变量A赋值给链接变量B

将链接变量B循环左移30位赋值位链接变量C

将链接变量C赋值给链接变量D

将链接变量D赋值给链接变量E

SHA1规定4轮运算的逻辑函数如表2所示。

表2  SHA1的逻辑函数

在操作程序中需要使用固定常数（i= 0，1，2，……79），的取值如表3所示：

表3  SHA1的常数K取值表

我们同样举一个例子来说明SHA1哈希算法中的每一步是怎样进行的，比起MD5算法，SHA1相对简单,假设W[1]=0x12345678，此时链接变量的值分别为A=0x67452301、B=0xEFCDAB、C=0x98BADCFE、D=0x10325476、E=0xC3D2E1F0,那么第1轮第1步的运算过程如下。

（1）将链接变量A循环左移5位，得到的结果为：0xE8A4602C。

（2）（2）将B，C，D经过相应的逻辑函数：

（3）将第（1）步，第2步的结果与E，W[0]，和K0相加得：

（4）将B循环左移30位得：(B<<<30)=0x7BF36AE2

（5）将第3步结果赋值给A，A（这里是指A原始结果）赋值给B，步骤4的结果赋值给C，C赋值给D，D赋值给E

（6）最后得到第1轮第1步的结果：

A = 0xB1E8EF2B

B = 0x67452301

C = 0x7BF36AE2

D = 0x98BADCFE

E = 0x10325476

按照这种方法，将80个步骤进行完毕。

第四轮最后一个步骤的A,B,C,D,E输出，将分别与记录单元A′，B′，C′，D′，E′中的数值求和运算。其结果将作为输入成为下一个512位明文分组的链接变量A,B,C,D,E，当进行完最后一个明文分组后，A,B,C,D,E中的数据就是最后散列函数值。