比time(0)更好的种子?(涉及IT技术)

10

我理解time(0)常用于为随机数生成器提供种子,只有当程序每秒运行超过一次时才会成为问题。我想知道在生成随机数时还有哪些更好的种子可供考虑。我了解到Windows上的GetTickCount、timeGetTime和QueryPerformanceCounter。这些是否足以满足几乎所有操作的需求,或者是否有更好的种子选项?

这里是使用boost库的快速代码示例:

#include <iostream>
#include <boost/random.hpp>
using namespace std;
using namespace boost;

int main()
{
    mt19937 randGen(42);
    uniform_int<> range(0,100);
    variate_generator<mt19937&, uniform_int<> > GetRand(randGen, range);

    for (int i = 0; i < 30; ++i)
        cout << GetRand() << endl;
}

这真的取决于随机数的用途。你说time(0)“只有在程序每秒运行一次以上时才会成为问题”,这表明你对随机数的要求非常低。大家都回答了安全需求。如果你只需要每次运行程序时的唯一种子,请将时间和PID连接起来。 - Steve Jessop
是的,显然大型程序,特别是在线游戏,每秒为数万名玩家进行随机数生成,需要更加强大的东西。然而,对于我目前简单的需求来说,每秒慢一点都没问题。我只是好奇。 - trikker
11个回答

12

早期对Netscape安全的一些黑客攻击集中在知道何时发送加密数据包并缩小可能的种子范围。因此,获取一个滴答计数或其他任何稍微确定性的东西都不是您最好的选择。

即使使用种子,"随机"数字序列也是基于该种子确定性的。内华达州游戏委员会的一位调查员意识到了这一点,并利用这一知识在被抓之前赚了很多钱。

如果您需要世界级的随机性,则可以向系统添加提供高度随机化数字的硬件。这就是众所周知的扑克网站的做法(至少他们是这么说的)。

除此之外,从系统中选择许多独立且快速更改的因素,并尽可能少地预测,以创建一个非常不错的种子。 SO上的一个相关帖子的答案建议使用Guid.NewGuid().GetHashCode()。由于Guid基于许多确定性因素,包括时间,因此这不构成种子的良好基础:

WinAPI GUID生成器的密码分析表明,由于V4 GUID序列是伪随机的,因此在给定初始状态的情况下,可以预测函数UuidCreate[2]返回的接下来的250,000个GUID。这就是为什么GUID不应用于密码学,例如作为随机密钥。

来源:Wikipedia全局唯一标识符


6

这是一篇关于在线扑克早期32位种子的有趣故事,因篇幅过长无法放在评论中。

ASF软件中使用的洗牌算法始终以有序的牌组开始,然后生成一系列随机数用于重新排序牌组。在真实的牌组中,有52! (~2^226) 种可能的独特洗牌。请记住,32位随机数生成器的种子必须是一个32位数字,这意味着仅有4十亿个可能的种子。由于每次重新初始化洗牌前都会重置牌组并重置生成器的种子,因此只能从该算法中得出4十亿个可能的洗牌结果。4十亿个可能的洗牌数远远小于52!。

利用这种漏洞开发的RST工具需要知道牌组中的五张牌。基于这五张已知的牌,程序搜索几十万个可能的洗牌,推断出哪一个是完美匹配的。对于德州扑克来说,这意味着程序将作弊玩家分配的两张牌和第一轮公共牌(翻牌)中展示的前三张牌作为输入。在四轮投注的第一轮之后,这五张牌就已知,足以实时(即在游戏进行过程中)确定完全洗牌。

http://www.ibm.com/developerworks/library/s-playing/


5
在Unix系统中,您可以从/dev/random获取一些字节作为随机数生成器的种子。/dev/random应该是非常好的随机源,使用PC上可用的不同熵源。当然,这完全取决于具体实现。
这可能有用的一个例子是加密应用程序,因为time(0)相对容易被猜测。

