Зачем вообще использовать класс C# System.Random вместо System.Security.Cryptography.RandomNumberGenerator?
Зачем кому-то вообще использовать "стандартный" генератор случайных чисел из System.Random вместо того, чтобы всегда использовать криптографически безопасный генератор случайных чисел из http://msdn.microsoft.com/en-us/library/system.security.cryptography.randomnumbergenerator.aspx (или его подклассов, потому что RandomNumberGenerator является абстрактным)?
Нейт Лоусон говорит нам в своей презентации Google Tech Talk " Crypto Strikes Back" в минуту 13:11 не использовать "стандартные" генераторы случайных чисел из Python, Java и C# и вместо этого использовать криптографически безопасную версию.
Я знаю разницу между двумя версиями генераторов случайных чисел (см. Вопрос 101337).
Но какой смысл в том, чтобы не всегда использовать безопасный генератор случайных чисел? Зачем вообще использовать System.Random? Производительность возможно?
13 ответов
Скорость и намерение. Если вы генерируете случайное число и не нуждаетесь в безопасности, зачем использовать медленную криптографическую функцию? Вам не нужна безопасность, так зачем заставлять кого-то думать, что номер может быть использован для чего-то защищенного, когда его не будет?
Помимо скорости и более полезного интерфейса (NextDouble() и т.д.) также возможно сделать повторяемую случайную последовательность, используя фиксированное начальное значение. Это очень полезно, среди прочего, во время тестирования.
Random gen1 = new Random(); // auto seeded by the clock
Random gen2 = new Random(0); // Next(10) always yields 7,8,7,5,2,....
Прежде всего, связанная с вами презентация говорит только о случайных числах в целях безопасности. Так что не претендует Random это плохо в целях безопасности.
Но я утверждаю, что это так..Net 4 реализация Random имеет недостатки в нескольких отношениях. Я рекомендую использовать его, только если вас не волнует качество ваших случайных чисел. Я рекомендую использовать лучшие сторонние реализации.
Ошибка 1: посев
Конструктор по умолчанию начинается с текущего времени. Таким образом, все случаи Random созданные с помощью конструктора по умолчанию в течение короткого периода времени (около 10 мс) возвращают ту же последовательность. Это задокументировано и "по замыслу". Это особенно раздражает, если вы хотите многопоточность вашего кода, так как вы не можете просто создать экземпляр Random в начале выполнения каждого потока.
Обходной путь должен быть очень осторожным при использовании конструктора по умолчанию и вручную заполнять при необходимости.
Другая проблема заключается в том, что начальное пространство довольно мало (31 бит). Так что если вы генерируете 50 000 экземпляров Random с совершенно случайными семенами вы, вероятно, получите одну последовательность случайных чисел дважды (из-за парадокса дня рождения). Так что ручной посев не так-то и прав.
Ошибка 2: распределение случайных чисел, возвращаемых Next(int maxValue) предвзятый
Есть параметры для которых Next(int maxValue) явно не равномерно. Например, если вы рассчитываете r.Next(1431655765) % 2 ты получишь 0 примерно в 2/3 образцов. (Пример кода в конце ответа.)
Недостаток 3: NextBytes() метод неэффективен.
Стоимость за байт NextBytes() примерно столько же, сколько стоимость генерации целочисленной выборки с Next(), Из этого я подозреваю, что они действительно создают один образец на байт.
Лучшая реализация, использующая 3 байта из каждого образца, ускорит NextBytes() почти в 3 раза.
Благодаря этому недостатку Random.NextBytes() только примерно на 25% быстрее, чем System.Security.Cryptography.RNGCryptoServiceProvider.GetBytes на моей машине (Win7, Core i3 2600MHz).
Я уверен, что если кто-нибудь проверит исходный / декомпилированный байт-код, он найдет еще больше недостатков, чем я обнаружил при анализе черного ящика.
Образцы кода
r.Next(0x55555555) % 2 сильно предвзято
Random r = new Random();
const int mod = 2;
int[] hist = new int[mod];
for(int i = 0; i < 10000000; i++)
{
int num = r.Next(0x55555555);
int num2 = num % 2;
hist[num2]++;
}
for(int i=0;i<mod;i++)
Console.WriteLine(hist[i]);
Спектакль:
byte[] bytes=new byte[8*1024];
var cr=new System.Security.Cryptography.RNGCryptoServiceProvider();
Random r=new Random();
// Random.NextBytes
for(int i=0;i<100000;i++)
{
r.NextBytes(bytes);
}
//One sample per byte
for(int i=0;i<100000;i++)
{
for(int j=0;j<bytes.Length;j++)
bytes[j]=(byte)r.Next();
}
//One sample per 3 bytes
for(int i=0;i<100000;i++)
{
for(int j=0;j+2<bytes.Length;j+=3)
{
int num=r.Next();
bytes[j+2]=(byte)(num>>16);
bytes[j+1]=(byte)(num>>8);
bytes[j]=(byte)num;
}
//Yes I know I'm not handling the last few bytes, but that won't have a noticeable impact on performance
}
//Crypto
for(int i=0;i<100000;i++)
{
cr.GetBytes(bytes);
}
System.Random гораздо более производительный, так как он не генерирует криптографически безопасные случайные числа.
Простой тест на моей машине, заполняющий буфер из 4 байтов случайными данными 1 000 000 раз, занимает 49 мс для Random, но 2845 мс для RNGCryptoServiceProvider. Обратите внимание, что если вы увеличиваете размер заполняемого буфера, разница сужается, так как издержки для RNGCryptoServiceProvider менее значимы.
Наиболее очевидные причины уже были упомянуты, поэтому вот еще более неясная: криптографические PRNG, как правило, должны постоянно пересеваться с "реальной" энтропией. Таким образом, если вы используете CPRNG слишком часто, вы можете исчерпать пул энтропии системы, который (в зависимости от реализации CPRNG) либо ослабит его (что позволит злоумышленнику предсказать его), либо заблокирует его при попытке заполнить его пул энтропии (таким образом, становясь вектором атаки для DoS-атаки).
В любом случае, ваше приложение теперь стало вектором атаки для других, совершенно не связанных приложений, которые, в отличие от ваших, фактически жизненно зависят от криптографических свойств CPRNG.
Кстати, это реальная проблема реального времени, которая наблюдалась на безголовых серверах (которые, естественно, имеют довольно небольшие пулы энтропии, потому что у них нет источников энтропии, таких как мышь и клавиатура), работающих под Linux, где приложения неправильно используют /dev/random ядро CPRNG для всех видов случайных чисел, тогда как правильное поведение было бы прочитать небольшое начальное значение из /dev/urandom и использовать это, чтобы посеять свой собственный PRNG.
Если вы программируете онлайн-карточную игру или лотерею, вам нужно убедиться, что последовательность почти невозможна. Однако, если вы показываете пользователям, скажем, цитату дня, производительность важнее, чем безопасность.
Обратите внимание, что класс System.Random в C# кодируется неправильно, поэтому его следует избегать.
https://connect.microsoft.com/VisualStudio/feedback/details/634761/system-random-serious-bug
Это обсуждалось довольно долго, но, в конечном счете, вопрос производительности является второстепенным фактором при выборе ГСЧ. Существует огромное количество ГСЧ, и консервированный ЛГМ, из которого состоит большинство системных ГСЧ, не самый лучший и даже не самый быстрый. На старых медленных системах это был отличный компромисс. Этот компромисс редко когда-либо действительно актуален в наши дни. Эта вещь сохраняется в современных системах прежде всего потому, что A) вещь уже построена, и нет никакой реальной причины "изобретать колесо" в этом случае, и B) для того, для чего большая часть людей будет использовать его, это 'достаточно хорошо'.
В конечном счете, выбор ГСЧ сводится к соотношению риск / вознаграждение. В некоторых приложениях, например, в видеоиграх, нет никакого риска. Lehmer RNG более чем адекватен, он небольшой, лаконичный, быстрый, понятный и "в коробке".
Если, например, приложение представляет собой онлайн-игру в покер или лотерею, в которой участвуют реальные призы, и в какой-то момент уравнения в игру вступают реальные деньги, Лемер "в коробке" больше не подходит. В 32-разрядной версии он имеет только 2^32 возможных допустимых состояний, прежде чем он начнет работать в лучшем случае. В наши дни это открытая дверь для атаки грубой силой. В таком случае разработчик захочет использовать нечто вроде очень длинного периода РНГ некоторых видов и, вероятно, получить его от криптографически сильного поставщика. Это дает хороший компромисс между скоростью и безопасностью. В таком случае человек будет искать что-то вроде Mersenne Twister или несколько рекурсивных генераторов в некотором роде.
Если приложение представляет собой что-то вроде передачи больших объемов финансовой информации по сети, сейчас существует огромный риск, и он значительно перевешивает любое возможное вознаграждение. До сих пор есть бронированные машины, потому что иногда хорошо вооруженные люди - это единственная адекватная охрана, и поверьте мне, если бригада спецназовцев с танками, истребителями и вертолетами была финансово возможной, это был бы метод выбора. В таком случае использование криптографически надежного ГСЧ имеет смысл, потому что, какой бы уровень безопасности вы не достигли, он не так высок, как вы хотите. Таким образом, вы возьмете столько, сколько сможете найти, а стоимость - очень, очень отдаленная проблема второго места, как по времени, так и по деньгам. И если это означает, что каждая случайная последовательность генерируется на очень мощном компьютере за 3 секунды, вы будете ждать эти 3 секунды, потому что в схеме вещей это тривиальная стоимость.
Не всем нужны криптографически безопасные случайные числа, и они могут получить больше пользы от более быстрого простого анализа. Возможно, еще важнее то, что вы можете контролировать последовательность номеров System.Random.
В симуляции, использующей случайные числа, которые вы, возможно, захотите воссоздать, вы перезапустите симуляцию с тем же начальным числом. Это может быть полезно для отслеживания ошибок, когда вы хотите восстановить заданный ошибочный сценарий - запуск вашей программы с точно такой же последовательностью случайных чисел, которая вызвала сбой программы.
Random это не генератор случайных чисел, это генератор детерминированных псевдослучайных последовательностей, который берет свое имя по историческим причинам.
Причина использования System.Random если вам нужны эти свойства, а именно детерминированная последовательность, которая гарантированно выдаст одинаковую последовательность результатов при инициализации одним и тем же начальным числом.
Если вы хотите улучшить "случайность", не жертвуя интерфейсом, вы можете наследовать от System.Random переопределение нескольких методов.
Зачем вам нужна детерминированная последовательность
Одна из причин иметь детерминированную последовательность, а не истинную случайность, состоит в том, что она повторяется.
Например, если вы выполняете численное моделирование, вы можете инициализировать последовательность с (истинным) случайным числом и записать, какое число было использовано.
Затем, если вы хотите повторить точно такое же моделирование, например, для целей отладки, вы можете сделать это, вместо этого инициализируя последовательность записанным значением.
Зачем вам нужна эта, не очень хорошая, последовательность
Единственная причина, по которой я могу придумать, заключается в обратной совместимости с существующим кодом, который использует этот класс.
Короче говоря, если вы хотите улучшить последовательность без изменения остальной части вашего кода, продолжайте.
Я написал игру (Crystal Sliders на iPhone: здесь), в которой на карте была бы "случайная" серия драгоценных камней (изображений), и вы поворачивали карту так, как хотели, выбирали их, и они исчезали. - Похож на Bejeweled. Я использовал Random(), и он был заселен с числом тиков 100 нс с момента загрузки телефона, довольно случайное начальное число.
Мне показалось удивительным, что он будет генерировать игры, которые были почти идентичны друг другу - из 90 или около того драгоценных камней, двух цветов, я получал бы два ТОЧНО одинаковых, за исключением 1-3 драгоценных камней! Если вы подбрасываете 90 монет и получаете тот же шаблон, за исключением 1-3 бросков, это ОЧЕНЬ маловероятно! У меня есть несколько снимков экрана, которые показывают их одинаково. Я был шокирован тем, насколько плохой был System.Random()! Я предположил, что я ДОЛЖЕН написать что-то ужасно неправильное в моем коде и неправильно его использовал. Я был неправ, хотя, это был генератор.
В качестве эксперимента - и окончательного решения, я вернулся к генератору случайных чисел, который я использую с 1985 года или около того - что НАМНОГО лучше. Это быстрее, имеет период 1,3 * 10^154 (2^521), прежде чем он повторяется. Исходный алгоритм был заполнен 16-битным числом, но я изменил его на 32-битное число и улучшил начальное заполнение.
Оригинальный здесь:
ftp://ftp.grnet.gr/pub/lang/algorithms/c/jpl-c/random.c
За эти годы я бросил каждый тест случайных чисел, который я мог придумать, и он прошел все из них. Я не ожидаю, что он имеет какое-либо значение, как криптографическое, но он возвращает число так же быстро, как и "return *p++;" пока он не исчерпает 521 бит, а затем запустит быстрый процесс над битами, чтобы создать новые случайные биты.
Я создал оболочку C# - назвал ее JPLRandom(), реализовал тот же интерфейс, что и Random(), и изменил все места, где я вызывал его в коде.
Разница была НАМНОГО лучше - О Боже, я был поражен - я не мог сказать, просто глядя на экраны по 90 или около того драгоценных камней в шаблоне, но я сделал аварийный выпуск своей игры после этого.
И я бы никогда больше не использовал System.Random() для чего-либо еще. Я шокирован тем, что их версия сдувается тем, кому сейчас 30 лет!
-Трейдхут игры
Разные потребности требуют разных ГСЧ. Для шифрования вы хотите, чтобы ваши случайные числа были как можно более случайными. Для моделирования Монте-Карло вы хотите, чтобы они равномерно заполняли пространство и могли запускать ГСЧ из известного состояния.
Если мне не нужна защита, т. Е. Я просто хочу относительно неопределенное значение, а не криптографически сильное, то Random имеет гораздо более простой интерфейс для использования.
Поскольку System.Random критикуется здесь за его "некорректность" и предвзятость, я проверил себя.
распространение
Этот код на F# демонстрирует, что он ведет себя действительно хорошо - на моей средней машине:
let r = System.Random()
Seq.init 1000000 (fun _ -> r.Next(0,10))
|> Seq.toList
|> Seq.groupBy id
|> Seq.map (fun (v,ls) -> v, ls |> Seq.length)
|> Seq.sortBy fst
|> Seq.iter (printfn "%A")
(0, 100208)
(1, 99744)
(2, 99929)
(3, 99827)
(4, 100273)
(5, 100280)
(6, 100041)
(7, 100001)
(8, 100175)
(9, 99522)
Версии фреймворка, машина, операционная система - все может иметь значение. Введите код в интерактивном F# на своем компьютере и попробуйте сами. Для Cyrptography я читал
let arr = [| 0uy |]
let rr = System. Security.Cryptography.RandomNumberGenerator.Create()
Seq.init 1000000 (fun _ -> rr.GetBytes(arr); arr.[0])
|> Seq.toList
|> Seq.groupBy id
|> Seq.map (fun (v,ls) -> v, ls |> Seq.length)
|> Seq.sortBy fst
|> Seq.take 10 // show first 10 bytes
|> Seq.iter (printfn "%A")
// distribution of first 10 bytes
(0uy, 3862)
(1uy, 3888)
(2uy, 3921)
(3uy, 3926)
(4uy, 3948)
(5uy, 3889)
(6uy, 3922)
(7uy, 3797)
(8uy, 3861)
(9uy, 3874)
спектакль
#time
let arr = [| 0uy |]
let r = System.Random()
Seq.init 1000000 (fun _ -> r.NextBytes(arr); arr.[0] |> int64) |> Seq.sum
Real: 00:00:00.204, CPU: 00:00:00.203, GC gen0: 45, gen1: 1, gen2: 1
val it : int64 = 127503467L
let rr = System. Security.Cryptography.RandomNumberGenerator.Create()
Seq.init 1000000 (fun _ -> rr.GetBytes(arr); arr.[0] |> int64) |> Seq.sum
Real: 00:00:00.365, CPU: 00:00:00.359, GC gen0: 44, gen1: 0, gen2: 0
val it : int64 = 127460809L
что предполагает соотношение 1:2 и несколько более приятное поведение памяти по сравнению с криптографической версией.
заключение
В основном из-за более приятного API, отчасти из-за его производительности и неплохого распространения предпочтение отдается System.Random. System.Random также может уменьшить зависимости библиотек, и если фреймворк будет перенесен, System.Random, вероятно, будет доступен раньше, чем вариант Crypto.