随机数生成:修订间差异
Time killer(留言 | 贡献) 无编辑摘要 |
小无编辑摘要 |
||
第1行: | 第1行: | ||
'''随机数发生器'''(RNG)是设计来产生数字或缺少任何图案,即出现随机符号的序列的计算或物理设备。 |
|||
'''随机数生成器'''(Random number generator)是通过一些[[算法]]、物理訊號、環境[[噪音]]等来产生看起來似乎沒有關聯性的[[數列]]的方法或裝置。丟[[硬幣]]、丟[[骰子]]、[[洗牌]]就是生活上常見的隨機數產生方式。 |
|||
随机性的许多应用已导致几种不同的方法,用于产生随机数据的开发。自古以来,包括骰子,硬币翻转,扑克牌洗牌,在易经使用蓍草秆(占卜),以及许多其他技术许多这些已经存在。因为这些技术的机械性质,从而产生大量的充分随机数的(在统计重要)需要大量的工作和/或时间的。因此,结果有时会被收集和分布的随机数表。如今,计算随机数发生器,越来越多的政府经营的彩票,和彩票游戏问世后,使用的是反而更传统的绘制方法的RNG。随机数发生器今天也用于确定现代老虎机的可能性。[1] |
|||
数的计算方法为随机数生成存在。许多达不到真正的随机性的目标 - 尽管他们可能满足,不同的成功,部分随机性的统计测试意欲测量它们的结果如何不可预知的是(即,到什么程度的模式是可辨别)。然而,仔细设计产生随机数确实存在,如那些基于亚罗算法和财神器(PRNG)和其他的加密安全计算基础的方法。 |
|||
大部分[[计算机]]上的[[偽随机数]],并不是真正的随机数,只是重复的周期比较大的數列,是按一定的[[算法]]和种子值生成的。 |
大部分[[计算机]]上的[[偽随机数]],并不是真正的随机数,只是重复的周期比较大的數列,是按一定的[[算法]]和种子值生成的。 |
||
== 实际应用 == |
|||
{{主|应用随机性}} |
|||
随机数生成器在[赌博]的应用,[统计抽样]][[计算机模拟],[密码],[完全随机设计],和其他地方产生不可预知的结果是可取的。 |
|||
需要注意的是,在一般情况下,其中的不可预测性是最重要的 - 例如在安全应用 - [[Hardware_random_number_generator|硬件发生器]]通常优选(在可行的情况)以上的伪随机算法。 |
|||
随机数发生器在显影[[蒙特卡洛方法|蒙特卡洛法]]非常有用的模拟中,如[[调试]]通过再次由同一''[开始运行的随机数相同的序列的能力促进了[随机种子]]''。它们还用在[[加密]] - 只要'种子'是秘密。发送器和接收器可以自动生成同一组号码作为键来使用。 |
|||
的产生[[伪随机数]] s是在计算机编程的重要和共同任务。而加密和某些数值计算算法需要的'表观'随机性程度非常高,许多其他操作仅需要不可预测的适度的量。一些简单的例子可能会向用户呈现一个“日随机报价”,或确定哪种方式由计算机控制的对手可能会在电脑游戏中。弱形式的'随机性'被用在[哈希算法]] s和创造[摊销|摊销]][[搜索算法|搜索]]和[[排序算法]]秒。 |
|||
它出现在第一眼就适合随机某些应用,其实远不是那么简单。举例来说,一个系统,“随机”选择音乐曲目的背景音乐系统只能''出现'随机的,甚至有可能的方式来控制音乐的选择:一个真正的随机制度,对同一项目没有限制出现两次或三次连续。 |
|||
== “真”的随机数与伪随机数 == |
|||
{{主|伪随机数生成器}} |
|||
有用于生成随机数的两种主要方法。第一种方法测量,预计将是随机的,然后补偿在测量过程中可能出现的偏差一些物理现象。例如来源包括测量大气噪声,热噪声和其他外部电磁和量子现象。例如,作为测量在短的时间尺度宇宙背景辐射或放射性衰变代表天然来源[[熵(信息论)|熵]]。 |
|||
上被测量的基本物理现象,在该熵可以从天然来源收获的速度是相关的。因此,被所述天然存在的“真正的”熵源进行[[阻断(计算)|块]]荷兰国际集团即速率限制,直到足够的熵被收获,以满足需求。在某些类Unix系统,包括Linux发行版,FreeBSD和NetBSD的,伪设备文件[为/ dev/随机]将[阻塞(计算)|块],直到有足够的熵从收获environment.<ref>{{man|4|random|Linux}}</ref><ref>{{man|4|random|FreeBSD}}</ref><ref>{{man|4|random|NetBSD}}</ref>由于这种阻塞行为,从大批量读取[为/ dev/随机],如填充硬盘随机位,往往是缓慢的。 |
|||
第二种方法使用的计算[[算法]] S可以制作长序列的明显随机的结果,这实际上是由一较短的初始值,被称为种子或完全确定[[密钥(密码)|键]。后一种类型通常被称为[[伪随机数发生器]]第这些类型的发电机通常不依赖于天然存在的熵,尽管它们可以周期性地接种由天然来源的来源,它们是非 - [[阻断(计算)|阻塞]]即不率限制由外部事件。 |
|||
仅在确定性计算基础A“随机数生成器”不能算是一个“真”随机数字的最纯粹的意义上产生的,因为它们的输出本质上是可预测的,如果所有的种子值是已知的。然而在实践中,他们都足以满足大多数任务。精心设计和实现的伪随机数生成器,甚至可以认证为安全关键的加密的目的,为的是与[[蓍算法]]和[[Fortuna的(PRNG)]]的情况。 (前者的<代码>的/ dev/随机</ code>的熵源[FreeBSD的],[AIX]的基础上,[[苹果OS X]],[[NetBSD的]]等人[[OpenBSD的]]还使用基于伪随机数的算法[[RC4]]称为[[RC4#基于RC4的随机数发生器| arc4random]]参见:[[加密安全伪随机数发生器]] 。) |
|||
== 生成方法 == |
|||
== 物理方法 == |
|||
{{主|硬件随机数生成器}} |
|||
最早的方法产生随机数 - [[骰子]],[[硬币翻转]],[[轮盘]]车轮 - 今天仍在使用,主要是在[[游戏]] s和赌博,因为他们往往过于缓慢对于在统计和加密大多数应用。 |
|||
物理随机数发生器可以基于一个基本上是随机的原子或亚原子物理现象的不可预测性,可以追溯到[量子力学]的法律。来源[熵(信息论)|熵]包括[放射性衰变]][[约翰逊奈奎斯特噪音|热噪声],[散粒噪声],雪崩在[齐纳二极管]] S噪音,[时钟漂移#随机数生成器|时钟漂移],一个[硬盘]实际运动的时间读/写头,[噪声(单选)|无线电噪声]。然而,用于测量它们的物理现象和工具一般不对称特征和[系统性偏差] ES,使他们的成果并不均匀随机的。 A〔〔随机性提取]]如[[密码散列函数]],可用于接近比特的均匀分布从非均匀随机源,虽然在较低的比特率。 |
|||
收集这些信息熵的各种富有想象力的方式已经制订。一种技术是由一个不可预知的源运行对一个视频流的帧的哈希函数。 [Lavarand]]使用该技术具有若干[[熔岩灯]] S的图像。 [http://www.fourmilab.ch/hotbits/ HotBits]措施放射性衰变[盖革 - 穆勒管]] S,的<ref>{{cite web |
|||
| last = Walker |
|||
| first = John |
|||
| title = HotBits: Genuine Random Numbers |
|||
| url = http://www.fourmilab.ch/hotbits/ |
|||
| accessdate = 2009-06-27 }}</ref>而[[Random.org]使用在记录有正常无线大气噪声的幅度变化。 |
|||
另一种常见的信息源,是人类系统的用户的行为。虽然人们并不认为应要求良好的随机性发电机,它们生成随机的行为相当不错的发挥[混合策略]游戏的背景。的<ref>{{cite paper |
|||
| author = Halprin, Ran |
|||
|author2=Naor, Moni |authorlink2=Moni Naor |
|||
| title = Games for Extracting Randomness |
|||
| publisher = Department of Computer Science and Applied Mathematics, Weizmann Institute of Science |
|||
| url = http://www.neko.co.il/games4rand.pdf |
|||
| format = PDF |
|||
| accessdate = 2009-06-27 }} [http://mae.neko.co.il Main site]</ref>一些与安全相关的计算机软件需要用户进行一系列冗长的鼠标移动或键盘输入创建需要生成随机[密钥(加密)|键]足够的熵。或者初始化伪随机数生成器的<ref>{{cite web |
|||
| last = TrueCrypt Foundation |
|||
| title = TrueCrypt Beginner's Tutorial, Part 3 |
|||
| url = http://www.truecrypt.org/docs/?s=tutorial3 |
|||
| accessdate = 2009-06-27 }}</ref> |
|||
== 计算方法 == |
|||
[伪随机数生成器(PRNG)是[[算法]] S,可以自动创建具有良好无规性数的长期运行,但最终的序列重复(或存储器使用生长无结合)。值由这样的算法所生成的字符串通常由称为''的固定数量来确定'种子'''的一个最常见的PRNG的是[[线性同余发生器]],它使用复发 |
|||
:<math>X_{n+1} = (a X_n + b)\, \textrm{mod}\, m</math> |
|||
生成的数字。数字式可产生的最大数目是[[模量(代数数论)|模量]],''米''。为了避免单个线性同余发生器的某些非随机性质,几个这样的随机数发生器与'一''可以并联使用,以“主”随机数发生器,其选择从其中的乘法系数'的稍有不同的值在几个不同的发电机。{{需要引用|日期=2009年12月}} |
|||
一个简单的笔和纸的方法生成随机数是所谓的[中间方法]由[[约翰·冯·诺依曼]建议。虽然容易实现,它的输出质量差。 |
|||
大多数计算机编程语言,包括功能和库函数提供随机数生成器。它们通常被设计来提供一个随机字节或字或[[浮点]]编号|0和1之间[[均匀分布(连续)均匀〕分布。 |
|||
这样的库函数的质量,即从随机性完全可预测的输出差别很大,以加密的安全。在许多语言,包括Python,Ruby中,R,IDL和PHP默认的随机数生成器是基于[梅森倍捻机]算法是''不是''足够加密的目的,如明确的语言文档中说明。这样的库函数往往较差的统计特性,有些人会后才试验数以万计的重复模式。他们使用的是一台计算机的[[实时时钟]]常初始化作为种,由于这种时钟通常测量毫秒,远远超出了人的[[准确性和精度|精度]]。这些功能可以提供足够的随机性对某些任务(例如视频游戏),但不适合需要高品质的随机性是必需的,例如在密码学应用中,统计信息或数值分析{{引文需要。|原因=为什么不适合数值分析? |日期=2014年5月}} |
|||
更高质量的随机数源可在大多数操作系统;例如,[[为/ dev/随机]各种BSD口味,在Linux,Mac OS X,IRIX和Solaris或[CryptGenRandom]用于Microsoft Windows。大多数编程语言,包括那些上面提到的,提供访问这些更高品质的源的装置。 |
|||
一个简单的伪随机数发生器的一个例子是由[[乔治马尔萨利亚]]发明了[[乘法与进位]]方法。它是计算速度快,具有良好的(虽然不是保密性强)随机性性 |
|||
:<ref>{{cite web |
|||
| last = Marsaglia | first = George | title = sci.stat.math | date = 1999-01-12 | work = | url=http://groups.google.com/group/sci.crypt/browse_thread/thread/ca8682a4658a124d/ | accessdate = 2010-02-10 }}</ref> |
|||
<source lang="c"> |
|||
m_w = <choose-initializer>; /* must not be zero, nor 0x464fffff */ |
|||
m_z = <choose-initializer>; /* must not be zero, nor 0x9068ffff */ |
|||
uint get_random() |
|||
{ |
|||
m_z = 36969 * (m_z & 65535) + (m_z >> 16); |
|||
m_w = 18000 * (m_w & 65535) + (m_w >> 16); |
|||
return (m_z << 16) + m_w; /* 32-bit result */ |
|||
} |
|||
</source> |
|||
== 从概率分布产生 == |
|||
有几个方法来生成基于[[概率密度函数]的随机数。这些方法包括转化以某种方式的均匀的随机数。正因为如此,这些方法在产生两个伪随机和真随机数同样工作良好。一种方法,称为[[反变换采样|反转方法],涉及集成到一个面积大于或等于随机数(它应该0和1之间产生适当的分布)。第二种方法,称为[[拒绝抽样|接受 - 拒绝方法],包括选择一个x和y的值和测试x的函数是否大于y值。如果是,x值被接受。否则,x值被拒绝,并且算法再次尝试。 |
|||
<ref>{{cite web |
|||
| last = The MathWorks | first = | title = Common generation methods | work = | url=http://www.mathworks.de/help/toolbox/stats/br5k9hi-1.html | accessdate = 2011-10-13 }}</ref><!-- [http://www.mathworks.com/access/helpdesk/help/toolbox/stats/bqttfc1.html#bqt8l8g]--><ref>{{ cite web | last = The Numerical Algorithms Group | first = | title = G05 – Random Number Generators | work = NAG Library Manual, Mark 23 | url = http://www.nag.co.uk/numeric/fl/nagdoc_fl23/pdf/G05/g05intro.pdf | accessdate = 2012-02-09 }}</ref> |
|||
== 人类 == |
|||
随机数的产生,也可以由人直接完成。然而,大多数研究发现,人类主体有一定程度的非随机性的产生,例如,数字或字母随机序列的时候。相比,一个良好的随机发生器它们可交替太多选择之间。 |
|||
<ref>{{Cite journal |
|||
| author = W. A. Wagenaar |
|||
| title = Generation of random sequences by human subjects: a critical survey of the literature |
|||
| journal = [[Psychological Bulletin]] |
|||
| year = 1972 |
|||
| volume = 77 |
|||
| issue = 1 |
|||
| pages = 65–72 |
|||
| doi = 10.1037/h0032060 |
|||
}}</ref> |
|||
出于这个原因,人类随机数生成被中断了商用电脑在2000年初。 |
|||
== 后处理和统计检查 == |
|||
”参见:[[统计随机性]]''和''[[列表中随机数发生器]]'' |
|||
甚至给予合理的随机数的源(可能是从一个量子机械基于硬件发生器),从而获得,这是完全无偏照顾号码。此外,这些发电机的行为往往与温度,电源电压,装置的年龄,或其他外部干扰而改变。和它运行在一个软件错误以伪随机数例程或硬件错误,在硬件上,可以类似地难以察觉。 |
|||
产生的随机数,有时进行统计测试使用前,以确保基础源仍然工作,然后后处理,以改善它们的统计特性。一个例子将是TRNG9803<ref>{{cite web|last=Dömstedt|first=B.|title=TRNG9803 True Random Number Generator|url=http://www.trng98.se/serial_trng_9803.html|publisher=www.TRNG98.se|location=Manufacturer|year=2009}}</ref>硬件随机数发生器,使用一个熵测量为硬件测试,然后后处理用的移位寄存器的流密码。其通常很难使用统计测试以验证所生成的随机数。王和尼科尔<ref>{{cite web|last=Wang|first=Yongge|title=Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL|url=http://link.springer.com/chapter/10.1007%2F978-3-319-11203-9_26|publisher=Springer LNCS|location=Heidelberg|year=2014}}</ref>提出,用于识别多个随机生成的弱点一个基于距离的统计测试技术。 |
|||
== 其他注意事项 == |
|||
随机数介于0均匀地分布和1可用于通过在所希望的分布的逆[[累积分布函数]](CDF)将它们传递来产生随机数的任何期望的分布。逆CDF是也被称为[位数功能]秒。要生成对[[统计独立性|统计独立]][[正态分布|标准正态分布]随机数(''X'',''Y''),可以首先生成[极坐标] ](''R'',''θ''),其中''R''〜[[卡方分布|χ<子>2</ SUB><SUP>2</ SUP>]]和““θ''〜[均匀分布(连续)| UNIFORM(0,2π)](见[箱穆勒变换])。 |
|||
有些0到1的RNG包括0但不包括1,而其他包括或排除两者。 |
|||
多个独立的随机数发生器的输出可以被组合(例如,使用一个位方式[[XOR]]操作),以提供一个组合的RNG至少一样好所使用的最好的RNG。这被称为[[硬件随机数发生器#软件美白|软件美白]]。 |
|||
计算和硬件随机数生成器,有时合并,以反映这两种益处。计算随机数发生器通常可以生成伪随机数不是物理发电机快得多,而物理发生器可以产生“真正的随机性”。 |
|||
== 低差异序列作为替代 == |
|||
利用一个随机数发生器的一些计算可以归纳为一个总的或平均的值的计算,如积分由[[蒙特卡洛方法]的计算。对于这样的问题,有可能找到通过使用所谓的[[低差异序列]] s的更精确的解决方案,也被称为[[准随机]]号码。这样的序列具有填补空白中均匀,质而言有一定的图案;一个真正的随机序列可能和通常不会,留下较大的差距。 |
|||
== 活动和示威 == |
|||
下面的站点让提供随机数样本: |
|||
#在[[SOCR]资源页面包含了一些[http://wiki.stat.ucla.edu/socr/index.php/SOCR_EduMaterials_Activities_RNG动手互动活动和游行]随机数生成使用Java小程序。 |
|||
#量子光学集团从量子真空源的[ANU]产生随机数。您可以通过访问他们的[http://photonics.anu.edu.au/qoptics/Research/qrng.php量子随机数发生器]研究网页下载随机数的样本。 |
|||
#[http://Random.Org Random.Org]让那些从大气噪声的随机性来源的可用随机数。 [http://www.random.org/访问他们的页面],得到了样品。 |
|||
#在[http://random.irb.hr/量子随机位发生器服务]从半导体光子发射量子过程[Ruđer博斯科维奇研究所]收获随机性。他们提供了多种获取数据,包括几种编程语言库的方式。 |
|||
== 后门 == |
|||
{{主|随机数发生器的攻击}} |
|||
由于大部分的加密依赖于对键和[加密乱数]]生成加密安全随机数生成器,如果一个随机数发生器可以使可预测的,它可以被用作[[后门(计算)|后门]]由攻击者打破加密。 |
|||
国家安全局报告给已插入一个后门进入[标准与技术〔研究所| NIST]]认证[[加密安全伪随机数发生器]] [[Dual_EC_DRBG]]。例如,如果使用此随机数生成器,然后根据被创建SSL连接[[马修绿色(密码员)|马修绿色]]它将允许NSA以确定该随机数生成器的状态,从而最终能够读发送通过SSL连接中的所有数据的<ref>{{cite web|url=http://blog.cryptographyengineering.com/2013/09/the-many-flaws-of-dualecdrbg.html|title=The Many Flaws of Dual_EC_DRBG|author=matthew Green}}</ref>虽然它是明显的Dual_EC_DRBG是一个非常贫穷的,可能后门伪随机数发生器不久,NSA后门程序在2013年被证实,它已经看到在实践中显著的使用,直到2013年,为例如,通过突出的担保公司[RSA安全]]。<ref name="green">{{cite web|url=http://blog.cryptographyengineering.com/2013/09/rsa-warns-developers-against-its-own.html|title=RSA warns developers not to use RSA products|author=Matthew Green}}</ref>还有后来被指责RSA安全明知插入NSA后门进它的产品,可能为[Bullrun(解密程序)的一部分| Bullrun] ]程序。 RSA否认故意插入后门到它的产品。的<ref>{{cite web|url=http://arstechnica.com/security/2013/09/we-dont-enable-backdoors-in-our-crypto-products-rsa-tells-customers/|title=We don’t enable backdoors in our crypto products, RSA tells customers|publisher=Ars Technica}}</ref> |
|||
还已经推论,硬件随机数发生器可以暗中修改成具有较少熵比表示,这将使用硬件RNG容易受到攻击使加密。已出版的作品,通过修改的芯片,这将是不可检测到的光的逆向工程的掺杂掩模一种这样的方法。的<ref>{{cite web|url=http://arstechnica.com/security/2013/09/researchers-can-slip-an-undetectable-trojan-into-intels-ivy-bridge-cpus/|title=Researchers can slip an undetectable trojan into Intel’s Ivy Bridge CPUs|publisher=Ars Technica}}</ref>例如,对于随机数生成在Linux中,它被看作是不可接受的使用英特尔的[[RdRand]硬件RNG没有在RdRand混合熵其他来源的输出,以抵消任何后门在硬件RNG,尤其是NSA Bullrun程序的启示后。 |
|||
<ref>{{cite web|url=https://plus.google.com/117091380454742934025/posts/SDcoemc9V3J|title=I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RdRand instruction. |publisher=Google Plus|author=Theodore Ts'o}}</ref><ref>{{cite web|url=https://lwn.net/Articles/567077/|title=Re: [PATCH] /dev/random: Insufficient of entropy on many architectures|publisher=LWN|author=Theodore Ts'o}}</ref> |
|||
== Further reading == |
== Further reading == |
2015年1月13日 (二) 17:40的版本
随机数发生器(RNG)是设计来产生数字或缺少任何图案,即出现随机符号的序列的计算或物理设备。
随机性的许多应用已导致几种不同的方法,用于产生随机数据的开发。自古以来,包括骰子,硬币翻转,扑克牌洗牌,在易经使用蓍草秆(占卜),以及许多其他技术许多这些已经存在。因为这些技术的机械性质,从而产生大量的充分随机数的(在统计重要)需要大量的工作和/或时间的。因此,结果有时会被收集和分布的随机数表。如今,计算随机数发生器,越来越多的政府经营的彩票,和彩票游戏问世后,使用的是反而更传统的绘制方法的RNG。随机数发生器今天也用于确定现代老虎机的可能性。[1]
数的计算方法为随机数生成存在。许多达不到真正的随机性的目标 - 尽管他们可能满足,不同的成功,部分随机性的统计测试意欲测量它们的结果如何不可预知的是(即,到什么程度的模式是可辨别)。然而,仔细设计产生随机数确实存在,如那些基于亚罗算法和财神器(PRNG)和其他的加密安全计算基础的方法。 大部分计算机上的偽随机数,并不是真正的随机数,只是重复的周期比较大的數列,是按一定的算法和种子值生成的。
实际应用
随机数生成器在[赌博]的应用,[统计抽样]][[计算机模拟],[密码],[完全随机设计],和其他地方产生不可预知的结果是可取的。
需要注意的是,在一般情况下,其中的不可预测性是最重要的 - 例如在安全应用 - 硬件发生器通常优选(在可行的情况)以上的伪随机算法。
随机数发生器在显影蒙特卡洛法非常有用的模拟中,如调试通过再次由同一[开始运行的随机数相同的序列的能力促进了[随机种子]]。它们还用在加密 - 只要'种子'是秘密。发送器和接收器可以自动生成同一组号码作为键来使用。
的产生伪随机数 s是在计算机编程的重要和共同任务。而加密和某些数值计算算法需要的'表观'随机性程度非常高,许多其他操作仅需要不可预测的适度的量。一些简单的例子可能会向用户呈现一个“日随机报价”,或确定哪种方式由计算机控制的对手可能会在电脑游戏中。弱形式的'随机性'被用在[哈希算法]] s和创造[摊销|摊销]]搜索和排序算法秒。
它出现在第一眼就适合随机某些应用,其实远不是那么简单。举例来说,一个系统,“随机”选择音乐曲目的背景音乐系统只能出现'随机的,甚至有可能的方式来控制音乐的选择:一个真正的随机制度,对同一项目没有限制出现两次或三次连续。
“真”的随机数与伪随机数
有用于生成随机数的两种主要方法。第一种方法测量,预计将是随机的,然后补偿在测量过程中可能出现的偏差一些物理现象。例如来源包括测量大气噪声,热噪声和其他外部电磁和量子现象。例如,作为测量在短的时间尺度宇宙背景辐射或放射性衰变代表天然来源熵。
上被测量的基本物理现象,在该熵可以从天然来源收获的速度是相关的。因此,被所述天然存在的“真正的”熵源进行块荷兰国际集团即速率限制,直到足够的熵被收获,以满足需求。在某些类Unix系统,包括Linux发行版,FreeBSD和NetBSD的,伪设备文件[为/ dev/随机]将[阻塞(计算)|块],直到有足够的熵从收获environment.[1][2][3]由于这种阻塞行为,从大批量读取[为/ dev/随机],如填充硬盘随机位,往往是缓慢的。
第二种方法使用的计算算法 S可以制作长序列的明显随机的结果,这实际上是由一较短的初始值,被称为种子或完全确定[[密钥(密码)|键]。后一种类型通常被称为伪随机数发生器第这些类型的发电机通常不依赖于天然存在的熵,尽管它们可以周期性地接种由天然来源的来源,它们是非 - 阻塞即不率限制由外部事件。
仅在确定性计算基础A“随机数生成器”不能算是一个“真”随机数字的最纯粹的意义上产生的,因为它们的输出本质上是可预测的,如果所有的种子值是已知的。然而在实践中,他们都足以满足大多数任务。精心设计和实现的伪随机数生成器,甚至可以认证为安全关键的加密的目的,为的是与蓍算法和Fortuna的(PRNG)的情况。 (前者的<代码>的/ dev/随机</ code>的熵源[FreeBSD的],[AIX]的基础上,苹果OS X,NetBSD的等人OpenBSD的还使用基于伪随机数的算法RC4称为 arc4random参见:加密安全伪随机数发生器 。)
生成方法
物理方法
最早的方法产生随机数 - 骰子,硬币翻转,轮盘车轮 - 今天仍在使用,主要是在游戏 s和赌博,因为他们往往过于缓慢对于在统计和加密大多数应用。
物理随机数发生器可以基于一个基本上是随机的原子或亚原子物理现象的不可预测性,可以追溯到[量子力学]的法律。来源[熵(信息论)|熵]包括[放射性衰变]]热噪声],[散粒噪声],雪崩在[齐纳二极管 S噪音,[时钟漂移#随机数生成器|时钟漂移],一个[硬盘]实际运动的时间读/写头,[噪声(单选)|无线电噪声]。然而,用于测量它们的物理现象和工具一般不对称特征和[系统性偏差] ES,使他们的成果并不均匀随机的。 A〔〔随机性提取]]如密码散列函数,可用于接近比特的均匀分布从非均匀随机源,虽然在较低的比特率。
收集这些信息熵的各种富有想象力的方式已经制订。一种技术是由一个不可预知的源运行对一个视频流的帧的哈希函数。 [Lavarand]]使用该技术具有若干熔岩灯 S的图像。 HotBits措施放射性衰变[盖革 - 穆勒管]] S,的[4]而[[Random.org]使用在记录有正常无线大气噪声的幅度变化。
另一种常见的信息源,是人类系统的用户的行为。虽然人们并不认为应要求良好的随机性发电机,它们生成随机的行为相当不错的发挥[混合策略]游戏的背景。的[5]一些与安全相关的计算机软件需要用户进行一系列冗长的鼠标移动或键盘输入创建需要生成随机[密钥(加密)|键]足够的熵。或者初始化伪随机数生成器的[6]
计算方法
[伪随机数生成器(PRNG)是算法 S,可以自动创建具有良好无规性数的长期运行,但最终的序列重复(或存储器使用生长无结合)。值由这样的算法所生成的字符串通常由称为的固定数量来确定'种子'的一个最常见的PRNG的是线性同余发生器,它使用复发
生成的数字。数字式可产生的最大数目是模量,米。为了避免单个线性同余发生器的某些非随机性质,几个这样的随机数发生器与'一可以并联使用,以“主”随机数发生器,其选择从其中的乘法系数'的稍有不同的值在几个不同的发电机。Template:需要引用
一个简单的笔和纸的方法生成随机数是所谓的[中间方法]由[[约翰·冯·诺依曼]建议。虽然容易实现,它的输出质量差。
大多数计算机编程语言,包括功能和库函数提供随机数生成器。它们通常被设计来提供一个随机字节或字或浮点编号|0和1之间[[均匀分布(连续)均匀〕分布。
这样的库函数的质量,即从随机性完全可预测的输出差别很大,以加密的安全。在许多语言,包括Python,Ruby中,R,IDL和PHP默认的随机数生成器是基于[梅森倍捻机]算法是不是足够加密的目的,如明确的语言文档中说明。这样的库函数往往较差的统计特性,有些人会后才试验数以万计的重复模式。他们使用的是一台计算机的实时时钟常初始化作为种,由于这种时钟通常测量毫秒,远远超出了人的精度。这些功能可以提供足够的随机性对某些任务(例如视频游戏),但不适合需要高品质的随机性是必需的,例如在密码学应用中,统计信息或数值分析Template:引文需要。
更高质量的随机数源可在大多数操作系统;例如,[[为/ dev/随机]各种BSD口味,在Linux,Mac OS X,IRIX和Solaris或[CryptGenRandom]用于Microsoft Windows。大多数编程语言,包括那些上面提到的,提供访问这些更高品质的源的装置。
一个简单的伪随机数发生器的一个例子是由乔治马尔萨利亚发明了乘法与进位方法。它是计算速度快,具有良好的(虽然不是保密性强)随机性性
m_w = <choose-initializer>; /* must not be zero, nor 0x464fffff */
m_z = <choose-initializer>; /* must not be zero, nor 0x9068ffff */
uint get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32-bit result */
}
从概率分布产生
有几个方法来生成基于[[概率密度函数]的随机数。这些方法包括转化以某种方式的均匀的随机数。正因为如此,这些方法在产生两个伪随机和真随机数同样工作良好。一种方法,称为[[反变换采样|反转方法],涉及集成到一个面积大于或等于随机数(它应该0和1之间产生适当的分布)。第二种方法,称为[[拒绝抽样|接受 - 拒绝方法],包括选择一个x和y的值和测试x的函数是否大于y值。如果是,x值被接受。否则,x值被拒绝,并且算法再次尝试。 [8][9]
人类
随机数的产生,也可以由人直接完成。然而,大多数研究发现,人类主体有一定程度的非随机性的产生,例如,数字或字母随机序列的时候。相比,一个良好的随机发生器它们可交替太多选择之间。 [10] 出于这个原因,人类随机数生成被中断了商用电脑在2000年初。
后处理和统计检查
”参见:统计随机性和列表中随机数发生器 甚至给予合理的随机数的源(可能是从一个量子机械基于硬件发生器),从而获得,这是完全无偏照顾号码。此外,这些发电机的行为往往与温度,电源电压,装置的年龄,或其他外部干扰而改变。和它运行在一个软件错误以伪随机数例程或硬件错误,在硬件上,可以类似地难以察觉。
产生的随机数,有时进行统计测试使用前,以确保基础源仍然工作,然后后处理,以改善它们的统计特性。一个例子将是TRNG9803[11]硬件随机数发生器,使用一个熵测量为硬件测试,然后后处理用的移位寄存器的流密码。其通常很难使用统计测试以验证所生成的随机数。王和尼科尔[12]提出,用于识别多个随机生成的弱点一个基于距离的统计测试技术。
其他注意事项
随机数介于0均匀地分布和1可用于通过在所希望的分布的逆累积分布函数(CDF)将它们传递来产生随机数的任何期望的分布。逆CDF是也被称为[位数功能]秒。要生成对统计独立[[正态分布|标准正态分布]随机数(X,Y),可以首先生成[极坐标] ](R,θ),其中R〜χ<子>2</ SUB>2</ SUP>和““θ〜[均匀分布(连续)| UNIFORM(0,2π)](见[箱穆勒变换])。
有些0到1的RNG包括0但不包括1,而其他包括或排除两者。
多个独立的随机数发生器的输出可以被组合(例如,使用一个位方式XOR操作),以提供一个组合的RNG至少一样好所使用的最好的RNG。这被称为软件美白。
计算和硬件随机数生成器,有时合并,以反映这两种益处。计算随机数发生器通常可以生成伪随机数不是物理发电机快得多,而物理发生器可以产生“真正的随机性”。
低差异序列作为替代
利用一个随机数发生器的一些计算可以归纳为一个总的或平均的值的计算,如积分由[[蒙特卡洛方法]的计算。对于这样的问题,有可能找到通过使用所谓的低差异序列 s的更精确的解决方案,也被称为准随机号码。这样的序列具有填补空白中均匀,质而言有一定的图案;一个真正的随机序列可能和通常不会,留下较大的差距。
活动和示威
下面的站点让提供随机数样本: #在[[SOCR]资源页面包含了一些[1]随机数生成使用Java小程序。 #量子光学集团从量子真空源的[ANU]产生随机数。您可以通过访问他们的[2]研究网页下载随机数的样本。 #Random.Org让那些从大气噪声的随机性来源的可用随机数。 [3],得到了样品。 #在[4]从半导体光子发射量子过程[Ruđer博斯科维奇研究所]收获随机性。他们提供了多种获取数据,包括几种编程语言库的方式。
后门
由于大部分的加密依赖于对键和[加密乱数]]生成加密安全随机数生成器,如果一个随机数发生器可以使可预测的,它可以被用作后门由攻击者打破加密。
国家安全局报告给已插入一个后门进入[标准与技术〔研究所| NIST]]认证加密安全伪随机数发生器 Dual_EC_DRBG。例如,如果使用此随机数生成器,然后根据被创建SSL连接马修绿色它将允许NSA以确定该随机数生成器的状态,从而最终能够读发送通过SSL连接中的所有数据的[13]虽然它是明显的Dual_EC_DRBG是一个非常贫穷的,可能后门伪随机数发生器不久,NSA后门程序在2013年被证实,它已经看到在实践中显著的使用,直到2013年,为例如,通过突出的担保公司[RSA安全]]。[14]还有后来被指责RSA安全明知插入NSA后门进它的产品,可能为[Bullrun(解密程序)的一部分| Bullrun] ]程序。 RSA否认故意插入后门到它的产品。的[15]
还已经推论,硬件随机数发生器可以暗中修改成具有较少熵比表示,这将使用硬件RNG容易受到攻击使加密。已出版的作品,通过修改的芯片,这将是不可检测到的光的逆向工程的掺杂掩模一种这样的方法。的[16]例如,对于随机数生成在Linux中,它被看作是不可接受的使用英特尔的[[RdRand]硬件RNG没有在RdRand混合熵其他来源的输出,以抵消任何后门在硬件RNG,尤其是NSA Bullrun程序的启示后。 [17][18]
Further reading
- Donald Knuth. Chapter 3 – Random Numbers. The Art of Computer Programming. Vol. 2: Seminumerical algorithms 3. 1997.
- Kroese, D. P.; Taimre, T.; Botev, Z.I. Chapter 1 - Uniform Random Number Generation. Handbook of Monte Carlo Methods. New York: John Wiley & Sons. 2011: 772. ISBN 0-470-17793-4.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. Chapter 7. Random Numbers. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007. ISBN 978-0-521-88068-8Template:Inconsistent citations
- NIST SP800-90A, B, C series on random number generation
外部鏈接
这是一篇與计算机相關的小作品。你可以通过编辑或修订扩充其内容。 |
- ^ Linux程序员手册页 – 特殊文件(Special Files) –
- ^ FreeBSD内核接口(Kernel Interfaces)手册页 –
- ^ NetBSD内核接口(Kernel Interfaces)手册页 –
- ^ Walker, John. HotBits: Genuine Random Numbers. [2009-06-27].
- ^ Halprin, Ran; Naor, Moni. Games for Extracting Randomness (PDF). Department of Computer Science and Applied Mathematics, Weizmann Institute of Science. [2009-06-27]. Main site
- ^ TrueCrypt Foundation. TrueCrypt Beginner's Tutorial, Part 3. [2009-06-27].
- ^ Marsaglia, George. sci.stat.math. 1999-01-12 [2010-02-10].
- ^ The MathWorks. Common generation methods. [2011-10-13].
- ^ The Numerical Algorithms Group. G05 – Random Number Generators (PDF). NAG Library Manual, Mark 23. [2012-02-09].
- ^ W. A. Wagenaar. Generation of random sequences by human subjects: a critical survey of the literature. Psychological Bulletin. 1972, 77 (1): 65–72. doi:10.1037/h0032060.
- ^ Dömstedt, B. TRNG9803 True Random Number Generator. Manufacturer: www.TRNG98.se. 2009.
- ^ Wang, Yongge. Statistical Properties of Pseudo Random Sequences and Experiments with PHP and Debian OpenSSL. Heidelberg: Springer LNCS. 2014.
- ^ matthew Green. The Many Flaws of Dual_EC_DRBG.
- ^ Matthew Green. RSA warns developers not to use RSA products.
- ^ We don’t enable backdoors in our crypto products, RSA tells customers. Ars Technica.
- ^ Researchers can slip an undetectable trojan into Intel’s Ivy Bridge CPUs. Ars Technica.
- ^ Theodore Ts'o. I am so glad I resisted pressure from Intel engineers to let /dev/random rely only on the RdRand instruction.. Google Plus.
- ^ Theodore Ts'o. Re: [PATCH] /dev/random: Insufficient of entropy on many architectures. LWN.