Зачем вообще использовать класс C # System.Random вместо System.Security.Cryptography.RandomNumberGenerator?

Зачем кому-либо вообще использовать «стандартный» генератор случайных чисел из System.Random вместо того, чтобы всегда использовать криптографически безопасный генератор случайных чисел из System.Security.Cryptography.RandomNumberGenerator (или его подклассов, потому что RandomNumberGenerator является абстрактным)?

Нейт Лоусон в своей презентации Google Tech Talk « Крипто наносит ответный удар » в 13:11, чтобы не использовать «стандартные» генераторы случайных чисел из Python, Java и C #, а вместо этого использовать криптографически безопасную версию.

Я знаю разницу между двумя версиями генераторов случайных чисел (см. Вопрос 101337 ).

Но в чем причина не всегда использовать безопасный генератор случайных чисел? Зачем вообще использовать System.Random? Возможно, производительность?

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

Помимо скорости и более полезного интерфейса (и 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 тысяч экземпляров 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 байтов случайными данными 1000000 раз, занимает 49 мс для Random, но 2845 мс для RNGCryptoServiceProvider. Обратите внимание: если вы увеличиваете размер заполняемого буфера, разница сужается, поскольку накладные расходы для RNGCryptoServiceProvider менее актуальны.

Наиболее очевидные причины уже были упомянуты, поэтому вот более неясная: криптографические ГПСЧ, как правило, необходимо постоянно заполнять «настоящей» энтропией. Таким образом, если вы используете CPRNG слишком часто, вы можете истощить пул энтропии системы, который (в зависимости от реализации CPRNG) либо ослабит его (тем самым позволяя злоумышленнику предсказать его), либо он будет блокироваться при попытке заполнить свой пул энтропии (таким образом, он становится вектором атаки DoS-атаки).

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

Это реальная проблема, BTW, которая наблюдалась на безголовых серверах (которые, естественно, имеют довольно небольшие пулы энтропии, потому что им не хватает источников энтропии, таких как ввод с клавиатуры и мыши) под управлением Linux, где приложения неправильно используют /dev/randomядро CPRNG для всех видов случайных чисел, тогда как правильным поведением было бы чтение небольшого начального значения из /dev/urandomи использование его для заполнения своего собственного PRNG.

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

Это обсуждалось довольно подробно, но в конечном итоге вопрос производительности является второстепенным при выборе ГСЧ. Существует огромное количество ГСЧ, и консервированный Lehmer LCG, из которого состоит большинство системных ГСЧ, не самый лучший и даже не обязательно самый быстрый. На старых, медленных системах это был отличный компромисс. В наши дни такой компромисс редко бывает актуальным. Вещь сохраняется в современных системах прежде всего потому, что А) вещь уже построена, и в данном случае нет реальной причины `` изобретать велосипед '', и Б) из-за того, для чего огромное количество людей будет ее использовать, 'достаточно хорошо'.

В конечном итоге выбор ГСЧ сводится к соотношению риска и вознаграждения. В некоторых приложениях, например в видеоиграх, нет никакого риска. ГСЧ Lehmer более чем адекватен, он небольшой, лаконичный, быстрый, хорошо понятный и готовый к использованию.

Если приложение представляет собой, например, онлайн-игру в покер или лотерею, в которой участвуют реальные призы и в какой-то момент в уравнении участвуют реальные деньги, то «в коробке» Лемера больше не подходит. В 32-битной версии у него есть только 2 ^ 32 возможных действительных состояния, прежде чем он начнет цикл в лучшем случае . В наши дни это открытая дверь для атаки грубой силы. В таком случае разработчик захочет перейти к чему-то вроде ГСЧ с очень длинным периодом некоторого вида и, вероятно, засеять его от надежного в криптографическом отношении поставщика. Это дает хороший компромисс между скоростью и безопасностью. В таком случае человек будет искать что-то вроде Mersenne Twister или какой- нибудь многократный рекурсивный генератор .

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

Обратите внимание, что класс System.Random в C # кодируется неправильно, поэтому его следует избегать.

https://connect.microsoft.com/VisualStudio/feedback/details/634761/system-random-serious-bug#tabs

Не всем нужны криптографически безопасные случайные числа, и они могут получить больше пользы от более быстрого простого запроса. Возможно, еще важнее то, что вы можете контролировать последовательность чисел System.Random.

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

Если мне не нужна безопасность, то есть мне просто нужно относительно неопределенное значение, а не криптографически стойкое, Random имеет гораздо более простой интерфейс в использовании.

Разные потребности требуют разных ГСЧ. Для криптографии вы хотите, чтобы ваши случайные числа были как можно более случайными. Для моделирования Монте-Карло вы хотите, чтобы они равномерно заполняли пространство и могли запускать ГСЧ из известного состояния.

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

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

Если вы хотите улучшить "случайность" без ущерба для интерфейса, вы можете унаследовать от System.Random переопределения несколько методов.

• https://msdn.microsoft.com/en-us/library/system.random.sample(v=vs.110).aspx

Зачем вам детерминированная последовательность

Одна из причин иметь детерминированную последовательность, а не истинную случайность, состоит в том, что она воспроизводима.

Например, если вы запускаете численное моделирование, вы можете инициализировать последовательность (истинным) случайным числом и записать, какое число использовалось. .

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

Зачем вам нужна именно эта, не очень хорошая последовательность

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

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

Я написал игру (Crystal Sliders на iPhone: здесь ), которая будет размещать «случайную» серию драгоценных камней (изображений) на карте, и вы можете вращать карту, как вы хотите, и выбирать их, и они исчезают. - Похоже на Bejeweled. Я использовал Random (), и он был заполнен количеством тиков 100 нс с момента загрузки телефона, довольно случайное начальное число.

Я нашел это потрясающим что он генерирует игры, которые были почти идентичны друг другу - из 90 или около того драгоценных камней 2 цветов, я бы получил два ТОЧНО одинаковых, за исключением от 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 лет!

-Игры Traderhut

Поскольку 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.