Генератор истинных случайных чисел [закрыт]

Question

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

Кто-нибудь знает об этой статье?

Answer 1

Я полагаю, что это было включено thedailywtf.com - то есть.это не то, что ты хочешь делать.

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

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

Answer 2

Я должен не согласиться со многими ответами на этот вопрос.

Можно собирать случайные данные на компьютере. SSL, SSH и VPN не будут безопасными, если вы не сможете.

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

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

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

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

Answer 3

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

Есть философские дебаты о том, что означает случайность. Здесь я буду иметь в виду «неотличим во всех отношениях от равномерного (0,1) IID распределение по выборкам» Я полностью игнорирую философские вопросы о том, что такое случайность.

У Кнута, том 2, есть анализ, в котором он пытается создать генератор случайных чисел, как вы предлагаете, а затем анализируется, почему он выходит из строя, и каковы истинные случайные процессы. В томе 2 подробно рассматриваются ГСЧ.

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

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

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

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

Answer 4

Алгоритм для действительно случайных чисел не может существовать, так как определение случайных чисел:

  

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

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

Теперь PRNG, для которых чрезвычайно трудно вывести начальное число, являются криптографически защищенными . Возможно, вы захотите посмотреть их в Google, если это то, что вы ищете.

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

Они все еще подвержены атакам, потому что их можно измерить независимо, иметь отклонения и так далее. Так что это действительно сложно. Это делается с помощью специального оборудования, которое обычно довольно дорого. Я понятия не имею, насколько хорош / dev / random , но могу поспорить, что он недостаточно хорош для криптографии (большинство криптографических программ поставляются со своим собственным RNG, и Linux при запуске также ищет аппаратный RNG). вверх).

Answer 5

Согласно Википедии / dev / random в Unix- как операционные системы, это специальный файл, который служит генератором истинных случайных чисел.

Драйвер / dev / random собирает шум окружающей среды из различных недетерминированных источников, включая, помимо прочего, синхронизацию между клавиатурой и синхронизацию между прерываниями, которые возникают в среде операционной системы. Данные шума отбираются и объединяются с CRC-подобной функцией микширования в постоянно обновляемый «энтропийный пул». Случайные битовые строки получают путем взятия MD5-хеша содержимого этого пула. Однонаправленная хеш-функция отлавливает истинные случайные биты из данных пула и скрывает состояние пула от злоумышленников.

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

Модуль ядра / dev / random также предоставляет другой интерфейс, / dev / urandom, который не ожидает перезарядки энтропийного пула и возвращает столько байтов, сколько требуется. В результате / dev / urandom значительно быстрее при генерации по сравнению с / dev / random, который используется только тогда, когда требуется очень высокое качество случайности.

Answer 6

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

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

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

Answer 7

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

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

Answer 8

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

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

Ум в криптографии редко вознаграждается. Пойдите с проверенными и верными решениями.

Answer 9

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

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

И иногда

• Аппаратное обеспечение, основанное на дрейфе часов
• Счетчики Гейгера и другие детекторы редких событий
• Всевозможные датчики, подключенные к аналого-цифровым преобразователям

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

Answer 10

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

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

Answer 11

Один из лучших способов генерации случайного числа - через Clock Drift . Это в первую очередь работает с двумя генераторами.

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

Очень легко генерировать и невозможно предсказать.