一文读懂基于单向散列函数的随机数

随机数

上回说到，小明制作了一个特殊的日记本，在每次输入正确的密码之后，都会随机的生成下一个密码，但是呢，由于小明设计随机数算法选的不太好，这让小红给钻了空子，这时候小明心里别提多伤感了，这。。。这我的日记不就相当于直接公开了吗，这是要社死的节奏啊，不行不行，我要换一个新的方法，这时候，小明刚好学完了密码学当中的散列函数，心想，这我要是直接用散列函数的输出作为随机密码的生成，这不就成了，哈哈，这时候小明心里别提有多美了，于是乎，小明设计出了如下的随机数生成算法。

小明设计的基于单向散列函数的随机数生成器

具体小明设计的伪随机数生成器步骤如下：

1. 先挑一个种子，作为随机数生成器的输入
2. 用单向散列函数计算内部状态的散列值
3. 将散列值作为伪随机数输出
4. 用刚才第三步生成的散列值作为新的内部状态
5. 重复执行第二步到第四步，然后不断生成新的伪随机序列

具体小明设计的方案呢，可以如下图所示:

小明设计的伪随机数生成器

看着自己刚设计出来的新的日记本，小明心里笑开了花，心想，这时候，小红你就没办法找到下一个密码了吧。

可是呢，没过多久小红就找到了密码生成的规律，然后呢，你懂得。。。

看到这里，各位读者发现小明所设计的伪随机数生成算法有什么问题吗？答案将在文末揭晓。

一般的基于单向散列函数的伪随机数生成器

下面，我们来看一下一个一般的基于散列函数的伪随机数生成算法的过程。

1. 选择一个种子作为生成器的初始状态(或者可以理解成为这是一个计数器)
2. 用单向散列函数计算内部状态的散列值, 这一块其实和小明设计的是一样的
3. 将散列值作为随机数输出, 这一步也和小明的想法一样
4. 将计数器+1， 这里和小明设计的是有区别的
5. 重复执行第二步到第四步，然后不断生成新的伪随机序列, 这里和小明的依然一样

具体的过程，可以看做是下图:

基于散列函数的伪随机数生成器

这里要注意，对于任何时候，种子都应该是保密的，如果攻击者拿到了种子，自然而然的就可以直接推导出所有的随机序列了，如果攻击者不知道种子，由于散列函数的单向性，攻击者无法去推导出来散列函数之前的值，也就无法对计数器进行加一操作，自然而然的无法去预测出来下一个随机数生成的值。

答案

看到这里，大家应该可能已经发现小明设计的伪随机数生成器的缺点在哪了，就是攻击者可以直接去预测下一次随机数生成的值，和常规的基于散列函数的伪随机数不同，对于小明的设计是可以拿到内部状态的。

小结

本文呢，简单的介绍了一下基于散列函数的伪随机数生成器的算法，整体算法还是比较容易理解的，对于伪随机数生成器的整体结构而言，无论是什么算法，其实都是相似的。

代码实现

对于这次代码呢，就不给出具体的实现了，这个比较简单，写个伪代码吧

seed = init_state; // 初始化的种子
function hash_based_prng() {
    output = hash(seed); // 计算内部状态作为输出
    seed += 1; // 计数器加一
}