Чем отличаются псевдослучайные и действительно случайные числа и почему это важно?

664

Я никогда не совсем понял это. Просто скажите, что вы пишете небольшую программу на любом языке, которая бросает несколько кубиков (просто в качестве примера). После 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
Peter
источник
1
Взгляните на статью в Википедии, посвященную сгенерированным аппаратным средствам случайным числам. Также посмотрите это - stats.stackexchange.com/questions/32794/…
stablefish
21
Что вы подразумеваете под "бросает кубики"? К нему прикреплена рука робота и камера?
звездный синий
3
Хотя я согласен с общей суть вашего тона, что мы часто слишком много беспокоимся об этом, но это использовалось в реальной жизни: en.wikipedia.org/wiki/Ronald_Dale_Harris
Grady Player
3
См. Эту статью об онлайн-игре в покер, в которой отсутствует истинная случайность, почему это важно.
Varaquilex
1
Если вы просто держите счетчик 0-5 и бросаете кубик соответственно, 666 гориллионов раз, вы также получите равное распределение.
Jcora

Ответы:

1382

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

У меня в руке пять карт - очевидно, мы не играем в Техасский Холдем. Предположим, карты раздаются одному мне, одному вам, одному мне, одному вам и так далее. Итак, у меня в колоде первая, третья, пятая, седьмая и девятая карты.

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

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

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

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

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

ОБНОВИТЬ

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

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

Вопросы под рукой:

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

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

Давайте начнем с предположения, что у нас есть волшебная коробка с надписью 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-разрядным беззнаковым номером.

В сторону: почему 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)чем мы заботимся? и ответ да . Мы также заботимся о непредсказуемости .

Другой способ взглянуть на проблему состоит в том, что, хотя распределение миллиона вызовов PRNG(6)может быть нормальным, поскольку PRNG выбирает только из 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)из этого факта о семени? До сих пор мы были довольно глупы, просто перебирая все возможные комбинации. Можем ли мы заглянуть внутрь волшебной коробки, выяснить, как она работает, и вывести факты о семени на основе результатов?

Нет. Детали слишком сложны для объяснения, но CPRNG продуманно спроектированы так, что невозможно вывести какой-либо полезный факт о семени из первого вывода 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)не относится к атакам , которые я описал.

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

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

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

Две причины.

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

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

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

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

Eric Lippert
источник
20
Хорошо, мальчики и девочки. Этого достаточно, чтобы комментировать сейчас. Если вы хотите обсудить это дальше, зайдите в чат, kthnxbye!
Ivo Flipse
1
@Eric Но семя не сбрасывается перед каждой новой колодой, не так ли? Таким образом, хотя вы и правы в том, что мы отбираем только относительно небольшое количество траекторий , вы не знаете точно, где в данный момент находится траектория, и траектории пересекаются.
AS
Хорошая (но плотная) трактовка связанных с этим вопросов содержится в TAOCP том 2, раздел 3.5 «Что такое случайная последовательность?» (Стр. 149) Кнута, начиная с ярких определений равнораспределенных, k-распределенных и ∞-распределенных последовательностей. Псевдослучайные последовательности обсуждаются в 3.5.F (стр. 170). См. Также критерии псевдослучайности из теории сложности и немецкого BSI .
ShreevatsaR
160

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

Один из ранних генераторов случайных чисел имеет последовательность в младшем значащем бите - он чередует 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

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

Брюс Барнетт
источник
30
Это так блестяще, что вызывает слезы на моих глазах. Должно быть приложение, которое создает их для каждой ОС (мобильной / настольной / серверной) и платформы (JVM / Javascript / и т. Д.).
HDave
5
Функция Windows rand () довольно хороша! Он создает облако, которое не имеет видимых паттернов. Посмотрите мою реализацию, чтобы попробовать ее (и другие алгоритмы): github.com/Zalastax/visualize_random
Zalastax
93

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

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

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

