Генерация случайных чисел: лучшие практики

У меня есть класс, который содержит два источника случайности.

std::random_device rd;
std::mt19937 random_engine;

Я засекаю std::mt19937 вызовом std::random_device. Если я хочу сгенерировать число, и мне не нужна повторяемость, я должен позвонить rd() или random_engine()?

В моем конкретном случае я уверен, что оба будут работать очень хорошо, потому что это будет вызвано в каком-то сетевом коде, где производительность невелика, и результаты не особенно чувствительны. Тем не менее, меня интересуют некоторые "эмпирические правила" о том, когда использовать аппаратную энтропию и когда использовать псевдослучайные числа.

В настоящее время я использую std::random_device для того, чтобы засеять мой движок std::mt19937 и любое генерирование случайных чисел, которое мне нужно для моей программы, я использую механизм std::mt19937.

edit: Здесь объяснение того, что я использую для этого конкретного примера для:

Это для игровой программы. Эта конкретная игра позволяет пользователю настраивать свою команду до начала раунда против соперника. Часть создания битвы предполагает отправку команды на сервер. Моя программа имеет несколько команд и использует случайное число, чтобы определить, какую команду загрузить. Каждое новое сражение вызывает вызов std::random_device, чтобы засеять генератор псевдослучайных чисел. Я регистрирую начальное состояние битвы, в которое входит эта команда, которую я произвольно выбираю, и начальное семя.

Частное случайное число, о котором я спрашиваю в этом вопросе, касается случайного выбора команды (где полезно не заранее знать, какая команда я использую, но не критически важна), но то, что я действительно ищу, - это эмпирическое правило. Хорошо ли всегда использовать std::random_device, если мне не нужна повторяемость моих чисел, или существует реальная опасность использовать энтропию быстрее, чем ее можно собрать?

Ответ 1

Стандартная практика, насколько мне известно, заключается в том, чтобы засеять генератор случайных чисел числом, которое не вычисляется компьютером (но оно исходит из какого-то внешнего, непредсказуемого источника). Это должно быть в случае с вашей функцией rd(). С этого момента вы вызываете генератор псевдослучайных чисел (PRNG) для каждого псевдослучайного числа, которое вам нужно.

Если вы беспокоитесь о том, что цифры не являются достаточно случайными, тогда вы должны выбрать другой PRNG. Энтропия - это дефицитный и ценный ресурс, и его следует рассматривать как таковой. Хотя, вам может не понадобиться много случайных чисел прямо сейчас, вы можете в будущем; или другие приложения могут нуждаться в них. Вы хотите, чтобы энтропия была доступна, когда приложение запрашивает ее.

Похоже, для вашего приложения, что mersenne twister удовлетворит ваши потребности просто отлично. Никто, кто играет в вашу игру, никогда не почувствует, что загруженные команды не являются случайными.

Ответ 2

Если вы не используете его для шифрования, хорошо и многократно использовать mt19937, который выставляется random_engine.

В оставшейся части ответа, я полагаю, вы используете случайные числа для шифрования в своем сетевом коде. Короче говоря, mt19937 не подходит для этого использования.

http://en.wikipedia.org/wiki/Mersenne_twister#Disadvantages

Существует потенциальный риск того, что вы будете утечка информации (возможно, косвенно) со временем, чтобы злоумышленник мог начать прогнозировать случайные числа. По крайней мере, теоретически, но об этом и говорят. Из Википедии

... так как эта цифра является размером вектора состояния из
какие будущие итерации производятся) позволяет предсказать все будущие итерации.

Простым средством предотвращения утечки информации о генерации случайных чисел для пользователя является использование односторонних хеш-функций, но там гораздо больше. Вы должны использовать генератор случайных чисел, предназначенный для этой цели:

http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator

Различные примеры (с кодом) можно найти здесь http://xlinux.nist.gov/dads/HTML/pseudorandomNumberGen.html

Ответ 3

Если вам нужна случайность для симуляции или игры, то, что вы делаете, все в порядке. Вызовите случайное устройство только один раз и сделайте все остальное с случайно засеваемым псевдо-RNG. В качестве бонуса вы должны сохранить начальное значение в файле журнала, чтобы впоследствии можно было воспроизвести псевдослучайную последовательность:

auto const seed = std::random_device()();
// save "seed" to log file
std::mt19937 random_engine(seed);

(Для нескольких потоков используйте PRNG в основном потоке, чтобы генерировать семена для дальнейших PRNG в порожденных потоках.)

Если вам нужно много истинной случайности для криптографических целей, тогда PRNG никогда не является хорошей идеей, хотя, поскольку длинная последовательность вывода содержит намного меньше случайности, чем истинная случайность, то есть вы можете предсказать все это из небольшое подмножество. Если вам нужна истинная случайность, вам следует собрать ее из непредсказуемого источника (например, датчиков тепла, активности клавиатуры/мыши пользователя и т.д.). Unix /dev/random может быть таким "истинным случайным" источником, но он может не быстро заполняться.

Ответ 4

Вы можете посмотреть http://channel9.msdn.com/Events/GoingNative/2013/rand-Considered-Harmful, в котором объясняется, почему вы должны использовать uniform_int_distribution и сильные стороны родственников random_device/mt19937.

В этом видео Stephan T. Lavavej конкретно заявляет, что на Visual С++ random_device может использоваться для криптографических целей.

Ответ 5

Ответ зависит от платформы. Я, кажется, помню, что с Visual С++ 2010 std:: random_device - это просто mt19937, засеянный некоторым недокументированным способом.

Конечно, вы понимаете, что любая специальная схема шифрования, основанная на генераторе случайных чисел, может быть очень слабой.

Ответ 6

Предполагая, что это не для криптографических целей, самое важное, что нужно помнить о генерации случайных чисел, - это подумать о том, как вы хотите распределить случайные числа и какой диапазон вы ожидаете.

Обычно стандартные генераторы случайных чисел в библиотеках предназначены для обеспечения равномерного распределения. Таким образом, цифры будут находиться в диапазоне от 0 до некоторого RAND_MAX (скажем, на 32-битной машине 2 ^ 31 -1)

Теперь вот что нужно запомнить с генераторами псевдослучайных чисел. Большинство из них предназначены для генерации случайных чисел, а не случайных бит. Разница тонкая. Если вам нужны номера от 0 до 8, большинство программистов скажут rand()% 8 Это плохо, потому что алгоритм предназначен для рандомизации 32 бит. Но вы используете только нижние 3 бита. Не хорошо. Это не даст вам равномерного распределения (предполагая, что это то, что вы ищете)

Вы должны использовать 8 * (rand() + 1)/(RAND_MAX), который теперь даст вам равномерно случайное число между 0 и 8.

Теперь с аппаратными генераторами случайных чисел вы можете создавать случайные биты. Если это действительно так, то каждый бит создается независимо. Тогда это больше похоже на набор идентичных независимых случайных бит. Моделирование здесь должно быть немного иным. Имейте это в виду, особенно в симуляциях распределение становится важным.