Как псевдослучайные и по-настоящему случайные числа различны и почему это имеет значение?

Я никогда не получал этого. Просто скажите, что вы пишете небольшую программу на любом языке, на которой выкладываете несколько кубиков (просто используя кости в качестве примера). После 600 000 рулонов каждый номер будет скатываться около 100 000 раз, что я и ожидал.

Почему существуют сайты, посвященные «истинной случайности»? Разумеется, учитывая вышеизложенное, шансы получить какое-либо число почти равны 1 по тому, сколько из многих чисел оно может выбрать.

Я попробовал его в Python : вот результат 60 миллионов рулонов. Самая высокая вариация равна 0,15. Разве это не так случайно, как это получится?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0
648 голосов | спросил 10 revs, 8 users 46%
Peter
1 Jam1000000amThu, 01 Jan 1970 03:00:00 +030070 1970, 03:00:00

18 ответов


1365

Давайте играть в компьютерный покер, только вы, я и сервер, которым мы оба доверяем. Сервер использует генератор псевдослучайных чисел, который инициализируется с 32-битным семенем прямо перед началом игры. Таким образом, существует около четырех миллиардов возможных колод.

Я получаю пять карт в руке - видимо, мы не играем в Texas Hold 'Em. Предположим, что карты раздаются мне одному, одному вам, одному ко мне, одному вам и т. Д. Поэтому у меня есть первая, третья, пятая, седьмая и девятая карты в колоде.

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

Предположим, что моя вторая карта - это три сердца. Теперь я запускаю свой RNG еще 80 миллионов раз, используя 80 миллионов семян, которые производят королеву пик в качестве первого номера. Это занимает пару секунд. Я записываю все колоды, которые производят три сердца в качестве третьей карты - вторую карту в руке. Это снова только около 2% колод, так что теперь мы упали до 2 миллионов колод.

Предположим, что третья карта в моей руке - это 7 клубов. У меня есть база данных из 2 миллионов семян, которые разыгрывают мои две карты; Я запускаю свой RNG еще 2 миллиона раз, чтобы найти 2% этих колод, которые производят 7 клубов в качестве третьей карты, и мы упали до 40 тысяч колод.

Вы видите, как это происходит. Я запускаю RNG 40000 еще раз, чтобы найти все семена, которые производят мою четвертую карту, и это заводит нас до 800 колод, а затем запускает его еще 800 раз, чтобы получить ~ 20 семян, которые производят мою пятую карту, и теперь я просто создайте эти двадцать колод карт, и я знаю, что у вас есть одна из двадцати возможных рук. Более того, у меня есть очень хорошее представление о том, что я буду делать дальше.

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

UPDATE

Основываясь на комментариях (теперь удаленных из-за их неконструктивного характера), по меньшей мере 0,3% людей, которые прочитали это, путаются в отношении моей точки зрения. Когда люди спорят против очков, которые я не сделал, или, что еще хуже, утверждать для точек, которые I сделал , на что я их не сделал, тогда я знаю, что мне нужно объяснять более четко и осторожно.

Кажется, что существует некоторая путаница вокруг слова distribution , поэтому я хочу тщательно выслушать обычаи.

Возникают следующие вопросы:

  • Как псевдослучайные числа и действительно случайные числа отличаются?
  • Почему разница важна?
  • Различия имеют какое-то отношение к распределению вывода PRNG?

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

Начнем с предположения, что у нас есть волшебное поле с надписью TRNG. В качестве его ввода мы даем ему целое число n, большее или равное единице, и в качестве его вывода оно дает нам действительно случайное число между одним и n, включительно. Вывод окна полностью непредсказуем (при задании числа, отличного от одного), и любое число между одним и n скорее всего другое; то есть распределение равно равномерному . (Есть другие более продвинутые статистические проверки случайности, которые мы могли бы выполнить, я игнорирую этот момент, поскольку это не связано с моим аргументом. TRNG является совершенно статистически случайным по предположению.)