bwDraco
источник
9
Криптографические PRNG существуют и широко используются. Они могут из семян небольшого размера генерировать практически неограниченный поток случайных чисел. В вычислительном отношении невозможно отличить такой поток от истинных случайных чисел, таким образом, никакая дополнительная информация не может быть получена из любой части такого потока, и для любой практической цели числа столь же хороши, как и истинные случайные числа.
aaaaaaaaaaaa
Я думаю, что самый простой способ объяснить это, что алгоритмы генератора случайных чисел должны быть запрограммированы. Это означает, что есть набор инструкций, которым следует следовать. Если есть набор инструкций, он не может быть случайным.
Келтари
6
@Keltari Вам не хватает элемента энтропии ... Большинство ГСЧ (по крайней мере, криптографических) собирают данные из внешних источников (например, движение мыши) и используют их как часть начального условия - таким образом, преобразование из Aв Bзапрограммировано, но начальное состояние A(должно быть) не угадывается. Linux /dev/randomбудет сохранять приблизительную величину энтропии и прекратит выдавать числа, если она упадет слишком низко.
Основное
Из любопытства - почему лавовые лампы считаются «действительно случайными»? Я понимаю, что он демонстрирует довольно непредсказуемое поведение, но тот, кто достаточно твердо разбирается в гидродинамике и в том, как эти жидкости взаимодействуют в гравитационной среде Земли, несомненно, может дать «предсказуемые» результаты, не так ли? Конечно, лавовые лампы непредсказуемы, но для меня они вовсе не случайны, а очень предсказуемы.
theGreenCabbage
1
@theGreenCabbage: Я подозреваю, что лавовые лампы хаотичны. Учитывая достаточно хорошую компьютерную модель и достаточное количество цифр точности, вы можете (в принципе) на некоторое время предсказать поведение. Но, поскольку система хаотична, две лавовые лампы с малейшим изменением начальных условий будут быстро расходиться в поведении. (И этот комментарий игнорирует хаотические аттракторы.)
dmm
76

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

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

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

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

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

 sqrt(N * 35.0 / 12.0).

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

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

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

  • 1 миллион рулонов: стандартное отклонение (1000066, 999666, 1001523, 999452, 999294, 999999) составляет 804
  • 60 миллионов рулонов: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) - 3827

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

Псевдо-ГСЧ имеют тенденцию проходить через последовательность различных чисел, начиная с начального числа и не пересматривая исходное число в течение определенного периода. Например, реализации старой rand()функции библиотеки C обычно имеют период 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 (Википедия) это должно происходить примерно в 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                |
Tony D
источник
Вы сравниваете яблоки и апельсины здесь. Два стандартных отклонения не имеют абсолютно никакого отношения друг к другу.
Jbeuh
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

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

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

Крис Тейлор
источник
2
«Генераторы псевдослучайных чисел ... генерируют предсказуемые числа с правильным распределением» - просто потому, что это PRNG, не гарантирует, что оно имеет идеальное распределение (фактически, коммерческие, в общем и целом, не обеспечивают причины, изложенные в этих ответах). Хотя они могут быть предсказуемыми при наличии достаточной информации (используемый алгоритм, начальное начальное число, выходные значения, w / e), они все равно имеют дисперсию.
Брайан С.
3
Кроме того, точки, я знаю, но get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so onпросто слишком элегантный , не говоря уже :)
Янус Troelsen
2
@BrianS На самом деле, PRNG, который не прошел тестирование распределения в течение долгого времени, будет предсказуемым по определению. Таким образом, в случае большого N, если вы добираетесь даже до N / 2 голов в N бросках монет, вы можете начать делать ставки на головы, и вы можете выиграть больше, чем проиграли. Точно так же, если вы получили идеальное распределение голов против хвостов, но головы всегда приходили парами, у вас снова был бы рецепт для победы. Тесты на распределение - это то, как вы знаете, PRNG - это хорошо.
Джон Кипарски
1
Вы забыли nonlocal next:-).
Кос,
5
Еще лучший пример: Pi считается нормальным , что означает, что любая последовательность цифр любой заданной длины в любом основании появляется не чаще, чем любая другая последовательность этой длины в этом основании. Алгоритм, который, когда запрашивается n случайных битов, берет следующие n битов числа pi и возвращает их («семя» - это бит, с которого вы начинаете), в конечном итоге должен давать идеально равномерное распределение. Но вы все равно не захотите этого для своего генератора - тот, кто знает последние сгенерированные вами биты, может найти первый раз, когда произойдет последовательность, предположить, что ваше семя есть, и, вероятно, будет правильным.
крайней мере,
26

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

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

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

Алекс Маккензи
источник
12
Большая проблема - когда вам нужны случайные числа, которые злоумышленник не может предсказать по соображениям безопасности.
Дэвид Шварц
16
Вы уверены, что, черт возьми, можете встретить время, когда вам нужно действительно случайное число. Достаточно открыть веб-страницу, которая начинается с https://...
Ян Худек
3
@JanHudec: Ну, при ежедневном использовании вам понадобятся безопасные случайные числа в момент, когда вы откроете любую программу, задолго до того, как вы введете в адресную строку: смотрите рандомизацию расположения адресного пространства . Вот почему такие вещи случаются.
Рейд
5
@JanHudec Я специально говорил в том смысле, что вам нужно будет использовать онлайн генератор случайных чисел. Истинные случайные числа используются часто, но на самом деле очень немногие люди должны генерировать их сами.
Алекс Маккензи
2
Игровые автоматы также используют PRNG, а не TRNG. Генератор работает все время, и число выбирается в то время, когда нажата кнопка отжима. Сумма PRNG и действительно случайное время нажатия кнопки составляют TRNG.
Роджер Даль
26

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

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

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

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

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

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

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

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

