Истинный генератор случайных чисел
Извините за то, что это не "настоящий" вопрос, но когда-то я помню, что видел здесь пост о рандомизации рандомизатора случайным образом для генерации действительно случайных чисел, а не просто псевдослучайного Я не вижу этого, если я ищу это.
Кто-нибудь знает об этой статье?
11 ответов
Я считаю, что это было на thedailywtf.com - то есть. не то, что вы хотите сделать.
Невозможно получить действительно случайное число из псевдослучайных чисел, независимо от того, сколько раз вы вызываете randomize().
Вы можете получить "истинные" случайные числа из специального оборудования. Вы также можете собирать энтропию от движений мыши и подобных вещей.
Я должен не согласиться с множеством ответов на этот вопрос.
Можно собирать случайные данные на компьютере. SSL, SSH и VPN не будут безопасными, если вы не сможете.
Принцип работы программного генератора случайных чисел состоит в том, что существует пул случайных данных, которые собираются из разных мест, таких как смещение тактового сигнала, время прерывания и т. Д.
Хитрость в этих схемах заключается в правильной оценке энтропии (шикарное название для случайности). Неважно, является ли источник смещением, если вы правильно оценили энтропию.
Чтобы проиллюстрировать это, вероятность того, что я попаду на букву e в этом комментарии, гораздо выше, чем у z, поэтому, если бы я использовал ключевые прерывания в качестве источника энтропии, это было бы смещением, но все же есть некоторая случайность, которая будет иметь место в этом входе. Вы не можете точно предсказать, какая последовательность букв будет следующей в этом абзаце. Вы можете извлечь энтропию из этой неопределенности и использовать ее как часть случайного байта.
Хорошие генераторы реальных случайных чисел, такие как Ярроу, имеют встроенную в них довольно сложную оценку энтропии и будут испускать столько байтов, сколько можно с уверенностью сказать, в своем "пуле случайностей".
Алгоритм для действительно случайных чисел не может существовать, поскольку определение случайных чисел:
Наличие непредсказуемых результатов и, в идеальном случае, все результаты одинаково вероятны; в результате такого выбора; отсутствует статистическая корреляция.
Существуют лучшие или худшие генераторы псевдослучайных чисел (PRNG), то есть полностью предсказуемые последовательности чисел, которые трудно предсказать, не зная части информации, называемой начальным числом.
Теперь PRNG, для которых чрезвычайно трудно вывести семя, криптографически безопасны. Возможно, вы захотите посмотреть их в Google, если это то, что вы ищете.
Другой способ (является ли это действительно случайным или нет - это философский вопрос) - использовать случайные источники данных. Например, непредсказуемые физические величины, такие как шум, или измерение радиоактивного распада.
Они по-прежнему подвержены атакам, потому что их можно измерить независимо, иметь отклонения и так далее. Так что это действительно сложно. Это делается с помощью специального оборудования, которое обычно довольно дорого. Я понятия не имею, насколько хорошо /dev/random есть, но я бы поспорил, что он недостаточно хорош для криптографии (большинство криптографических программ поставляются с собственным RNG, а Linux также ищет аппаратный RNG при запуске).
В конце поста я отвечу на ваш вопрос о том, почему вы можете использовать несколько генераторов случайных чисел для "большей случайности".
Есть философские споры о том, что означает случайность. Здесь я буду иметь в виду "неотличим во всех отношениях от равномерного (0,1) iid-распределения по отобранным выборкам". Я полностью игнорирую философские вопросы о том, что такое случайность.
Во втором томе Кнута есть анализ, в котором он пытается создать генератор случайных чисел, как вы предлагаете, а затем анализируется, почему он выходит из строя, и каковы истинные случайные процессы. В томе 2 подробно рассматриваются ГСЧ.
Другие рекомендуют использовать случайные физические процессы для генерации случайных чисел. Однако, как мы видим из взаимодействия Espo/vt, эти процессы могут иметь тонкие периодические элементы и другие неслучайные элементы, отчасти из-за внешних факторов с детерминированным поведением. В общем, лучше никогда не предполагать случайность, но всегда проверять ее, и вы обычно можете исправить такие артефакты, если вы их знаете.
Можно создать "бесконечный" поток битов, который кажется совершенно случайным, детерминированным. К сожалению, такие подходы растут в памяти с количеством запрашиваемых битов (как и должно быть, чтобы избежать повторяющихся циклов), поэтому их область действия ограничена.
На практике вам почти всегда лучше использовать генератор псевдослучайных чисел с известными свойствами. Ключевыми числами, которые нужно искать, является измерение фазового пространства (которое примерно смещено между выборками, которые вы все еще можете рассчитывать на равномерное распределение) и ширина в битах (количество битов в каждой выборке, которые являются равномерно случайными по отношению друг к другу.) и размер цикла (количество выборок, которое вы можете взять до того, как распределение начнет повторяться).
Однако, поскольку случайные числа из данного генератора детерминистически находятся в известной последовательности, ваша процедура может быть раскрыта кем-то, кто просматривает генератор и находит выравнивающую последовательность. Следовательно, вы можете избежать немедленного распознавания вашего распределения как поступающего от определенного генератора случайных чисел, если вы поддерживаете два генератора. В первом случае вы выбираете i, а затем отображаете это равномерно по единице на n, где n - самое большее размер фазы. Затем во втором вы выбираете i раз и возвращаете i-й результат. Это уменьшит размер вашего цикла до (первоначального размера цикла /n) в худшем случае, но для этого цикла все равно будут генерироваться одинаковые случайные числа, и это будет таким образом, что поиск выравнивания будет экспоненциальным по n. Это также уменьшит длину независимой фазы. Не используйте этот метод, если вы не понимаете, что уменьшенная продолжительность цикла и независимая фаза означают для вашего приложения.
Согласно Википедии /dev/randomв Unix-подобных операционных системах представляет собой специальный файл, который служит генератором истинных случайных чисел.
Драйвер / dev / random собирает шум окружающей среды из различных недетерминированных источников, включая, помимо прочего, временные интервалы между клавиатурами и временные прерывания, возникающие в среде операционной системы. Данные шума отбираются и объединяются с CRC-подобной функцией микширования в постоянно обновляемый "энтропийный пул". Случайные битовые строки получают путем взятия MD5-хеша содержимого этого пула. Однонаправленная хеш-функция отлавливает истинные случайные биты из данных пула и скрывает состояние пула от злоумышленников.
Процедура / dev / random поддерживает оценку истинной случайности в пуле и уменьшает ее каждый раз, когда случайные строки запрашиваются для использования. Когда оценка падает до нуля, процедура блокирует и ожидает появления недетерминированных событий для обновления пула.
Модуль ядра / dev / random также предоставляет другой интерфейс, / dev / urandom, который не ожидает перезарядки энтропийного пула и возвращает столько байтов, сколько требуется. В результате / dev / urandom значительно быстрее при генерации по сравнению с / dev / random, который используется только тогда, когда требуется очень высокое качество случайности.
Джон фон Нейман однажды сказал что-то о том, что "всякий, кто пытается генерировать случайные числа с помощью алгоритмических средств, конечно же, живет во грехе".
Даже / dev / random не является случайным в математическом или физическом смысле этого слова. Даже измерение распада радиоизотопа не является случайным. (Скорость затухания равна. Измерения нет. Счетчики Гейгера имеют небольшое время сброса после каждого обнаруженного события, в течение которого они не могут обнаружить новые события. Это приводит к незначительным отклонениям. Существуют способы существенного смягчения этого, но не полностью устранить это.)
Хватит искать истинную случайность. Хороший генератор псевдослучайных чисел - это то, что вам нужно.
Если вы верите в детерминированную вселенную, настоящей случайности не существует.:-) Например, кто-то предположил, что радиоактивный распад действительно случайный, но ИМХО, просто потому, что ученые еще не разработали схему, не означает, что там нет схемы, которую нужно разрабатывать. Обычно, когда вам нужны "случайные" числа, вам нужны числа для шифрования, которые никто не сможет угадать.
Самое близкое, что вы можете получить к случайному, - это измерить что-то естественное, что ни один враг не сможет измерить. Обычно вы отбрасываете наиболее значимые биты из ваших измерений, в результате чего числа с большей вероятностью будут равномерно распределены. Пользователи случайных чисел с твердым ядром получают специальное оборудование, которое измеряет радиоактивные события, но вы можете получить некоторую случайность от человека, использующего компьютер, от таких вещей, как интервалы нажатия клавиш и движения мыши, и, если у компьютера нет прямых пользователей, от датчиков температуры процессора, и из сетевого трафика. Вы также можете использовать такие вещи, как веб-камеры и микрофоны, подключенные к звуковым картам, но я не знаю, кто это делает.
На компьютере обычно имеется много легко доступных физических источников случайного шума:
- Микрофон (надеюсь, в шумном месте)
- Сжатое видео с веб-камеры (указывает на что-то переменное, например, на лавовую лампу или улицу)
- Время клавиатуры и мыши
- Сетевой пакет контента и времени (весь мир способствует)
И иногда
- Аппаратные средства, основанные на дрейфе
- Счетчики Гейгера и другие детекторы редких событий
- Все виды датчиков, подключенных к аналого-цифровым преобразователям
Трудно оценить энтропию этих источников, которая в большинстве случаев является низкой, несмотря на высокие скорости передачи данных и очень изменчивой; но энтропия может быть оценена с помощью консервативных предположений или, по крайней мере, не потраченных впустую, для систем питания, таких как Ярроу или Фортуна.
Подводя итог, можно сказать, что наше рабочее определение того, что является безопасным источником случайности, аналогично нашему определению криптографической безопасности: оно кажется случайным, если умные люди смотрят на него и не могут показать, что это не так. т совершенно непредсказуемо.
Не существует системы для генерации случайных чисел, которые невозможно было бы предсказать, так же как и нет криптографического шифра, который невозможно было бы взломать. Надежные решения, используемые для важной работы, - это просто те, которые до сих пор было трудно победить. Если кто-то говорит вам иначе, они продают вам что-то.
Хитрость редко вознаграждается в криптографии. Перейти с проверенными и верными решениями.
Невозможно получить "истинные" случайные числа, компьютер - это логическая конструкция, которая не может создать "действительно" случайные числа, только псевдослучайные. Однако существуют лучшие и худшие псевдослучайные алгоритмы.
Чтобы получить "действительно" случайное число, вам нужен физический случайный источник, некоторые игровые автоматы на самом деле имеют эти встроенные - часто это радиоактивный источник, радиоактивный распад (который, насколько я знаю, действительно случайный) используется для генерации число.
Один из лучших методов для генерации случайного числа - через Clock Drift. Это в первую очередь работает с двумя генераторами.
Аналогия того, как это работает, представляет собой гоночный автомобиль на простой овальной трассе с линией "время" в начале круга, а также линия "время" на одной из шин. Когда автомобиль преодолеет круг, будет сгенерировано число на основе разницы между положением белой линии на дороге и на шине.
Очень легко генерировать и невозможно предсказать.