问题描述
Java的Random函数接受一个种子并产生一系列'伪随机'数字。
（它基于 Donald Knuth，计算机程序设计的艺术，第3卷，第3.2.1节中讨论的一些算法实现。），但文章是对我来说太技术了解）
Java's Random function takes a seed and produces the a sequence of 'psuedo-random' numbers.(It is implemented based on some algorithm discussed in Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.), but the article is too technical for me to understand)
它有反函数吗？
也就是说，给定一系列数字，是否有可能在数学上确定种子是什么？
（，这意味着，暴力破解不算作有效方法）
Is there an inverse function of it?That is, given a sequence of numbers, would it be possible to mathematically determine what the seed would be?(, which means, brute-forcing doesn't count as a valid method)
似乎有相当多的数字这里的评论...我想我会澄清我在寻找什么。
There seems to be quite a number of comments here... I thought I'd clarify what I am looking for.
所以例如，函数 y = f（x ）= 3x 具有反函数， y = g（x）= x / 3 。
So for instance, the function y = f(x) = 3x has an inverse function, which is y = g(x) = x/3.
但函数 z = f（x，y）= x * y 没有反函数，因为（我可以提供完整的数学证明在这里，但我不想偏离我的主要问题），直观地说，有一对以上（x，y）这样（x * y）== z 。
But the function z = f(x, y) = x * y does not have an inverse function, because (I could give a full mathematical proof here, but I don't want to sidetrack my main question), intuitively speaking, there are more than one pair of (x, y) such that (x * y) == z.
现在回到我的问题，如果你说这个功能不可逆，请解释原因。
Now back to my question, if you say the function is not inversible, please explain why.
（我希望从那些真正读过文章并理解它的人那里得到答案。像这是不可能的这样的答案并没有真正起作用）
(And I am hoping to get answers from those who have really read to article and understand it. Answers like "It's just not possible" aren't really helping)
推荐答案
如果我们谈论的是，然后是的，一旦你知道足够的比特就可以。
If we're talking about the Oracle (née Sun) implementation of java.util.Random, then yes, it is possible once you know enough bits.
随机使用48位种子和线性同余生成器。这些不是加密安全的发生器，因为微小的状态大小（暴力！）和输出不是随机的事实（许多发生器在某些位中会表现出小的周期长度，这意味着这些位甚至可以很容易地预测如果其他位看似随机）。
Random uses a 48-bit seed and a linear congruential generator. These are not cryptographically safe generators, because of the tiny state size (bruteforceable!) and the fact that the output just isn't that random (many generators will exhibit small cycle length in certain bits, meaning that those bits can be easily predicted even if the other bits seem random).
随机的种子更新如下：
nextseed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
这是一个非常简单的功能，它如果通过计算知道种子的所有位，则可以反转
This is a very simple function, and it can be inverted if you know all the bits of the seed by calculating
seed = ((nextseed - 0xBL) * 0xdfe05bcb1365L) & ((1L << 48) - 1)
，因为 0x5DEECE66DL * 0xdfe05bcb1365L = 1 mod 2 。有了这个，任何时间点的单个种子值都足以恢复所有过去和将来的种子。
since 0x5DEECE66DL * 0xdfe05bcb1365L = 1 mod 2. With this, a single seed value at any point in time suffices to recover all past and future seeds.
随机没有显示整个种子的功能，所以我们必须要有点聪明。
Random has no functions that reveal the whole seed, though, so we'll have to be a bit clever.
现在，很明显， 48位种子，你必须观察至少48位输出，否则你显然没有一个内射（因此可逆）功能。我们很幸运： nextLong 返回（（长）（next（32））<< 32< 32）+ next（32）; ，因此它产生64位输出（超过我们需要的）。实际上，我们可能会使用 nextDouble （产生53位），或者只是重复调用任何其他函数。请注意，由于种子的大小有限，这些函数不能输出超过2个唯一值（因此，例如，有2个 -2 long s nextLong 将永远不会产生。）
Now, obviously, with a 48-bit seed, you have to observe at least 48 bits of output or you clearly don't have an injective (and thus invertible) function to work with. We're in luck: nextLong returns ((long)(next(32)) << 32) + next(32);, so it produces 64 bits of output (more than we need). Indeed, we could probably make do with nextDouble (which produces 53 bits), or just repeated calls of any other function. Note that these functions cannot output more than 2 unique values because of the seed's limited size (hence, for example, there are 2-2 longs that nextLong will never produce).
让我们具体看一下 nextLong 。它返回一个数字（一个<<<< 32）+ b 其中 a 和 b 都是32位数量。在 nextLong 被调用之前，让 s 成为种子。然后，让 t = s * 0x5DEECE66DL + 0xBL ，这样 a 是<$ c $的高32位c> t ，并让 u = t * 0x5DEECE66DL + 0xBL 以便 b 是 u 的高32位。设 c 和 d 是 t 的低16位和 u 分别。
Let's specifically look at nextLong. It returns a number (a << 32) + b where a and b are both 32-bit quantities. Let s be the seed before nextLong is called. Then, let t = s * 0x5DEECE66DL + 0xBL, so that a is the high 32 bits of t, and let u = t * 0x5DEECE66DL + 0xBL so that b is the high 32 bits of u. Let c and d be the low 16 bits of t and u respectively.
注意，因为 c 和 d 是16位数量，我们可以强制它们（因为我们只需要一个）并完成它。这很便宜，因为2 只有65536 - 对于一台电脑来说很小。但是让我们更聪明一点，看看是否有更快的方式。
Note that since c and d are 16-bit quantities, we can just bruteforce them (since we only need one) and be done with it. That's pretty cheap, since 2 is only 65536 -- tiny for a computer. But let's be a bit more clever and see if there's a faster way.
我们有（b 。因此，做一些代数，我们得到（b ，mod 2 。由于 c 和 d 都是16位数量， c * 0x5DEECE66DL 最多有51位。这有用意味着
We have (b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11. Thus, doing some algebra, we obtain (b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - d, mod 2. Since c and d are both 16-bit quantities, c*0x5DEECE66DL has at most 51 bits. This usefully means that
(b << 16) - 11 - (a << 16)*0x5DEECE66DL + (k<<48)
等于 c * 0x5DEECE66DL - d 对于某些 k 最多为6.（有更复杂的方法来计算 c 和 d ，但由于 k 的界限非常小，因此更容易暴力破坏。
is equal to c*0x5DEECE66DL - d for some k at most 6. (There are more sophisticated ways to compute c and d, but because the bound on k is so tiny, it's easier to just bruteforce).
我们可以测试 k 的所有可能值，直到我们得到一个值为否定余数mod 0x5DEECE66DL 是16位（mod 2 ），这样我们就可以恢复 t 和<$的低16位C $ C>û。那时，我们有一个完整的种子，所以我们可以使用第一个等式找到未来的种子，或使用第二个等式找到过去的种子。
We can just test all the possible values for k until we get a value whos negated remainder mod 0x5DEECE66DL is 16 bits (mod 2 again), so that we recover the lower 16 bits of both t and u. At that point, we have a full seed, so we can either find future seeds using the first equation, or past seeds using the second equation.
代码演示方法：
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());
}
}
这篇关于Java的Random函数的反函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！