Прабху
источник
3
Я бы обвинял WEP в плохо спроектированном протоколе с использованием слабого шифра. С современными потоковыми шифрами вы можете использовать счетчик как IV.
CodesInChaos
2
Основной проблемой с WEP было повторение ключа в 2 ^ 24 (почти 16 миллионов) кадров. Еще хуже было с родственными ключами, которые позволяли взломать код примерно за 40000 кадров. Главное здесь то, что ключ не случайный. Это тесно связано, так что это легко взломать.
Прабху
1
Псевдослучайность плоха в криптографии только при генерации криптографических ключей . Это совершенно нормально за пределами этого. Действительно, RC4 - это чуть больше, чем генератор псевдослучайных чисел, засеянный 128-разрядным расширением ключа XORed на открытый текст сообщения.
Мэтт
12

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

Вот довольно хорошее видео на эту тему: http://www.youtube.com/watch?v=itaMNuWLzJo

Fatal705
источник
Предсказуемость! = Повтор. Мерсенн Твистер - хороший тому пример. На большинстве реализаций после 624 Int32 вы можете предсказать все следующие числа, но последовательность Мерсенна Твистера намного длиннее этой (2 ^ 19937 - 1).
HoLyVieR
Я не понимаю, почему этот ответ не помещается в стек, так как мне кажется, что это точный и краткий ответ на вопрос, хотя бы частично. Псевдослучайные числа могут быть легко предсказаны после некоторых розыгрышей, причем количество розыгрышей зависит от алгоритма «качества» псевдослучайного числа. При выборе «хорошего» алгоритма учитываются следующие аспекты: 1. каждое значение рисуется с одинаковой частотой (распределение), 2. требуется «много времени», чтобы перезапустить последовательность в начале и снова начать рисовать те же числа в тот же порядок.
минут
msgstr "истинные случайные числа не [предсказуемы]". На сегодня это правда. Теперь, если мы верим в теорию Большого взрыва, и у нас есть много возможностей для вычисления состояния Вселенной в любое время после ВВ, основываясь на физике, тогда ... мы можем предсказать будущее, включая тот факт, что Я пишу этот очень точный комментарий. Правильно?
минут
Это гипотетически верно, однако, учитывая огромную степень энтропии, связанной с реальными действиями реальных тел, требуемая вычислительная мощность будет смехотворно огромной. Думайте континенты, покрытые компьютерами. Кроме того, из-за зависимости от предыдущего состояния необходимо сохранять состояние каждого тела во вселенной в каждый момент времени, что по определению потребует больше места, чем доступно во вселенной, полностью заполненного устройством памяти
TheEnvironmentalist
@ Эколог - Ах! «Континенты покрыты компьютерами» ... разве это не «Путеводитель автостопом по Галактике»? ;-)
ysap
10

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

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

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

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

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

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

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

DoubleFission
источник
10

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

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

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

gnasher729
источник
8

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

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

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

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

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

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

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

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

Эрван Легран
источник
2
Это не обязательно вопрос безопасности. Я думаю, что есть причины использовать действительно случайные числа, которые не связаны с безопасностью. Если бы я проводил какое-то научное исследование, которое зависит от случайных чисел, и по любой причине было критически важно, чтобы числа были как можно более случайными, я бы, конечно, воспользовался аппаратным ГСЧ, поэтому я могу быть уверен, что любые наблюдаемые свойства не являются следствием к причудам ГСЧ.
Кеф Шектер
3
@KefSchecter Это их аппаратные PRNG, как правило, имеют смещенный и / или коррелированный вывод. Им нужен шаг постобработки, чтобы превратить его в единый независимый вывод. Нет оснований полагать, что этот этап постобработки более надежен, чем современный потоковый шифр. Я, конечно, больше доверял бы потоковому шифру. В качестве дополнительного бонуса он воспроизводим, что ценно в науке.
CodesInChaos
ОК, достаточно справедливо. Но не относится ли это в равной степени к приложениям криптографии? Даже ответ здесь гласит, что вам нужен аппаратный RNG для заполнения CSPRNG.
Кеф Шектер
2
@KefSchecter Да, криптографическим приложениям нужны истинные случайные числа для заполнения CSPRNG. Но для всего остального мы можем использовать этот CSPRNG.
CodesInChaos
@KefSchecter: криптографические приложения требуют, чтобы поток не воспроизводился всем миром. Напротив, в научных приложениях полезно показать, что используемые «случайные» числа не просто выбраны, чтобы показать анализ в хорошем свете. Например, если после объявления методов вы объявляете, что будете генерировать данные определенным образом, используя номера лотереи на следующий день, читатели могут быть несколько уверены в том, что вы не обманули свои результаты, даже если у розыгрыша в будний день всего пара десятков. биты энтропии.
суперкат
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 возможностей.

