为什么有专门致力于“真正随机性”的网站?当然,根据上述观察,获得任意数字的机会几乎等于可以选择多少个数字。
我在Python中进行了尝试:这是6000万次掷骰的结果。最高变化约为0.15。这不是随机的吗?
1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0
#1 楼
让我们玩一些计算机扑克,只有您,我和我们都信任的服务器。服务器使用伪随机数生成器,该伪随机数生成器在播放之前就已用32位种子初始化。因此,大约有40亿个可能的套牌。我手里有五张牌-显然我们不在玩德州扑克。假设发给我一张,给您一张,给我一张,给您一张,依此类推。所以我在甲板上有第一张,第三张,第五张,第七张和第九张卡。
我早先对伪随机数生成器运行了40亿次,每个种子都运行了一次,并将为每个种子生成的第一张卡记入数据库。假设我的第一张牌是黑桃皇后。在所有这些可能的套牌中,只有52个套牌中的第一张牌显示出来,因此我们将可能的套牌从40亿张减少到了大约8000万张。
假设我的第二张牌是三颗心。现在,我使用产生黑桃皇后的8000万个种子作为第一个数字,再运行8000万次RNG。这花了我几秒钟。我写下所有产生三颗心的牌组作为第三张牌-我手上的第二张牌。仍然只有大约2%的套牌,所以现在我们只有200万套套牌。
假设我手中的第三张牌是7杆。我有一个200万种子的数据库,可以分发我的两张卡片;我再次运行RNG 200万次,以发现产生7个俱乐部的卡组的2%作为第三张牌,而现在只有4万个卡组。
您会看到这种情况。我再运行RNG 40000次以查找产生我的第四张牌的所有种子,这使我们下降到800个牌组,然后再运行800次以得到约20个产生我的第五张牌的种子,现在我只是生成那二十副牌,我知道您有二十只可能的手之一。而且,我对接下来要绘制的内容非常了解。
现在您知道为什么真正的随机性很重要吗?在描述它的方式上,您认为分布很重要,但是分布并不是使过程随机化的原因。不可预测性是使过程随机化的原因。
UPDATE
基于(由于其非建设性的性质,现在已删除)注释,至少有0.3%的人阅读了此注释就我的观点感到困惑。当人们反对我没有提出的观点,或更糟的是,我根据我没有提出的观点提出我的观点,那么我知道我需要更清楚,仔细地解释。 br />
在单词分配方面似乎存在特殊的困惑,因此我想仔细地指出用法。
手头的问题是:
伪随机数和真正的随机数有何区别?
为什么区别很重要?
区别与PRNG输出的分布有关吗?
让我们首先考虑一种完美的方式来生成随机的纸牌来玩扑克。然后,我们将了解其他用于生成牌组的技术有何不同,以及是否有可能利用这种差异。
让我们首先假设我们有一个标记为
TRNG
的魔术盒。作为输入,我们给它一个大于或等于1的整数n;作为输出,它给我们一个真正的随机数,介于1和n之间(含)。盒子的输出是完全不可预测的(当给定一个数字而不是一个数字时),介于1和n之间的任何数字与另一个数字的可能性相同;也就是说,分布是均匀的。 (我们可以执行其他一些更高级的随机性统计检查;我忽略了这一点,因为它与我的论点没有密切关系。TRNG在假设上完全是统计随机性。)我们从一副打牌的纸牌开始。我们要求输入框一个介于1到52之间的数字,即
TRNG(52)
。无论它返回多少数字,我们都会从已分类的纸牌中算出那么多卡片,然后将其取出。它成为洗牌后的第一张牌。然后我们要求TRNG(51)
并选择第二张卡,以此类推。以此类推。另一种查看方式是:有52个! = 52 x 51 x 50 ... x 2 x 1个可能的副牌,大约为2226。我们实际上是随机选择的。
现在我们发卡。当我看我的卡片时,我什么都不知道。 (除了显而易见的事实,您没有我拥有的所有牌。)它们可以是几率相等的任何牌。
所以,请确保我清楚地解释一下。我们对
TRNG(n)
的每个输出都有统一的分布;每个人都以1 / n的概率选择1到n之间的数字。此外,此过程的结果是我们选择了52个之一!可能的牌组概率为1/52 !,因此在可能的牌组集合中的分布也是均匀的。好。
现在,让我们假设我们有一个标记为
PRNG
的魔术盒。在使用它之前,必须使用32位无符号数字作为种子。 ASIDE:为什么要32?不能用64位,256位或10000位数字作为种子吗?当然。但是(1)实际上,大多数现成的PRNG都是用32位数字播种的;(2)如果您有10000位随机性来进行种子播种,那么为什么要使用PRNG?您已经有10000位随机源!
无论如何,请回到PRNG的工作方式:将其植入种子后,就可以像使用
TRNG
一样使用它。也就是说,您向其传递一个数字n,它会返回一个介于1到n之间(包括1和n)的数字。而且,该输出的分布或多或少是均匀的。也就是说,当我们问PRNG
1到6之间的一个数字时,无论种子是什么,我们大约分别有六分之一的时间得到1、2、3、4、5或6。 我想多次强调这一点,因为它似乎使某些评论者感到困惑。 PRNG的分布至少在两个方面是均匀的。首先,假设我们选择任何特定的种子。我们希望序列
PRNG(6), PRNG(6), PRNG(6)...
产生一百万次将在1到6之间产生均匀的数字分布。第二,如果我们选择一百万个不同的种子并为每个种子调用一次PRNG(6)
,那么我们还将期望从1至6。PRNG在这两个操作中的一致性与我描述的攻击无关。 因为框的行为实际上是完全确定的,所以该过程被称为伪随机过程。它根据种子从232种可能的行为中选择一种。也就是说,一旦被播种,
PRNG(6), PRNG(6), PRNG(6), ...
就会产生具有均匀分布的数字序列,但是该序列完全由种子决定。对于给定的调用序列,例如PRNG(52),PRNG(51)等,只有232个可能的序列。种子实际上选择了我们得到的种子。要生成一副牌,服务器现在会生成一个种子。 (如何?我们回到这一点。)然后他们调用
PRNG(52)
,PRNG(51)
等来生成牌组,类似于之前。该系统容易受到我描述的攻击。要攻击服务器,我们首先要提前为自己的包装盒播种0并要求
PRNG(52)
并将其写下来。然后,我们用1重新种子,要求PRNG(52)
,并将其写下来,一直到232-1。 现在,使用PRNG生成套牌的扑克服务器必须以某种方式生成种子。他们如何这样做并不重要。他们可以致电
TRNG(2^32)
获得真正的随机种子。或者他们可以将当前时间作为种子,这几乎是随机的。我知道现在和你一样多。我攻击的重点是没有关系,因为我有数据库。当我看到第一张卡片时,可以消除98%的种子。当我看到第二张卡片时,我可以再消除98%,依此类推,直到最终我可以了解到少量可能的种子,并且极有可能知道您手中的情况。现在再次强调一下,这里的假设是,如果我们将
PRNG(6)
调用一百万次,则每个数字将获得大约六分之一的时间。该分布(或多或少)是均匀的,如果您只关心分布的均匀性,那很好。问题的关键是我们还关心PRNG(6)
的分布以外的事情吗?答案是肯定的。我们也关注不可预测性。 解决问题的另一种方法是,即使分配给
PRNG(6)
的一百万个电话可能很好,因为PRNG仅从232种可能的行为中进行选择,但它无法生成所有可能的套牌。它只能生成2226个可能的套牌中的232个。一小部分。因此,所有套牌的分布都很糟糕。但同样,这里的根本性攻击是基于我们能够通过少量输出样本成功预测PRNG
的过去和将来的行为。 让我说三遍或四遍,以确保它陷入其中。这里有三种分布。首先,分配产生随机32位种子的进程。这可能是完全随机的,不可预测的并且是统一的,并且攻击仍然有效。其次,向
PRNG(6)
分配一百万个电话。这可以是完全统一的,并且攻击仍然有效。第三,我已经描述了通过伪随机过程选择的牌组分布。这种分配非常差;可能只选择了IRL可能的套牌的一小部分。攻击取决于PRNG行为的可预测性(基于对PRNG输出的部分了解)。ASIDE:此攻击要求攻击者知道或能够猜测PRNG使用的确切算法是什么是。这是否现实是一个悬而未决的问题。但是,在设计安全系统时,即使攻击者知道程序中的所有算法,也必须将其设计为能够抵御攻击。换句话说,为了使系统安全,必须保密的安全系统部分称为“密钥”。如果系统的安全性取决于您用作机密的算法,则密钥包含这些算法。
继续前进。
现在,让我们假设我们有第三个标记为
CPRNG
的魔术盒。它是PRNG
的加密强度版本。它需要256位种子而不是32位种子。它与PRNG
共享种子从2256种可能行为之一中选择的属性。就像我们的其他机器一样,它具有以下特性:对CPRNG(n)
的大量调用会在1和n之间产生均匀的结果分布:每次发生的时间都是1 / n。我们可以对其发起攻击吗?我们最初的攻击要求我们存储从种子到
PRNG(52)
的232个映射。但是2256是一个大得多的数字。多次运行CPRNG(52)
并存储结果是完全不可行的。但是,假设还有其他方法可以获取
CPRNG(52)
的值,从而得出有关种子的事实?到目前为止,我们一直很愚蠢,只是对所有可能的组合进行了暴力破解。我们可以看看魔术盒内部,弄清楚它是如何工作的,并根据输出推断出种子的事实吗?否。详细信息太复杂,难以解释,但是CPRNG的设计巧妙,因此无论
CPRNG(52)
的第一个输出还是输出的任何子集,无论大小如何,都无法推断出有关种子的任何有用事实。好,现在让我们假设服务器正在使用
CPRNG
生成卡片组。它需要256位种子。它如何选择种子?如果它选择了攻击者可以预测的任何值,则突然攻击又变得可行了。如果我们可以确定2256个可能的种子中,服务器可能只选择其中的40亿个,那么我们就重新开始营业。我们可以再次发动这种攻击,只注意可能会生成的少量种子。因此,服务器应努力确保256位数字均匀分布-就是说,以1/2256的概率选择每个可能的种子。基本上,服务器应该调用
TRNG(2^256)-1
来生成CPRNG
的种子。 如果我可以入侵服务器并查看服务器以查看选择了什么种子,该怎么办?在这种情况下,攻击者知道CPRNG的过去和将来。服务器作者需要防范这种攻击! (当然,如果我可以成功发起这种攻击,那么我也可以直接将钱转入我的银行帐户,所以也许那没那么有趣。要点是:种子必须是一个难以猜测的秘密,并且真正的随机256位数字非常难以猜测。)
回到我前面的深度防御方面:256位种子是此安全系统的关键。 CPRNG的想法是只要密钥是安全的,系统就是安全的。即使知道该算法的所有其他事实,只要您可以将密钥保密,对手的卡也是不可预测的。
好,所以种子应该既是秘密的又要均匀分布,因为如果不是,我们可以发起攻击。我们假设
CPRNG(n)
的输出分布是均匀的。 您可能会说:CPRNG输出2256个可能的序列,但是只有2226个可能的甲板。因此,比套牌有更多的可能序列,所以我们很好。现在,在该系统中,每个可能的IRL牌组(很有可能)都是可能的。这是一个很好的论据,除了...
2226仅是52!的近似值。分开。 2256/52!不可能是整数,因为一件事就是52!被3整除,但没有2的幂!由于这不是一个整数,所以我们面临这样一种情况,即所有甲板都可以使用,但是某些甲板比其他甲板更有可能。
如果不清楚,请考虑数字较小的情况。假设我们有3张卡,A,B和C。假设我们使用具有8位种子的PRNG,所以有256种可能的种子。
PRNG(3)
有256种可能的输出,具体取决于种子。因为256不能被3整除,所以没有办法让它们中的三分之一成为A,其中三分之一成为B,而三分之一则成为C。 同样,52不是均匀地分成2256,因此在选择第一张牌时,某些牌必须有一定的偏见,而其他牌则必须有偏见。
在我们最初的带有32位种子的系统中,存在很大的偏差,并且从未生产过绝大多数可能的套牌。在该系统中,可以生产所有甲板,但是甲板的分布仍然存在缺陷。有些套牌比其他套牌的可能性要高得多。
现在的问题是:我们是否有基于此漏洞的攻击?答案是在实践中,可能不是。设计CPRNG的目的是,如果种子确实是随机的,那么在计算上难以分辨出
CPRNG
和TRNG
之间的区别。好,让我们总结一下。
伪随机数和真正的随机数有何不同?
它们在显示的可预测性水平上有所不同。
/>
真正的随机数是不可预测的。
如果可以确定或猜测种子,则所有伪随机数都是可预测的。
为什么差异如此重要?
因为在某些应用中系统的安全性依赖于不可预测性。
如果使用TRNG选择每张卡,则系统是无懈可击的。
如果使用CPRNG来选择每张卡,那么如果种子既不可预测又是未知的,则系统是安全的。
如果使用种子空间小的普通PRNG,则无论种子是不可预测的还是未知的,系统都不安全。足够小的种子空间容易受到我所描述的那种蛮力攻击。
差异是否与PRNG的输出分布有关? />
单独调用
RNG(n)
的分配均匀性或缺乏统一性与我描述的攻击无关。 正如我们已经看到的,无论
PRNG
和CPRNG
产生的分布很差,在所有可能的牌组中选择任何一个牌组的可能性都很大。 PRNG
差很多,但都存在问题。比PRNG更好,为什么有人使用CPRNG或PRNG?两个原因。
第一:费用。 TRNG很昂贵。生成真正的随机数是困难的。对于任意多次调用,CPRNG都会产生良好的结果,而对于种子,仅一次调用TRNG。不利的一面当然是您必须保守种子的秘密。
第二:有时候我们想要可预测性,而我们关心的只是良好的分配。如果您正在生成“随机”数据作为测试套件的程序输入,并且它显示了一个错误,那么再次运行该测试套件会再次产生该错误将是很好的!
我希望现在,这个要清楚得多了。
最后,如果您喜欢它,那么您可能会喜欢一些关于随机性和置换性的文章:
假设我具有均匀分布的随机数据。如何将其转换为给定的非均匀分布?
为什么某些GUID是随机生成的?他们的位都是随机的吗? (不。)我可以依靠GUID作为真正随机性的来源吗? (不!)
如何使用乘数符号生成大随机数?
如何将其转换为随机排列?
如何才能针对随机排列对此处所述的攻击进行攻击?
通过使用余数技术来引入多少偏差实施
RNG(n)
?评论
好吧,男孩和女孩。现在就足够了。如果您想进一步讨论这个问题,那就去聊天室kthnxbye吧!
– Ivo Flipse
2014年2月11日,23:23
@Eric但是种子不会在每次新的套牌抽签之前重置,是吗?因此,虽然您是正确的,我们仅从相对较少的轨迹中进行采样,但是您不知道当前您在轨迹中的确切位置,并且轨迹相交。
– A.S.
16-3-12在20:33
有人实际上做了这样的事情
–EJoshuaS-恢复莫妮卡
17年4月20日在20:10
Knuth的TAOCP第2卷第3.5节“什么是随机序列?”是对相关问题的一种很好(但密集的)处理。 (p。149),从对等分布,k分布和∞分布序列的启发性定义开始。伪随机序列在3.5.F(第170页)中进行了讨论。另请参阅复杂性理论和德国BSI提供的伪随机性准则。
–ShreevatsaR
17年9月23日在15:05
#2 楼
正如埃里克·利珀特(Eric Lippert)所说,它不只是发行。还有其他测量随机性的方法。早期的随机数生成器之一的最低有效位有一个序列-它交替使用0和1。因此,LSB是100%可预测的。但是您需要担心的不只是这些。每一位必须是不可预测的。
这里是思考问题的好方法。假设您正在生成64位随机性。对于每个结果,取前32位(A)和后32位(B),并在数组x [A,B]中建立索引。
现在执行测试一百万次,并进行每个结果,都以该数字递增数组,即X [A,B] ++;
现在绘制2D图,其中数字越大,该位置的像素越亮。 />
如果确实是随机的,则颜色应为统一的灰色。但是您可能会得到模式。以Windows NT系统的TCP序列号中的“随机性”图为例:
甚至是Windows 98中的一个:
这是思科路由器(IOS)实现的随机性。
这些图由MichałZalewski的论文提供。在这种特殊情况下,如果可以预测一个系统的TCP序列号,则可以在与另一个系统建立连接时模拟该系统-这将允许劫持连接,截取通信等。
即使我们不能100%地预测下一个数字,但如果我们可以在我们的控制下创建新的连接,则可以增加成功的机会。当计算机可以在几秒钟内生成100,000个连接时,成功攻击的可能性就从天文数字变为可能甚至什至是可能。
评论
这是如此辉煌,它使我流泪。应该有一个应用程序可以为每个操作系统(移动设备/桌面/服务器)和平台(JVM / Javascript / etc)创建这些应用程序。
– HDave
2014年2月9日在18:54
Windows rand()函数非常好!它产生的云没有任何明显的模式。查看我的实现以尝试它(和其他算法):github.com/Zalastax/visualize_random
– Zalastax
2014-02-17 14:56
#3 楼
尽管计算机生成的伪随机数对于计算机用户遇到的大多数使用情况都是可以接受的,但是在某些情况下,需要完全不可预测的随机数。在安全敏感的应用程序(例如加密)中,伪随机数生成器(PRNG)可能会产生一些值,尽管它们在外观上是随机的,但实际上是攻击者可以预测的。如果使用了PRNG,并且攻击者掌握了PRNG的状态信息,则试图破解加密系统的人可能能够猜出加密密钥。因此,对于这样的应用,需要产生真正不可猜测的值的随机数生成器。请注意,某些PRNG被设计为具有加密安全性,并且可用于此类对安全敏感的应用程序。
有关RNG攻击的更多信息可以在此Wikipedia文章中找到。
评论
存在加密PRNG,并且被广泛使用。它们可以从中等大小的种子中生成几乎无限的随机数流。将这种流与真正的随机数区分开来在计算上是不可行的,因此不能从这种流的任何部分获得额外的信息,并且出于任何实际目的,该数目与真实的随机数一样好。
–aaaaaaaaaaaa
2014年2月5日在21:20
我认为最简单的解释方法是必须对随机数生成器算法进行编程。这意味着要遵循一组指令。如果有一组指令,则不能是随机的。
–凯尔塔里(Keltari)
2014年2月7日在21:49
@Keltari您缺少熵的元素...大多数RNG(至少是加密RNG)从外部来源(例如鼠标移动)收集输入并将其用作开始条件的一部分-因此,从A到B的转换是已编程,但A的初始状态(应该)不可猜测。 Linux的/ dev / random会大致估计可用的熵量,如果下降太低,则停止给出数字。
–基本
2014年2月7日在23:58
出于好奇-为什么熔岩灯被认为是“真正随机的”?我知道它表现出相当不可预测的行为,但是对流体动力学以及这些流体如何在地球引力环境中有足够把握的人肯定可以产生“可预测”的结果,不是吗?当然,熔岩灯是无法预测的,但是对我来说,它们根本不是随机的,而是高度可预测的。
–The GreenCabbage
2014-2-10 14:29
@theGreenCabbage:我怀疑熔岩灯很乱。给定足够好的计算机模型和足够的准确性,您可以(原则上)预测行为一段时间。但是,由于系统是混乱的,所以在初始条件下变化最小的两个熔岩灯将在行为上迅速发散。 (此评论忽略了混沌吸引子。)
– dmm
2014-02-10 19:44
#4 楼
我在Python中尝试过:这是6000万次滚动的结果。最高变化约为0.15。
实际上,它是如此“好”,这很不好...所有现有的答案都集中在给定一小部分初始值的可预测性上。我想提出另一个问题:
您的分布的标准偏差比随机滚动应该小得多
真正的随机性与平均数“几乎恰好等于1可以选择多少个数字来表示质量。
如果您查看有关多个骰子掷骰概率分布的Stack Exchange问题,您会看到一个N个骰子掷骰的标准偏差的公式(假设为真实随机结果):
sqrt(N * 35.0 / 12.0).
使用该公式,标准偏差为:
100万卷是1708
6000万卷是13229
如果我们查看您的结果:
100万卷:stddev(1000066,999666,1001523,999452,999294,999999)是804
6000万卷:stddev(9997653,9997789,9996853,10006533,10002774,9998398)是3827
您不能指望有限截面的标准偏差可以完全匹配该公式,但是应该非常接近。然而,一百万卷您还不到标准stddev的一半,而六千万卷您还不到标准stddev的三分之一-情况越来越糟,这绝非偶然....
伪RNG倾向于在一系列不同的数字之间移动,从种子开始,在特定时期内不重新访问原始数字。例如,旧的C库
rand()
函数的实现通常具有2 ^ 32的周期,并且在重复种子之前,它们将访问0到2 ^ 32-1之间的每个数字一次。因此,如果模拟2 ^ 32掷骰子,则预模(%
)结果将包括从0到2 ^ 32的每个数字,则每个1-6个结果的计数将为715827883或715827882(2 ^ 32不是6的倍数),因此标准偏差仅在0之上。使用上面的公式,2 ^ 32卷的正确标准偏差为111924。无论如何,随着伪随机卷数的增加,您会收敛到0标准偏差。当掷骰数是周期的很大一部分时,预计该问题将很严重,但是某些伪RNG可能会比其他伪RNG出现更严重的问题-甚至样本数量更少的问题。因此即使您不关心加密漏洞,在某些应用程序中,您也可能关心分布没有过度,人为的结果。某些类型的模拟非常专门地试图计算出大量随机个体样本自然产生的不均匀结果的后果,但在某些pRNG结果中代表性不足。如果您要模拟大量人口对某个事件的反应,那么此问题可能会从根本上改变您的结果,从而导致结论不正确。举一个具体的例子:假设一位数学家告诉扑克机器程序员,经过6000万次模拟掷骰-曾经在屏幕周围闪烁数百个小“灯光”,如果已经有10,013,229个或更多的6,则数学家期望距离均值1 stddev时,应该有少量支出。根据68–95–99.7规则(维基百科),这应该发生在大约16%的时间中(〜68%落在标准偏差内/只有一半以上在标准偏差内)。对于您的随机数生成器,这是来自均值上方约3.5个标准差的:0.025%的机会不到-几乎没有客户能获得此收益。请参阅刚才提到的页面上的“高偏差”表,特别是:
| Range | In range | Outside range | Approx. freq. for daily event |
| µ ± 1σ | 0.68268... | 1 in 3 | Twice a week |
| µ ± 3.5σ | 0.99953... | 1 in 2149 | Every six years |
评论
您在这里比较苹果和桔子。这两个标准偏差绝对彼此无关。
– Jbeuh
2014年2月10日20:33
#5 楼
我刚刚写了这个随机数生成器来生成骰子掷骰子def get_generator():
next = 1
def generator():
next += 1
if next > 6:
next = 1
return next
return generator
你像这样使用它
>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1
等等。您是否愿意将这个生成器用于运行骰子游戏的程序?请记住,它的分布恰好是您从“真正随机”生成器所期望的分布!
伪随机数生成器所做的本质上是相同的-它们生成具有正确分布的可预测数。它们之所以不好,是因为上述简单化的随机数生成器很糟糕,它们不适合您需要真正的不可预测性而不仅仅是正确分布的情况。
评论
“伪随机数生成器...生成具有正确分布的可预测数”-仅仅因为它是PRNG并不能保证它具有完美的分布(实际上,商业的PRNG基本上没有,这些答案中概述的原因)。尽管可以给定足够的信息(使用的算法,起始种子,输出值,w / e)是可以预测的,但它们仍然存在差异。
– Brian S
2014年2月5日在20:46
除了要点,我知道,但是get_generator = lambda:itertools.cycle(range(1,7)),generator = get_generator(),next(generator)#等等太优雅了,更不用说了:)
– Janus Troelsen
2014年2月6日在22:30
@BrianS实际上,根据定义,经过一段时间的分配测试失败的PRNG是可以预测的。因此,在某个较大的N上,如果您在N次掷硬币中从N / 2个筹码中走了几步,您就可以开始押注筹码,您获胜的可能会大于损失。同样,如果您获得了正面与反面的完美分布,但是正面总是成对出现,那么您将再次获得制胜法宝。通过分布测试,您可以了解PRNG的好处。
–乔恩·基帕斯基
2014年2月7日下午6:45
您接下来忘记了非本地:-)。
–科斯
2014年2月7日在9:41
甚至更好的例子:Pi被认为是正常的,这意味着在任何基数中任何给定长度的数字序列出现的频率都比该基数中该长度的任何其他序列的出现频率低。从长远来看,从长远来看,当要求n个随机位时,采用pi的下n个位并将其返回(“种子”是您开始的位)的算法。但是您仍然不希望生成器使用它-知道您生成的最后一堆比特的人可能会发现序列第一次出现,并假设您的种子在那儿并且可能是正确的。
–cpast
2014年2月10日在21:31
#6 楼
您的计算机可以执行的随机数生成适合大多数需求,并且您不太可能需要真正的随机数。真正的随机数生成虽然有其用途。在计算机安全,赌博,大量统计采样等方面。
如果您对随机数的应用感兴趣,请查阅Wikipedia文章。
评论
最大的问题是当您需要攻击者出于安全原因无法预测的随机数时。
– David Schwartz
2014年2月5日,下午3:45
您肯定会在需要一个真正随机数的时候遇到麻烦。打开以https:// ...开头的网页就足够了。
– Jan Hudec
2014年2月5日在7:47
@JanHudec:嗯,在日常使用中,打开任何程序时都需要安全的随机数,正好是在输入地址栏之前:请参阅地址空间布局随机化。这就是为什么发生这种情况的原因。
–里德
2014年2月5日在8:31
@JanHudec我的意思是要使用在线随机数生成器。真正的随机数经常使用,但是实际上很少有人需要自己生成它们。
– Alex McKenzie
2014年2月6日在6:02
老虎机也使用PRNG,而不是TRNG。生成器一直运行,并在按下旋转按钮的确切时间选择一个数字。 PRNG和真正的随机按钮按下时间之和等于TRNG。
–罗杰·达尔(Roger Dahl)
2014年2月10日19:00
#7 楼
大多数编程语言中由典型函数生成的随机数并非纯粹是随机数。它们是伪随机数。由于它们不是纯粹的随机数,因此可以用先前生成的数字的足够信息来猜测它们。因此,这对于加密安全性而言将是一场灾难。例如,在
glibc
中使用的以下随机数生成器函数不会生成纯粹的随机数。由此产生的伪随机数可以猜测。这是安全问题的大错。有这种灾难性的历史。 glibc random():
r[i] ← ( r[i-3] + r[i-31] ) % (2^32)
output r[i] >> 1
这种类型的伪随机数生成器永远不要在安全敏感的地方使用,即使在统计学上非常重要。
对伪随机密钥的著名攻击之一是对802.11b WEP的攻击。 WEP具有104位的长期密钥,并与24位的IV(计数器)相连接以构成128位的密钥,然后将其应用于RC4算法以生成伪随机密钥。
( RC4( IV + Key ) ) XOR (message)
键彼此紧密相关。在此,每一步仅将IV增加1,其他所有步保持不变。由于这并非纯粹是随机的,因此是灾难性的,很容易分解。通过分析大约40000帧即可恢复密钥,这只需几分钟。如果WEP使用纯随机的24位IV,那么直到大约2 ^ 24(将近1680万)帧之前,它才是安全的。
因此,当安全敏感问题出现时,应该使用纯随机数生成器可能。
评论
我会把WEP的问题归咎于使用弱密码而设计不良的协议。使用现代流密码,您可以将计数器用作IV。
– CodesInChaos
2014年2月5日在9:05
WEP的主要问题是在2 ^ 24(近1600万)帧中重复密钥。相关密钥甚至更糟,这使得在大约40000帧中破解代码成为可能。这里的重点是密钥不是随机的。它密切相关,因此很容易破解。
–布拉布
2014年2月5日在18:18
仅当生成加密密钥时,伪随机性在加密中才是不好的。除此之外,还可以。确实,RC4只是一个伪随机数生成器,其种子是将密钥XOR的128位扩展扩展到消息的明文上。
–马特
2014年2月11日下午5:14
#8 楼
不同之处在于伪随机数生成的数字在一段时间后是可预测的(重复的),而真正的随机数不是。重复的时间长短取决于种子生成的时间。以下是有关该主题的非常不错的视频:http://www.youtube.com/watch? v = itaMNuWLzJo
评论
可预测性!=重复。 Mersenne Twister就是一个很好的例子。在624 Int32之后的大多数实现中,您可以预测所有下一个数字,但是Mersenne Twister序列要长得多(2 ^ 19937-1)。
–HoLyVieR
2014年2月8日在1:58
我不明白为什么这个答案没有被推高,因为在我看来,这至少是部分问题的准确而简洁的答案。伪随机数可以在一些抽签之后容易地预测,抽签的数量随伪随机算法“质量”而变化。选择一种“好的”算法要着眼于以下方面:1.每个值以相等的频率(分布)绘制,2.需要“很长时间”才能从头开始重新启动序列,并再次从图中开始绘制相同的数字。相同的顺序。
–分钟
2014年2月8日在16:06
“真正的随机数不是[可预测的]”。今天,这是真的。现在,如果我们相信“大爆炸”理论,并且有足够的能力根据物理原理在BB之后的任何时间计算宇宙的状态,那么我们就能预测未来,包括以下事实:我正在写这个非常准确的评论。对?
–分钟
2014年2月8日在16:14
假设是正确的,但是考虑到人体实际动作所涉及的熵的巨大程度,所需的计算能力将非常高。想想计算机覆盖的大洲。另外,由于依赖于先前的状态,将需要存储宇宙中每个时间点上每个身体的状态,根据定义,这将需要比宇宙中可用空间更多的空间,并完全用存储设备填充
–环境主义者
2014年2月9日在13:43
@TheEnvironmentalist-啊! “计算机覆盖的大陆” ...不是《银河旅行者指南》的全部内容吗? ;-)
–ysap
14年2月15日在8:16
#9 楼
假设任何人都可以在生成伪随机数之前猜出它。对于微不足道的应用,伪随机性很好,就像您的示例一样,您将获得大约正确的百分比(大约1 /总结果集的第6个),但有一些细微的变化(您将看到是否掷骰子60万次);
但是,涉及计算机安全之类的问题;真正的随机性是必需的。
例如,RSA算法首先从计算机选择两个随机数(P和Q)开始,然后对这些数字执行几个步骤,以生成称为公钥和私钥的特殊数字。 (私有密钥的重要部分是它是私有的,其他人都不知道!)
如果攻击者可以知道您的计算机将要选择的两个“随机”数字,它们可以执行相同的步骤来计算您的私钥(其他人不应该知道的!)
利用您的私钥,攻击者可以执行以下操作:a)与您的银行假装是您,b)聆听您的“安全”互联网流量并能够对其进行解码,c)您与互联网上其他各方之间的伪装。
这就是真正的随机性(即无法猜出/计算出)是必需的。
#10 楼
我曾经使用的第一个随机数具有任何两个连续随机数的出色性能,第二个随机数更大,概率为0.6。不是0.5。第三个大于第二个,概率为0.6,依此类推。您可以想象模拟会如何造成破坏。有些人甚至不相信我,即使随机数是均匀分布的,但如果您看一下序列(1、3、5、2、4、1, 3、5、2、4,...),其中两个数字中的第二个以0.6的概率较大。
另一方面,对于模拟来说,能够重现随机数可能很重要。假设您进行了流量模拟,并想了解您可能会采取的某些措施如何改善流量。在这种情况下,您希望能够通过尝试改善交通状况的不同操作来重新创建完全相同的交通数据(例如试图进入城镇的人)。
#11 楼
简短的答案是,通常人们出于一个不好的原因而要求“真正的随机性”,即他们不了解密码学。诸如密码学和CSPRNG之类的密码原语用于产生大量不可预测的信息流一旦它们被喂了一些不可预测的比特。
细心的读者现在将意识到这里存在一个引导问题:我们必须收集一些熵才能将其全部启动。然后be可以将它们提供给CSPRNG,后者将愉快地提供我们需要的所有不可预测的位。因此,需要硬件RNG来播种CSPRNG。这是真正需要熵的唯一情况。
(我认为这应该已经发布在安全或密码学中。)
编辑:最后,必须选择一个足以满足预期任务的随机数生成器,就随机数生成而言,硬件不一定等同于良好的生成器。就像不良的PRNG一样,硬件随机源通常也有偏差。
编辑:这里的一些人假设使用一种威胁模型,攻击者可以在其中读取CSPRNG的内部状态,然后得出结论,即CSPRNG不是一个安全的解决方案。这是不良线程建模的一个示例。如果攻击者拥有您的系统,则游戏已经结束,简单而简单。此时,您使用TRNG还是CSPRNG都没有任何区别。
编辑:因此,总结所有这些……熵是CSPRNG的种子。一旦完成,CSPRNG将比我们(通常)收集熵快得多的速度提供安全应用程序所需的所有不可预测的比特。如果不需要不可预测性(例如,对于模拟),梅森扭曲器将以更高的速率为数字提供良好的统计属性。
编辑:任何愿意了解安全随机数生成问题的人都应阅读以下内容:http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf
评论
这不一定是安全问题。我认为有理由使用不涉及安全性的真正随机数。如果我要进行一些依赖于随机数的科学研究,并且无论出于何种原因至关重要,那么随机数都应尽可能地随机,那么我当然会利用硬件RNG的优势,因此我可以放心,观察到的任何特性都不应该归因于对RNG的怪癖。
– Kef Schecter
2014年2月5日14:13
@KefSchecter他们听到的硬件PRNG通常具有偏差和/或相关的输出。他们需要后处理步骤才能将其转换为统一的独立输出。没有理由相信此后处理步骤比现代流密码更可靠。我当然会更信任流密码。作为额外的奖励,它是可重现的,这在科学中很有价值。
– CodesInChaos
2014年2月5日在17:45
好,可以。但是,难道不是同样适用于密码学应用程序吗?即使是这里的gievn回答,您也需要硬件RNG来播种CSPRNG。
– Kef Schecter
2014年2月5日在20:41
@KefSchecter是的,加密应用程序需要真实的随机数来播种CSPRNG。但是对于其他所有内容,我们都可以使用该CSPRNG。
– CodesInChaos
2014年2月6日在16:56
@KefSchecter:加密应用程序要求该流不能被整个世界复制。相比之下,在科学应用中,能够证明一个人正在使用的“随机”数字并非简单地选择用来很好地展示自己的分析,这是有帮助的。例如,如果某人在宣布自己的方法后宣布将使用第二天的州彩票号码以某种方式生成数据,那么即使平日的图纸只有几打,读者也可以确信自己并没有对结果进行捏造熵位。
–超级猫
2014年2月15日下午4:03
#12 楼
并非所有PRNG都适合所有用途。例如,Java.util.SecureRandom使用SHA1哈希,其输出大小为160位。这意味着可能有2160个可能的随机数流。就那么简单。您所获得的内部状态值不能超过2160。因此,无论您的种子来自何处,都无法从单个种子获得2160个以上的唯一随机数流。 Windows CryptGenRandom被认为使用40字节状态,它具有2320个可能的随机数流。随机播放标准52卡组的方法为52 !,大约为2226。因此,无论播种如何,您都无法使用Java.util.SecureRandom来洗牌。它无法产生大约266种可能的混洗。当然,我们不知道它们是哪一个...
所以,如果我有一个256位真正随机性的来源(例如,来自Quantis RNG卡),我可以用该种子为PRNG之类的CryptGenRandom()种子,然后使用PRNG洗牌。如果每次混洗都以真正的随机性来进行播种,那会很好:不可预测且统计上是随机的。如果我对Java.util.SecureRandom做同样的事情,将可能无法产生洗牌,因为它无法以256位熵进行播种,并且其内部状态无法表示所有可能的洗牌。
请注意,java.util.SecureRandom结果既不可预测,而且在统计上也是随机的。没有任何统计测试可以确定问题!但是RNG的输出不足以覆盖模拟一副纸牌所需的所有可能输出的全部范围。
请记住,如果添加了小丑,它的数量就是54个!您必须涵盖的范围,这大约需要2238种可能性。
评论
您为什么要担心某些改组不会发生?这种限制没有明显的效果。
– CodesInChaos
2014年2月6日在16:20
我对这个问题有些疑惑。对于监管严格的游戏公司,这种偏见可以从数学上证明您使用计算机而不是纸牌游戏赢得纸牌游戏的机会是不同的。机会的好坏并不重要。他们是不同的。该计算机在道德上并不等同于真实的卡座。此外,我们无法描述差异。面临严厉的监管罚款的博彩公司将非常关心。
– Paco Hope
2014年2月6日下午16:26
但这是可检测的。我使用一个已知过程对其进行检测:源代码审查和问题域知识。那是了不起的。我不能使用自动统计分析。它与使用java.util.Random或Mersenne Twister的用户一样可检测。统计分析不是RNG /问题域不匹配的唯一有效检测机制。根据定义,通过该检测器的失败不是成功。
– Paco Hope
2014年2月6日在16:40
我从不不同意那句话。我的意思是,统计分析并不是RNG / PRNG正确无误的证明。这是一个假阴性的例子。它应该是不正确的,但是统计输出测试将通过它。如果我将SHA1(1),SHA1(2),SHA1(3)... SHA1(n)用作我的“ RNG”,这也将通过统计测试。这也是错误的。正确的定义超出了“通过统计检验”的定义。通过统计测试是必要的,但还不够。
– Paco Hope
2014年2月6日17:09
@CodesInChaos:论点“我们不知道可以利用绝大多数可能的IRL改组将永远不会产生的事实的攻击”,并不意味着这样的攻击是不可能的,只是我们没有不知道它是什么或如何防御它。在这种情况下,正确的态度是通过消除条件来消除攻击的可能性:制造质量足够高的RNG,使其实际上可以生成所有可能的套牌。
–埃里克·利珀特
2014年2月7日,0:02
#13 楼
伪随机数是使用数学函数和初始值(称为种子)生成的,而随机数不是。它们的可预测性使它们对于游戏重播极为有用,因为您只需要保存种子和玩家输入-AI每次都会以完全相同的“随机”方式做出响应。#14 楼
“真实”随机数和“伪”随机数之间的差异是可预测性。但是,可预测性并不一定像大多数示例所示的那样糟糕。这是一个可预测性很好的罕见情况的实际例子:全球定位系统。每个卫星使用适合自动相关或互相关的不同PRN码(Gold码)。这是测量信号传播时间所必需的。对于这些Gold码,彼此之间的相关性特别弱,从而可以明确识别卫星,但允许通过发射序列与接收器之间的相关性进行距离计算。
#15 楼
为了快速检查随机性,您可以在[0; 1)中获取具有随机坐标的点,然后将其置于k维立方体中。然后执行将这个立方体切成子立方体的过程-必须按照众所周知的定理通过此过程正确测量子立方体(或子球体)的每个体积。满足的随机性很重要...
安全目的。当您生成数字用作密钥生成的参数时,它是可以很好预测的-敌人会以100%的概率找到它,并使搜索范围变得更小。
科学目的。在科学中,您不仅必须拥有处于良好状态的平均均值,而且还必须消除各种随机数之间的相关性。因此,如果采用(a_i-a)(a_ {i + 1} -a)并找到其分布,则它必须与统计信息相对应。
对相关性被称为“弱随机性”。
如果要获得真正的随机性,则必须具有2个以上方差的高阶相关性。
如今,只有量子力学生成器才能提供真正的随机性。
#16 楼
为什么真正的随机性很重要?
基本上需要真正的随机性的主要原因有两个:
如果使用RNG用于密码学(包括真钱赌博和开彩票之类的东西),那么PRNG将使您的密码变得比您认为的数学分析(假设为TRNG)弱得多。 PRNG实际上不是随机的,而是具有模式的-攻击者可以利用该模式来破解本应不可破解的密码。
如果您使用RNG来模拟“随机”输入,例如错误测试或仿真,那么PRNG会使您的方法变得脆弱。当您没有发现任何bug时,总会有一个令人困扰的疑问:是否存在我的PRNG模式不明显的bug,但是如果我仅使用TRNG就会出现?我的模拟结果是否准确地描述了现实,还是我发现的现象仅仅是PRNG模式的伪影?
在这些区域之外,这并不重要。注意:如果您的PRNG非常非常糟糕,可能仍然不合适-您不想制作掷骰子总是连上骰子的掷骰子游戏,而您的玩家会不喜欢它。
Python的PRNG不够好吗?
使用这种简单的方法,您不太可能检测到真实PRNG的缺陷。 RNG的统计分析本身就是一个科学领域,并且可以使用一些非常复杂的测试来对算法的“随机性”进行基准测试。这些比您的简单尝试要先进得多。
每个创建现实世界库的软件开发人员(例如Python开发人员)都将这些统计测试作为衡量标准,以查看其PRNG实现是否足够好。因此,除了实际的开发人员监督之外,您几乎不可能在实际的PRNG中轻松检测到模式。这并不意味着没有模式-PRNG从定义上就具有模式。
#17 楼
基本上,您无法通过对输出的数学分析来证明来源是随机的,例如需要一个物理模型,表示源是随机的(如放射性衰变)。您可以运行批处理测试以找到输出数据中的统计相关性,在这种情况下,数据被证明是非随机的(但随机源也可以有非随机输出,如果不能给出特定的输出,它就不是真正的随机)。否则,如果通过测试,则可以说数据是伪随机的。
通过一些随机性测试仅意味着您拥有良好的PRNG(伪随机数生成器),这对于安全性较高的应用程序很有用。
如果涉及安全性(即加密,生成密钥盐,用于赌博的随机数生成...),那么拥有良好的PRNG是不够的,它需要具有其他品质,例如在不容易从以前的输出中猜出功能输出的情况下,该功能需要具有可取的计算成本(要有足够的限制才能使用,但又要足够高以克服残酷的强制尝试),运行该功能的硬件或设备。今天奇怪的情况是它是一个模拟设备-不应该轻易篡改,等等。
具有良好的PRNG可以在游戏中创建新的不可预测的模式以及加密方面非常有用-太繁琐,无法在一个帖子,只是想作为拇指角色退出加密系统n该过程应该是伪随机的,不显示可能将先前的加密数据与随后的加密数据相关联,或者将纯文本数据与加密数据相关联,或者将两个不同的密文彼此关联的模式(因此可以对纯文本进行猜测)。 ...
#18 楼
简短的故事:通过使用系统的当前微秒来生成随机种子。
此技巧相当古老,并且仍然可以使用。
不包括暴力因素,我可以通过“下注”所有可能的数字来确定每种组合,而这并不是这个问题的重点,特别是当大多数随机数在使用前四舍五入时。
举个例子,我可以仅使用10个值来确定使用的种子。因此,知道种子后,我就可以猜出下一个值。
如果我使用seed = 1,那么我可以获得下一个序列:
1、2、3 ,4、5、6、7、8、9 ...(然后我推断出种子使用ID 1和下一个值10)
但是,如果更改send “第n个”值?将种子更改当前的微秒是一个便宜的技巧(也就是说,它不需要很多CPU周期)。
所以现在的顺序是:
(seed = 1)1,2 ,3、4、5,(种子= 2),7、9、11、13 ...(15吗?)
在这种情况下:
a)I
b)嗯,我猜不出下一个值。
c)我唯一能做的就是扣除
无论如何,大多数现代随机生成器算法已经在后台使用了这种技巧。
真正的事实是,我们不会需要一个量子计算机来创建一个“真实的”随机数,我们计算机的石英晶体的不精确性会充当一个随机生成器,而且我们的CPU的随机效率也是可变的,而无需考虑CPU通常会在计算机上执行多项任务同时。
评论
这是一个非常糟糕的主意,它是需要真正不可预测序列的漏洞的源头。如果花费微秒,则只有10 ^ 6的种子可能性很小。
–HoLyVieR
2014年2月8日在1:50
@HoLyVieR:如果您关心安全性,那肯定是个坏主意,但还不如您了解的那么糟糕:自系统启动(或unix epoch ....)以来,通常会使用微秒,这会大大增加可能的值范围。
– mikera
2014年2月9日在2:12
@mikera并没有什么更好的,处理请求的时间是可以预测的。大量的密码重置功能是漏洞的向量。这些脚本使用您的技术生成了“随机”令牌,并且攻击者可以找到所生成的令牌,因为发现执行令牌的时间相当微不足道... ...同时发送密码重置请求的时间为+-150ms。
–HoLyVieR
2014年2月9日在2:53
当然,这种情况非常糟糕。但是,状态是在系统启动时产生种子,并且攻击者没有很好的猜测启动时间的方式的情况并没有那么糟糕。您可能很容易就可以选择10 ^ 12个微秒,这会使某些类型的攻击变得不可行。需要明确的是:从加密角度来看,所有这些解决方案都非常糟糕,但是常量很重要。
– mikera
2014年2月9日在4:27
对于在线服务器,有时会公开提供系统正常运行时间信息。或者,您可以从状态页面“事件。再次启动服务器”中获取它。或者,您可以Ping,等待大量的停机时间,然后注意这可能是计算机重新启动(这将花费数亿时间进行检查,这相当少)。
–德雷克森
2014年2月9日在8:07
评论
看看有关硬件生成的随机数的Wikipedia文章另请参阅此-stats.stackexchange.com/questions/32794/…“掷骰子”是什么意思?它是否装有机械臂和相机?
虽然我同意您语气的基本要点,但我们经常对此担心太多,但在现实生活中已被利用:en.wikipedia.org/wiki/Ronald_Dale_Harris
有关为何如此重要,请参见有关在线扑克游戏缺少真正随机性的文章。
如果仅保留0-5个计数器并相应地掷骰子(666亿亿次),那么您也将获得均等的分配。