如何安全存储密码都不知道，难怪我会被面试官吊打咯！( 四 ) _安全存储密码

答案是肯定的，但是彩虹表对于明文的内在联系是建立在数学的基础上的，我们来继续探讨，彩虹表的H函数和R函数。
5.3 H函数和R函数各位读者坐稳扶好打起精神，H函数和R函数是理解彩虹表的关键所在。
先解释一下H函数和R函数分别是什么及其内在联系：

H函数
H函数也就是哈希函数，实现明文到密文的单向不可逆转换；
R函数
R函数理解为Reduction function，这里看到Reduction这个单词，其实在之前P和NP问题的文章中，我们有接触到这个单词，归约/约化的意思。
H函数和R函数的关系
一句话概括：H函数的定义域是R函数的值域，H函数的值域是R函数的定义域，但是R并不是H的反函数，因为H函数是不可逆的。

举个例子：
假如密码范围是长度在10个以内的字母数字组合，不区分大小写，假设输入明文为abcdfg,则存在如下关系：

// 哈希函数H实现明文向密文的映射H(abcdfg)=AB8GFTYG// 归约函数R实现密文向'明文相同格式字符串'的映射R(AB8GFTYG)=erfdtk

特别地，R函数将H函数的输出作为输入，也就是H的值域作为R的定义域，R函数生成了erfdtk，这个新明文字符串并不是原始输入的明文，但是格式却是相同的。
这里可以隐约感受到R函数的重要性，它可以将相同格式的明文生成的密文作为输入，进而输出相同格式的新明文，从而产生一个相同格式的明文的集合链条，也就是找到了一类有内在联系的明文。
换句话说，我们可以只存储一个明文，中间把多个H-R进行组合串联起来，从而形成一个明文-密文的映射集合，也就是空间减少了但是信息量并没有减少，这么看来R函数确实很cool 。

画外音：这里提到的R函数生成相同格式的新明文，"相同格式"这个词语的理解不好拿捏，需要借助数学手段来实现，我们暂且简单理解为长度和组合方式类似吧！

5.4 预计算哈希链和R冲突在彩虹表出现之前有种预计算哈希链集合，就是多组哈希链组成的明文-密文集合，这里简单提一下。
前面提到了一组H-R函数，实际上只有多组H-R函数才有实际意义，比如有2000组H-R组合，那么我们将有2000对明文-密文的映射，但是只需要存储非常小的一部分即可，这也就是我们要说的哈希链，如图为2组H-R函数组成的哈希链：

文章插图

上图展示的两组H-R函数中的R都是相同的，由于哈希冲突的存在我们并不能表示全部独立的明文，这样空间存储率就打折了，看下这个图：

文章插图

上面两条哈希链EDEDED和FEDECE经过R函数计算分别得到222和333，222经过H函数得到FEDEFE，再经过R函数也得到了333，这样两条哈希链就存在重叠部分，也就是R函数出现了冲突。
// 哈希链中的R函数冲突R(FEDECE)=333R(FEDEFE)=333更重要的是这种冲突是不好被发现的！
为啥这么说呢，因为实际中只存储哈希链中的首尾两个明文，对于上图中中间发生了R冲突，但是从重合起点看上面的链比下面的链位置更靠后，下面的链会继续进行余下的H-R函数最终生成尾部明文是555，然而上面的链生成尾部明文是444，在实际存储中是这样的：
//哈希链1111->444//哈希链2454->555也就是假如你设计的k=2,也就是每组2个H-R函数，两个哈希链可以表示8个明文，但是实际上333和444是存在重复的，从而只有6个有效不同的明文，由于尾部明文的不同，这种重叠是无法被检测的。
这么看来拥有个分布均匀的R函数是多么重要，但是在几千组H-R函数中要求完全没有冲突是非常难的，于是出现了多组R函数的新形式。