在C++中找出随机数生成器的种子是什么。

Question

我有一个未经管理的C++控制台应用程序，在其中使用了srand()和rand()函数。虽然我不需要解决特定问题，但我很好奇：在我可以查询的内存中，srand()函数传递的原始种子是否被存储？是否有任何方法可以确定种子是什么？

- Brian

Answer 1

不需要存储种子，只需存储返回的最后一个随机数。

以下是man页上的示例：

       static unsigned long next = 1;

       /* RAND_MAX assumed to be 32767 */
       int myrand(void) {
           next = next * 1103515245 + 12345;
           return((unsigned)(next/65536) % 32768);
       }

       void mysrand(unsigned seed) {
           next = seed;
       }

- P Shved

Answer 2

如果您有一个简单的线性同余生成器，并且您有多个值，则会产生一组方程：

 v1 = ( seed * a + b ) % m
 v2 = (   v1 * a + b ) % m;
 v3 = (   v2 * a + b ) % m;
... 

如果您知道第一个值，您可以倒序查找该序列：

seed = (v1 - b)/a (mod m)

你无法唯一地知道种子，你只知道它对m取模（通常这样做是没有问题的，因为（0 < seed < m））如果v1-b为负数，则需要加上m直到再次变成正数。

你也可以看看中国剩余定理，尽管它不是完全匹配的。

- Justin

---

你刚才说“只需尝试所有64位种子”？你的电脑有多快啊？ :D - Andrew Coleson

尝试所有的64位种子？那将有18,446,744,073,709,551,616个不同的可能性 - 远远超出可行范围。 - Eclipse

如果你知道种子来自哪里，就可以尝试几百万次猜测。通常情况下，srand会使用当前时间作为种子。如果你大概知道生成器最初的种子是什么时候设定的，就可以猜测在那个时间点上time()函数返回了什么值。请记住，不要改变原意。 - Eclipse

是的，64可能现在有点多了，但你绝对可以用现代硬件尝试所有32位数字。请注意，你不需要尝试所有2^64个值，只需尝试小于m的那些值。 - Justin

我认为您可以恢复线性同余发生器的a和b，一旦知道这些，再加上已知的v1和m，种子就可以得到。 - Calyth

Answer 3

理论上来说，不会 - 种子值用于计算下一个随机值，该值（理论上）用于种子下一个随机数，以此类推。

从安全角度来看，能够窥视种子（无论是原始种子还是新种子）是一个严重的安全问题，因此我认为即使必须在某个地方存储它，您也不应该能够查看它。

- Guss

---

我认为“should”应该是“shouldn't”（因为它现在的意思不太合理）。 - Dan Walker

我不知道你的rand()函数使用了什么，但大多数好的函数都会维护一个洗牌表，而不仅仅是一个“当前”状态。 - Justin

-1. rand() 完全不具有密码学安全性，很容易被反向破解。 - tc.

我从未声称rand（）是密码学安全的，但即使您不进行密码学，能够窥视种子也是有问题的 :-) - Guss

Answer 4

我不知道你的汇编熟练程度如何，或者你是否可以访问未管理应用程序的源代码/调试符号，但除了这种诡计之外，没有可行的方法来确定原始种子值。随机数生成器的整个目的是想出一种给你不可预测的数字的方法 - 任何两个rand()调用之间的关系都不应该是可推断的。在密码学强伪随机数生成器中，如果能够根据生成的随机数猜测种子，那将被认为是一个严重的缺陷。

最简单的方法是，在调试器下启动应用程序并设置一个断点，其中包含srand()的调用 - 然后只需查看传递的参数即可。

接下来是反汇编应用程序并找出srand调用的情况。它完全有可能使用当前时间进行播种 - 然后您可以尝试一堆猜测（您可能可以将其缩小到几千个左右），看看是否有任何一个给出与应用程序正在使用的相同的随机数序列。 （当然，这假设您有某种方式知道正在生成的随机值是什么）。也有可能种子始终是像“0”这样的愚蠢东西。

- Eclipse

---

-1. rand() 不是加密安全的，它几乎总是返回 LCG 的高位比特。调用 rand() 函数的几次输出通常足以推断出当前状态，从而向后工作。 - tc.