4
你需要一种备用/次要的熵源。根据你想使用的熵量,你可以计算以下任何输入的哈希值,并将其用作最终生成器的种子:
  • 在堆栈上声明一个未初始化的随机大小的字符数组
  • 分配随机字节的内存
  • 要求用户移动鼠标
  • 要求用户将随机 CD 放入 CD 驱动器中,并从第一轨道的随机位置读取随机字节
  • 打开用户的麦克风或摄像头,收集随机秒数的输入,计算哈希和种子
  • Windows:使用 CryptGenRandom 获取加密随机字节的缓冲区
  • Unix:如其他人所述,从 /dev/random 读取

第二个和第三个可能会带来比它们值得的麻烦。:D - Gordon Gustafson
取决于随机种子对 @trikker 有多重要 :-) - Franci Penov

4
在Unix系统中,可以尝试从/dev/random读取。从该设备读取数据速度较慢,因此不要频繁使用——例如,只用于设置初始种子。随机设备获取来自硬件生成的熵(来自设备的环境噪声)的数据,在给定时间段内没有无限量的可用熵。如果熵耗尽,则SSL库可能会失败。熵在一段时间后重新填充(实际上是一个熵池)。据我所知,还有更经济但不太随机且在熵不足时不会阻塞的urandom。

2

1

使用tickCout()或任何高频率的东西都是一个坏主意。这是因为计数器很快就会循环回零,从而可能具有相同的种子。

time(NULL):   Repeats every 64 years.  
tickCouter()  Repeats every X days.

你可以尝试从自然界中获取一些随机值。
上一秒全球范围内的闪电击中次数(显然这是在线的)?(不过你可能需要进行研究以确定它是否是可变的)。

2
在最后一秒内发生的闪电就像没有超级加密的超级加密。如果攻击者知道您的随机源和生成种子的大致时间,那么由于他可以访问与您相同的数据,您将回到使用 time(0) 的状态。如果攻击者不知道您的随机源,则会有所改善,但这是您能保守秘密的实现细节吗?如果有人发现您连接到哪个网站怎么办? - Steve Jessop
1
由于滴答计数器循环非常快,而time(0)的问题在于它循环得太慢了,显然的解决方案是同时使用两者进行种子生成。如果您的RNG种子仅限于16或32位,则会遇到麻烦。在这种情况下,请使用滴答计数器作为RNG的种子,并保存其中的一些位。使用time(0)重新生成种子并丢弃一些初始值,或使用最初保存的位对所有后续结果进行XOR运算。 - MSalters
投票支持这个回答,因为它很出色。 - trikker

1

你可以在程序退出时存储随机种子,并在启动时加载它,因此你只需要在第一次程序启动时使用time(0)来初始化你的RNG。


你的意思是在退出时存储rng的当前值,并将其用作下一次运行的种子吗? - Patrick

1

既然您已经在使用boost,那么您可能需要boost::random_device

(至少在Linux上是这样。我不记得它的明显CryptGenRandom实现是否已经在Windows上可用。)


0

使用随机数生成器的方法是只需要种子一次,因此您提到的在线游戏的例子并不是问题,因为在程序第一次启动时(可能是几年前),潜在地将使用相同的rng来生成每个值。

同样,在您自己的代码中,尝试仅对rng进行一次种子,并在需要的任何地方使用相同的实例,而不是在各个地方创建具有新种子的新rng。


Patrick,在编程中使用PRNG来种子化其他PRNG会产生相当严重的后果,应该避免使用(除非你绝对知道自己在做什么——有一些方法可以实现这个功能,但没有一个是天真或容易的)。 - Joey
1
它还会影响模拟和其他非加密任务的执行效果,这也是在并行和分布式模拟中适当使用伪随机数生成器的一个痛点原因之一。 - Joey
有趣,我之前不知道这个。你不会偶然间有一个链接能够更详细地解释一下吧? - Patrick

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