Начнем с непроверенной колоды карт. Мы запрашиваем поле для номера от одного до 52, то есть TRNG(52). Какой бы номер он ни выдал, мы подсчитываем, что многие карты из нашей сортированной колоды и удаляют эту карточку. Он становится первой карточкой в ​​перетасованной колоде. Затем мы запрашиваем TRNG(51) и делаем то же самое, чтобы выбрать вторую карту и т. Д.

Еще один способ взглянуть на это: есть 52! = 52 x 51 x 50 ... x 2 x 1 возможных колод, что примерно равно 2 226 . Мы выбрали одного из них по-настоящему случайным образом.

Теперь мы имеем дело с карточками. Когда я смотрю на свои карты, у меня есть не знаю что , какие у вас есть карты. (Помимо очевидного факта, что у вас нет ни одной из моих карт). Они могут быть любыми картами с равной вероятностью.

Итак, позвольте мне убедиться, что я это четко объясняю. У нас есть равномерное распределение каждого отдельного выхода TRNG(n); каждый из них выбирает число от 1 до n с вероятностью 1 /n. Кроме того, результатом этого процесса является то, что мы выбрали один из 52! возможные палубы с вероятностью 1/52 !, поэтомураспространение по множеству возможных колод равно также .

Хорошо.

Теперь давайте предположим, что у нас есть менее волшебное поле, помеченное PRNG. Прежде чем вы сможете использовать его, он должен быть посеянным с 32-разрядным беззнаковым числом.

ASIDE: Почему 32 ? Не может ли он быть посеян с номером 64 или 256 или 10000 бит? Конечно. Но (1) на практике большинство готовых PRNG засеваются 32-битным числом и (2) если у вас есть 10000 бит случайности, чтобы сделать семя, то почему вы используете PRNG? У вас уже есть источник 10000 бит случайности!

В любом случае, вернемся к тому, как работает PRNG: после того, как он посеян, вы можете использовать его так же, как вы используете TRNG. То есть вы передаете ему число n, и оно возвращает вам число от 1 до n включительно. Более того, распределение этого вывода более или менее равномерное . То есть, когда мы запрашиваем PRNG для числа от 1 до 6, мы получаем 1, 2, 3, 4, 5 или 6 каждый примерно в одну шестую часть времени, независимо от того, что это за семя.

Я хочу подчеркнуть этот момент несколько раз, потому что, похоже, это путает некоторых комментаторов. Распределение PRNG равномерно по меньшей мере двумя способами. Во-первых, предположим, что мы выбираем какое-либо конкретное семя. Мы ожидаем, что последовательность PRNG(6), PRNG(6), PRNG(6)... миллион раз приведет к равномерному распределению чисел между 1 и 6. И во-вторых, если мы выбрал миллион разных семян и назвал PRNG(6) один раз для каждого семени, и мы ожидаем равномерного распределения чисел от 1 до 6. PRNG по любой из этих операций не относится к атаке, которую я описываю .

Этот процесс называется псевдослучайным , потому что поведение поля действительно полностью детерминировано; он выбирает из одного из 2 32 возможных вариантов поведения на основе семени. То есть, после того, как оно высевается, PRNG(6), PRNG(6), PRNG(6), ... создает последовательность с равномерным распределением, но эта последовательность полностью определяется семенем. Для данной последовательности вызовов, скажем, PRNG (52), PRNG (51) ... и т. Д., Возможны только 2 32 возможных последовательностей. Семя по существу выбирает тот, который мы получаем.

Чтобы создать колоду, сервер теперь генерирует семя. (Как мы вернемся к этому вопросу.) Затем они вызывают PRNG(52), PRNG(51) и т. Д., Чтобы создать колоду, аналогичную предыдущей .

Эта система подвержена атаке, описанной мной. Чтобы напасть на сервер, мы сначала опередили время, запустив собственную копию поля с 0 и попросим PRNG(52) и запишем это. Затем мы заново засеваем 1, попросим PRNG(52) и напишем это вниз, вплоть до 2 32 -1.

