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

Question

例如,如果java 通过使用23作为种子产生伪随机序列:9 3 2 5 6,我该如何进行反转？即从序列中获得23 个3 3 2 5 6.

或者如何为特定序列分配种子？

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

INSERT INTO SEQUENCE_TABLE VALUES (RANDOM_KEY, SEQUENCE)

但是,如果我不被允许使用数据库,是否有一个公式来做这样的事情？

Answer 1

随机数生成器的要点是这是不可能的.SecureRandom的设计特别强大,但一般来说,如果你正在编写一个随机数生成器,这是可能的或简单的,你做错了.

也就是说,Java内置的Random类可能并非不可能.(尽管SecureRandom是另一个故事.)但它需要数量惊人的数学.

更具体一点:如果存在多项式时间算法来做你想要的,对于某些特定的伪随机数生成器,那么根据定义它将失败链接的维基百科文章中描述的"下一位测试",因为你可以预测将生成的下一个元素.

Answer 2

是的,对设计不良的伪随机数生成器的数字流进行逆向工程是非常容易的,例如Java编程语言中的线性同余PRNG实现(java.util.Random).

事实上,只要该特定生成器的两个值,以及值出现顺序的信息,就可以预测整个流.

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 (((seed * multiplier + addend) & mask) >>> 16) == v2) {
        System.out.println("Seed found: " + seed);
        break;
    }
}

这正是为什么使用加密安全随机数生成器至关重要的原因,这些生成器已被整个社区审查为需要安全性的实现.

有关逆向工程PRNG的更多信息,包括java.util.Random 此处....

Answer 3

当然可以恢复java.util.Random使用的种子。这篇文章描述了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中的“随机”数字生成器进行逆向工程，那将是相当困难的（我认为）。

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