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

如果我们谈论Oracle(néeSun)的实现java.util.Random,那么是的,一旦你知道了足够的位,就有可能.

Random使用48位种子和线性同余生成器.这些不是加密安全的发生器,因为微小的状态大小(强力执行!)以及输出不是随机的事实(许多发生器在某些位中会表现出小的周期长度,这意味着这些位甚至可以很容易地预测如果其他位似乎是随机的).

Random种子更新如下:

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

这是一个非常简单的函数,如果你通过计算知道种子的所有位,它就可以被反转

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

自0x5DEECE66DL * 0xdfe05bcb1365L = 1mod 2 ⁴⁸.有了这个,任何时间点的单个种子值就足以恢复所有过去和未来的种子.

Random 但是,它没有揭示整个种子的功能,所以我们必须要有点聪明.

现在,显然,对于48位种子,您必须观察至少48位输出,否则您显然没有内射(因而可逆)功能.我们很幸运:nextLong返回((long)(next(32)) << 32) + next(32);,因此它产生64位输出(超过我们需要的).实际上,我们可能会做nextDouble(产生53位),或者只是重复调用任何其他函数.注意,这些功能不能输出超过2个⁴⁸独特的,因为所述种子的有限大小的值(因此,例如,有2 ⁶⁴ -2 ^48个 long s表示nextLong绝不会产生).

我们来看看nextLong.它返回一个数字(a << 32) + b,其中a和b都是32位数.s在nextLong被召唤之前,让我们成为种子.然后,让t = s * 0x5DEECE66DL + 0xBL,以便a为高32位t,并让u = t * 0x5DEECE66DL + 0xBL以便b为高32位u.设c和d是低16位t,并u分别.

请注意,由于c和d是16位数量,我们可以强制它们(因为我们只需要一个)并完成它.这很便宜,因为2 ¹⁶只有65536 - 对于电脑来说很小.但是让我们更聪明一点,看看是否有更快的方法.

我们有(b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11.因此,做一些代数,我们得到(b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - dmod 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位(模2 ⁴⁸再一次),所以我们恢复双方的低16位t和u.那时,我们有一个完整的种子,所以我们可以使用第一个方程找到未来的种子,或使用第二个方程找到过去的种子.

代码演示了这种方法:

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

Answer 2

我通常不会只链接文章......但我发现一个网站，有人对此进行了深入研究，并认为值得发布。http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html

看来你可以这样计算种子：

seed = (seed * multiplier + addend) mod (2 ^ precision)

其中乘数为 25214903917，加数为 11，精度为 48（位）。你无法仅用 1 个数字来计算种子是什么，但用 2 个数字就可以。

编辑：正如 nhahtdh 所说，在第二部分中，他深入研究了种子背后的更多数学知识。