Теперь покерный сервер, использующий PRNG для создания колод, должен как-то генерировать семя. Неважно, как они это делают. Они могли вызвать TRNG(2^32), чтобы получить поистине случайное семя. Или они могли бы взять текущее время как семя, которое вообще не является случайным; Я знаю, в какое время это так, как ты. Пункт моей атаки заключается в том, что это не имеет значения, , потому что у меня есть моя база данных . Когда я вижу свою первую карту, я могу устранить 98% возможных семян. Когда я вижу свою вторую карту, я могу устранить 98% больше и так далее, пока, в конце концов, я не смогу спуститься до нескольких возможных семян и знаю с большой вероятностью, что у вас в руке.

Теперь, опять же, я хочу подчеркнуть, что здесь предполагается, что , если мы будем называть PRNG(6) миллион раз, мы получим каждое число примерно в одну шестую часть времени . Это распределение (более или менее) равномерное и , если однородность этого дистрибутива - это все, о чем вы заботитесь , это нормально. Суть вопроса заключалась в том, что есть ли что-то другое для распределения PRNG(6), о котором мы заботимся? и ответ yes . Мы также заботимся о непредсказуемости .

Еще один способ взглянуть на проблему состоит в том, что хотя распределение миллиона вызовов на PRNG(6) может быть прекрасным, , потому что PRNG выбирает только 2 32 возможных поведений, он не может генерировать все возможные колоды. Он может генерировать только 2 32 из 2 226 возможных колод; крошечная фракция. Поэтому распределение по множеству всех колод очень плохое. Но опять же, фундаментальная атака здесь основана на том, что мы можем успешно предсказать прошлое и будущее поведение PRNG из небольшого образца его вывода.

Позвольте мне сказать это третье или четыре раза, чтобы убедиться, что это утонет. Здесь есть три дистрибутива. Во-первых, распределение процесса, которое производит случайное 32-битное семя. Это может быть совершенно случайным, непредсказуемым и единообразным, а атака будет работать . Во-вторых, распределение миллиона звонков на PRNG(6). Чтоможет быть совершенно однородным, и атака все равно будет работать. В-третьих, распределение колод, выбранных псевдослучайным процессом, который я описал. Это распределение крайне плохое; может быть выбрана только небольшая часть возможных палуб IRL. Атака зависит от предсказуемости поведения PRNG на основе частичного знания его выхода .

ASIDE: эта атака требует, чтобы злоумышленник знал или мог угадать, какой именно алгоритм используется PRNG. Реально ли это или нет, это открытый вопрос. Тем не менее, при разработке системы безопасности вы должны создать ее защищенную от атак, даже если злоумышленник знает все алгоритмы в программе . Иными словами: часть системы безопасности, которая должна оставаться секретной для обеспечения безопасности системы, называется «ключом». Если ваша система зависит от ее безопасности от используемых вами алгоритмов, то ваш ключ содержит эти алгоритмы . Это чрезвычайно слабая позиция, чтобы быть в!

Перемещение.

Теперь давайте предположим, что у нас есть третий магический бокс с надписью CPRNG. Это криптопрочность версии PRNG. Требуется 256-битное семя, а не 32-битное семя. Он разделяет с PRNG свойство, которое семя выбирает из одного из 2 возможных вариантов поведения 256 . И, как и наши другие машины, у него есть свойство, что большое количество вызовов CPRNG(n) создает равномерное распределение результатов между 1 и n: каждый из них занимает 1 /n времени. Можем ли мы запустить нашу атаку против него?

Наша первоначальная атака требует от нас хранить 2 32 сопоставления от семян до PRNG(52). Но 2 256 - намного большее число; совершенно невозможно выполнить CPRNG(52), что много времени и сохранить результаты.

Но предположим, существует какой-то другой способ взять значение CPRNG(52) и из этого вывести факт о семени? До сих пор мы были довольно глупыми, просто грубо заставляли все возможные комбинации. Можем ли мы заглянуть в волшебный бокс, выяснить, как он работает, и вывести факты о семени на основе результата?