Пако Хоуп
источник
2
Почему тебя волнует, что некоторые тасовки не могут произойти? Это ограничение не имеет видимого эффекта.
CodesInChaos
2
Я сорта ошеломлен этим вопросом. Для жестко регулируемых игровых компаний такой уклон математически доказывает, что ваши шансы выиграть в карточную игру отличаются от компьютера, чем от бумажной колоды карт. Неважно, шансы лучше или хуже. Они РАЗНЫЕ. Компьютер морально не эквивалентен реальной колоде. Более того, мы не можем охарактеризовать разницу. Игровая компания, столкнувшаяся с жесткими регулятивными штрафами, очень заботится.
Пако Хоуп
1
Но это заметно. Я обнаружил это, используя известный процесс: просмотр исходного кода и знание проблемной области. Вот что замечательно. Я не могу использовать автоматический статистический анализ. Это так же легко обнаружить, как кто-то, кто использует java.util.Random или Mersenne Twister. Статистический анализ - не единственный действительный механизм обнаружения несоответствия ГСЧ / проблемной области. Отказы, которые проходят этот детектор, по определению не являются успехами.
Пако Хоуп
1
Я никогда не соглашался с этим утверждением. Я сказал, что статистический анализ не является надежным доказательством правильности ГСЧ / ГСЧ. Это пример ложного негатива. Это должно быть неверно, но тест статистического вывода пройдет его. Если я использую SHA1 (1), SHA1 (2), SHA1 (3) ... SHA1 (n) в качестве моего "RNG", это также пройдет статистические тесты. Это тоже неправильно. Определение правильности выходит за рамки определения «проходит статистические тесты». Прохождение статистических тестов необходимо, но не достаточно.
Пако Хоуп
4
@CodesInChaos: аргумент «мы не знаем об атаке, которая может использовать тот факт, что подавляющее большинство возможных перестановок IRL никогда не будет произведено», не означает, что такая атака невозможна, просто мы не знаю, что это такое и как от него защититься. Правильный подход в этом случае состоит в том, чтобы исключить возможность атаки путем устранения условия: создать ГСЧ достаточного качества, чтобы он мог фактически генерировать каждую возможную колоду.
Эрик Липперт
6

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

BonzaiThePenguin
источник
6

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

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

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

radouxju
источник
2

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

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

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

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

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

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

sanaris
источник
1

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

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

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

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

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

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

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

Superbest
источник
0

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

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

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

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

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

оборота Dice9
источник
-5

Короткий рассказ:

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

Этот трюк довольно стар и все еще функционален.

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

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

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

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

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

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

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

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

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

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

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

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

magallanes
источник
2
Это довольно плохая идея, и она является источником уязвимости для вещей, которые нуждаются в совершенно непредсказуемой последовательности. Если вы берете микросекунды, у вас есть только 10 ^ 6 возможностей семян, что довольно мало.
HoLyVieR
@HoLyVieR: это, конечно, плохая идея, если вы заботитесь о безопасности, но не так плохо, как кажется: вы обычно используете микросекунды с момента запуска системы (или эпоху Unix ....), что значительно увеличивает диапазон возможных значений.
Микера
1
@mikera Это не лучше, время обработки запроса предсказуемо. Это вектор уязвимости для большого количества функций сброса пароля. Эти сценарии генерировали «случайный» токен с вашей техникой, и злоумышленник мог найти сгенерированный токен, поскольку найти время, в которое он был выполнен, довольно тривиально ... в это же время был отправлен запрос на сброс пароля + - 150 мс.
HoLyVieR
Конечно, эта ситуация очень плохая. Но ситуация, когда состояние заполнялось при запуске системы, а злоумышленник не может точно угадать время запуска, не так плоха. Вы можете легко выбрать из 10 ^ 12 возможных микросекунд, что может сделать некоторые типы атак невозможными. Чтобы было ясно: все эти решения довольно плохи с крипто-точки зрения, но константы имеют значение .
Микера
Для онлайн-серверов информация о работоспособности системы иногда предоставляется публично. Или вы можете получить его на странице состояния «Инциденты. Сервер снова запущен». Или вы можете пропинговать, дождаться большого простоя и заметить, что это может быть перезагрузка компьютера (что даст несколько сотен миллионов времени на проверку, что довольно мало).
Дерексон