28

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。

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

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

4

3 回答 3

28

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

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

Random的种子更新如下：

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

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

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

从0x5DEECE66DL * 0xdfe05bcb1365L = 1mod 2 48开始。有了这个，任何时间点的单个种子值都足以恢复所有过去和未来的种子。

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

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

我们来具体看看nextLong。它返回一个数字(a << 32) + b，其中a和b都是 32 位量。Let sbe the seed beforenextLong被调用。然后，让t = s * 0x5DEECE66DL + 0xBL,a是 的高 32 位t，让u = t * 0x5DEECE66DL + 0xBL,b是 的高 32 位u。令c和分别为和d的低 16 位。tu

请注意，因为c和d是 16 位的量，我们可以强行使用它们（因为我们只需要一个）并完成它。这很便宜，因为 2 16只有 65536——对于计算机来说很小。但是让我们更聪明一点，看看是否有更快的方法。

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

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

最多等于6。（c*0x5DEECE66DL - d有k更复杂的方法来计算c和d，但由于边界k非常小，因此蛮力更容易）。

我们可以测试所有可能的值，k直到我们得到一个取反的余数 mod0x5DEECE66DL是 16 位的值（再次是 mod 2 48），这样我们就可以恢复 和 的低 16t位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());
    }
}
于 2013-03-06T01:54:43.533 回答
4

我通常不会只链接文章......但我发现了一个网站，有人对此进行了深入研究并认为值得发布。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 所说，在第 2 部分中，他深入研究了种子背后的更多数学。

于 2013-03-05T23:51:15.103 回答
3

我想提出一个实现来反转由nextInt().

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

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

请注意，在某些情况下，结果与您在SEED变量中设置为秘密种子的结果不同。如果您设置为秘密种子的数字占用超过 48 位（这是内部用于生成随机数的位数），则该方法long中将删除64 位的高 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);
  }
}
于 2013-03-06T01:22:32.607 回答