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

Давайте поиграем в компьютерный покер, только вы, я и сервер, которому мы оба доверяем. Сервер использует генератор псевдослучайных чисел, который инициализируется 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 ²²⁶ . Мы выбрали один из них поистине наугад.

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

Итак, позвольте мне убедиться, что я объясню это ясно. У нас есть равномерное распределение каждого отдельного выхода 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 ³² возможных вариантов поведения на основе начального числа. То есть, как только он будет посеян, он PRNG(6), PRNG(6), PRNG(6), ... создает последовательность чисел с равномерным распределением, но эта последовательность полностью определяется начальным числом . Для данной последовательности вызовов, скажем, PRNG (52), PRNG (51) ... и т. Д., Существует только 2 ³² возможных последовательности. Семя по сути выбирает, какое мы получим.

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

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

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

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

Другой способ взглянуть на проблему состоит в том, что, хотя распределение миллиона вызовов PRNG(6)может быть нормальным, поскольку PRNG выбирает только из ³² возможных вариантов поведения, он не может генерировать все возможные колоды. Он может генерировать только 2 ³² из 2 ²²⁶ возможных колод; крошечная фракция. Так что распределение по множеству всех колод очень плохое. Но опять же, фундаментальная атака здесь основана на том, что мы можем успешно предсказать прошлое и будущее поведение на PRNGоснове небольшой выборки его результатов.

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

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

Двигаемся дальше.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Две причины.

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

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

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

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

• Предположим, у меня есть равномерно распределенные случайные данные. Как я могу преобразовать это в данное неравномерное распределение?
• Почему некоторые GUID генерируются случайным образом? Все их биты случайны? (Нет.) Могу ли я полагаться на GUID в качестве источника истинной случайности? (Нет!)
• Как я могу генерировать большие случайные числа, используя факторические обозначения?
  • Как я могу превратить это в случайную перестановку?
• Как мы можем смонтировать описанную здесь атаку против случайной перестановки?
• Какое смещение вводится при использовании оставшейся техники для реализации RNG(n)?

As Eric Lippert says, it not just distribution. There are other ways to measure randomness.

One of the early random number generators has a sequence in the least significant bit - it alternated 0's and 1's. Therefore the LSB was 100% predictable. But you need to worry about more than that. Each bit must be unpredictable.

Here is a good way to think about the problem. Let's say you are generating 64 bits of randomness. For each result, take the first 32 bits (A), and the last 32 bits(B), and make an index into an array x[A,B]. Now perform the test a million times, and for each result, increment the array at that number, i.e. X[A,B]++;

Now draw a 2D diagram, where the larger the number, the brighter the pixel at that location.

If it is truly random, the color should be a uniform grey. But you might get patterns. Take for instance this diagram of the "randomness" in the TCP sequence number of the Windows NT system:

or even this one from Windows 98:

And here is the randomness of the Cisco router (IOS) implementation.

These diagrams are courtesy of Michał Zalewski's paper. In this particular case, if one can predict what the TCP sequence number will be of a system, one can impersonate that system when making a connection to another system - which would allow hijacking of connections, interception of communication, etc. And even if we can't predict the next number 100% of the time, if we can cause a new connection to be created under our control, we can increase the chance of success. And when computers can generate 100,000 of connections in a few seconds, the odds of a successful attack goes from astronomical to possible or even likely.

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

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

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

I tried it in Python: Here's the result of 60 million rolls. The highest variation is like 0.15. Isn't that as random as it's going to get?

Actually, it's so "good" it's bad... All the existing answers focus on predictability given a small sequence of initial values. I want to raise another issue:

    your distribution has much smaller standard deviation than random rolls should

True randomness just doesn't come quite that close to averaging "almost exactly 1 over how ever many numbers it can choose from" that you're using as an indication of quality.

If you look at this Stack Exchange question about probability distributions for multiple dice rolls, you'll see a formula for the standard deviation of N dice rolls (assuming genuinely random outcomes):

 sqrt(N * 35.0 / 12.0). 

Using that formula, the standard deviation for:

• 1 million rolls is 1708
• 60 million rolls is 13229

If we look at your results:

• 1 million rolls: stddev(1000066, 999666, 1001523, 999452, 999294, 999999) is 804
• 60 million rolls: stddev(9997653, 9997789, 9996853, 10006533, 10002774, 9998398) is 3827

You can't expect the standard deviation of a finite sample to exactly match the formula, but it should come pretty close. Yet, at 1 million rolls you've less than half the proper stddev, and by 60 million you're under a third - it's getting worse, and that's no coincidence....

Pseudo-RNGs tend to move through a sequence of distinct numbers, starting with the seed and not revisiting the original number for a specific period. For example, implementations of the old C library rand() function commonly have a period of 2^32, and they'll visit every number between 0 and 2^32-1 exactly once before repeating the seed. So, if you simulated 2^32 dice rolls the pre-modulus (%) results would include each number from 0 to 2^32, the counts for each 1-6 outcome would be 715827883 or 715827882 (2^32 isn't a multiple of 6), and the standard deviation therefore only trivially above 0. Using the formula above, the correct standard deviation for 2^32 rolls is 111924. Anyway, as your number of pseudo-random rolls increases you converge towards 0 standard deviation. The issue can be expected to be significant when the number of rolls is a significant fraction of the period, but some pseudo-RNGs may exhibit worse problems - or problems even with fewer samples - than others.

So even if you don't care about cryptographic vulnerabilities, in some applications you may care about having distributions that don't have overly, artificially even results. Some types of simulation are quite specifically trying to work out the consequences of the uneven results that naturally occur with large samples of individually random outcomes, but they're under-represented in some pRNG's results. If you're trying to simulate how a huge population reacts to some event, this issue could radically alter your results leading to wildly inaccurate conclusions.

To give a concrete example: Say a mathematician tells a poker machine programmer that after 60 million simulated rolls - used to flicker hundreds of little "lights" around the screen, if there've been 10,013,229 or more sixes, which the mathematician expects to be 1 stddev away from mean, there should be a small payout. Per the 68–95–99.7 rule (Wikipedia) this should happen about 16% of the time (~68% fall within a standard deviation / only half outside are above). With your random number generator, this is from about 3.5 standard deviations above the mean: Under 0.025% chance - almost no customers get this benefit. See the Higher Deviations table on the page just mentioned, specifically:

| 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 | 

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

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 

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

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

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

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

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

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

Например, следующая функция генератора случайных чисел, используемая в 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 миллионов) кадров.

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

The difference is that pseudorandom generated numbers are predictable (repeating) after some time where true random numbers aren't. The length it takes to repeat depends on the length of the seed which is used for its generation.

Here is a pretty nice video about that topic: http://www.youtube.com/watch?v=itaMNuWLzJo

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

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

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

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

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

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

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

The first random number that I ever used had the excellent property that of any two consecutive random numbers, the second one was larger with a probability of 0.6. Not 0.5. And the third was larger than the second with probability 0.6, and so on. You can imagine how that plays havoc with a simulation.

Some people wouldn't believe me this was even possible with the random numbers being equally distributed, but it's obviously possible if you look at the sequence (1, 3, 5, 2, 4, 1, 3, 5, 2, 4, ... ) where the second of two numbers is larger with probability 0.6.

On the other hand, for simulations it can be important to be able to reproduce random numbers. Let's say you do a traffic simulation and want to find out how some actions you might take could improve traffic. In that case you want to be able to re-create the exact same traffic data (like people trying to enter a town) with different actions you tried to improve traffic.