Last Updated: 2023-11-20 14:10:41 Monday
-- TOC --
哈希算法，这两个字取自Hash，也叫摘要算法，或者散列算法，或者杂凑算法，在计算机和通信领域，有非常广泛的应用，比如数字签名和比特币！
哈希算法也叫散列算法，一般来说满足这样的关系：f(data)=key，输入任意长度的data数据，经过哈希算法处理后输出一个固定定长的数据key。同时，计算过程不可逆，无法由key逆推出data！由于哈希计算得到是固定长度的数据，因此哈希算法也被称为摘要算法，对一段任何长度的信息，计算一个短小且长度固定的值（摘要）。
哈希算法的初衷是用来加速数据存取。计算机领域内的大多数查找算法都与存储数据的规模呈正相关，用于衡量查找算法效率的量我们称为平均查找长度，一般情况下，比较优秀的查找算法的平均查找长度也不会小于 \(O(\log_2{N})\)，而且数据还要有序存放，比如二分查找算法。
如果有一个data数据集，经过哈希算法处理后得到key数据集，然后将key与原始数据进行一一映射，这样就得到了一个哈希表（Hash Table）。一般来说哈希表T符合T[key]=data这种形式。哈希表是一个查找复杂度为\(O(1)\)的数据表！（理想或一般情况下，非最坏情况）
哈希表的好处是，当原始数据较大时，我们可以用哈希算法处理得到定长的哈希值key，这个key相对原始数据要小得多，我们就可以用这个较小的key数据集来做索引，达到快速查找的目的。
稍微想一下就可以发现，既然输入数据不定长，而输出的哈希值却是固定长度的，这意味着哈希值是一个有限集合，而输入数据则可以有无穷多个。那么建立一对一关系显然不现实。所以碰撞（不同的输入数据对应了相同的哈希值）是必然会发生的。一个成熟的哈希算法会有较好的抗冲突性（一般key越长，抗碰撞性就越好）。同时在实现哈希表的结构时也要考虑到如何去解决哈希冲突。（计算并哈希表的碰撞概率）
本文后续介绍的哈希算法，主要用于安全领域，而非数据结构和算法领域...
先将信息应用到某个哈希算法，得到一个摘要，然后用发送者的私钥对摘要加密，得到的就是数字签名。信息接收者先用发送者的公钥解密，然后使用相同的哈希算法得到摘要，将两份摘要进行对比，如果一样，就说明信息没有被篡改，并且证明了发送者的身份！
数字签名有两个作用：
安全的前提是：私钥不可丢失！
MD5，Message-Digest Algorithm 5（信息-摘要算法5）。
MD5是计算机广泛使用的杂凑算法之一，主流编程语言都有MD5的实现。将输入数据运算为一个固定长度值是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。
1992年8月Ronald L. Rivest在向IETF提交了一份重要文件中，描述了这种算法的原理，由于这种算法的公开性和安全性，在90年代被广泛应用，用以确保资料传递无误等。MD5由MD4、MD3、MD2改进而来，主要是增强算法复杂度和不可逆性。
现在MD5也有弱点。MD5较老，散列长度为128位（16字节），随着计算机运算能力的提高，找到碰撞是可能的。因此，在安全要求很高的场合，不推荐使用MD5。
2004年，中国数学家王小云证明MD5算法可以产生碰撞。2007年，Marc Stevens，Arjen K. Lenstra和Benne de Weger进一步指出通过伪造软件签名，可重复性攻击MD5算法。研究者使用前缀碰撞法（chosen-prefix collision），使程序前端包含恶意程序，利用后面的空间添上垃圾代码凑出同样的MD5散列值。
2008年，荷兰埃因霍芬技术大学的科学家成功把2个可执行文件进行了MD5碰撞，使得这两个运行结果不同的程序被计算出同一个MD5值，显然，这样会为病毒的传播打开方便之门。
一般128位的MD5散列值被表示为32位十六进制数字，以下是一个43位长ASCII字母列的MD5散列：
MD5("The quick brown fox jumps over the lazy dog")
= 9e107d9d372bb6826bd81d3542a419d6
即使在原文中作一个小变化（比如用c取代d），其散列也会发生巨大的不可预测的变化：
MD5("The quick brown fox jumps over the lazy cog")
= 1055d3e698d289f2af8663725127bd4b
空字符串的MD5散列为：
MD5("")
= d41d8cd98f00b204e9800998ecf8427e
下面用Python计算MD5，代码所示计算模式，也适用于其它Hash算法。
>>> import hashlib
>>> hashlib.md5(b'').digest()
b'\xd4\x1d\x8c\xd9\x8f\x00\xb2\x04\xe9\x80\t\x98\xec\xf8B~'
>>> hashlib.md5(b'cs.pynote.net').digest()
b'7s\xb0ucc\xa2\xc1\xf51\xc8a\x8c\x13c\xda'
hashlib库，使用了digest这个名称的接口来实现提取hash值。>>> hashlib.md5(b'').hexdigest()
'd41d8cd98f00b204e9800998ecf8427e'
>>> hashlib.md5(b'cs.pynote.net').hexdigest()
'3773b0756363a2c1f531c8618c1363da'
hexdigest接口自动将hash值转换成hex string。另一种风格如下：
>>> h = hashlib.md5()
>>> h.update(b'cs.')
>>> h.update(b'pynote.')
>>> h.update(b'net')
>>> h.digest()
b'7s\xb0ucc\xa2\xc1\xf51\xc8a\x8c\x13c\xda'
>>> h.hexdigest()
'3773b0756363a2c1f531c8618c1363da'
update并不是输入新的content，而是追加。SHA，Secure HAsh。
SHA安全散列算法能计算出一个信息所对应到的长度固定的字串（又称讯息摘要）。且若输入的讯息不同，它们对应得到不同字串的机率非常高，而SHA算法是FIPS所认证的五种安全杂凑算法的统称。
这些SHA算法之所以称作安全，是基于以下两点（根据官方标准的描述）：
SHA家族有五个算法，分别是SHA-1, SHA-224, SHA-256, SHA-384, 和SHA-512，它们由美国国家安全局(NSA)设计，并由美国国家标准与技术研究院（NIST）发布，是美国的政府标准。后四者有时并称为SHA-2。
SHA-1和SHA-2是该算法的两个不同版本，它们在算法构造上（散列结果是怎样从原始数据创建出来的）和输出位数（输出的散列值的长度）上都不相同。你应该把SHA-2看作是SHA-1的继承者，因为这是一个整体上的改进。
MD5 --> SHA-1 --> SHA-2
SHA-1在许多安全协定中广为使用，包括 TLS 和 SSL、PGP、SSH、S/MIME和IPsec，曾被视为是MD5的后继者。但SHA-1的安全性如今被密码学家严重质疑。
SHA-1算法生成是160位（20字节）的散列值。
SHA-1已被攻破，建议使用SHA-256！Google已经实现了对SHA-1的碰撞攻击，可以创造两个内容不同，但Hash值相同的文件。此外，一些安全公司也认为SHA-1可能存在一些缺陷。但目前来说，产生SHA-1碰撞攻击的代价非常高，需要大量的计算能力，如果购买亚马孙云服务的计算力用于攻击，可能需要几十万美元的费用。
SHA-256算法有多少种不同的散列结果？如果一个散列算法能够为每一个可能的输入产生唯一的散列值，那么会有多少个可能的散列结果呢？
一个比特位有两个可能的值：0和1。唯一散列值的可能数量可以表示为，可能的值的数量与位数的乘方。对于SHA-256算法，就有 \(2^{256}\) 种可能的组合。
所以，\(2^{256}\) 种组合。这是多少呢？这是一个巨大的数字。请认真对待！！它使得像万亿和亿亿亿（一亿的三次方）这样的数字相形见绌。\(2^{256}\) 远远超过了世界上沙粒的数量。
SHA-256算法生成是256位（32字节）的散列值。
可能的散列值的数量越大，产生相同散列结果的可能性就越小。从技术上讲，有无数个可能的输入，但是输出的数量是有限的。因此，最终每一个散列算法，包括安全的算法，都会产生冲突。
比特币使用SHA-256算法，当算力继续提升，会不会有一天就....
Python的hashlib库中的各种hash算法接口，使用模式都一样。
>>> hashlib.sha256(b'cs.pynote.net').digest()
b'\xc6\x94<Z\xe9\xe6\x13\xc4<\x90\x01>R\x17\xf8\xaa\xe4\xde\x08\xf0"\xdf\xa7\x06^\xe0\xe3U?\xeeO\xfa'
>>> hashlib.sha256(b'cs.pynote.net').hexdigest()
'c6943c5ae9e613c43c90013e5217f8aae4de08f022dfa7065ee0e3553fee4ffa'
>>>
>>> sha256 = hashlib.sha256()
>>> sha256.update(b'cs.')
>>> sha256.update(b'pynote.')
>>> sha256.update(b'net')
>>> sha256.digest()
b'\xc6\x94<Z\xe9\xe6\x13\xc4<\x90\x01>R\x17\xf8\xaa\xe4\xde\x08\xf0"\xdf\xa7\x06^\xe0\xe3U?\xeeO\xfa'
>>> sha256.hexdigest()
'c6943c5ae9e613c43c90013e5217f8aae4de08f022dfa7065ee0e3553fee4ffa'
网站的数据库管理着用户的ID及口令，口令以MD5等HASH加密后的形式存在。如果数据库泄露，HASH值被攻击者获取，黑客可以通过对此HASH值进行暴力破解（比如查找密码字典），以获取用户的口令。由于存在很多用户使用相同密码的情况，这些用户密码的hash值也是一样的，一个用户的密码hash被破解，其它相同hash值全都被破解。
通过加入盐值(salt)，即盐化，可以很好的降低这种攻击带来的危害。
盐值是一组随机的字符串，通过插入口令后（与密码进行某种形式的混合），再进行HASH，这样即使是相同的口令，插入不同的盐值后生成的HASH值也是不相同的。
具体的流程是，用户注册时：
身份验证时：
如果数据库泄露，攻击者能够拿到hash值和salt，但是不知道salt插入用户口令的方式，暴力破解hash后，得到的是password和salt的混合物。也许能够通过sale值分离出password，但相同password因为salt不同，而导致hash不同，增加了破解难度，降低了破坏程度。
看到一个网站：https://www.cmd5.com/
本站针对md5、sha1等全球通用公开的加密算法进行反向查询，通过穷举字符组合的方式，创建了明文密文对应查询数据库，创建的记录约90万亿条，占用硬盘超过500TB，查询成功率95%以上，很多复杂密文只有本站才可查询。
使用海量的存储空间，来实现部分hash值的反向查询，即实现部分破解。
此网站的盈利模式为，部分查询需要付费。
本文链接：https://cs.pynote.net/se/jjm/202110235/
-- EOF --
-- MORE --