Java随机函数的反函数

Question

Java的Random函数接受一个种子，并产生一个“psuedo-random”数字序列。（它是基于Donald Knuth，The Art of Computer Programming，第3卷，第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=1mod 2⁴⁸。这样，任何时间点的单个种子值就足以恢复所有过去和将来的种子。

但是random没有显示整个种子的函数，所以我们必须稍微聪明一点。

让我们具体看看nextlong。它返回一个数字(a<<32)+B，其中a和B都是32位的量。在调用NextLong之前，让s作为种子。然后，设t=s*0x5DEECE66DL+0xBL，使A为t的高32位，设U=t*0x5DEECE66DL+0xBL，使B为U的高32位。设C和D分别为T和U的低16位。

注意，由于c和d是16位的量，我们可以硬性地强制它们（因为我们只需要一个）并完成它。这是相当便宜的，因为2¹⁶只有65536--对于一台电脑来说很小。但让我们聪明一点看看有没有更快的方法。

我们有(b<<16)+d=((a<<16)+c)*0x5DEECE66DL+11。因此，通过代数运算，我们得到了(b<<16)-11-(a<<16)*0x5deece66dl=C*0x5deece66dl-d，mod2⁴⁸。由于C和D都是16位量，C*0x5DEECE66DL最多有51位。这很有意义地意味着

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

对于某些k，最多等于C*0x5DEECE66dl-d。（计算C和D有更复杂的方法，但因为K的界限很小，所以更容易使用暴力）。

我们只需测试K的所有可能值，直到我们得到一个值，该值被否定的余数mod0x5deece66dl是16位（又是mod2⁴⁸)，这样我们就可以恢复T和U的低16位。在这一点上，我们有一个完整的种子，所以我们可以使用第一个方程找到未来的种子，或者使用第二个方程找到过去的种子。

演示该方法的代码：

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());
    }
}