随机数产生算法和常见库的随机数算法

[hxndg]

前两天被人问了一个随机数产生算法，然后我当时没反应过来，愣住了。今天翻了下笔记整理了一下。因为 V 站 markdown 不支持公式，所以不贴公式了，自己搜索吧

1 随机数产生算法，常规方法

一般来说怎么衡量随机数的随机性呢？考察两个方面：

• 是不是均匀分布，也就是
• 是否满足独立性，也就是不能由其它的数字推导出来另一个数字。

目前常见的伪随机数产生器是线性同余算法，线性同余法也有很多变种，比方说使用离散对数 /大整数分解难题继续拓展

2 基于密码算法的随机数产生器

除了上面的常规随机数产生方法，还有基于加密算法的随机数算法。

• 循环加密，主密钥保密，计数器循环加密并计算，可以用来产生随机数。
• DES 的 OFB 反馈，
• ANSI X9.17 伪随机数产生器，3des+日期+种子

3 随机比特产生器

• BBS 产生器：这个的难度是基于大整数分解难题。

• Rabin 产生器：k 是一个大于等于 2 的整数，在[2^k，2^{k+1}]之间选取两个奇素数，p,q，有 p=q=3(mod 4)，利用这两个 p/q 进行计算

• 离散指数比特序列产生器

4 crypto++的随机数实现

crypto++的随机数同样需要先 seed，而且不是线程安全的实现。

crypto++的随机数算法比较多：

• LC_RNG is a Linear Congruential Generator 。也就是线性同余方法
• RandomPool is a PGP style random pool，实际上是 AES 加密算法
• AutoSeededX917RNG，就是上面的 ANSI X9.17 算法
• NIST 算法

5 openssl 的随机数实现

Openssl 内部实现了足够安全的随机数产生器，使用的算法包括 NIST, ANSI X9 committee (X9.17 and X9.31)等算法。

默认情况下 openssl 使用 md5 作为随机数产生函数。一般情况下 openssl 使用 /dev/urandom 作为随机数产生器的种子源。设置好 seed 之后，可以通过软算方式获得产生的密钥。

如果你是 openssl1.0.1，使用的 cpu 是 i5/i7 三代 cpu 也可以使用硬件随机数产生器。