1.1 哈希算法

1.1.1 Hash的定义

hash （哈希或散列）算法是IT领域非常基础也非常重要的一类算法。可以将任意长度的二进制值（明文）映射为较短的固定长度的二进制值（Hash 值），并且不同的明文很难映射为相同的 Hash 值。hash 值在应用中又被称为数字指纹（fingerprint）或数字摘要（digest）、消息摘要。

例如计算一段话“hello blockchain”的 MD5 hash 值为：78e6a8bcdef7a4a254c16054b082c783

这意味着只要对某文件进行 MD5 Hash 计算，得到结果为 78e6a8bcdef7a4a254c16054b082c783，这就说明文件内容极大概率上就是 “hello blockchain”。可见，Hash 的核心思想十分类似于基于内容的编址或命名。

一个优秀的 hash 算法，在给定明文和 hash 算法的情况下，可以在有限时间和有限资源内能计算出 hash 值。在给定（若干） hash 值的情况下，很难（基本不可能）在有限时间内逆推出明文。即使修改一点点原始输入信息，也能对hash值产生巨大的改变。不同的输入信息几乎不可能产生相同的hash值。

1.1.2 流行的哈希算法

目前常见的 Hash 算法包括 Message Digest（MD）系列和 Secure Hash Algorithm（SHA）系列算法。

MD 算法主要包括 MD4 和 MD5 两个算法。MD4（RFC 1320）是 MIT 的 Ronald L. Rivest在 1990 年设计的，其输出为 128 位。MD4 已证明不够安全。MD5（RFC 1321）是 Rivest于 1991 年对 MD4 的改进版本。它对输入仍以 512 位进行分组，其输出是 128 位。MD5 比MD4 更加安全，但过程更加复杂，计算速度要慢一点。MD5 已于 2004 年被成功碰撞，其安全性已不足应用于商业场景。

SHA 算法由美国国家标准与技术院（National Institute of Standards and Technology，NIST）征集制定。首个实现 SHA-0 算法于 1993 年问世，1998 年即遭**。随后的修订版本 SHA-1 算法在 1995 年面世，它的输出为长度 160 位的 Hash 值，安全性更好。SHA-1 设计采用了 MD4 算法类似原理。SHA-1 已于 2005 年被成功碰撞，意味着无法满足商用需求。为了提高安全性，NIST 后来制定出更安全的 SHA-224、SHA-256、SHA-384，和 SHA-512算法（统称为 SHA-2 算法）。新一代的 SHA-3 相关算法也正在研究中。

目前认为 MD5 和 SHA1 已经不够安全，推荐至少使用 SHA-256 算法。比特币系统中就是使用SHA-256哈希算法。

SHA-3算法，之前被命名为Keccak算法。Keccak的输出长度分别有：512、384、256、224

SHA-3并不是要取代SHA-2，因为SHA-2目前并没有出现明显的弱点。由于对MD5出现成功的**，以及对SHA-1出现理论上**的方法，NIST感觉需要一个与之前算法不同的、可替换的加密杂凑算法，也就是现在的SHA-3。区块链中的以太坊系统就是使用Keccak256算法。

下面列举数字1经过hash算法后形成的密文。

md5('1')，加密后长度为128位，16字节 。密文如下所示。                  

c4ca4238a0b923820dcc509a6f75849b  //32位16进制数字

SHA1('1')，加密后长度为160位，20字节。密文如下所示。

356a192b7913b04c54574d18c28d46e6395428ab     //40位16进制数字

RIPEMD-160('1')，加密后长度为160位，20字节。密文如下所示。                 

c47907abd2a80492ca9388b05c0e382518ff3960  //40位16进制数字

SHA256('1')，加密后长度为256位，32字节。密文如下所示。

6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b //64位16进制数

Keccak256('1')，加密后长度为256位，32字节。密文如下所示。

c89efdaa54c0f20c7adf612882df0950f5a951637e0307cdcb4c672f298b8bc6 //64位16进制数

1.1.3 Hash与加密解密的区别

Hash是将目标文本转换成具有相同长度的、不可逆的杂凑字符串，而加密（Encrypt）是将目标文本转换成具有不同长度的、可逆的密文。如图13.1所示。

图1.1 哈希与加密

选择哈希（Hash）与加密（Encrypt）的基本原则有如下两点。

l 如果被保护数据仅仅用作比较验证，在以后不需要还原成明文形式，则使用哈希；

l 如果被保护数据在以后需要被还原成明文，则需要使用加密。

对简单哈希（Hash）的攻击，主要有寻找碰撞法和穷举法。

1. 寻找碰撞法

目前对于MD5和SHA1并不存在有效地寻找碰撞方法。

我国杰出的数学家王小云教授曾经在国际密码学会议上发布了对于MD5和SHA1的碰撞寻找改进算法，但这种方法和“**”相去甚远。该理论目前仅具有数学上的意义，她将**MD5的预期步骤降低了好几个数量级，但对于实际应用来说仍然是一个天文数字。

2. 穷举法（或暴力**法）

通俗来说，就是在一个范围内，如从000000到999999，将其中所有值一个一个用哈希算法哈希，然后将结果和杂凑串比较，如果相同，则这个值就一定是源字串或源字串的一个碰撞，于是就可以用这个值非法登录了。

穷举法看似笨拙，但目前几乎所有的MD5**机或MD5在线**都是用这种穷举法。纠其缘由，就是相当一部分口令是非常简单的，如“123456”或“000000”。穷举法是否能成功很大程度上取决于口令的复杂性。因为穷举法扫描的区间往往是单字符集、规则的区间，或者由字典数据进行组合，因此，如果使用复杂的口令，例如“[email protected]#$%^&*()”这种口令，穷举法就很难奏效了。

1.1.4 SHA256

SHA-256算法输入报文的最大长度不超过2^64 bit，产生的输出是一个256-bit的报文摘要。SHA256算法步骤如下。

（1）step1:附加填充比特。

对报文进行填充使报文长度与448 模512 同余（长度=448 mod 512）,填充的比特数范围是1 到512，填充比特串的最高位为1,其余位为0。就是先在报文后面加一个 1，再加很多个0，直到长度满足mod 512=448.为什么是448，因为448+64=512. 第二步会加上一个 64bit的原始报文的 长度信息。

（2）step2:附加长度值。

 将用64-bit 表示的初始报文（填充前）的位长度附加在步骤1的结果 后（低位字节优先）。

（3）step3:初始化缓存。

使用一个256-bit 的缓存来存放该散列函数的中间及最终结果。该缓存表示为A=0x6A09E667 , B=0xBB67AE85 , C=0x3C6EF372 , D=0xA54FF53A, E=0x510E527F , F=0x9B05688C , G=0x1F83D9AB , H=0x5BE0CD19 。

（4）step4:处理512-bit（16 个字）报文分组序列。

 该算法使用了六种基本逻辑函数，由64 步迭代运算组成。每步都以256-bit 缓存值ABCDEFGH 为输入，然后更新缓存内容。