Обратная функция функции Java Random

Ответ 1

Если мы говорим о реализации 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 = 1 mod 2 ⁴⁸. При этом одно значение затравки в любой момент времени достаточно для восстановления всех прошлых и будущих семян.

Random не имеет функций, которые показывают все семя, однако, мы должны быть немного умными.

Теперь, очевидно, с 48-битным семенем вы должны наблюдать не менее 48 бит вывода или у вас явно нет инъективной (и, следовательно, обратимой) функции для работы. Нам повезло: nextLong возвращает ((long)(next(32)) << 32) + next(32);, поэтому он выводит 64 бита вывода (больше, чем нам нужно). Действительно, мы могли бы, вероятно, сделать с nextDouble (который производит 53 бит) или просто повторные вызовы любой другой функции. Обратите внимание, что эти функции не могут вывести более 2 ⁴⁸ уникальных значений из-за ограниченного размера семени (следовательно, есть 2 ⁶⁴ -2 ⁴⁸long, который 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 - 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 ⁴⁸ снова), так что мы восстанавливаем нижнюю 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());
    }
}

Ответ 2

Я обычно не просто связывал статьи... Но я нашел сайт, на котором кто-то заглядывал в это глубже и думал, что стоит опубликовать. http://jazzy.id.au/default/2010/09/20/cracking_random_number_generators_part_1.html

Кажется, вы можете рассчитать семя таким образом:

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

где множитель равен 25214903917, addend равно 11, а точность - 48 (бит). Вы не можете рассчитать, что семя было только с 1 номером, но вы можете с 2.

EDIT: Как сказал nhahtdh, часть 2, где он вникает в большую часть математики за семенами.

Ответ 3

Я хотел бы представить реализацию для обратной последовательности целых чисел, сгенерированных nextInt().

Программа будет грубой силой на более низком 16-битном разряде, отбрасываемом nextInt(), используя алгоритм, предоставленный в блоге Джеймсом Ропером, чтобы найти предыдущее семя, затем проверьте, что верхний 32-разрядный бит-бит семени одинаковый как предыдущий номер. Нам нужно как минимум 2 целое число для получения предыдущего семени. В противном случае для предыдущего семестра будут доступны 2 ¹⁶ и все они одинаково действительны, пока мы не получим хотя бы еще одно число.

Он легко расширяется для nextLong(), а 1 long достаточно, чтобы найти семя, так как у нас есть 2 части верхнего 32-битного семени в одном long, из-за способа его создания.

Обратите внимание, что есть случаи, когда результат не совпадает с тем, что вы задали как секретное семя в переменной SEED. Если номер, который вы устанавливаете как секретное семя, занимает более 48 бит (это число бит, используемое для генерации случайных чисел внутри), тогда верхние 16 бит 64 бит long будут удалены в методе setSeed(), В таких случаях возвращаемый результат будет не таким, как тот, который вы установили изначально, вероятно, что нижний 48-бит будет таким же.

Я хотел бы отдать должное Джеймсу Роперу, автору этой статьи в блоге, которая позволяет сделать пример кода ниже:

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