Нет. Детали слишком сложны для объяснения, но CPRNGs продуманно разработаны так, что невозможно сделать вывод any полезного факта о семени от первого выхода CPRNG(52) или из любого подмножества вывода, независимо от того, насколько велика .

ОК, поэтому давайте предположим, что сервер использует CPRNG для создания колод. Ему требуется 256-битное семя. Как он выбирает это семя? Если он выбирает любое значение, которое атакующий может предсказать , то внезапно атака снова станет жизнеспособной . Если мы сможем определить, что из 2 256 возможных семян, только четыре миллиарда из них, вероятно, будут выбраны сервером, тогда мы вернемся в бизнес . Мы можем снова установить эту атаку, обращая внимание только на небольшое количество семян, которые могут быть сгенерированы.

Поэтому сервер должен работать, чтобы обеспечить 256-разрядное число равномерно распределенное , то есть каждое возможное семя выбрано с вероятностью 1/2 256 , В основном сервер должен вызывать TRNG(2^256)-1 для генерации семпла для CPRNG.

Что делать, если я могу взломать сервер и заглянуть в него, чтобы узнать, какое семя выбрано? В этом случае злоумышленник знает полное прошлое и будущее CPRNG . Автору сервера необходимо защититься от этой атаки! (Конечно, если я смогу успешно смонтировать эту атаку, то я, вероятно, также могу просто перенести деньги на свой банковский счет напрямую, так что, возможно, это не так интересно. Точка: семя должно быть труднодоступной тайной, и действительно случайное 256-битное число довольно сложно продумать.)

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

ОК, поэтому семя должно быть как секретным, так и равномерно распределенным, потому что, если это не так, мы можем установить атаку. По предположению, что распределение выходов CPRNG(n) равномерно. Как насчет распределения по множеству всех возможных колод?

Вы могли бы сказать: есть 2 256 возможных последовательностей, выводимых CPRNG, но есть только 2 226 возможных колод. Поэтому есть более возможные последовательности, чем колоды, поэтому мы в порядке; каждая возможная колода IRL теперь (с большой вероятностью) возможна в этой системе. И это хороший аргумент, кроме ...

2 226 - это только приближение 52 !. Разделите его. 2 256 /52! не может быть целым числом, потому что, во-первых, 52! делится на 3, но не имеет двухявляется! Так как это не целое число, мы имеем ситуацию, когда все колоды возможны , но некоторые колоды более вероятны, чем другие .

Если это неясно, рассмотрим ситуацию с меньшими числами. Предположим, что у нас есть три карты: A, B и C. Предположим, мы используем PRNG с 8-битным семенем, поэтому имеется 256 возможных семян. Существует 256 возможных выходов PRNG(3) в зависимости от семени; нет никакой возможности, чтобы одна треть из них была A, одна треть из них была B, а одна треть из них была C, потому что 256 не делится равномерно на 3. Там должно быть небольшое смещение по отношению к одному из них.

Аналогично, 52 не равномерно разделяется на 2 256 , поэтому должно быть некоторое смещение к некоторым картам в качестве первой выбранной карты и смещение от других.

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

Теперь возникает вопрос: есть ли у нас атака, основанная на этом недостатке? , а ответ на практике, возможно, не . CPRNG разработаны таким образом, что , если семя действительно случайное , тогда невозможно вычислить разницу между CPRNG и TRNG.

Хорошо, давайте подведем итог.

  

Как псевдослучайные числа и действительно случайные числа отличаются?

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

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

Почему разница важна?

Поскольку существуют приложения, в которых безопасность системы зависит от непредсказуемости .

  • Если TRNG используется для выбора каждой карты, система недоступна.
  • Если CPRNG используется для выбора каждой карты, система безопасна, если семя является непредсказуемым и неизвестным.
  • Если используется обычный PRNG с небольшим пространством семян, система не защищена независимо от того, является ли семя непредсказуемым или неизвестным; достаточно небольшое пространство семян восприимчиво к атакам грубой силы, описанным мной.
  

