Java的Random函数的反函数

Java的Random函数接受一个种子并产生一系列’伪随机’数字。 （它是基于Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.)讨论的一些算法实现的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没有反函数，因为（我可以在这里给出一个完整的数学certificate，但我不想偏离我的主要问题），直观地说，那里不止一对(x, y)使得(x * y) == z 。

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

（我希望从那些真正阅读过文章并理解它的人那里得到答案。像“这是不可能的”这样的答案并没有真正起作用）

Answer 1

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

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

Random种子更新如下：

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

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

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

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

然而， Random没有显示整个种子的function，所以我们必须有点聪明。

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

我们来看看nextLong 。 它返回一个数字(a << 32) + b ，其中a和b都是32位数。 让我们成为nextLong之前的种子。 然后，让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 ，mod 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和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()); } } 

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说的那样，他在第二部分深入研究种子背后的数学。

Answer 3

我想提出一个实现来反转nextInt()生成的整数序列。

该程序将对nextInt()丢弃的低16位进行暴力破解，使用James Roper在博客中提供的算法查找先前的种子，然后检查48位种子的高32位是否与之前相同数。 我们需要至少2个整数来导出前一个种子。 否则，前一个种子将有2 ^16种可能性，并且在我们至少再有一个种子之前，它们都是同等有效的。

它可以很容易地扩展到nextLong() ，并且1个 long数足以找到种子，因为由于它的生成方式，我们在一个long有2个上部32位种子。

请注意，在某些情况下，结果与您在SEED变量中设置为秘密种子的结果不同。 如果您设置为秘密种子的数量占用超过48位（这是用于在内部生成随机数的位数），那么64位long的高16位将在setSeed()方法中被删除。 在这种情况下，返回的结果将与您最初设置的结果不同，较低的48位可能是相同的。

我想对本博客文章的作者James Roper给予最多的赞誉，该文章使下面的示例代码成为可能：

 import java.util.Random; import java.util.Arrays; class TestRandomReverse { // The secret seed that we want to find private static long SEED = 782634283105L; // Number of random numbers to be generated private static int NUM_GEN = 5; private static int[] genNum(long seed) { Random rand = new Random(seed); int arr[] = new int[NUM_GEN]; for (int i = 0; i < arr.length; i++) { arr[i] = rand.nextInt(); } return arr; } public static void main(String args[]) { int arr[] = genNum(SEED); System.out.println(Arrays.toString(arr)); Long result = reverse(arr); if (result != null) { System.out.println(Arrays.toString(genNum(result))); } else { System.out.println("Seed not found"); } } private static long combine(int rand, int suffix) { return (unsignedIntToLong(rand) << 16) | (suffix & ((1L << 16) - 1)); } private static long unsignedIntToLong(int num) { return num & ((1L << 32) - 1); } // This function finds the seed of a sequence of integer, // generated by nextInt() // Can be easily modified to find the seed of a sequence // of long, generated by nextLong() private static Long reverse(int arr[]) { // Need at least 2 numbers. assert (arr.length > 1); int end = arr.length - 1; // Brute force lower 16 bits, then compare // upper 32 bit of the previous seed generated // to the previous number. for (int i = 0; i < (1 << 16); i++) { long candidateSeed = combine(arr[end], i); long previousSeed = getPreviousSeed(candidateSeed); if ((previousSeed >>> 16) == unsignedIntToLong(arr[end - 1])) { System.out.println("Testing seed: " + previousSeed + " --> " + candidateSeed); for (int j = end - 1; j >= 0; j--) { candidateSeed = previousSeed; previousSeed = getPreviousSeed(candidateSeed); if (j > 0 && (previousSeed >>> 16) == unsignedIntToLong(arr[j - 1])) { System.out.println("Verifying: " + previousSeed + " --> " + candidateSeed); } else if (j == 0) { // The XOR is done when the seed is set, need to reverse it System.out.println("Seed found: " + (previousSeed ^ MULTIPLIER)); return previousSeed ^ MULTIPLIER; } else { System.out.println("Failed"); break; } } } } return null; } private static long ADDEND = 0xBL; private static long MULTIPLIER = 0x5DEECE66DL; // Credit to James Roper // http://jazzy.id.au/default/2010/09/21/cracking_random_number_generators_part_2.html private static long getPreviousSeed(long currentSeed) { long seed = currentSeed; // reverse the addend from the seed seed -= ADDEND; // reverse the addend long result = 0; // iterate through the seeds bits for (int i = 0; i < 48; i++) { long mask = 1L << i; // find the next bit long bit = seed & mask; // add it to the result result |= bit; if (bit == mask) { // if the bit was 1, subtract its effects from the seed seed -= MULTIPLIER << i; } } return result & ((1L << 48) - 1); } }