提取PRNG的初始种子值？

Question

最近，我读，你可以预测PRNG的结果，如果你：

1. 知道正在使用哪种算法。
2. 有连续的数据点。

是否可以从数据点中计算出用于PRNG的种子？

Answer 1

我设法找到Kelsey et al的论文，详细描述了不同类型的攻击，并总结了一些真实世界的例子。似乎大多数攻击依赖于类似技术来对付密码系统，并且在大多数情况下实际上利用了PRNG被用于密码系统的事实。

Answer 2

肯定的是，“足够”的数据点是由PRNG生成的绝对第一个数据点，没有间隙。大多数PRNG功能都是可逆的，所以只需反向工作，就可以获得种子。

例如，典型的return seed=(seed*A+B)%N具有return seed=((seed-B)/A)%N的倒数。

Answer 3

如果你“允许”强行推测种子的所有可能值，并且如果你有足够的数据点，只有一个种子可以产生该输出，那么总是在理论上是可能的。如果PRNG随时间播种，并且大致知道发生了什么时，那么这可能会非常快，因为没有太多合理的值可供尝试。如果PRNG用来自具有64位熵的真正随机源的数据播种，则这种方法在计算上是不可行的。

是否还有其他技术取决于算法。例如，对Blum Blum Shub这样做相当于整数因子分解，这通常被认为是一个难以计算的问题。其他更快的PRNG在这个意义上可能不太“安全”。任何用于加密目的的PRNG，例如流密码，几乎都不需要知道可行的方法。