Разница имеет какое-то отношение к распределению вывода PRNG?

Равномерность распределения или отсутствия для индивидуальных вызовов до RNG(n) не относится к описанным атакам.

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

Еще один вопрос:

  

Если TRNG намного лучше, чем CPRNG, что в свою очередь намного лучше, чем PRNG, почему кто-нибудь использует CPRNG или PRNG?

Две причины.

Во-первых: расход. TRNG дорогой . Создание действительно случайных чисел сложно. CPRNG дают хорошие результаты для произвольно многих вызовов с вызовом только one для TRNG для семени. Нижняя сторона, конечно, состоит в том, что вам нужно сохранить это семя в секрете .

Второе: иногда мы хотим предсказуемость, и все, о чем мы заботимся, - хорошее распределение. Если вы генерируете «случайные» данные в качестве программных входов для тестового набора и обнаруживает ошибку, тогда было бы неплохо, что запуск набора тестов снова вызывает ошибку!

Надеюсь, теперь это намного яснее.

Наконец, если вам понравилось это, вам может понравиться дальнейшее чтение предмета случайности и перестановок:

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
153

Как говорит Эрик Липперт, это не просто распространение. Существуют и другие способы измерения случайности.

Один из ранних генераторов случайных чисел имеет последовательность в младшем значении бит - он чередует 0 и 1. Поэтому LSB был на 100% предсказуемым. Но вам нужно больше беспокоиться об этом. Каждый бит должен быть непредсказуемым.

Вот хороший способ подумать о проблеме. Предположим, вы генерируете 64 бит случайности. Для каждого результата возьмите первые 32 бита (A) и последние 32 бита (B) и сделайте индекс в массив x [A, B]. Теперь выполните тест миллион раз, и для каждого результата увеличьте массив на это число, т. Е. X [A, B] ++;

Теперь нарисуйте 2D-диаграмму, где чем больше число, тем ярче пиксель в этом месте.

Если он действительно случайный, цвет должен быть однородным серым. Но вы можете получить образцы. Возьмем, к примеру, эту диаграмму «случайности» в порядковом номере TCP системы Windows NT:

Windows NT

или даже этот из Windows 98:

Windows 98

И вот случайность реализации маршрутизатора Cisco (IOS). Cisco ISO

Эти диаграммы любезно предоставлены MichaÅ, Залевский . В этом конкретном случае, если можно предсказать, какой порядковый номер TCP будет иметь систему, вы можете олицетворять эту систему при подключении к другой системе, что позволило бы захватить соединения, перехватить связь и т. Д. И даже если мы не сможем предсказать следующее число в 100% случаев, если мы сможем создать новое соединение под нашим контролем , мы можем увеличить вероятность успеха. И когда компьютеры могут генерировать 100 000 соединений за несколько секунд, шансы успешной атаки идут от астрономических до возможных или даже вероятных.

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
91

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

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

Более подробную информацию о атак RNG можно найти в этой статье в Википедии .

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
75
  

Я попробовал это в Python: вот результат 60 миллионов рулонов. Самая высокая вариация равна 0,15. Разве это не так случайно, как это получится?

На самом деле это , поэтому «хорошо» это плохо. ... Все существующие ответы сосредоточены на предсказуемости учитывая небольшую последовательность начальных значений. Я хочу поднять еще одну проблему:

    ваш дистрибутив имеет гораздо меньшее стандартное отклонение, чем случайные броски

Истинная случайность просто не достигает довольно , что приближается к усреднению «почти точно 1 по тому, как многие числа он может выбирать из», который вы используете в качестве показателя качества.

Если вы посмотрите на этот вопрос в Stack-Exchange о распределении вероятностей для нескольких бросков кубиков , вы увидите формулу стандартного отклонения бросков N кубиков (предполагая действительно случайные результаты):

 sqrt(N * 35.0 / 12.0).

Используя эту формулу, стандартное отклонение для:

  • 1 миллион рулонов 1708
  • 60 миллионов рулонов 13229

