logo标签列表

运行时如何生成随机数？

c#algorithmprogramming-languagesrandom
13

由于计算机不能随机选择数字（难道它们可以吗？），那么这个随机数是如何生成的呢？例如在C#中，我们说：

Random.Next()

里面会发生什么？

5
搜索 - 这个问题已经有了数十个答案。 - RogerG
这是另一个涉及请求AS3实现随机.next的主题：http://stackoverflow.com/questions/3930291/actionscript-3-implementation-of-random-next 这里面还包含了代码片段。 - Stephan Schinkel
1
@RogerG > 你有链接分享吗？因为我没有看到任何链接... @hacticks > 非常感谢 - naveen
我在这里找到了两个有对话和额外链接的问题：https://dev59.com/j3VD5IYBdhLWcg3wQZQg或https://dev59.com/MnRB5IYBdhLWcg3wZmlz - RogerG
7个回答
14
1
这是一篇非常好的文章，它包括了一些链接到源代码，展示了一些伪随机数生成器，这非常棒。+1 - Michael Trausch
7
由于计算机不能选择随机数（可以吗？），正如其他人所指出的，“随机”实际上是伪随机。回答你的括号内问题：是的，计算机可以选择真正的随机数。这样做比伪随机数生成器的简单整数算术要昂贵得多，并且通常不需要。但是，有些应用程序必须具有不可预测的真正随机性：密码学和在线扑克立即想到。如果其中任何一种使用可预测的伪随机性源，则攻击者可以更轻松地解密/伪造消息，而作弊者可以弄清楚谁手中拥有什么。

.NET加密类具有适用于加密或涉及资金的游戏的随机数的方法。至于它们的工作原理：关于加密强度的随机性的文献非常广泛；有关详细信息，请参阅任何一本好的大学本科密码学教材。

还存在专门硬件以获取随机位。如果您需要从大气噪声中抽取的随机数，请参见www.random.org。

2
所有基于计算机/逻辑的随机数生成器都是伪随机的，除非它们具有真正的随机源。随机源可以是放射性衰变之类的东西。一些计算机硬件具有随机数生成器，其晶体管处于不稳定状态并创建随机位的恒定流。伪随机和真随机的区别在于伪随机是确定性的，但从许多来源提取数据并且很难预测，而真正的随机是即使您知道所有来源，直到发生事件之前仍然无法知道输出结果。 - Bengie
@Bengie：我相信加密类从诸如击键时间等来源中派生出它们的熵。对于实际目的，这些源是足够随机的。 - Eric Lippert
1
所以Crypto类确实有良好的熵源？那么在没有人为干预且无法使用人作为熵源的服务器上呢？我知道一个好的熵源是将一个拆解的烟雾探测器与一个未经滤波的网络摄像头紧贴其放射性部分。它还可以作为一个很棒的屏幕保护程序，提供一串漂亮的随机位元流 :-) - Bengie
1
@Bengie：我不知道加密类为其熵源做了什么。按键时间只是系统内可能的熵源之一。如果您对加密类的实现细节感兴趣，应该向专家咨询。 - Eric Lippert
5
Knuth很好地涵盖了随机性的主题。
我们并不真正理解随机。可预测的东西如何是随机的？然而，伪随机序列可以通过统计测试看起来完全随机。
有三类随机生成器，扩展了上面的评论。
首先，您有伪随机数生成器，如果您知道当前的随机数，那么计算下一个随机数就很容易。如果您发现一些数字，则可以轻松地逆向工程其他数字。
然后，有加密算法使这个过程更加困难。我认为它们仍然是伪随机序列（与上面的评论相反），但具有非常重要的特性，即知道序列中的一些数字并不会让其明显如何计算其余部分。其工作方式是加密程序倾向于散列该数字，因此如果一个位改变，则每个位等可能地改变。
考虑一个简单的模数生成器（类似于C rand()中的某些实现）
int rand() { return seed = seed * m + a; }
如果m=0并且a=0，则这是一个周期为1的不好的生成器：0、0、0、0、.... 如果m=1并且a=1，它看起来也不是很随机：0、1、2、3、4、5、6、... 但是，如果您选择m和a为2^16左右的质数，则这将跳跃得很好，如果您只是随意检查，它看起来非常随机。但是由于两个数字都是奇数，您会发现低位会切换，即该数字交替为奇数和偶数。不是一个很好的随机数生成器。而且，由于32位数字中只有2^32个值，因此按定义，在最多2^32次迭代后，您将再次重复序列，从而明显地表明生成器不是随机的。如果您认为中间的位已经很好地混合在一起，而较低的位不太随机，则可以通过其中几个构造更好的随机数生成器，各个位异或在一起，以便所有位都被很好地覆盖。例如：(rand1() >> 8) ^ rand2() ^ (rand3() > 5) ...

