Альтернативные источники энтропии
Ладно, я думаю, это совершенно субъективно и все такое, но я думал об источниках энтропии для генераторов случайных чисел. Получается, что большинство генераторов посеяно с текущим временем, верно? Что ж, мне было любопытно, какие другие источники могут быть использованы для генерации совершенно достоверных, случайных чисел.
Будет ли использование нескольких источников (таких как время + текущее время поиска жесткого диска [мы здесь фантастически]) вместе создать "более случайное" число, чем один источник? Каковы логические пределы количества источников? Сколько на самом деле достаточно? Время выбрано просто потому, что это удобно?
Извините, если такого рода вещи не разрешены, но мне любопытно, что такое теория источников.
15 ответов
В статье Википедии об аппаратном генераторе случайных чисел перечислены несколько интересных источников случайных чисел с использованием физических свойств.
Мои любимые:
- Источник радиационного распада, обнаруженный счетчиком Гейгера, подключенным к ПК.
- Фотоны путешествуют через полупрозрачное зеркало. Взаимоисключающие события (отражение - передача) обнаруживаются и ассоциируются с битовыми значениями "0" или "1" соответственно.
- Тепловой шум от резистора усиливается для обеспечения случайного источника напряжения.
- Лавинный шум, генерируемый лавинным диодом. (Как это круто?)
- Атмосферный шум, обнаруженный радиоприемником, подключенным к ПК
Раздел " Проблемы" статьи Википедии также описывает хрупкость многих из этих источников / датчиков. Датчики почти всегда производят убывающие случайные числа, поскольку они стареют / ухудшаются. Эти физические источники должны постоянно проверяться статистическими тестами, которые могут анализировать сгенерированные данные, гарантируя, что инструменты не сломались бесшумно.
SGI однажды использовала фотографии лавовой лампы в различных "фазах глобуса" в качестве источника энтропии, которая в конечном итоге превратилась в генератор случайных чисел с открытым исходным кодом под названием LavaRnd.
Я использую Random.ORG, они предоставляют бесплатные случайные данные из атмосферного шума, которые я использую для периодического повторного посева RNG Мерсена-Твистера. Это почти так же случайно, как вы можете получить без аппаратных зависимостей.
Не беспокойтесь о "хорошем" семени для генератора случайных чисел. Статистические свойства последовательности не зависят от того, как посеян генератор. Однако есть и другие вещи. беспокоиться о. См. Подводные камни в генерации случайных чисел.
Что касается аппаратных генераторов случайных чисел, эти физические источники должны быть измерены, и процесс измерения имеет систематические ошибки. Вы можете найти "псевдо" случайные числа более высокого качества, чем "реальные" случайные числа.
Ядро Linux использует время прерывания устройства (мышь, клавиатура, жесткие диски) для генерации энтропии. В Википедии есть хорошая статья об энтропии.
Современные ГСЧ проверяются на наличие корреляций в соседних семенах и проходят несколько сотен итераций после посева. Итак, к сожалению скучный, но верный ответ заключается в том, что это действительно не имеет большого значения.
Вообще говоря, использование случайных физических процессов должно быть проверено, чтобы они соответствовали равномерному распределению и в противном случае были отклонены.
На мой взгляд, часто лучше использовать очень хорошо понятный генератор псевдослучайных чисел.
Некоторые "микросхемы" TPM (Trusted Platform Module) имеют аппаратный RNG. К сожалению, TPM (Broadcom) в моем ноутбуке Dell не имеет этой функции, но многие компьютеры, продаваемые сегодня, поставляются с аппаратным ГСЧ, который использует действительно непредсказуемые квантово-механические процессы. Intel внедрила разнообразие тепловых шумов.
Кроме того, не используйте только текущее время, чтобы заполнить ГСЧ в криптографических целях или в любом приложении, где важна непредсказуемость. Использование нескольких младших битов времени в сочетании с несколькими другими источниками, вероятно, хорошо.
Подобный вопрос может быть полезен для вас.
Я нашел HotBits несколько лет назад - числа получены из радиоактивного распада, действительно случайные числа.
Существуют ограничения на количество номеров, которые вы можете загрузить в день, но мне всегда было забавно использовать их как действительно, действительно случайные начальные числа для ГСЧ.
Я использовал программу шифрования, которая использовала движение мыши пользователя для генерации случайных чисел. Единственная проблема заключалась в том, что программе приходилось приостанавливать работу и просить пользователя произвольно перемещать мышь в течение нескольких секунд для правильной работы, что не всегда может быть практичным.
Извините, что опоздал на эту дискуссию (сколько ей сейчас 3 с половиной года?), Но у меня вновь возник интерес к генерации PRN и альтернативным источникам энтропии. Разработчик ядра Linux Расти Рассел недавно провел в своем блоге обсуждение альтернативных источников энтропии (кроме /dev/urandom).
Но я не так впечатлен его выбором; MAC-адрес сетевой карты никогда не меняется (хотя он уникален среди всех остальных), и PID кажется слишком маленьким возможным размером выборки.
Я баловался с Mersenne Twister (на моем компьютере с Linux), который был засеян по следующему алгоритму. Я прошу любые комментарии / отзывы, если кто-то хочет и заинтересован:
- Создать буфер массива из 64 бит + 256 бит * количество
/procфайлы ниже. - Поместите значение счетчика меток времени (TSC) в первые 64 бита этого буфера.
Для каждого из следующих
/procфайлы, рассчитайте сумму SHA256:/proc/meminfo/proc/self/maps/proc/self/smaps/proc/interrupts/proc/diskstats/proc/self/statПоместите каждое 256-битное значение хеш-функции в собственную область массива, созданного в (1).
- Создайте хэш SHA256 для всего этого буфера. ПРИМЕЧАНИЕ: я мог (и, вероятно, должен) использовать другую хеш-функцию, полностью независимую от SHA-функций - этот метод был предложен в качестве "защиты" от слабых хеш-функций.
Теперь у меня есть 256 бит НАДЕЖДЫ случайных (достаточно) энтропийных данных, чтобы заполнить мой тварь Мерсенна. Я использую вышеупомянутое, чтобы заполнить начало массива MT (624 32-разрядных целых числа), а затем инициализировать остаток этого массива с кодом автора MT. Кроме того, я мог бы использовать другую хеш-функцию (например, SHA384, SHA512), но мне нужен буфер массива другого размера (очевидно).
Оригинальный код Mersenne Twister требовал одного 32-битного начального числа, но я чувствую, что это ужасно неадекватно. Запуск "просто" 2^32-1 разных МТ в поисках взлома криптозащиты не выходит за рамки практической возможности в наше время.
Я хотел бы прочитать чьи-либо отзывы по этому поводу. Критика приветствуется. Я буду защищать свое использование /proc файлы, как указано выше, потому что они постоянно меняются (особенно /proc/self/* файлы, и TSC всегда дает другое значение (разрешение наносекунды [или лучше], IIRC). Я провел тесты Diehard на этот счет (с точностью до нескольких сотен миллиардов битов), и, похоже, он проходит с летающими цветами. Но это, вероятно, больше свидетельствует о надежности Mersenne Twister в качестве PRNG, чем о том, как я его сею.
Конечно, это не совсем невосприимчиво к тому, что кто-то их взламывает, но я просто не вижу, чтобы все эти (и SHA*) были взломаны и сломаны в моей жизни.
Источник семян не так уж важен. Более важным является алгоритм генератора псевдо-чисел. Однако некоторое время назад я слышал о создании семян для некоторых банковских операций. Они взяли много факторов вместе:
- время
- температура процессора
- скорость вентилятора
- напряжение процессора
- Я не помню больше:)
Даже если некоторые из этих параметров не сильно меняются во времени, вы можете поместить их в хорошую функцию хеширования.
Как сгенерировать хорошее случайное число?
Может быть, мы можем учесть бесконечное количество вселенных? Если это правда, что все время создаются новые параллельные вселенные, мы можем сделать что-то вроде этого:
int Random() {
return Universe.object_id % MAX_INT;
}
В каждый момент мы должны находиться в другой ветви параллельных вселенных, поэтому у нас должен быть другой идентификатор. Единственная проблема заключается в том, как получить объект Вселенной:)
Некоторые используют ввод с клавиатуры (тайм-ауты между нажатиями клавиш), я слышал о том, что в романе я думаю, что можно использовать радиостатический прием, но, конечно, для этого требуется другое аппаратное и программное обеспечение...
Шум на вершине космического микроволнового фона. Конечно, вы должны сначала удалить некоторую анизотропию, объекты переднего плана, коррелированный шум детектора, галактику и локальные групповые скорости, поляризации и т. Д. Остается много подводных камней.
Как насчет вращения потока, который будет манипулировать некоторой переменной в узком цикле в течение фиксированного промежутка времени, прежде чем он будет убит. То, что вы получите в итоге, будет зависеть от скорости процессора, загрузки системы и т. Д. Очень хамски, но лучше, чем просто srand(время (NULL))...
Не беспокойтесь о "хорошем" семени для генератора случайных чисел. Статистические свойства последовательности не зависят от того, как посеян генератор.
Я не согласен с советами Джона Д. Кука. Если вы затравите Mersenne Twister со всеми битами, установленными в ноль, кроме одного, он будет первоначально генерировать числа, которые не являются случайными. Генератору требуется много времени, чтобы превратить это состояние во все, что могло бы пройти статистические тесты. Простая установка первых 32 битов генератора в начальное число будет иметь аналогичный эффект. Кроме того, если все состояние установлено в ноль, генератор будет производить бесконечные нули.
Правильно написанный код RNG будет иметь правильно написанный алгоритм заполнения, который принимает, скажем, 64-битное значение и заполняет генератор, так что он будет генерировать приличные случайные числа для каждого возможного ввода. Так что, если вы используете надежную библиотеку, подойдет любое семя. Но если вы взламываете собственную реализацию, вам нужно быть осторожным.