Если мы посмотрим на ваши результаты:

  • 1 миллион рулонов: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) 804
  • 60 миллионов рулонов: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) 3827

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

Псевдо-RNG имеют тенденцию перемещаться по последовательности различных чисел, начиная с семени и не пересматривая исходное число за определенный период. Например, реализации старой функции библиотеки C rand() обычно имеют период 2 ^ 32, и они будут посещать каждое число от 0 до 2 ^ 32-1 ровно один раз, прежде чем повторять семя , Таким образом, если вы имитировали 2 ^ 32 кубика, то результаты предварительного модуля (%) будут включать в себя каждое число от 0 до 2 ^ 32, подсчеты для каждого результата 1-6 будут 715827883 или 715827882 ( 2 ^ 32 не кратно 6), а стандартное отклонение поэтому тривиально выше 0. Используя приведенную выше формулу, правильное стандартное отклонение для 2 ^ 32 рулонов равно 111924. В любом случае, по мере увеличения количества псевдослучайных рулонов вы сходитесь к 0 стандартным отклонениям. Можно ожидать, что проблема будет значительной, если количество рулонов будет значительной частью периода, но некоторые псевдо-ГСЧ могут иметь более серьезные проблемы - или проблемы даже с меньшим количеством выборок - чем другие.

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


Чтобы привести конкретный пример: скажем, математик говорит программисту по покерным машинам, что после 60 миллионов симулированных рулонов - используется для мерцания сотен маленьких «огней» вокруг экрана, если было 10,013,229 или более шестерок, которые математик Ожидается, что на 1 уровень меньше среднего, должна быть небольшая выплата. По 68 - 95 - правило 99.7 ( Wikipedia) , это должно произойти примерно 16% того времени (~ 68% попадают в стандартное отклонение /только половина снаружи выше). С вашим генератором случайных чисел это примерно от 3,5 стандартных отклонений выше среднего: при 0.025% шансы - почти нет клиентов получить это преимущество. См. Таблицу «Высокие отклонения» на упомянутой странице, в частности:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |
ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
50

Я просто написал этот генератор случайных чисел для генерации бросков кубиков

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Вы используете его так

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

и т. д. Вы бы с удовольствием использовали этот генератор для программы, которая запускала игру в кости? Помните, что его распределение именно то, что вы ожидаете от «действительно случайного» генератора!

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
26

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

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

Если вас интересуют приложения случайных чисел, просмотрите статью в Википедии .

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
26

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

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

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

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

Одной из известных атак на псевдослучайный ключ является атака на 802.11b WEP . WEP имеет 104-битный длинный ключ, объединенный с 24-битным IV (счетчиком), чтобы сделать 128-битный ключ, который, в свою очередь, применяется к алгоритму RC4 для генерации псевдослучайного ключа.

( RC4( IV + Key ) ) XOR (message)

Ключи были тесно связаны друг с другом. Здесь только IV увеличилось на 1 на каждом шаге, а все остальные остались прежними. Поскольку это не было чисто случайным, это было катастрофическим и легко разбитым. Ключ можно восстановить, проанализировав около 40000 кадров, что является вопросом минут. Если WEP использовал чисто случайный 24-битный IV, тогда он может быть безопасным до примерно 2 ^ 24 (почти 16,8 миллионов) кадров.

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
12

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

Вот довольно приятное видео по этой теме: http://www.youtube.com/смотреть? v = itaMNuWLzJo

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
10

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

Для тривиальных приложений псевдослучайность прекрасна, так как в вашем примере вы получите примерно правильный процент (приблизительно 1/6 из общего набора результатов) с небольшим изменением (что вы увидите, если бы вы бросили кости 600 тыс. раз);

Однако, когда дело доходит до таких вещей, как компьютерная безопасность; Требуется истинная случайность.

Например, алгоритм RSA начинается с того, что компьютер выбирает два случайных числа (P и Q), а затем делает несколько шагов для этих чисел, чтобы генерировать специальные числа, известные как ваши общедоступные и закрытые ключи. (Важная часть закрытого ключа состоит в том, что она является частной, и никто ее не знает!)

