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

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

Будет использовать несколько источников (например, время + текущее время поиска жесткого диска [мы здесь фантастические]) вместе создают "более случайное" число, чем один источник? Каковы логические пределы количества источников? Сколько на самом деле достаточно? Является ли время выбранным просто потому, что это удобно?

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

Ответ 1

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

Мои избранные:

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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

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

Ответ 7

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

Но я не настолько впечатлен его выборами; MAC-адрес NIC никогда не изменяется (хотя он уникален для всех остальных), а 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 бит HOPEFULLY случайных (достаточно) энтропийных данных, чтобы засеять мой Mersenne Twister. Я использую вышеуказанное, чтобы заполнить начало MT Array (624 32-битных целых числа), а затем инициализировать оставшуюся часть этого массива с помощью MT-кода автора. Кроме того, я мог бы использовать другую хэш-функцию (например, SHA384, SHA512), но мне понадобился бы другой буфер массива размера (очевидно).

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

Я бы с удовольствием прочитал отзывы об этом. Критика более чем приветствуется. Я буду защищать мое использование файлов /proc, как указано выше, потому что они постоянно меняются (особенно файлы /proc/self/*, а TSC всегда дает другое значение (наносекундное [или лучшее] разрешение, IIRC). Diehard tests об этом (до нескольких сотен миллиардов), и, похоже, он проходит с полетом цвета, но это, вероятно, больше свидетельствует о прочности Mersenne Twister как PRNG, а не о том, как я его посеял.

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

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

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

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

Ответ 11

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

Ответ 12

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

Ответ 13

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

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

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

Ответ 14

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

Время
температура процессора
скорость вентилятора
cpu voltage
Я не помню больше:)

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

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

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

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

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

Ответ 15

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