Вопрос по c++11, random, c++ – Должен ли я использовать случайный движок, посеянный из std :: random_device или использовать std :: random_device каждый раз

22

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

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 если мне не нужна повторяемость моих чисел, или существует реальный риск использования энтропии быстрее, чем ее можно собрать?

Ваш Ответ

6   ответов
7

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

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

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

Если вам нужно много истинной случайности для криптографических целей, тогда PRNG никогда не будет хорошей идеей, так как длинная последовательность вывода содержит намного меньше случайности, чем истинная случайность, то есть вы можете предсказать все из небольшого подмножества. Если вам нужна истинная случайность, вы должны собрать ее из какого-то непредсказуемого источника (например, тепловые датчики, пользовательская клавиатура / мышь и т. Д.). Unix & APOS; s/dev/random может быть такой «истинной случайностью» источник, но он может заполняться не очень быстро.

Неверно, что вы в целом можете вывести информацию из PRNG, используя небольшой набор случайных чисел из него. Для многих да, но не для всех.
@ Ela782: Абсолютно, спасибо!
@JohanLundberg: Достаточно справедливо - я полагаю, это зависит от того, что вы подразумеваете под словом "маленький". :-)
@KerrekSB Я думаю, что первая строка в вашем коде должна бытьauto const seed = std::random_device()();неstd::random_engine()()?
8

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

В остальной части этого ответа я предполагаю, что вы используете случайные числа для шифрования в своем сетевом коде.In short, mt19937 is not suitable for that use.

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

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

...since this figure is the size of the state vector from
which future iterates are produced) allows one to predict all future iterates.

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

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

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

-2

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

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

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

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

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

Кроме того, ваша формула8 * (rand() + 1) / (RAND_MAX) неверно (это вызовет переполнение целых чисел. Даже если это не так, существует небольшая вероятность того, что будет возвращено 8). А такжеRAND_MAX не является пределом при использовании библиотеки случайных чисел C ++ 11, только сrand().
То, что касается младших / старших битов, верно для старых генераторов случайных чисел LCG, но, вероятно, не относится к современным. Это не проблема с Mersenne Twister, который использует OP.
Ну, для примера я использовал rand (), а не генератор случайных чисел C ++ 11. Таким образом, RAND_MAX применяется там. Но я согласен, что он говорил о генераторе случайных чисел C ++.
Я использую стандартную библиотеку C ++ 11std::uniform_int_distribution чтобы сгенерировать мои дистрибутивы, так что я покрыл эту часть. David Stone
3

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

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

Стандарт не требует, чтобы random_device был криптографически безопасным. Так что да, в Windows с Visual C ++ это реализовано таким образом, но на других платформах может быть (и есть) нет. Мы можем согласиться, что глупо не делать это криптографически безопасным, но ...
2

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

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

10

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

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

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

Похожие вопросы