从线性同余生成器预测值

X_n = (aX_(n-1) + c) mod m

#1 楼

此答案与该问题的一个较早变体有关，该变体曾给出a，c和m的示例问题，如下所示：


考虑一下在Java中打印100的以下内容从0到5的随机数：

Random r = new Random(); // seeded by system time for (int i=0; i<100; i++) System.out.println(r.nextInt(6));

其中r.nextInt(6)本质上是：

seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1); // i.e. seed = (seed * multiplier + addend) $ \ bmod 2 ^ {48} $ <是的，可以从其线性输出生成器的第一个输出预测其输出。首先，唯一未知的是int bits = (int)(seed >>> (48 - 31)); return bits % 6;的原始值，即48位。给定适当的资源（一些CPU.days），这可能是蛮力的，而且我们有足够的输出（如果输出是真正随机的，则大约有$ 100 \ cdot {log} _2（6）\ approx 258 $位信息）。但是，可能有更好的攻击方法，可以在几秒钟内成功。

问题本身已经发生了变化。最初，它使用的是8的小整数（最终模数），而不是6。我们首先研究它，因为事实证明它更容易，并且对于使用6.的版本来说是一个很好的介绍。

问题，以seed结尾


此处return bits % 8有48位，seed是它的最左边31位，结果bits是那3位低位。 bits % 8的高28位永远不会有机会影响发生器的输出（在模数seed为2的幂的LCG中，m的位变化永远不会传播到seed的低阶位）。因此，出于预测输出的目的，seed表现为20位（而非48位）状态。此外，可以从第一个输出中直接知道该减少的20位状态的3个高位。

现在，由于除了RNG的初始状态之外的所有其他信息都是已知的，因此对其余17位进行了强行强制几乎是瞬间。有一些更聪明的方法可以避免猜测。

这说明当使用2的幂作为模数seed的LCG的输出取模数为2的幂的m时，输出的周期比原始LCG小得多（其他缺点即使对于仿真也可能是个灾难。目的）。

更新：事实证明Java的n方法是特例，当nextInt(int n)为2的幂时，会发生什么，然后做的事情与原始问题中所显示的完全不同。这样做是为了避免上述效果。

其他问题以n结尾


这里，return bits % 6的所有48位都对输出序列有影响。但是，有一种简单的方法可以将这48位分解为两个分别受到攻击的段。

因为最终模数6是偶数，所以seed的低位也是输出的低位，并且直接泄漏。它是主LCG的高位，减少为bits的低18位。这样就可以从第一个输出的低位恢复seed的低18位（我想应该多于18位）。一种简单的方法是枚举seed的低18位的$ 2 ^ {18} $值，并对每个校验，检查给出第一个输出值的正确奇偶性。这样一秒钟就能很好地恢复seed的低18位，并且足以预测进一步输出的奇偶校验。再次，有一些更聪明的方法可以避免猜测。

现在我们剩下seed的30个高位未知；可以在几秒钟内强行使用。可能有更聪明的方法。

更新：事实证明，即使seed不是2的幂，Java的nextInt(int n)方法也不能完全如原始问题所示。这是为了消除输出中的偏差。但是，给出的简化描述足够好，以至于所描述的密码分析有很大的机会按原样工作，并且可以进行调整以可靠地工作。


更新2：上面的方法起作用，因为n是2的幂，并且最终模数m被$ 2 ^ k $除以$ k> 1 $。这允许对$ k + r $个低位进行单独攻击，其中$ r $是n不用于生成输出的右位数目（在上面的示例中，$ k = 1 $，$ r = 17 $） 。如果seed和/或a和/或$ r $是未知的，则仍然有可能进行这种分离，并找到c，seed和a的每一个的$ k + r $低位，以及$ r的值不考虑其他未知数，从连续的多个$ \ bmod 2 ^ k $输出的$。 c和/或n可以在布尔可满足性的形式下对问题进行编码，并使用许多可用的自动求解器之一。我无法预测运行时间。这种灵活的方法打破了一些轻度严重的密码，例如这种对A5 / 1的密码分析或这种密码分析。


LCGs严重不利于加密。它们适合用于连续仿真（将输出转换为浮点数的尾数并直接用于浮点数），但对于离散仿真则很脆弱。特别是，如果LCG使用2的幂作为模数a，则不要将其输出模数设为偶数，并期望结果像骰子那样具有一定数量的面：假设不正确，许多简单的测试将显示那个。

例如，连续（模拟）掷骰子时，奇数和偶数之间的不平衡在抛出$ 2 ^ {1 + r} $之后精确地为零。使用c甚至m的双向卡方检验，甚至可以用更少的样本检测到这一点。难以置信的可以运行此测试代码；当真正的随机数通常会给出3位数时，它几乎总是输出0（例外是另一个个位数）。

import java.util.Random;
public class diceparity {
    public static void main(String[] args) {
        final int m = 262144; // number of dice throws
        Random rand = new Random();
        int s = -m/2; for (int i = m; i != 0; --i)
            s += rand.nextInt(6)%2;
        System.out.println("Deviation from expected: "+s);
    }
}

奇偶校验在262144投掷（或略少）后重复。

#2 楼

是。我手头没有参考资料，但我敢打赌，您可以使用自己喜欢的搜索引擎进行查找。我记得，使用线性同余生成器中的三个值，您可以预测值。如果您只截断到八位，可能会更多，但这是一个可怕的缺陷，您甚至不应该考虑这么多。

如果您必须使用快速-和肮脏的随机位生成器，采用一个不错的哈希函数（即使SHA-1对此也足够好）并迭代哈希值。用于复制上下文，将其最终确定并随后将值散列到累积上下文中的奖励积分。

但是，使用设计为快速PRNG的东西可以获得更多的奖励积分。获得NIST AES-CTR DRBG（即确定性随机位生成器）的实现，该实现在计数器模式下使用AES生成随机位。

有开源实现，即使使用软件AES。我使用的最后一个甚至比rc4random更快，后者是许多unix的一部分。如果您使用的是带有AES-NI的Intel处理器（并进行了软件工程设计），它的运行就像是发臭的一样。获得良好的PRNG。

编辑

回应您的评论，请看这篇名为“如何破解线性同余生成器”的文章。它甚至包含源代码。