10

例如，如果 java 通过使用23作为种子产生伪随机序列： 9 3 2 5 6，我该如何做相反的事情？即从9 3 2 5 6序列中取出23。

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

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

INSERT INTO SEQUENCE_TABLE VALUES (RANDOM_KEY, SEQUENCE)

但是，如果我不允许使用数据库，是否有公式可以做这样的事情？

4

5 回答 5

9

是的，对设计不佳的伪随机数生成器的数字流进行逆向工程绝对容易，例如 Java 编程语言中的 Linear Congruential 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 这里。...

于 2015-03-11T01:33:52.577 回答
6

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

也就是说，Java 内置的 Random 类可能并非不可能。（不过，SecureRandom 是另一回事。）但它需要大量的数学运算。

更具体地说：如果存在多项式时间算法来执行您想要的操作，对于某些特定的伪随机数生成器，那么根据定义，它会通过链接的 Wikipedia 文章中描述的“下一位测试”失败，因为您可以预测将生成的下一个元素。

于 2012-01-20T05:12:09.530 回答
6

恢复 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 开头的伪随机数字序列。

于 2013-11-25T01:23:33.947 回答
2

如果您可以使用 aString作为种子，则可以使用：

String seed = "9 3 2 5 6";

然后您的生成器将如下所示：

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

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

如果可以的话，最好反过来做：从种子开始，产生序列，然后从那里开始。

于 2012-01-20T04:55:56.007 回答
0

您想获取任意数字序列，然后确定一个短（固定长度？）密钥，它允许您重新生成该数字序列，而不存储原始数字？不幸的是，你想要的在技术上是不可能的。原因如下：

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

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

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

于 2012-01-20T05:24:34.983 回答