提取 PRNG 的初始种子值？
我最近读到，如果您满足以下条件，您就可以预测 PRNG 的结果：
- 知道正在使用什么算法。
- 具有连续的数据点。
是否可以仅根据数据点找出用于 PRNG 的种子？
I recently read that you can predict the outcomes of a PRNG if you:
- Know what algorithm is being used.
- Have consecutive data points.
Is it possible to figure out the seed used for a PRNG from only data points?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我设法找到了 Kelsey et al 的论文，其中详细介绍了不同类型的攻击，并总结了一些现实世界的例子。似乎大多数攻击都依赖于与针对密码系统的类似技术，并且在大多数情况下实际上利用了密码系统中使用 PRNG 的事实。
I managed to find a paper by Kelsey et al which details the different types of attack and also summarises some real-world examples. It seems most attacks rely on similar techniques to those against cryptosystems, and in most cases actually taking advantage of the fact that the PRNG is used in a cryptosystem.
当然，“足够”的数据点是 PRNG 生成的绝对第一个数据点，没有间隙。大多数 PRNG 函数都是可逆的，因此只需向后操作，您就应该获得种子。
例如，典型的
returnseed=(seed*A+B)%N具有returnseed=((seed-B)/A)%N的逆。With "enough" data points that are the absolute first data points generated by the PRNG with no gaps, sure. Most PRNG functions are invertible, so just work backwards and you should get the seed.
For example, the typical
return seed=(seed*A+B)%Nhas an inverse ofreturn seed=((seed-B)/A)%N.从理论上讲，如果您被“允许”暴力破解种子的所有可能值，并且您有足够的数据点表明只有一个种子可以产生该输出，那么从理论上讲，这总是可能的。如果 PRNG 是用时间作为种子的，并且您大致知道发生的时间，那么这可能会非常快，因为没有太多可信的值可供尝试。如果 PRNG 的种子来自具有 64 位熵的真正随机源的数据，那么这种方法在计算上是不可行的。
是否还有其他技术取决于算法。例如，对 Blum Blum Shub 执行此操作相当于整数分解，这通常被认为是一个困难的计算问题。从这个意义上说，其他更快的 PRNG 可能不太“安全”。任何用于加密目的的 PRNG（例如在流密码中）几乎都需要没有已知的可行方法来实现。
It's always theoretically possible, if you're "allowed" to brute force all possible values for the seed, and if you have enough data points that there's only one seed that could have produced that output. If the PRNG was seeded with the time, and you know roughly when that happened, then this might be very fast since there aren't many plausible values to try. If the PRNG was seeded with data from a truly random source having 64 bits of entropy, then this approach is computationally infeasible.
Whether there are other techniques depends on the algorithm. For example doing this for Blum Blum Shub is equivalent to integer factorization, which is generally believed to be a hard computational problem. Other, faster PRNGs might be less "secure" in this sense. Any PRNG used for crypto purposes, for example in a stream cipher, pretty much needs there to be no known feasible way of doing it.