V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
hxndg
V2EX  ›  程序员

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

  •  
  •   hxndg · 2021-08-24 17:20:40 +08:00 · 702 次点击
    这是一个创建于 948 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前两天被人问了一个随机数产生算法,然后我当时没反应过来,愣住了。今天翻了下笔记整理了一下。因为 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 也可以使用硬件随机数产生器。

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2879 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 13:09 · PVG 21:09 · LAX 06:09 · JFK 09:09
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.