Войти
Этот ускоритель TLS компьютерная карта использует аппаратное обеспечение генератор случайных чисел для генерации криптографических ключей для шифрования данных, передаваемых по компьютерным сетям. В вычислениях, аппаратный генератор случайных чисел (HRNG ) или истинный генератор случайных чисел (TRNG ) - это устройство, которое генерирует случайные числа из физического процесса, а не с помощью средства алгоритма . Такие устройства часто основаны на микроскопических явлениях, которые генерируют низкоуровневые статистически случайные «шум » сигналы, такие как тепловой шум, фотоэлектрический эффект., включая светоделитель и другие квантовые явления. Эти стохастические процессы теоретически полностью непредсказуемы, и утверждения теории о непредсказуемости подлежат экспериментальной проверке. Это контрастирует с парадигмой генерации псевдослучайных чисел, обычно реализуемой в компьютерных программах.
Аппаратный генератор случайных чисел обычно состоит из преобразователя для преобразования некоторых аспектов физических явлений в электрический сигнал, усилитель и другие электронные схемы для увеличения амплитуды случайных колебаний до измеримого уровня, а также некоторый тип аналого-цифрового преобразователя для преобразования выходного сигнала в цифровое число, часто простая двоичная цифра 0 или 1. Путем многократной выборки случайно изменяющегося сигнала получается серия случайных чисел.
Основное приложение для генераторов случайных чисел электронного оборудования находится в криптографии, где они используются для генерации случайных криптографических ключей для безопасной передачи данных. Они широко используются в протоколах Интернет-шифрования, таких как Transport Layer Security (TLS).
Генераторы случайных чисел также могут быть построены из "случайных" макроскопических процессов с использованием таких устройств, как подбрасывание монеты, игральные кости, колеса рулетки и лотерейные автоматы. Наличие непредсказуемости в этих явлениях может быть оправдано теорией неустойчивых динамических систем и теорией хаоса. Несмотря на то, что макроскопические процессы детерминированы в рамках механики Ньютона, производительность хорошо спроектированного устройства, такого как колесо рулетки, невозможно предсказать на практике, потому что это зависит от чувствительных микродеталей исходного . условия каждого использования.
Хотя кости в основном использовались в азартных играх, а также в качестве элементов «рандомизации» в играх (например, ролевые игры ), викторианские ученый Фрэнсис Гальтон описал способ использования игральных костей для явной генерации случайных чисел в научных целях в 1890 году.
Аппаратные генераторы случайных чисел обычно производят только ограниченное количество случайных битов в секунду. Чтобы увеличить доступную скорость передачи данных, они часто используются для генерации «seed » для более быстрого криптографически безопасного генератора псевдослучайных чисел, который затем генерирует псевдослучайное выходная последовательность с гораздо более высокой скоростью передачи данных.
Первыми были непредсказуемые случайные числа исследованы в контексте азартных игр, и многие устройства рандомизации, такие как игральные кости, тасование игральных карт и рулетка, были впервые разработаны для такого использования. Справедливо произведенные случайные числа имеют жизненно важное значение для электронных азартных игр, и способы их создания иногда регулируются правительственными комиссиями по азартным играм.
Случайные числа также используются для целей, не связанных с азартными играми, как там, где их использование математически важно, например, выборка для опросов общественного мнения, так и в ситуациях, когда справедливость приближается к рандомизации, например, лотереи призывников и выбор присяжных.
Основное применение аппаратных генераторов случайных чисел - в области шифрования данных, например, для создания случайных криптографических ключей и одноразовых номеров, необходимых для шифрования и подписи данных. Они являются более безопасной альтернативой генераторам псевдослучайных чисел (ГПСЧ), программам, обычно используемым в компьютерах для генерации «случайных» чисел. ГПСЧ используют детерминированный алгоритм для создания числовых последовательностей. Хотя эти псевдослучайные последовательности проходят тесты статистических шаблонов на случайность, зная алгоритм и условия, используемые для его инициализации, называемые «начальным числом», выходные данные можно предсказать. Поскольку последовательность чисел, производимая ГПСЧ, в принципе предсказуема, данные, зашифрованные с помощью псевдослучайных чисел, потенциально уязвимы для криптоанализа. Аппаратные генераторы случайных чисел создают последовательности чисел, которые, как предполагается, нельзя предсказать, и поэтому обеспечивают максимальную безопасность при использовании для шифрования данных.
Одним из первых способов получения случайных чисел была разновидность тех же машин, на которых играли кено или выбирали лотерейные числа. Они включали смешанные пронумерованные шары для пинг-понга с продуваемым воздухом, возможно, в сочетании с механическим перемешиванием, и использовали некоторый метод для извлечения мячей из смесительной камеры (Патент США 4786056 ). В некоторых смыслах этот метод дает разумные результаты, но генерируемые таким образом случайные числа дороги. Этот метод по своей сути медленный и непригоден для большинства вычислительных приложений.
29 апреля 1947 года RAND Corporation начала генерировать случайные цифры с помощью «электронного колеса рулетки», состоящего из источника случайных частотных импульсов примерно 100 000 импульсов в секунду, стробируемых один раз в секунду с помощью импульс постоянной частоты и подается на пятиразрядный двоичный счетчик. Компания Douglas Aircraft построила оборудование, реализовав предложение Сесила Хастинга (RAND P-113) для источника шума (скорее всего, это хорошо известное поведение миниатюрной газовой трубки тиратрон 6D4 при помещении в магнитное поле). Двадцать из 32 возможных значений счетчика были отображены на 10 десятичных цифр, а остальные 12 значений счетчика были отброшены.
Результаты длительного прогона с машины RAND, отфильтрованные и проверенные, были преобразованы в таблицу, который был опубликован в 1955 году в книге Миллион случайных цифр со 100 000 нормальных отклонений. Таблица RAND стала значительным прорывом в доставке случайных чисел, потому что такой большой и тщательно подготовленной таблицы никогда не было. Это был полезный источник для моделирования, моделирования и получения произвольных констант в криптографических алгоритмах, чтобы продемонстрировать, что константы не были выбраны злонамеренно. Блочные шифры Khufu и Khafre относятся к числу приложений, которые используют таблицу RAND. См.: В моем рукаве нет цифр.
Есть два фундаментальных источника практической квантовой механики физической случайности : квантовая механика на атомном или субатомном уровне и тепловой шум (некоторые из которых имеют квантово-механическое происхождение). Квантовая механика предсказывает, что определенные физические явления, такие как ядерный распад атомов, являются фундаментально случайными и в принципе не могут быть предсказаны (для обсуждения эмпирической проверки квантовой непредсказуемости, см. Тестовые эксперименты Белла ). И поскольку мир существует при температуре выше абсолютного нуля, каждая система имеет некоторые случайные вариации в своем состоянии; например, молекулы газов, составляющих воздух, постоянно отражаются друг от друга случайным образом (см. статистическая механика.) Эта случайность также является квантовым явлением (см. фонон ).
Поскольку исход квантово-механических событий невозможно предсказать даже в принципе, они являются «золотым стандартом » для генерации случайных чисел. Некоторые квантовые явления, используемые для генерации случайных чисел, включают:
Тепловые явления легче обнаружить. Они в некоторой степени уязвимы для атак из-за снижения температуры системы, хотя большинство систем перестанут работать при температурах, достаточно низких, чтобы уменьшить шум в два раза (например, ~ 150 K). Некоторые из используемых тепловых явлений включают:
В отсутствие квантовых эффектов или теплового шума другие явления, которые имеют тенденцию быть случайными, хотя и трудно охарактеризовать по законам физики можно использовать. Когда несколько таких источников тщательно объединяются (как, например, алгоритм Ярроу или Fortuna CSPRNGs ), можно собрать достаточно энтропии для создания криптографических ключи и одноразовые номера, хотя обычно с ограниченными частотами. Преимущество этого подхода в том, что в принципе не требуется специального оборудования. Недостатком является то, что достаточно осведомленный злоумышленник может незаметно модифицировать программное обеспечение или его входные данные, тем самым уменьшая случайность выходных данных, возможно, существенно. Основным источником случайности, обычно используемым в таких подходах, является точная синхронизация прерываний, вызванных механическими устройствами ввода / вывода, такими как клавиатуры и дисковые накопители, различные счетчики системной информации и т. Д..
Этот последний подход следует применять осторожно, и в противном случае он может подвергнуться атаке. Например, прямая безопасность генератора в ядре Linux 2.6.10 может быть нарушена с временной сложностью 2 или 2.
Еще одно переменное физическое явление, которое легко измерить, это часы дрейфуют. Есть несколько способов измерить и использовать дрейф часов как источник случайности.
Микросхема Intel 82802 Firmware Hub (FWH) включает аппаратный ГСЧ, использующий два свободно работающих генератора, один быстрый и один медленный. Источник теплового шума (не синфазный шум от двух диодов) используется для модуляции частоты медленного генератора, который затем запускает измерение быстрого генератора. Затем этот вывод подвергается сглаживанию с использованием шага декорреляции типа фон Неймана (см. Ниже). Скорость вывода этого устройства несколько меньше 100 000 бит / с. Этот чип был дополнительным компонентом семейства наборов микросхем 840, который поддерживал более раннюю шину Intel. В современные ПК он не входит.
Все микропроцессоры VIA C3 имеют аппаратный ГСЧ на микросхеме процессора с 2003 года. Вместо использования теплового шума необработанные биты генерируются с помощью четырех автономных генераторов, которые предназначены для работы на разных ставки. Выход двух осцилляторов подвергается операции XOR для управления смещением третьего генератора, выход которого синхронизирует выход четвертого генератора для получения необработанного бита. Незначительные изменения температуры, характеристик кремния и местных электрических условий вызывают постоянные изменения скорости генератора и, таким образом, создают энтропию необработанных битов. Для дополнительной гарантии случайности на каждом кристалле фактически есть два таких RNG, каждый из которых расположен в разных средах и вращается на кремнии. Окончательный результат - смесь этих двух генераторов. Скорость вывода необработанных данных составляет от десятков до сотен мегабит в секунду, а скорость отбеливания - несколько мегабит в секунду. Программное обеспечение пользователя может получить доступ к сгенерированному случайному потоку битов с помощью новых непривилегированных инструкций машинного языка.
Программная реализация связанной идеи на обычном оборудовании включена в CryptoLib, библиотеку криптографических подпрограмм. Алгоритм называется. Большинство современных компьютеров имеют два кварцевых генератора: один для часов реального времени, а другой - для основных часов ЦП; truerand использует этот факт. Он использует службу операционной системы, которая устанавливает будильник по часам реального времени. Одна подпрограмма устанавливает этот будильник так, чтобы он срабатывал за один такт часов (обычно 1/60 секунды). Затем другой входит в цикл while, ожидая срабатывания сигнала тревоги. Поскольку аварийный сигнал не всегда срабатывает ровно в один тик, младшие значащие биты счетчика итераций цикла между установкой аварийного сигнала и его триггером будут варьироваться случайным образом, что, возможно, будет достаточно для некоторых применений. Truerand не требует дополнительного оборудования, но в многозадачной системе следует проявлять большую осторожность, чтобы избежать нерандомизирующего вмешательства со стороны других процессов (например, при приостановке процесса цикла подсчета, когда планировщик операционной системы запускает и останавливает различные процессы.).
Код операции RDRAND возвращает значения из встроенного аппаратного генератора случайных чисел. Он присутствует в процессорах Intel Ivy Bridge и AMD64 с 2015 года.
Битовый поток из таких систем склонен к предвзятости, либо Преобладают единицы или нули. Есть два подхода к устранению предвзятости и других артефактов. Первый - спроектировать ГСЧ, чтобы минимизировать смещение, присущее работе генератора. Один из методов исправления этого - обратная связь сгенерированного битового потока, отфильтрованного фильтром нижних частот, для регулировки смещения генератора. Согласно центральной предельной теореме, контур обратной связи будет иметь тенденцию хорошо настраиваться «почти все время ». Этот метод часто используют сверхбыстрые генераторы случайных чисел. Даже в этом случае полученные числа обычно несколько необъективны.
Второй подход к преодолению предвзятости - уменьшить ее после генерации (программно или аппаратно). Существует несколько методов уменьшения смещения и корреляции, часто называемых алгоритмами «отбеливания », по аналогии с соответствующей проблемой создания белого шума из коррелированного сигнала.
Джон фон Нейман изобрел простой алгоритм, чтобы исправить простую систематическую ошибку и уменьшить корреляцию. Он рассматривает два бита одновременно (неперекрывающиеся), выполняя одно из трех действий: когда два последовательных бита равны, они отбрасываются; последовательность 1,0 становится 1; и последовательность 0,1 становится нулем. Таким образом, он представляет собой передний фронт с 1 и передний фронт с 0. Это устраняет простое смещение и легко реализуется в виде компьютерной программы или в цифровой логике. Этот метод работает независимо от того, как были созданы биты. Однако он не может гарантировать случайность вывода. Что он может сделать (со значительным количеством отброшенных битов), так это преобразовать смещенный случайный поток битов в несмещенный.
Другим методом улучшения почти случайного потока битов является исключающее ИЛИ битовый поток с выходом высококачественного криптографически безопасного генератора псевдослучайных чисел, такого как Блюм Блюм Шуб или сильный потоковый шифр. Это может улучшить декорреляцию и смещение цифр при небольших затратах; это можно сделать с помощью оборудования, такого как ПЛИС, что быстрее, чем с помощью программного обеспечения.
Связанный метод, который уменьшает смещение в потоке битов, близком к случайному, состоит в том, чтобы брать два или более некоррелированных потока битов, близких к случайному, и исключающих или их вместе. Пусть вероятность того, что поток битов создаст 0, равна 1/2 + e, где -1/2 ≤ e ≤ 1/2. Тогда e - это смещение потока битов. Если два некоррелированных потока битов со смещением e объединяются по принципу «исключающее или единое», то смещение результата будет равно 2e. Это можно повторить с другими битовыми потоками (см. Также лемму о накоплении данных ).
В некоторых проектах применяются криптографические хэш-функции, такие как MD5, SHA-1 или RIPEMD-160 или даже функцию CRC для всего или части битового потока, а затем использовать вывод как случайный битовый поток. Это привлекательно, отчасти потому, что это относительно быстро.
Многие физические явления могут быть использованы для генерации битов с сильным смещением, но каждый бит независим от других. Счетчик Гейгера (с временем выборки больше, чем время восстановления трубки) или полупрозрачный зеркальный фотонный детектор генерируют потоки битов, которые в основном равны «0» (бесшумный или пропускающий) со случайной «1» (щелчок или отражение). Если каждый бит независим от других, стратегия фон Неймана генерирует один случайный несмещенный выходной бит для каждого из редких битов «1» в таком сильно смещенном потоке битов. Методы отбеливания, такие как Расширенная многоуровневая стратегия (AMLS), могут извлекать больше выходных битов - выходных битов, которые столь же случайны и несмещены - из такого сильно смещенного потока битов.
В других конструкциях используются так называемые истинные случайные биты в качестве ключа для высококачественного алгоритма блочного шифра , принимая зашифрованный вывод как случайный поток битов. Однако в этих случаях следует проявлять осторожность, чтобы выбрать соответствующий режим блока. В некоторых реализациях PRNG запускается для ограниченного числа цифр, в то время как устройство генерирования оборудования создает новое начальное число.
Программные инженеры без истинных генераторов случайных чисел часто пытаются разработать их, измеряя физические события, доступные программному обеспечению. Примером может служить измерение времени между нажатиями клавиш пользователем, а затем получение младшего бита (или двух или трех) счетчика как случайной цифры. Аналогичный подход измеряет планирование задач, количество обращений к сети, время поиска головки на диске и другие внутренние события. Один проект Microsoft включает очень длинный список таких внутренних значений, форму криптографически безопасного генератора псевдослучайных чисел. Лавовые лампы также использовались в качестве физических устройств, подлежащих наблюдению, как в системе Lavarand.
Этот метод опасен, когда он использует управляемые компьютером события, потому что умный злоумышленник может предсказать криптографический ключ, управляя внешними событиями. Это также рискованно, потому что предполагаемое событие, генерируемое пользователем (например, нажатие клавиш), может быть подделано достаточно изобретательным злоумышленником, позволяющим контролировать «случайные значения», используемые криптографией.
Однако при достаточной осторожности можно разработать систему, которая производит криптографически безопасные случайные числа из источников случайности, доступных в современном компьютере. Базовая схема состоит в том, чтобы поддерживать «пул энтропии» случайных битов, которые считаются неизвестными злоумышленнику. Новая случайность добавляется всякий раз, когда это возможно (например, когда пользователь нажимает клавишу), и сохраняется оценка количества битов в пуле, которая не может быть известна злоумышленнику. Некоторые из используемых стратегий включают:
Настоящий генератор случайных чисел может быть (де) центральной службой. Одним из примеров централизованной системы, в которой может быть получено случайное число, является служба маяка случайности от Национального института стандартов и технологий. Платформа Cardano использует участников своего децентрализованного протокола Proof-of-Stake для генерации случайных чисел.
Очень легко неправильно сконструировать аппаратные или программные устройства, которые попытаться сгенерировать случайные числа. Кроме того, большинство из них «ломаются» незаметно, по мере ухудшения часто производя все меньше случайных чисел. Физическим примером может служить быстро уменьшающаяся радиоактивность детекторов дыма, упомянутых ранее, если бы этот источник использовался напрямую. Режимы отказа в таких устройствах многочисленны, они сложны, медленны и трудно обнаруживаются. Методы, сочетающие несколько источников энтропии, более надежны.
Поскольку многие источники энтропии часто бывают довольно хрупкими и тихо выходят из строя, статистические тесты их выходных данных следует выполнять непрерывно. Многие, но не все, такие устройства включают такие тесты в программное обеспечение, которое считывает данные с устройства.
Как и в случае с другими компонентами криптографической системы, программный генератор случайных чисел должен быть разработан так, чтобы противостоять определенным атакам. Защититься от этих атак без аппаратного источника энтропии сложно.
Существуют математические методы для оценки энтропии последовательности символов. Ни один из них не является настолько надежным, чтобы на его оценки можно было полностью положиться; всегда есть предположения, которые бывает очень трудно подтвердить. Они полезны для определения, например, достаточности энтропии в исходном пуле, но они, как правило, не могут отличить истинный случайный источник от псевдослучайного генератора. Этой проблемы можно избежать путем консервативного использования аппаратных источников энтропии.
Аппаратные генераторы случайных чисел должны постоянно контролироваться на предмет правильной работы. RFC 4086, FIPS Pub 140-2 и NIST Special Publication 800-90b включают тесты, которые можно использовать для этого. Также см. Документацию к новозеландской библиотеке криптографического программного обеспечения cryptlib.
Поскольку многие практические проекты полагаются на аппаратный источник в качестве входных данных, будет полезно хотя бы проверить, что источник все еще работает. Статистические тесты часто могут обнаружить отказ источника шума, например, радиостанции, ведущей передачу по каналу, который считается пустым. Перед тем, как пропустить через «отбеливатель», необходимо отбирать пробы с выхода генератора шума для тестирования. Некоторые дизайны отбеливателей могут пройти статистические тесты без случайного ввода. Хотя обнаружение большого отклонения от совершенства будет признаком того, что истинный источник случайного шума ухудшился, небольшие отклонения являются нормальным явлением и могут указывать на правильную работу. Корреляция смещения на входах для конструкции генератора с другими параметрами (например, внутренней температурой, напряжением на шине) может быть дополнительно полезна в качестве дополнительной проверки. К сожалению, с доступными в настоящее время (и предполагаемыми) тестами прохождения таких тестов недостаточно, чтобы быть уверенным, что выходные последовательности случайны. Тщательно подобранный дизайн, проверка того, что изготовленное устройство реализует этот дизайн, и постоянная физическая безопасность для защиты от взлома - все это может потребоваться в дополнение к тестированию для высокоэффективного использования.
использует полупроводниковые PN переходы с обратным смещением с достаточно высоким напряжением, чтобы приблизить их для, но не более, поломки с целью создания шума.
использует аппаратный генератор случайных чисел TRNG9803.
