WikiDer > Аппаратный генератор случайных чисел

эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью от добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Аппаратный генератор случайных чисел» – Новости · газеты · книги · ученый · JSTOR (Июнь 2014 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

Эта Ускоритель TLS компьютерная карта использует аппаратный генератор случайных чисел для генерации криптографические ключи для шифрования данных, передаваемых по компьютерным сетям.

В вычисление, а аппаратный генератор случайных чисел (HRNG) или истинный генератор случайных чисел (TRNG) - это устройство, которое генерирует случайные числа из физический процесс, а не с помощью алгоритм. Такие устройства часто основаны на микроскопических явлениях, которые генерируют низкоуровневые, статистически случайный "шум"сигналы, такие как тепловой шум, то фотоэлектрический эффектс участием Разделитель луча, и другие квант явления. Эти стохастический теоретически процессы совершенно непредсказуемы, и утверждения теории о непредсказуемости подлежат экспериментальный тест. Это контрастирует с парадигмой генерации псевдослучайных чисел, обычно реализуемой в компьютерные программы.

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

Основное приложение для электронных аппаратных генераторов случайных чисел находится в криптография, где они используются для генерации случайных криптографические ключи для безопасной передачи данных. Они широко используются в протоколах шифрования Интернета, таких как Безопасность транспортного уровня (TLS).

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

Хотя кости в основном использовались в азартные игры, и как элементы "рандомизации" в играх (например, ролевые игры), Викторианский ученый Фрэнсис Гальтон описал способ использования игральных костей для явной генерации случайных чисел в научных целях в 1890 году.^[1]

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

Использует

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

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

Криптография

Основное применение аппаратных генераторов случайных чисел - в области шифрование данных, например, для создания случайных криптографические ключи и nonces необходимо для шифрования и подписи данных. Это более безопасная альтернатива генераторы псевдослучайных чисел (PRNG), программы, обычно используемые в компьютерах для генерации «случайных» чисел. ГПСЧ используют детерминированный алгоритм для создания числовых последовательностей. Хотя эти псевдослучайные последовательности проходят статистические шаблоны тестов на случайностьзная алгоритм и условия, используемые для его инициализации, называемые «начальным числом», можно предсказать результат. Поскольку последовательность чисел, производимая ГПСЧ, в принципе предсказуема, данные, зашифрованные с помощью псевдослучайных чисел, потенциально уязвимы для криптоанализ. Аппаратные генераторы случайных чисел создают последовательности чисел, которые, как предполагается, нельзя предсказать, и поэтому обеспечивают максимальную безопасность при использовании для шифрования данных.

Ранняя работа

Одним из первых способов получения случайных чисел был вариант тех же машин, на которых играли кено или выберите лотерея числа. В них использовались смешанные пронумерованные шары для пинг-понга с продувкой воздухом, возможно, в сочетании с механическим перемешиванием, и использовались некоторые методы для извлечения мячей из смесительной камеры (Патент США 4786056 ). В некоторых смыслах этот метод дает разумные результаты, но генерируемые таким образом случайные числа дороги. Этот метод по своей сути медленный и непригоден для большинства вычислительных приложений.

29 апреля 1947 г. RAND Corporation начал генерировать случайные цифры с помощью «электронного колеса рулетки», состоящего из источника импульсов со случайной частотой около 100 000 импульсов в секунду, стробируемых один раз в секунду с импульсом постоянной частоты и подаваемых в пятиразрядный двоичный счетчик. Компания Douglas Aircraft построила оборудование, реализовав предложение Сесила Хастинга (RAND P-113).^[2] для источника шума (скорее всего, хорошо известное поведение миниатюрного газа 6Д4 тиратрон трубка, помещенная в магнитное поле^[3]). Двадцать из 32 возможных значений счетчика были отображены на 10 десятичных разрядов, а остальные 12 значений счетчика были отброшены.^[4]

Отфильтрованные и протестированные результаты длительного прогона с помощью машины RAND были преобразованы в таблицу, которая была опубликована в 1955 году в книге Миллион случайных цифр с 100000 нормальных отклонений. Таблица RAND стала значительным прорывом в доставке случайных чисел, потому что такой большой и тщательно подготовленной таблицы никогда не было. Это был полезный источник для моделирования, моделирования и получения произвольных констант в криптографических алгоритмах, чтобы продемонстрировать, что константы не были выбраны злонамеренно. Блочные шифры Хуфу и Хафр входят в число приложений, использующих таблицу RAND.^[5] Увидеть: Ничего в моем рукаве.

Физические явления со случайными свойствами

Квантовые случайные свойства

Есть два основных источника практических квантово-механический физическая случайность: квантовая механика на атомном или субатомном уровне и тепловой шум (некоторые из них имеют квантово-механическое происхождение). Квантовая механика предсказывает, что определенные физические явления, такие как ядерный распад атомов,^[6] находятся принципиально случайный^[7] и в принципе не может быть предсказан (обсуждение эмпирической проверки квантовой непредсказуемости см. Белл тестовые эксперименты). И поскольку мир существует при температуре выше полный ноль, каждая система имеет случайные изменения в своем состоянии; например, молекулы газов, составляющих воздух, постоянно отталкиваются друг от друга случайным образом (увидеть статистическая механика.) Эта случайность - тоже квантовое явление (увидеть фонон).

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

• Дробовой шум, квантово-механический источник шума в электронных схемах. Простой пример - лампа, светящаяся на фотодиоде. Из-за принцип неопределенностиПоступающие фотоны создают шум в цепи. Сбор шума для использования создает некоторые проблемы, но это особенно простой случайный источник шума. Однако энергия дробового шума не всегда хорошо распределяется по интересующей полосе пропускания. Газовые диодные и тиратронные электронные лампы в поперечном магнитном поле могут генерировать значительную шумовую энергию (10 В или более при нагрузках с высоким импедансом), но имеют очень пиковое распределение энергии и требуют тщательной фильтрации для достижения равномерности в широком спектре.^[8]
• А ядерный распад источник излучения, обнаруженный счетчик Гейгера прикреплен к ПК.
• Фотоны путешествие через полупрозрачное зеркало. В взаимоисключающие события (отражение / передача) обнаруживаются и связываются со значениями битов «0» или «1» соответственно.
• Усиление сигнала, создаваемого на основе обратный транзистор. Эмиттер насыщен электронами, и иногда они будут туннель сквозь запрещенная зона и выйдите через базу. Тогда этот сигнал усиленный через еще несколько транзисторы и результат был передан в Триггер Шмитта.
• Самопроизвольное параметрическое преобразование с понижением частоты приводящий к отбору бинарного фазового состояния в вырожденном оптический параметрический генератор.^[9]
• Колебания в энергия вакуума измеряется через гомодинное обнаружение.^{[10][11][требуется сторонний источник]}

Классические случайные свойства

Тепловые явления обнаружить легче. Они несколько уязвимы для атак из-за снижения температуры системы,^[12] хотя большинство систем перестанут работать при температурах, достаточно низких, чтобы уменьшить шум в два раза (например, ~ 150 K). Некоторые из используемых термических явлений включают:

• Тепловой шум из резистор, усиленный, чтобы обеспечить случайный источник напряжения.^[12]
• Лавинный шум генерируется из лавинный диод, или Пробой стабилитрона шум от обратного смещения Стабилитрон.
• Атмосферный шум, обнаруженный радиоприемником, подключенным к ПК (хотя большая его часть, например шум молнии, не является собственно тепловым шумом, но, скорее всего, хаотичный явление).

В отсутствие квантовых эффектов или теплового шума можно использовать другие явления, которые имеют тенденцию быть случайными, хотя и не так легко описываются законами физики. При тщательном объединении нескольких таких источников (как, например, Алгоритм тысячелистника или Фортуна CSPRNG) можно собрать достаточно энтропии для создания криптографических ключей и nonces, хотя обычно по ограниченным ценам. Преимущество этого подхода в том, что в принципе не требуется специального оборудования. Недостатком является то, что достаточно осведомленный злоумышленник может незаметно модифицировать программное обеспечение или его входные данные, что, возможно, существенно снижает случайность выходных данных. Основной источник случайности, обычно используемый в таких подходах, - это точное время прерывает вызванные механическими устройствами ввода / вывода, такими как клавиатуры и Дисковый привод, различные счетчики системной информации и др.

Этот последний подход следует применять осторожно, и в противном случае он может подвергнуться атаке. Например, прямая безопасность генератора в ядре Linux 2.6.10 может быть нарушена двумя⁶⁴ или 2⁹⁶ временная сложность.^[13]

Дрейф часов

Другое переменное физическое явление, которое легко измерить, - это дрейф часов. Существует несколько способов измерения и использования дрейфа часов в качестве источника случайности.

В Intel Микросхема 82802 Firmware Hub (FWH) с аппаратным ГСЧ^[14] с использованием двух свободно работающих осцилляторов, быстрого и медленного. Источник теплового шума (не синфазный шум от двух диодов) используется для модуляции частоты медленного генератора, который затем запускает измерение быстрого генератора. Затем этот вывод очищается с помощью фон Нейман шаг декорреляции типа (см. ниже). Скорость вывода этого устройства несколько меньше 100 000 бит / с. Этот чип был дополнительным компонентом семейства наборов микросхем 840, который поддерживал более раннюю шину Intel. В современные ПК он не входит.

Все ЧЕРЕЗ C3 микропроцессоры включают аппаратный ГСЧ в микросхему процессора с 2003 года. Вместо использования теплового шума необработанные биты генерируются с помощью четырех свободно работающих генераторов, которые предназначены для работы с разной скоростью. Выход двух осцилляторов подвергается операции XOR для управления смещением третьего генератора, выход которого синхронизирует выход четвертого генератора для получения необработанного бита. Незначительные изменения температуры, характеристик кремния и местных электрических условий вызывают постоянные изменения скорости генератора и, таким образом, создают энтропию необработанных битов. Для дополнительной гарантии случайности на каждом кристалле фактически есть два таких RNG, каждый из которых расположен в разных средах и вращается на кремнии. Конечный результат - смесь этих двух генераторов. Скорость вывода необработанных данных составляет от десятков до сотен мегабит в секунду, а скорость отбеливания - несколько мегабит в секунду. Программное обеспечение пользователя может получить доступ к сгенерированному случайному потоку битов с помощью новых непривилегированных инструкций машинного языка.

Программная реализация родственной идеи на обычном оборудовании включена в CryptoLib,^[15] библиотека криптографических подпрограмм. Алгоритм называется правда и. Большинство современных компьютеров имеют два кварцевых генератора: один для часов реального времени, а другой - для основных часов ЦП; truerand использует этот факт. Он использует службу операционной системы, которая устанавливает будильник по часам реального времени. Одна подпрограмма устанавливает этот будильник так, чтобы он срабатывал за один такт часов (обычно 1/60 секунды). Затем другой входит в цикл while, ожидая срабатывания сигнала тревоги. Поскольку аварийный сигнал не всегда срабатывает ровно в один тик, младшие значащие биты счетчика итераций цикла между установкой аварийного сигнала и его триггером будут варьироваться случайным образом, что, возможно, будет достаточно для некоторых применений. Truerand не требует дополнительного оборудования, но в многозадачной системе следует проявлять большую осторожность, чтобы избежать нерандомизирующего вмешательства со стороны других процессов (например, при приостановке процесса цикла подсчета, когда планировщик операционной системы запускает и останавливает различные процессы. ).

В RDRAND opcode будет возвращать значения из встроенного аппаратного генератора случайных чисел. Он присутствует в Intel Ivy Bridge процессоров и AMD64 с 2015 года.^[16]

Работа с предвзятостью

Поток битов от таких систем склонен к смещению, с преобладанием единиц или нулей.^{[нужна цитата]} Есть два подхода к устранению предвзятости и других артефактов. Первый - спроектировать ГСЧ, чтобы минимизировать смещение, присущее работе генератора. Один из методов исправления этого - обратная связь сгенерированного битового потока, отфильтрованного фильтром нижних частот, для регулировки смещения генератора. Посредством Центральная предельная теорема, цикл обратной связи будет хорошо отрегулирован »почти все время'. Этот метод часто используют сверхбыстрые генераторы случайных чисел. Даже в этом случае полученные числа обычно несколько необъективны.

Программное отбеливание

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

Джон фон Нейман изобрел простой алгоритм, чтобы исправить простое смещение и уменьшить корреляцию. Он одновременно рассматривает два бита (неперекрывающиеся), выполняя одно из трех действий: когда два последовательных бита равны, они отбрасываются; последовательность 1,0 становится 1; и последовательность 0,1 становится нулем. Таким образом, он представляет собой падающий край с 1 и поднимающийся край с 0. Это устраняет простую систематическую ошибку и легко реализуется в виде компьютерной программы или цифровой логики. Этот метод работает независимо от того, как были созданы биты. Однако он не может гарантировать случайность вывода. Что он может сделать (со значительным количеством отброшенных битов), так это преобразовать смещенный случайный поток битов в несмещенный.

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

Связанный метод, который уменьшает смещение в почти случайном потоке битов, состоит в том, чтобы взять два или более некоррелированных почти случайных потока битов, и Эксклюзивный или их вместе. Пусть вероятность того, что поток битов создаст 0, равна 1/2 +е, где −1/2 ≤е ≤ 1/2. потом е это смещение потока битов. Если два некоррелированных битовых потока со смещением е исключают или объединяют, то смещение результата будет равно 2е². Это может повториться с большим количеством битовых потоков (см. Также Лемма о накоплении).

В некоторых конструкциях применяется криптографическая хэш-функции такие как MD5, SHA-1, или РИПЭМД-160 или даже CRC для всего или части битового потока, а затем использовать вывод как случайный битовый поток. Это привлекательно, отчасти потому, что это относительно быстро.

Многие физические явления могут использоваться для генерации битов, которые сильно смещены, но каждый бит не зависит от других. Счетчик Гейгера (с временем выборки больше, чем время восстановления трубки) или полупрозрачный зеркальный фотонный детектор генерируют потоки битов. которые в основном равны «0» (без звука или передачи) с периодической «1» (щелчок или отражение). Если каждый бит не зависит от других, стратегия фон Неймана генерирует один случайный несмещенный выходной бит для каждого из редких «1» "биты в таком сильно смещенном битовом потоке. Методы отбеливания, такие как Расширенная многоуровневая стратегия (AMLS)^[17] может извлекать больше выходных битов - таких же случайных и несмещенных выходных битов - из такого сильно смещенного потока битов.^[18]

ГПСЧ с периодически обновляемым случайным ключом

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

Использование наблюдаемых событий

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

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

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

• Когда запрашиваются случайные биты, верните это количество битов, полученных из пула энтропии (например, с помощью криптографической хеш-функции), и уменьшите оценку количества случайных битов, оставшихся в пуле. Если доступно недостаточно неизвестных бит, подождите, пока не станет доступно достаточно. Это верхний уровень дизайна "/ dev / случайный"устройство в Linux, написанное Теодор Ц'О и используется во многих других Unix-подобных операционных системах.Он обеспечивает высококачественные случайные числа, если оценки случайности входных данных достаточно осторожны. Устройство Linux «/ dev / urandom» представляет собой простую модификацию, которая не учитывает оценки случайности ввода и, следовательно, с меньшей вероятностью будет иметь высокую энтропию в результате.
• Поддерживать потоковый шифр с ключом и вектор инициализации (IV), полученный из пула энтропии. Когда будет собрано достаточно бит энтропии, замените ключ и IV новыми случайными значениями и уменьшите оценочную энтропию, оставшуюся в пуле. Это подход, принятый тысячелистник библиотека. Он обеспечивает сопротивление некоторым атакам и сохраняет труднодоступную энтропию.

(Де) централизованные системы

Истинный генератор случайных чисел может быть (де) центральной службой. Одним из примеров централизованной системы, в которой можно получить случайное число, является служба маяка случайности от Национальный институт стандартов и технологий. Платформа Cardano использует участников их децентрализованных доказательство ставки протокол для генерации случайных чисел.^[19]

Проблемы

Очень легко неправильно сконструировать аппаратные или программные устройства, которые пытаются генерировать случайные числа. Кроме того, большинство из них «ломаются» незаметно, часто по мере ухудшения качества производя все меньше случайных чисел. Физическим примером может служить быстро уменьшающаяся радиоактивность детекторов дыма, упомянутых ранее, если бы этот источник использовался напрямую. Режимы отказа в таких устройствах многочисленны, они сложны, медленны и трудно обнаруживаются. Методы, сочетающие несколько источников энтропии, более надежны.

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

Атаки

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

Оценка энтропии

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

Тест производительности

Аппаратные генераторы случайных чисел следует постоянно контролировать на предмет правильной работы. RFC 4086, FIPS Паб 140-2 и NIST Специальная публикация 800-90b^[20] включите тесты, которые можно использовать для этого. Также см. Документацию к библиотеке программного обеспечения криптографии Новой Зеландии. cryptlib.

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

Смотрите также

• AN / CYZ-9
• Белл тестовые эксперименты
• / dev / случайный
• ЭРНИ
• Список генераторов случайных чисел
• Лотерея
• Экстрактор случайности
• RDRAND
• Модуль доверенной платформы

использованная литература

Общие ссылки

внешние ссылки

• RFC 4086 по рекомендациям случайности для безопасности (заменяет более ранний RFC 1750), IETF.
• Генератор случайных чисел Intel (PDF), Intel.
• Ключ энтропии, Simtec, использует полупроводниковые переходы P-N с обратным смещением с достаточно высоким напряжением, чтобы приблизить их к пробою, но не выйти за его пределы, чтобы создать шум.
• Скачать случайные числа, случайный сервер, использует аппаратный генератор случайных чисел TRNG9803.
• ProtegoST SG100, ProtegoST, «Аппаратный генератор случайных чисел» на основе квантовой физики источника случайных чисел на стабилитроне ».