有没有办法从数字序列中生成种子？

Question

例如，如果 java 生成伪随机序列：9 3 2 5 6 通过使用 23 作为种子，我怎样才能进行逆运算？即从序列 9 3 2 5 6 中取出 23。

或者如何为某个序列分配种子？

如果有数据库，这很容易做到 - 只需为序列分配一个随机密钥

INSERT INTO SEQUENCE_TABLE VALUES (RANDOM_KEY, SEQUENCE)

但是，如果我不被允许使用数据库，是否有公式可以做到这一点？

Answer 1

是的，对设计不佳的伪随机数生成器的数字流进行逆向工程绝对是容易的，例如 Java 编程语言中的线性同余 PRNG 实现 (

java.util.Random

)。

事实上，只需来自特定生成器的TWO值，以及有关值出现顺序的信息，就可以预测整个流。

Random random = new Random();
long v1 = random.nextInt();
long v2 = random.nextInt();
for (int i = 0; i < 65536; i++) {
    long seed = v1 * 65536 + i;
    if ((int)(((seed * multiplier + addend) & mask) >>> 16) == (int)v2) {
        System.out.println("Seed found: " + seed);
        break;
    }
}

这正是为什么使用经过整个社区审查的加密安全随机数生成器对于需要安全性的实现至关重要。

有更多关于逆向工程 PRNG 的信息，包括

java.util.Random

这里。 ...

Answer 2

随机数生成器的点是这是不可能的。 SecureRandom 的设计特别加密强度，但一般来说，如果您正在编写一个随机数生成器并且这是可能或容易的，那么您就做错了。

也就是说，对于 Java 内置的 Random 类来说，这可能不是“不可能”。 （不过，SecureRandom 是另一个故事。）但这需要大量的数学知识。 更具体地说：如果存在多项式时间算法来执行您想要的操作，对于某些特定的伪随机数生成器，那么根据定义，它会无法通过链接的维基百科文章中描述的“下一位测试”，因为您可以预测将生成的下一个元素。

Answer 3

这篇文章

描述了 Random 线性同余公式背后的数学原理，这里是一个函数，用于从 nextInt() 返回的最后两个整数中发现当前种子。

public static long getCurrentSeed(int i1, int i2) {
        final long multiplier = 0x5DEECE66DL;
        final long inv_mult = 0xDFE05BCB1365L;
        final long increment = 0xBL;
        final long mask = ((1L << 48) - 1);

        long suffix = 0L;
        long lastSeed;
        long currSeed;
        int lastInt;

        for (long i=0; i < (1<<16); i++) {
                suffix = i;
                currSeed = ((long)i2 << 16) | suffix;
                lastSeed = ((currSeed - increment) * inv_mult) & mask;
                lastInt = (int)(lastSeed >>> 16);

                if (lastInt == i1) {
                        /* We've found the current seed, need to roll back 2 seeds */
                        currSeed = lastSeed;
                        lastSeed = ((currSeed - increment) * inv_mult) & mask;
                        return  lastSeed ^ multiplier;
                }
        }

        /* Error, current seed not found */
        System.err.println("current seed not found");
        return 0;
}

此函数返回一个值，可与 rand.setSeed() 一起使用来生成以 i1 和 i2 开头的伪随机数字序列。 

Answer 4

String

作为种子，则可以使用此：

String seed = "9 3 2 5 6";

那么你的生成器将如下所示：

String[] numbers = seed.split(" ");

如果你真的想对java中的“随机”数字生成器进行逆向工程，那将非常困难（我认为）。

如果可以的话，最好以相反的方式进行：从种子开始，产生序列，然后从那里开始计算。

Answer 5

这是压缩的一种特殊情况。您有一个很长的数据序列，您希望能够从较小的信息中无损地重新创建这些数据。如果您的要求是可能的，那么我将能够将整个堆栈溢出压缩为一个整数（因为整个网站可以序列化为一系列数字，尽管很长！）

不幸的是，数学并不是这样运作的。任何给定的序列都有特定的熵度量——该序列的平均复杂度。为了无损地重现该序列，您必须能够编码至少足够的信息来表示其熵。

对于某些序列，实际上可能有一个种子能够生成一个长的、特定的序列，但这只是因为有一个硬编码的数学函数可以采用该种子并生成一个特定的数字序列。但是，要获取“任意”值序列并生成这样的种子，您需要一个种子和一个能够从该种子生成该序列的函数。为了对这两件事进行编码，您会发现您获得的数据比您预期的要多得多！