Альтернативные источники энтропии

StackOverflow https://stackoverflow.com/questions/300854

  •  08-07-2019
  •  | 
  •  

Вопрос

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

Будет ли использование нескольких источников (например, время + текущее время поиска жесткого диска [мы здесь фантастически]) создать «более случайное» число, чем один источник?Каковы логические пределы количества источников?Насколько действительно достаточно?Время выбрано просто потому, что оно удобно?

Извините, если подобные вещи не разрешены, но мне любопытна теория, лежащая в основе источников.

Это было полезно?

Решение

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

Мои любимые:

  • Источник излучения ядерного распада, обнаруженный счетчиком Гейгера, подключенным к ПК.
  • Фотоны проходят через полупрозрачное зеркало.Взаимоисключающие события (отражение — передача) обнаруживаются и связываются со значениями битов «0» или «1» соответственно.
  • Тепловой шум резистора, усиленный для создания случайного источника напряжения.
  • Лавинный шум, создаваемый лавинным диодом. (Как это круто?)
  • Атмосферный шум, обнаруженный радиоприемником, подключенным к ПК.

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

Другие советы

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

Я использую Random.ORG , они предоставляют бесплатные случайные данные из атмосферного шума, которые я использую для периодически повторно сеять Мерсен-Твистер RNG. Это почти так же случайно, как вы можете получить без аппаратных зависимостей.

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

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

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

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

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

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

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

Я обнаружил HotBits несколько лет назад - цифры генерируются в результате радиоактивного распада, действительно случайные числа.

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

Некоторые TPM (доверенный платформенный модуль) "чипы" есть аппаратный RNG. К сожалению, TPM (Broadcom) в моем ноутбуке Dell не имеет этой функции, но многие компьютеры, продаваемые сегодня, поставляются с аппаратным RNG, который использует действительно непредсказуемые квантово-механические процессы. Intel внедрила разнообразие тепловых шумов.

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

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

Извините, что опоздал на эту дискуссию (сколько ему сейчас 3,5 года?), но у меня возобновился интерес к генерации PRN и альтернативным источникам энтропии.Разработчик ядра Linux Расти Рассел недавно обсуждал свою блог об альтернативных источниках энтропии (кроме /dev/urandom).

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

я баловался Мерсенн Твистер (на моем компьютере с Linux), который засеян по следующему алгоритму.Я прошу любые комментарии/отзывы, если кто-то хочет и заинтересован:

  1. Создайте буфер массива размером 64 бита + 256 бит * количество /proc файлы ниже.
  2. Поместите значение счетчика меток времени (TSC) в первые 64 бита этого буфера.

  3. Для каждого из следующих /proc файлы, вычислите сумму SHA256:

    • /proc/meminfo
    • /proc/self/maps
    • /proc/self/smaps
    • /proc/interrupts
    • /proc/diskstats

    • /proc/self/stat

      Поместите каждое 256-битное значение хеш-функции в отдельную область массива, созданного в (1).

  4. Создайте хэш SHA256 всего этого буфера. ПРИМЕЧАНИЕ: Я мог бы (и, вероятно, должен) использовать другую хеш-функцию, полностью независимую от функций SHA — этот метод был предложен как «защита» от слабых хэш-функций.

Теперь у меня есть 256 бит С НАДЕЖДОЙ случайные (достаточные) энтропийные данные, чтобы засеять мой Твистер Мерсенна.Я использую приведенное выше для заполнения начала массива MT (624 32-битных целых числа), а затем инициализирую остальную часть этого массива кодом автора MT.Как и я мог используйте другую хэш-функцию (например.SHA384, SHA512), но мне понадобится буфер массива другого размера (очевидно).

Исходный код Mersenne Twister требовал одного 32-битного начального числа, но я считаю, что этого совершенно недостаточно.Запуск «всего лишь» 2^32-1 различных МТ в поисках взлома криптографии не выходит за рамки практической возможности в наши дни.

Я хотел бы прочитать чьи-либо отзывы по этому поводу.Критика более чем приветствуется.Я буду защищать свое использование /proc файлы, как указано выше, поскольку они постоянно меняются (особенно /proc/self/* файлы, а TSC всегда выдает другое значение (наносекундное [или лучшее] разрешение, IIRC).я побежал Непреклонные тесты по этому поводу (на сумму нескольких сотен миллиард бит), и, похоже, это проходит с честью.Но это, вероятно, больше свидетельствует о правильности Твистера Мерсенна как ГПСЧ, чем о том, как я его засеиваю.

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

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

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

Источник семян не так уж и важен.Более важным является алгоритм генератора псевдоцифр.Однако некоторое время назад я слышал о создании начального числа для некоторых банковских операций.Они объединили множество факторов:

  • время
  • температура процессора
  • скорость вентилятора
  • напряжение процессора
  • больше не помню :)

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

Как сгенерировать хорошее случайное число?

Может быть, мы сможем принять во внимание бесконечное количество вселенных?Если это правда, что все время создаются новые параллельные вселенные, мы можем сделать что-то вроде этого:

int Random() {
    return Universe.object_id % MAX_INT;
}

В каждый момент мы должны находиться в другой ветви параллельных вселенных, поэтому у нас должен быть другой идентификатор.Единственная проблема заключается в том, как получить объект Universe :)

Как насчет выделения потока, который будет управлять некоторой переменной в узком цикле в течение фиксированного промежутка времени, прежде чем он будет уничтожен. То, что вы получите в итоге, будет зависеть от скорости процессора, загрузки системы и т. Д. Очень просто, но лучше, чем просто srand (time (NULL))) ...

  

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

Я не согласен с советом Джона Д. Кука . Если вы затравите Mersenne Twister со всеми битами, установленными в ноль, кроме одного, он первоначально будет генерировать числа, которые не являются случайными. Генератору требуется много времени, чтобы превратить это состояние во все, что могло бы пройти статистические тесты. Простая установка первых 32 битов генератора в начальное число будет иметь аналогичный эффект. Кроме того, если все состояние установлено в ноль, генератор будет производить бесконечные нули.

Правильно написанный код ГСЧ будет иметь правильно написанный алгоритм заполнения, который принимает, скажем, 64-битное значение и запускает генератор, чтобы он генерировал приличные случайные числа для каждого возможного ввода. Так что, если вы используете надежную библиотеку, подойдет любое семя. Но если вы взламываете собственную реализацию, вам нужно быть осторожным.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top