java - Java的Random函数的反函数

Question

Java 的 Random 函数接受一个种子并产生一个“伪随机”数字序列。(它是基于 Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1 中讨论的一些算法实现的。)，但是这篇文章太技术性了，我无法理解)

它有反函数吗？也就是说，给定一个数字序列，是否有可能在数学上确定种子是什么？(也就是说，暴力破解不算是有效的方法)

[编辑]这里似乎有很多评论......我想我会澄清我在寻找什么。

例如，函数 y = f(x) = 3x 有一个反函数，即 y = g(x) = x/3。

但是函数 z = f(x, y) = x * y 没有反函数，因为(我可以在这里给出完整的数学证明，但我不想绕过我的主要问题)，直观地说，有不止一对 (x, y) 使得 (x * y) == z.

现在回到我的问题，如果你说函数不可逆，请解释原因。

(我希望从那些真正阅读并理解文章的人那里得到答案。像“这是不可能的”这样的答案并没有真正帮助)

Answer 1

如果我们谈论的是 java.util.Random 的 Oracle(née Sun)实现，那么是的，只要你知道足够多的位，就有可能。

Random使用 48 位种子和线性同余生成器。这些不是加密安全的生成器，因为状态大小很小(可暴力破解!)并且输出不是那么随机的事实(许多生成器在某些位中会表现出小的循环长度，这意味着即使这些位也可以很容易地预测如果其他位看起来是随机的)。

Random的种子更新如下:

nextseed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)

这是一个很简单的函数，如果你通过计算知道种子的所有位，就可以倒置它

seed = ((nextseed - 0xBL) * 0xdfe05bcb1365L) & ((1L << 48) - 1)

自从 0x5DEECE66DL * 0xdfe05bcb1365L = 1模组 2⁴⁸。这样，任何时间点的单个种子值都足以恢复所有过去和 future 的种子。

Random但是，它没有揭示整个种子的函数，所以我们必须要聪明一点。

现在，显然，对于 48 位种子，您必须观察至少 48 位输出，否则您显然没有可使用的单射(因此是可逆的)函数。我们很幸运:nextLong返回 ((long)(next(32)) << 32) + next(32); ，所以它产生 64 位的输出(比我们需要的多)。确实，我们或许可以使用 nextDouble (产生 53 位)，或者只是重复调用任何其他函数。请注意，由于种子的大小有限，这些函数不能输出超过 2⁴⁸ 个唯一值(因此，例如，有 2⁶⁴-2⁴⁸ long s 那 nextLong 永远不会产生)。

我们具体看nextLong .它返回一个数字 (a << 32) + b在哪里 a和 b都是 32 位的量。让 s成为nextLong之前的种子叫做。然后，让 t = s * 0x5DEECE66DL + 0xBL ，所以 a是 t 的高 32 位, 并让 u = t * 0x5DEECE66DL + 0xBL这样b是 u 的高 32 位.让 c和 d是 t 的低 16 位和 u分别。

请注意，由于 c和 d是 16 位的量，我们可以暴力破解它们(因为我们只需要一个)并完成它。这相当便宜，因为 2¹⁶ 仅 65536 —— 对于计算机来说很小。但是让我们更聪明一点，看看是否有更快的方法。

我们有 (b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11 .因此，做一些代数，我们得到 (b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - d , 模组 2⁴⁸。从 c和 d都是 16 位数量，c*0x5DEECE66DL最多有 51 位。这很有用地意味着

(b << 16) - 11 - (a << 16)*0x5DEECE66DL + (k<<48)

等于 c*0x5DEECE66DL - d对于一些 k最多 6 个。(有更复杂的方法来计算 c 和 d，但是因为 k 上的界限非常小，所以使用暴力破解更容易)。

我们可以测试 k 的所有可能值直到我们得到一个否定余数 mod 0x5DEECE66DL 的值是 16 位(再次 mod 2⁴⁸)，所以我们恢复了 t 的低 16 位和 u .此时，我们有一个完整的种子，所以我们可以使用第一个方程找到 future 的种子，或者使用第二个方程找到过去的种子。

演示方法的代码:

import java.util.Random;

public class randhack {
    public static long calcSeed(long nextLong) {
        final long x = 0x5DEECE66DL;
        final long xinv = 0xdfe05bcb1365L;
        final long y = 0xBL;
        final long mask = ((1L << 48)-1);

        long a = nextLong >>> 32;
        long b = nextLong & ((1L<<32)-1);
        if((b & 0x80000000) != 0)
            a++; // b had a sign bit, so we need to restore a
        long q = ((b << 16) - y - (a << 16)*x) & mask;
        for(long k=0; k<=5; k++) {
            long rem = (x - (q + (k<<48))) % x;
            long d = (rem + x)%x; // force positive
            if(d < 65536) {
                long c = ((q + d) * xinv) & mask;
                if(c < 65536) {
                    return ((((a << 16) + c) - y) * xinv) & mask;
                }
            }
        }
        throw new RuntimeException("Failed!!");
    }

    public static void main(String[] args) {
        Random r = new Random();
        long next = r.nextLong();
        System.out.println("Next long value: " + next);
        long seed = calcSeed(next);
        System.out.println("Seed " + seed);
        // setSeed mangles the input, so demangle it here to get the right output
        Random r2 = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48)-1));
        System.out.println("Next long value from seed: " + r2.nextLong());
    }
}