Если злоумышленник может узнать, какие два «случайных» номера, которые ваш компьютер собирается выбрать, они могут сделать те же шаги, чтобы вычислить ваш закрытый ключ (тот, который никто не должен знать!)

С вашим личным ключом злоумышленник может делать такие вещи, как a) Поговорите с вашим банком, претендующим на то, что вы, б) Слушайте свой «безопасный» интернет-трафик и сможете его расшифровать, c) Маскарад между вами и другими сторонами Интернет.

В этом случае требуется истинная случайность (т. е. невозможность угадать /рассчитать).

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
10

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

Некоторые люди не поверят мне, что это возможно даже при случайном распределении случайных чисел, но очевидно, что если вы посмотрите на последовательность (1, 3, 5, 2, 4, 1, 3, 5, 2 , 4, ...), где второе из двух чисел больше с вероятностью 0,6.

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
8

Короткий ответ заключается в том, что обычно люди требуют «истинной случайности» по плохой причине, а именно, что они не имеют понимания криптографии.

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

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

(Я думаю, что это должно было быть опубликовано в разделе «Безопасность» или «Криптография».)

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

Изменить: некоторые люди здесь предполагают модель угрозы, в которой злоумышленник может читать внутреннее состояние CSPRNG, и оттуда приходит к выводу, что CSPRNG не являются безопасным решением. Это пример плохого моделирования потоков. Если злоумышленник владеет вашей системой, игра закончена, проста и проста. Не имеет значения, используете ли вы TRNG или CSPRNG на этом этапе.

Изменить: Итак, чтобы суммировать все это ... Энтропия необходима для семени CSPRNG. Как только это будет сделано, CSPRNG предоставит все непредсказуемые биты, которые нам нужны для приложений безопасности, намного быстрее, чем мы можем (обычно) собирать энтропию. Если непредсказуемость не требуется, например, для моделирования, Mersenne Twister будет предоставлять номера с хорошими статистическими свойствами с гораздо более высокой скоростью.

Изменить: любой, кто хочет понять проблему безопасного генерации случайных чисел, должен прочитать следующее: http://www.cigital.com/whitepapers/dl/The_Importance_of_Reliable_Randomness.pdf

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
7

Не все PRNG подходят для всех целей. Например, Java.util.SecureRandom использует хэш SHA1, размер которого равен 160 бит. Это означает, что есть 2 160 возможных потоков случайных чисел, которые могут исходить от него. Просто как тот. Вы не можете получить более 2 160 значений внутреннего состояния. Таким образом, вы не можете получить более 2 160 уникальных потоков случайных чисел из одного семени, независимо от того, откуда взялось ваше семя. Предполагается, что Windows CryptGenRandom использует 40-байтовое состояние, оно имеет 2 320 возможных потоков случайных чисел.

Количество способов перетасовки стандартной колоды 52-карточек составляет 52 !, что составляет примерно 2 226 . Таким образом, независимо от посева, вы не можете использовать Java.util.SecureRandom для перетасовки колоды карт. Существует примерно 2 66 возможных тасов, которые он не может произвести. Конечно, мы не знаем, какие они ...

Итак, если бы у меня был источник, скажем, 256-бит истинной случайности (например, с карты Quantis RNG), я мог бы вынести PRNG, например CryptGenRandom (), с этим семенем, а затем использовать PRNG для перетасовки колоду карт. Если я повторюсь с истинной случайностью в каждом тасовании, это будет хорошо: непредсказуемо и статистически случайно. Если бы я сделал то же самое с Java.util.SecureRandom, там были бы тасованы, которые невозможно было бы создать, потому что они не могут быть высечены с 256 битами энтропии, а его внутреннее состояние не может представлять все возможные тасования.

