伪随机数生成算法探究

计算机生成的随机数都是伪随机数，必然依赖某个算法。真正的随机过程只能从自然界寻找，真随机数发生器这样的设备通常是基于一些能生成低等级、统计学随机的“噪声”信号的微观现象，如热力学噪声、光电效应和量子现象。

伪随机数生成方法，如js的Math.random生成0到1的左闭右开区间内的随机数，用到的算法一般是线性同余算法。也有人手动实现的随机数生成算法：

var rand = (function(){
  var today = new Date();
  var seed = today.getTime();
  function rnd(){
    seed = ( seed * 9301 + 49297 ) % 233280;
    return seed / ( 233280.0 );
  };
  return function rand(number){
    return Math.ceil(rnd(seed) * number);
  };
})();
console.log(rand(100))
console.log(rand(100))
console.log(rand(100))

这里rnd函数的生成方法就是线性同余算法。种子数字由时间函数产生，这使得最终生成的每个值都近似随机。这种伪随机数生成器叫做线性同余生成器（LCG, Linear Congruential Generator)，几乎所有的运行库提供的rand都是采用的LCG。数字9301、42297、233280这几个数字并不是神仙数字，这是算法的数学要求。该算法形如：

生成的伪随机数序列最大周期m，范围在0到m-1之间。要达到这个最大周期，必须满足

c与m互质
a - 1可以被m的所有质因数整除
如果m是4的倍数，a - 1也必须是4的倍数

以上三条被称为Hull-Dobell定理。

作为一个伪随机数生成器，周期需要足够大，但又不能超过计算机的最大数字限度，以防止溢出错误。可以看到，a=9301, c = 49297, m = 233280这组参数，以上三条全部满足。

从工程的角度来讲，（m-1）a+c的值要（在合理的范围内）足够小，以避免溢出的问题；从安全（实用）性的角度来讲，还要满足良好的随机性。
当然判定一个随机数生成算法的优劣有多种办法如“nist随机性测试”、Knuth’s Spectral Test等方法。以Knuth’s Spectral Test方法为例：

其中每个点代表三个连续的RANDU生成的伪随机数值，可以看到所有伪随机数分布在了15个二维平面上。
在这种要求面前，c的值最好：

是质数（c = 49297就是质数）
接近（1/2-1/6*根号3）*m,(m = 233280时为49297.86460172205)

所以有了这样一些基本的标准，能够选择的参数范围就小了很多，弄个程序跑下Spectral Test，就能得到可选的参数组。

从中选取一组3个值作为线性同余算法的参数，就可以生成一个周期足够大的伪随机数数列。

理论上算法的本质是数学问题，破解一个算法就是求解一个复杂数学问题。正如知乎答案所说的“由于随机数是密码学中最为重要的安全组件，你可以参考相应密码学文献来生成随机数和伪随机数。从理论上说，任何伪随机数的生成方案破解等同于求解一个数学难题，从然后实践上讲，首先应该通过nist测试包。已经记不太清楚，大致需要通过20种不同的攻击测试。如果你是想用而已，可以使用一些现成的加密算法库来用。如果是想自己弄，建议还是到此为止。各类无线通信协议的安全漏洞首先都是从随机数中冒出来的。随机数是密码学的一个大坑，都搞了几十年了。不懂就别弄，后果很严重”。

主要引用链接：
1.https://www.zhihu.com/question/22818104 作者知乎猫杀
2.https://www.zhihu.com/question/20222653/answer/31419120 作者知乎白喵黑咪

伪随机数生成算法探究

评论 0

发表评论