Kernel :: srand имеет максимальное входное значение?

Question

Я пытаюсь заполнить генератор случайных чисел выводом хэша.В настоящее время я вычисляю хэш SHA-1, преобразовываю его в гигантское целое число и передаю его в srand для инициализации RNG.Это сделано для того, чтобы я мог получить предсказуемый набор случайных чисел для набора бесконечных декартовых координат (я хэширую координаты).

Мне интересно, действительно ли Kernel :: srand имеет максимальное значение, котороеэто займет, после чего он каким-то образом обрезает его.Документы на самом деле не делают это очевидным - они просто говорят «число».

Я постараюсь выяснить это сам, но я предполагаю, что кто-то уже сталкивался с этим.

Answer 1

Зная, на что похожи программисты, он, вероятно, просто вызывает libc srand().В любом случае, это, вероятно, ограничено 2 ^ 32-1, 2 ^ 31-1, 2 ^ 16-1 или 2 ^ 15-1.

Существует также опасность того, что значение обрезается при приведении избольшой интеграл в C int / long вместо того, чтобы брать только младшие биты.

Простой тест состоит в том, чтобы начать с 1 и получить первый вывод.Затем начните с 2 ⁱ + 1 для i в [1..64] или около того, возьмите первый результат каждого и сравните.Если вы получаете совпадение для некоторых i=n и всех больших i с, то, вероятно, он выполняет арифметику по модулю 2 ⁿ .

Обратите внимание, что генератор случайных чисел почти наверняка ограничен32 или 48 бит энтропии в любом случае, так что нет смысла заполнять ее огромным значением, и злоумышленник может достаточно легко предсказать будущие выходные данные с учетом прошлых выходных данных (а «злоумышленник» может просто быть игроком на общедоступном сетевом сервере).1015 *

РЕДАКТИРОВАТЬ: Так что я ошибся.

Согласно документации для Kernel :: rand (),

В настоящее время Ruby использует модифицированныйMersenne Twister с периодом 2 ** 19937-1.

Это означает, что это не просто вызов libc's rand().Mersenne Twister является статистически превосходящим (но не криптографически безопасным).Но в любом случае.

Тестирование с использованием Kernel::srand(0); Kernel::sprintf("%x",Kernel::rand(2**32)) для различных выходных размеров (2 * 16, 2 * 32, 2 * 36, 2 * 60, 2 * 64, 2 * 32 + 1, 2 * 35, 2 * 34 + 1), несколько вещей очевидны:

1. Вычисляет, сколькобиты, в которых он нуждается (количество бит в max-1).
2. Он генерирует выходные данные в группах по 32 бита, начиная со старших значащих бит, и сбрасывает верхние биты (т. е. 0x [r0] [r1][r2] [r3] [r4] с замаскированными старшими битами).
3. Если оно не меньше max, выполняется какая-то попытка.Непонятно, что это за вывод.
4. Если он меньше max, выводится результат.

Я не уверен, почему 2 *32 + 1 и 2 * 64 + 1 являются особыми (они выдают одинаковый результат из Kernel::rand(2**1024), поэтому, вероятно, имеют точно такое же состояние) - другого столкновения я не обнаружил.

Хорошие новостиявляется то, что он не просто обрезает до некоторого произвольного максимума (то есть передача в огромных числах не эквивалентна передаче в 2 ** 31-1), что является наиболее очевидной вещью, которая может пойти не так.Kernel :: srand () также возвращает предыдущее начальное число, которое выглядит 128-битным, поэтому вполне вероятно, что безопасно передать что-то большое.

РЕДАКТИРОВАТЬ 2: Конечнонет никакой гарантии, что выходные данные будут воспроизводиться между различными версиями Ruby (документы просто говорят о том, что он «использует в настоящее время»; очевидно, это было изначально зафиксировано в 2002 году).В Java есть несколько портативных детерминированных PRNG (SecureRandom.getInstance("SHA1PRNG","SUN"), хотя и медленных);Я не знаю ничего подобного для Ruby.