Обратите внимание, что результаты java.util.SecureRandom были бы непредсказуемыми и статистически случайными. Никакой статистический тест никогда не выявил бы проблему! Но выход RNG недостаточно велик, чтобы охватить весь домен всех возможных выходов, необходимых для имитации колоды карт.

И помните, если вы добавите джокеров, это будет 54! что вам нужно покрыть, что требует около 2 238 возможностей.

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
6

Псевдослучайные числа генерируются с использованием математической функции и начального значения (называемого seed ), а случайные числа - нет. Их предсказуемость делает их невероятно полезными для игровых повторов, так как вам нужно только сохранить семя и вход игрока - AI будет реагировать точно таким же «случайным образом» каждый раз.

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
6

Разница между «истинным» случайным и «псевдо» случайным числом - это предсказуемость. Этот ответ уже предоставлен.

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

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
2

Для быстрой проверки случайности вы берете точки со случайными координатами в [0; 1), затем помещаете их в k-мерный куб. Затем вы выполняете процедуру, чтобы разрезать этот куб на подкубы - каждый том субкуба (или подсемейства) должен быть правильно измерен этой процедурой с флуктуациями в соответствии с известной теоремой.

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

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

  2. научные цели. В науке вы должны не только иметь среднее среднее значение в хорошем состоянии, но и устранять корреляции между различными случайными числами. Поэтому, если вы возьмете (a_i - a) (a_ {i + 1} -a) и найдите его распределение, оно должно соответствовать статистике.

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

Сегодня только генераторы квантовой механики обеспечивают истинную случайность.

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
1
  

Почему важна истинная случайность?

В основном есть две основные причины, по которым необходима истинная случайность:

  1. Если вы используете RNG для криптографии (включая такие вещи, как азартные игры на реальные деньги и запуск лотереи), тогда PRNG сделает вас намного лучше, чем математический анализ (который предполагает TRNG). PRNG на самом деле не будет случайным, но имеет шаблон - противники могут использовать шаблон для взлома шифрования, который должен был быть невоспроизводимым.
  2. Если вы используете RNG для имитации «случайных» входов, например, для тестирования или моделирования ошибок, PRNG делает ваш подход слабым. Когда вы не обнаружите ошибок, всегда будет сомневаться в этом: есть ли ошибка, которая не заметна в моем шаблоне PRNG, но появлялась бы, если бы я использовал только TRNG? Точно ли мое симуляторное описание точно описывает реальность, или это явление, которое я обнаружил просто артефакт шаблона PRNG?

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

  

Как PRNG Python недостаточно хорош?

Очень маловероятно, что вы сможете обнаружить подводные камни реального PRNG, используя такую ​​простую методологию. Статистический анализ RNG является самостоятельной областью науки, и некоторые очень сложные тесты доступны для сравнения «случайности» алгоритма. Они намного более продвинуты, чем ваша простая попытка.

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
0

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

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

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

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

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30
-4

Рассказ:

  

Создает случайное семя, используя текущую микросекунду системы.

Этот трюк довольно старый и по-прежнему функционирует.

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

Скажем, пример, я могу определить семя, используя только 10 значений. Итак, зная семя, я могу угадать следующее значение.

Если бы я использовал seed = 1, я мог бы получить следующую последовательность:

1, 2, 3, 4, 5, 6, 7, 8, 9 ... (и я вычитаю, что семя использовало id 1 и следующее значение 10)

Но что произойдет, если при изменении отправить все «n-ые» значения ?. Изменение семени на текущие микросекунды - дешевый трюк (то есть, он не требует много циклов процессора).

Итак, теперь последовательность: (seed = 1) 1, 2, 3, 4, 5, (семя = 2), 7, 9, 11, 13 ... (15?)

В этом случае:

a) Я не могу вычесть, какое семя использовалось.

b) Ergo, я не могу угадать следующее значение.

c) Единственное, что я могу сделать, это вычесть, что следующее семя может быть большим числом.

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

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

ответил nwgat 11 MaramTue, 11 Mar 2014 05:49:30 +04002014-03-11T05:49:30+04:0005 2014, 05:49:30

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132