尽管如此，每个数字都在同步翻转，这使得它变得可预测。如果您获得两个连续的值，它们是相关的，因此如果您绘制它们，您将在屏幕上获得线条。现在想象一下，您有结合生成器的规则，使得连续的值不是下一个值。 例如

v1 = rand1() >> 8 ^ rand2() ... v2 = rand2() >> 8 ^ rand5() ..

并且想象种子不总是会前进。现在，您正在开始制作一些更难以基于反向工程预测的东西，并且序列更长。

例如，如果您每次计算rand1()，但仅在第3次时才推进rand2()中的种子，则组合它们的生成器可能不会重复超过任何一个周期。

现在想象一下，您将（相当可预测的）模数类型随机数生成器通过DES或其他加密算法进行处理。那将混淆位。

显然，有更好的算法，但这可以给你一个想法。Numerical Recipes实现了很多算法并加以解释。一个非常好的技巧是：在表中生成一组随机值而不是一个。然后使用独立的随机数生成器来选择其中一个生成的数字，生成一个新的数字并替换它。这样可以打破相邻数字之间的任何相关性。
第三类是基于实际硬件的随机数生成器，例如基于大气噪声。

http://www.random.org/randomness/

根据当前的科学，这是真正的随机。也许有一天我们会发现它遵循某些基本规则，但目前，我们无法预测这些值，对我们来说它们是“真正”的随机。

如果您想查看一些源代码，Boost库具有出色的C ++ Fibonacci生成器实现，这是伪随机序列的统治者。

4
我只会回答第一个问题（“他们可以吗？”）。计算机可以生成（好吧，“生成”可能不是一个完全准确的词）随机数（即，不是伪随机数）。具体来说，可以通过使用专用硬件设备获取环境随机性（例如基于噪声生成随机性）或者使用环境输入（例如硬盘时间、用户输入事件时间）来实现。然而，这与第二个问题（即 Random.Next() 如何工作）无关。
2

Random类是一个伪随机数生成器。

它基本上是一个极长但确定性的重复序列。 "随机性" 来自于不同的起始位置。指定起始位置是通过为随机数生成器选择种子来完成的，例如可以使用系统时间或从另一个随机源获取随机种子。默认的 Random 构造函数使用系统时间作为种子。

用于生成数字序列的实际算法在MSDN中有文档记录：

当前 Random 类的实现基于 Donald E. Knuth 的减法随机数生成器算法。有关更多信息，请参见 D. E. Knuth。《计算机程序设计艺术，卷 2：半数值算法》。Addison-Wesley，Reading，MA，第二版，1981年。

那么，我们不应该在加密功能中使用C#的Random类，是这样吗？我想可能会有一些API可用于获取这样的数字，或者需要通过P/Invoke使用Win32函数来实现？ - Michael Trausch
1
@Michael Trausch：你可能想要查看RandomNumberGenerator，以便用于加密目的：http://msdn.microsoft.com/zh-cn/library/system.security.cryptography.randomnumbergenerator.aspx - Mark Byers
1

计算机使用伪随机数生成器。它们的工作原理是从一个种子数字开始，并通过算法迭代每次需要新的伪随机数。

这个过程当然是完全确定性的，因此给定的种子每次使用时都会生成完全相同的数字序列，但生成的数字形成了统计上均匀分布（大约），这是可以接受的，因为在大多数情况下，你只需要随机性。

通常的做法是使用当前系统时间作为种子，但如果需要更高的安全性，则可以从物理源（如磁盘延迟）中收集“熵”以生成更难预测的种子。在这种情况下，您还需要使用密码学强随机数生成器，例如this。

0

我不知道太多细节，但我知道的是种子用于生成随机数，然后基于某些算法使用该种子获得新数字。

如果您基于相同的种子获取随机数，则它们通常会相同。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接