Обратное проектирование числа для Math.random() в Java на основе случайной строки

ProgramBox

Обратное проектирование числа для Math.random() в Java на основе случайной строки

Post author:admin
Запись опубликована:21 марта, 2023
Post category:Вопросы по программированию

#java #algorithm

#java #алгоритм

Вопрос:

Итак, у меня есть вопрос по небольшой проблеме, над которой я работаю.

Учитывая случайную строку, сгенерированную Java-программой любой длины, например jdefreq .

Каждый символ в строке генерируется с помощью,

 final String[] dict = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
        "s", "t", "u", "v", "w", "x", "y", "z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", ",", ".", "?" };

final int dictIndex = (int)Math.floor(Math.random() * dict.length);

У меня есть способ репликации Math.random() , но мне нужно точное первое число, которое используется, начиная с последовательности.

Способ, которым я пытался это сделать, прямо сейчас — это взять первый символ и выполнять цикл, Math.random() пока я не получу число, которое может воспроизвести тот же индекс этого первого символа, но этого недостаточно, поскольку я создаю только похожее число, но не точно такое же.

Итак, я пришел сюда, коллеги-программисты!

У кого-нибудь есть идеи, как / что я могу сделать, чтобы это осуществить?

Очень рад услышать советы людей / их мнение по проблеме!

Спасибо и хорошего дня!

1. «маленькая проблема» — я очень сомневаюсь в этом!

2. Это может быть сложно! Но это просто то, что появилось как «побочное» упражнение в классе!

3. Только 48 бит энтропии должны быть перебором.

4. Также обратите внимание, что алгоритм учитывает системное время для начального числа, когда число было сгенерировано. Я не уверен, возможно ли вообще вернуть оригинал. Взгляните: this(seedUniquifier() ^ System.nanoTime()); из Random класса

5. @Prashant прав: если вы приблизительно знаете, когда Random был создан экземпляр, и из него сначала не были извлечены числа (или вы знаете, сколько), количество возможностей, которые вам нужно попробовать, должно быть ограничено. Я не помню подробностей, но покерный сайт однажды опубликовал свой исходный код и создавал новую случайную последовательность каждый день в полночь, что позволяет пользователям-фанатам не слишком сложно угадать руку своего противника. Им пришлось изменить это очень скоро.

Ответ №1:

Чтобы расширить мой комментарий: существует только 2 ⁴⁸ различных последовательностей, которые Math.random могут быть получены. Это довольно много, но не так много, чтобы вы не могли попробовать их все за мыслимое количество времени. Настройка выглядит следующим образом

 for (long seed = 0; seed < (1L << 48); seed  ) {
    Random r = new Random(seed);
    if (generateString(r).equals(desiredString)) return seed;
}

где generateString(r) генерирует строки таким же образом, за исключением использования r.nextDouble() вместо Math.random() .

Другим подходом было бы закодировать соответствующую настройку как теорию выполнимости по модулю, а затем использовать для нее решатель. Поскольку генератор псевдослучайных чисел Java является линейным конгруэнтным генератором, который не использует деление, эта часть не слишком сложна. Наивно можно было бы предположить, что нам нужно реализовать арифметику с плавающей запятой для Random.nextDouble() , но мы можем напрямую рассуждать о диапазонах относительно генерируемого 53-битного целого nextDouble() числа. В целом, это утомительно, но относительно просто, потому что сложная логика алгоритма инкапсулирована в решателе.