2

我最近读到，如果您满足以下条件，您可以预测 PRNG 的结果：

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

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

4

3 回答 3

2

我设法找到了Kelsey 等人的一篇论文，其中详细介绍了不同类型的攻击，并总结了一些现实世界的例子。似乎大多数攻击都依赖于与针对密码系统的技术类似的技术，并且在大多数情况下实际上利用了 PRNG 用于密码系统的事实。

于 2011-10-06T14:34:14.660 回答
1

当然，“足够”的数据点是 PRNG 生成的绝对第一个数据点，没有间隙。大多数 PRNG 函数都是可逆的，所以只要向后工作，你就应该得到种子。

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

于 2011-10-06T14:32:32.663 回答
0

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

是否有其他技术取决于算法。例如，对 Blum Blum Shub 执行此操作等效于整数分解，这通常被认为是一个难以计算的问题。从这个意义上说，其他更快的 PRNG 可能不太“安全”。任何用于加密目的的 PRNG，例如在流密码中，几乎都需要没有已知的可行方法。

于 2011-10-06T15:55:41.253 回答