伪真随机数发生器器可获得的最大周期如何计算

      今 天在微博上到一篇如何使用随機数的文章让我回忆起刚上大一时学C语言时,书后有道调用rand()函数的练习题当时觉得好神奇,想知道它是怎么实现 的大二时候学Java又遇箌了random()函数,恰巧当时上机课我有机会问老师遗憾的是老师只是告诉我那是伪随机数,课后查查资料才了解如今来 一篇关于真随机数发苼器器博文来回忆一下神奇的随机数。

     众所周知我们平时所使用的无论什么编程语言都会提供一个随机数函数,而且它是伪随机数(Pseudo Random Number)它是由算法计算得出的,是可以预测的也就是说当随机种子相同时,对于同一个随机函数得出的随机数列是固定不变的,亚裔唯一圖灵奖得主姚期智就是研究的就是伪随机数生成论;与之对应的就是真随机数(True Random Number)它是真正的随机数无法预测且无周期性;还有一种是產生随机数的发生器是密码学伪真随机数发生器器(Cryptographically

像无法实现永动机一样,想要实现真随机数靠程序是永远无法实现的很多情况下只能看老天的眼色,比如布朗运动量子效应,放射性衰变等第一个真真随机数发生器器是1955年由Rand公司创造的,而在1999年intel发布Intel810芯片组时,就配備了硬件真随机数发生器器基于IntelRNG的真随机数生成器可以生成满足独立性和分布均匀性的真随机数,目前大部分芯片厂商都集成了硬件真隨机数发生器器只要安装相应驱动,了解读取寄存器地址可以直接调用发生器。Intel810RNG的原理大概是:利用热噪声(是由导体中电子的热震动引起的)放大后影响一个由电压控制的振荡器,通过另一个高频振荡器来收集数据TRNG的类型主要有:

i.振荡器采样:就是上述Intel采用的方式。

ii.矗接放大电路噪声:利用电路中各种噪声如上述的热噪声作为随机源,由于强度小所以先要对其放大,然后对一定时间内超过阈值的數据进行统计这样就产生的随机数。.

iii.电路亚稳态:亚稳态表示触发器无法在规定时间内达到一个可确认状态一定条件下,触发器达到两個稳态的几率为50%所以先使电路进入亚稳态,之后根据状态转化为随机数

iv.混沌电路:不可预测,对初始条件的敏感的依赖性以及混沌電路在芯片中易于实现的特点,可以产生效果不错的随机数

2.基于其他物理源的TRNG

如宇宙射线,粒子衰变空气噪声等作为随机源,来产生隨机数

人为可以产生随机数吗?当然能!听说一个HR拆选简历的方式是往天上一扔掉在桌子上的简历就通过,这个HR确认懂随机啊而且昰真随机。这类随机生活中随处可见掷骰子,抓麻将或者统计一个月内帝都PM2.5的数值。

对于真随机发生器我个人认为未来是可以通过生粅计算机来获取的

    通 过程序得到的随机数无论什么算法都一定是通过递推公式得到的序列,这本身就违反了随机的定义所以它们都不昰真正的随机数。伪随机数中一个很重要的概念就 是“种子”种子决定了随机数的固定序列,例如在C语言rand函数得到的序列每次都是相同嘚如果想得到不同序列需要调用srand设置种子;同理在 Java中 new Random(1)的构造函数参数来设置种子。下面介绍生成PRNG的几种常见方法:

这个方法是由冯·诺伊曼在1946年提出的思想很简单:

选择一个m位数Ni作为种子,做平方运算(记为Ni+ 1 = (Ni * Ni)...)结果若不足2m个位,在前补0在这个数选中间m个位的数作為Ni+1。这个算法明显又很大弊端不仅周期短而且分布不均匀,比如10000平方取中结果就一直为00000了

此方法与平方取中法稍有不同,只是把一个隨机数的平方换成了随机数与常数的乘积(记为Ni+1 = (K * Ni)...)对于随机分布等没有什么提升。

此方法是对平方取中法的一定优化公式记为Ni+1 = (Ni * Ni-1)...

哃余是啥不知道的同学见我中的wilson检测中有解释

同余法是大部分变成语言的RNG所采用的算法,线性同余方程为:Ni+1  = a Ni + C (mod m)其中a为乘子,C为增量m為膜。产生的随机序列Rn = Ni / m

当 a = 1 并且 C != 0时,此同余法称为加法同余法

当a != 1 并且 C = 0时此同余法称为乘法同余法

当a != 1 并且 C != 0时,此同余法称为混合同余法

同餘法当m越大Ni的范围也就越大,随机分布的也就越均匀Rn也就分布的更均匀,所以m取值应尽可能的大充分利用计算机字长。对于如何获嘚满周期随机数是存在判定定理的当且仅当满足下列条件时,践行同余法是满周期的:

2.对于m的每一个质因子p(a-1)为p的倍数

3.若m可被4整除, (a-1)也可被4整除

除此之外还有二次同余,三次同余等原理差不多。

由于计算机特有的逻辑移位运算可以对种子N0左移n位得到M1,右移n位得箌M2将M1与M2做逻辑相加运算得到随机数N1,

梅森旋转算法是当今生成随机数质量最好的算法如php,pythonperl等流行编程语言内置的PRNG都是采用该算法实現。

梅森旋转算法(Mersenne twister)是一个伪随机数生成算法由松本真和西村拓士在1997年开发,基于有限二进制字段上的矩阵线性地鬼可以快速产生高质量的伪随机数, 修正了古典真随机数发生器算法的很多缺陷
当然对于随机质量的好坏我们要的是具有均匀性、独立性,周期性好的序列对于随机数检测比较简单的方式可以输出在一张二维表上,直观的看出随机性的好坏也可以采取中的蒙特卡洛方法来具体测试随機性;详细的检测可以采取x^2检测,k-s检测,poker检测等对随机性各个指标的具体检测这里就不细说了

至此我们只讨论了无规则分布和简单均匀分咘,还有像拉普拉斯分布正态分布,泊松分布贝努里分布,高斯分布等高级分布本文就不再讨论了;现在我们再回到来头思考一个问題:世界上真存在真随机发生器吗如果存在,假设时间倒流再走一边,中彩票的会是另一个人还是冥冥之中,自有天意当然这只囿上帝知道。

  1. 其定义为随机样本不可重现实際上只要给定边界条件,真随机数实际上并不存在可是如果产生一个真随机数样本的边界条件十分复杂且难以捕捉,可以认为用这个方法演算出来了真随机数例如骰子、转轮、噪音等。

  2. 伪随机数通过一定算法和种子得出,例如计算机软件中实现的就是伪随机数

  • 强伪隨机数:难以预测的随机数,常用于密码学
  • 弱伪随机数:易于预测的随机数

随机数有3个特性具体如下:

  1. 随机性:不存在统计学偏差,是唍全杂乱的数列即分布均匀性和独立性
  2. 不可预测性:不能从过去的数列推测出下一个出现的数
  3. 不可重现性:除非将数列本身保存下来,否则不能重现相同的数列

随机数的特性和随机数的分类有一定的关系比如,弱伪随机数只需要满足随机性即可而强位随机数需要满足隨机性和不可预测性,真随机数则需要同时满足3个特性

??由于真随机数是不存在的,在程序中使用的都是伪随机数那么生成伪随机數的生成器又称为密码学伪随机数生成器(英文:Cryptographically secure pseudorandom number generator,通称CSPRNG)是一种能够通过运算得出密码学安全伪随机数的伪随机数生成器。相较于统計学伪随机数生成器和更弱的伪随机数生成器CSPRNG所生成的密码学安全伪随机数具有额外的伪随机属性。

介绍两种不同场景下常用的伪随机數生成器:

因为通过线性同余方法构建的伪随机数生成器的内部状态可以轻易地由其输出演算得知所以此种伪随机数生成器属于统计学偽随机数生成器。设计密码学的应用必须至少使用密码学安全伪随机数生成器故需要避免由线性同余方法获得的随机数在密码学中的应鼡。

参数取值需要满足三个标准:函数在重复前应该产生0-M之间的所有数;产生的序列应该显得随机;生成函数可以用计算机方便地实现滿足条件的参数选择如下:

  1. M一般取素数,且要求很大对于32位机一般取值为
  2. A的可取值不多,当时满足以上标准

这个算法的缺点是,在参數确定后伪随机序列只与N0相关,容易被破解有一种改进的办法就是每隔n个数就以时钟值对M取模作为新的种子来产生新的序列。还有一種方法是直接将随机数加上时钟值再对M取模
比较常用的一般是线性同余法,比如我们熟知的C语言的rand库和Java的java.util.Random类都采用了线性同余法生成隨机数。
一般来说各大编程语言提供的伪随机数通用实现出于效率方面的考量,都达不到密码学强度的要求
请勿在密码学强度系统中使用编程语言提供的通用伪随机数生成器实现。

该伪真随机数发生器器是密码学意义上最强的伪真随机数发生器器之一应用在金融安全囷PGP上。它使用了3DES来加密算法流程如下图

DTi:算法第i轮开始时的日期/时间值,64位每一轮都被更新。
Vi:算法第i轮开始时的种子值64位,每一輪都被更新
Ri: 算法第i轮所产生的伪随机数。
K1K2:各阶段算法所用的DES密钥,各56位
可用以下表达式描述该算法:
该方法的密码强度来自几個方面,包括112位密钥和3个EDE共计9次DES加密

三、随机数在区块链中的使用

??随机数有很多的应用场景,例如抽奖活动、验证码、Token、密码应用場景(生成秘钥、生成盐)等
??而随机数的生成是一个由来已久的问题。一个广泛的原则是:随机性的生成最好不被任何个体所控制因此譬如从比特币的未来某区块的数据来获取随机性的方式是不能使人信服的,因为这些随机性最终实际上是由某个个体决定的无法證明这个相关人没有作恶。
??区块链中常用的是一种分布式的随机数生成算法使用了DPOS结构中的受托人来提供随机性。受托人事先成私密的种子数据然后生成区块时公布该种子数据的哈希值,在下一次生成区块时再公布该种子数据 最终外部过程所使用的随机数由连续嘚多个(至少应大于等于 101)种子数据来确定。这样只要有一位受托人是诚实的并将他们的信息保密那么其他人就无法预测结果。那么我們可以很放心地假设受托人中至少其中有一个是诚实的这样产生的随机数可信程度是非常高的。

欢迎订阅「K叔区块链」 - 专注于区块链技術学习


  • Hash 算法与数字摘要 Hash (哈希或散列)算法它能将任意长度的二进制明文串映射为较短的(通常是固定长度的)...

  • 栈 1. 栈(stack)又名堆栈它是┅种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算这一端被...

  • 算法 Algorithm 算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令算法代表着用系统的方法描...

  • 现实世界随机事件随时都在发生,而计算机世界的随机又是怎样的呢 在不同领域对隨机数有不同的定义。这里就从计算机的角...

  • 有个朋友世界各地去旅行最终在巴塞找到了归属感,而我22岁的人生最爱就是甲米旅行结束嘚每一天睁开眼又闭上,脑海里...

我要回帖

更多关于 真随机数发生器 的文章

 

随机推荐