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

Аппаратный генератор истинных случайных чисел с USB-подключением

В вычислительной технике используются аппаратный генератор случайных чисел ( HRNG ), генератор истинных случайных чисел ( TRNG ), недетерминированный генератор случайных битов ( NRBG ), или физический генератор случайных чисел это устройство, которое генерирует случайные числа из физического процесса, способного производить энтропию (другими словами, устройство всегда имеет доступ к физическому источнику энтропии) ), в отличие от генератора псевдослучайных чисел (PRNG, также известного как «детерминированный генератор случайных битов», DRBG), который использует детерминированный алгоритм. и нефизические недетерминированные генераторы случайных битов , которые не включают в себя аппаратное обеспечение, предназначенное для генерации энтропии.

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

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

• источник шума , который реализует физический процесс, производящий энтропию. Обычно этот процесс является аналоговым , поэтому дигитайзер ; для преобразования выходного сигнала аналогового источника в двоичное представление используется
• кондиционер ) , ( экстрактор случайности улучшающий качество случайных битов;
• тесты на здоровье . TRNG в основном используются в криптографических алгоритмах, которые полностью ломаются, если случайные числа имеют низкую энтропию, поэтому обычно включаются функции тестирования.

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

Использование

См. Также: Применение случайности.

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

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

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

1. прямая секретность гарантирует, что знание прошлых выходных данных и внутреннего состояния устройства не позволит злоумышленнику предсказать будущие данные;
2. обратная секретность защищает «противоположное направление»: знание выходного и внутреннего состояния в будущем не должно разглашать предыдущие данные.

Типичный способ выполнения этих требований — использование TRNG для создания криптографически безопасного генератора псевдослучайных чисел .

История

Физические устройства использовались для генерации случайных чисел на протяжении тысячелетий, в первую очередь для азартных игр . В частности, игральные кости известны уже более 5000 лет (их можно найти в современных Ираке и Иране). монета (таким образом производящая случайный бит) датируется, по крайней мере, временами Древнего Рима .

Первое задокументированное использование физического генератора случайных чисел в научных целях было осуществлено Фрэнсисом Гальтоном (1890 г.). Он разработал способ выборки распределения вероятностей , используя обычные игральные кости. Помимо верхней цифры, Гальтон также смотрел на ближайшую к нему грань игральной кости, создавая таким образом 6*4 = 24 исхода (около 4,6 бит случайности).

Кендалл и Бабингтон-Смит (1938) использовал быстро вращающийся 10-секторный диск, который освещался периодическими вспышками света. Отбор проб проводил человек, который написал номер под лучом света на блокноте. Устройство использовалось для создания таблицы случайных чисел из 100 000 цифр (в то время такие таблицы использовались для статистических экспериментов, таких как сегодня PRNG).

29 апреля 1947 года корпорация RAND начала генерировать случайные цифры с помощью «электронного колеса рулетки», состоящего из источника импульсов случайной частоты с частотой около 100 000 импульсов в секунду, стробируемого один раз в секунду с импульсом постоянной частоты и подаваемого в пятибитный двоичный код. прилавок. Компания Douglas Aircraft построила оборудование, реализовав предложение Сесила Гастингса (RAND P-113). для источника шума (скорее всего, известное поведение миниатюрной газовой тиратронной трубки 6Д4 при помещении ее в магнитное поле ). Двадцать из 32 возможных значений счетчика были сопоставлены с 10 десятичными цифрами, а остальные 12 значений счетчика были отброшены. Результаты длительного прогона машины RAND, отфильтрованные и протестированные, были преобразованы в таблицу, которая первоначально существовала только в виде колоды перфокарт , но позже была опубликована в 1955 году в виде книги, 50 строк по 50 цифр на каждой странице. ( Миллион случайных цифр со 100 000 нормальных отклонений ). Таблица RAND стала значительным прорывом в предоставлении случайных чисел, поскольку такая большая и тщательно подготовленная таблица никогда раньше не была доступна. Это был полезный источник для симуляций, моделирования и получения произвольных констант в криптографических алгоритмах, чтобы продемонстрировать, что константы не были выбраны злонамеренно (« ничего в моем рукаве »).

С начала 1950-х годов исследования TRNG были очень активными: к 2017 году были опубликованы тысячи исследовательских работ и выдано около 2000 патентов.

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

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

• использование общедоступного недорогого кремниевого процесса;
• эксклюзивное использование методов цифрового дизайна. Это упрощает интеграцию системы на кристалле и позволяет использовать FPGA ;
• компактная конструкция с низким энергопотреблением. Это препятствует использованию аналоговых компонентов (например, усилителей );
• математическое обоснование механизмов сбора энтропии.

Стипчевич и Коч в 2014 году классифицировали физические явления, используемые для реализации TRNG, на четыре группы:

• электрический шум;
• автономные генераторы;
• хаос;
• квантовые эффекты.

ГСЧ на основе электрического шума

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

• Шум Джонсона – Найквиста («тепловой шум»);
• Зенеровский шум ;
• лавинный обвал .

Недостатками использования источников шума для конструкции ГСЧ являются:

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

ГСЧ на основе хаоса

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

ГСЧ на основе автономных генераторов

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

Квантовый ГСЧ

Технология квантовой генерации случайных чисел хорошо зарекомендовала себя благодаря 8 коммерческим продуктам квантового генератора случайных чисел ( QRNG ), предложенным до 2017 года.

Эрреро-Коллантес и Гарсия-Эскартен называют следующие случайные процессы «квантовыми»:

• Исторически ядерный распад был самым ранним квантовым методом, использовавшимся с 1960-х годов, благодаря своей популярности благодаря наличию счетчиков Гейгера и калиброванных источников излучения . Сбор энтропии осуществлялся с использованием счетчика событий, выборка которого производилась периодически, или счетчика времени, выборка которого производилась во время события. Подобные конструкции использовались в 1950-х годах для генерации случайного шума в аналоговых компьютерах . Основными недостатками были проблемы радиационной безопасности , низкая скорость передачи данных и неравномерное распределение ;
• Дробовой шум , источник квантово-механического шума, обнаруженный в электронных схемах, хотя технически и является квантовым эффектом, его трудно изолировать от теплового шума , поэтому, за некоторыми исключениями, источники шума, использующие его, являются лишь частично квантовыми и обычно классифицируются как «классические». ;
• квантовая оптика :
  • генератор разветвленного пути с использованием светоделителя, так что фотон из однофотонного источника случайным образом выбирает один из двух путей и воспринимается одним из двух однофотонных детекторов, таким образом генерируя случайный бит;
  • генератор времени прибытия и генератор счета фотонов используют источник слабых фотонов, энтропия которого собирается так же, как и в случае радиоактивного распада;
  • генераторы ослабленных импульсов – это обобщение (упрощение аппаратуры) вышеперечисленных методов, позволяющее одновременно находиться в системе более одного фотона;
  • вакуумных флуктуаций генераторы используют лазерное гомодинное обнаружение для исследования изменений состояния вакуума ;
  • Генераторы лазерного фазового шума используют фазовый шум на выходе лазера с одной пространственной модой , который преобразуется в амплитуду с помощью несбалансированного интерферометра Маха-Цендера . Шум улавливается фотодетектором;
  • усиленного спонтанного излучения генераторы используют спонтанное излучение света, присутствующее в оптических усилителях, в качестве источника шума;
  • комбинационного рассеяния света Генераторы извлекают энтропию из взаимодействия фотонов с твердотельными материалами;
  • оптических параметрических генераторов Генератор использует спонтанное параметрическое преобразование с понижением частоты, приводящее к выбору двоичного фазового состояния в вырожденном параметрическом генераторе оптических сигналов;

Чтобы снизить затраты и повысить надежность квантовых генераторов случайных чисел, реализованы онлайн-сервисы.

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

Отказ TRNG может быть весьма сложным и незаметным, требующим проверки не только результатов (выходного потока битов), но и непредсказуемости источника энтропии. Аппаратные генераторы случайных чисел должны постоянно контролироваться на предмет правильной работы, чтобы защититься от деградации источника энтропии вследствие естественных причин и преднамеренных атак. FIPS Pub 140-2 и NIST 800-90B. специальная публикация определить тесты, которые можно использовать для этого.

Минимальный набор тестов в реальном времени, требуемый органами по сертификации, невелик; например, NIST в SP 800-90B требует всего два непрерывных теста на здоровье :

1. тест подсчета повторений проверяет, что последовательности одинаковых цифр не слишком длинные. Для (типичного) случая TRNG, который оцифровывает один бит за раз, это означает отсутствие длинных строк из 0 или 1;
2. тест адаптивной пропорции проверяет, что любая случайная цифра не встречается слишком часто в потоке данных (низкое смещение ). Для бит-ориентированных источников энтропии это означает, что количество единиц и нулей в битовом потоке примерно одинаковое.

Проблемы

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

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

Атаки

Основная статья: Атака на генератор случайных чисел

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

Физические процессы в HRNG открывают новые возможности для атак. Например, TRNG на основе автономного генератора можно атаковать с помощью частотной инъекции .

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

См. также: Оценка энтропии.

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

См. также

• АН/ЦИЗ-9
• Тестовые эксперименты Белла
• /dev/случайный
• ЭРНИ
• Лаваранд (аппаратный генератор случайных чисел, основанный на движении плавающего материала в лавовых лампах)
• Список генераторов случайных чисел
• Лотерейный автомат
• РДРАНД
• Доверенный платформенный модуль

Источники

• Туран, Мелтем Сёнмез; Баркер, Элейн; Келси, Джон; Маккей, Керри А; Баиш, Мэри Л; Бойл, Майк (2018). NIST SP800-90B: Рекомендации по источникам энтропии, используемым для генерации случайных битов (отчет). Гейтерсбург, Мэриленд: Национальный институт стандартов и технологий. дои : 10.6028/nist.sp.800-90b .
• Темпл, М. (2016). Моделирование для науки о данных с помощью R . Пакт Паблишинг. ISBN  978-1-78588-587-7 . Проверено 7 августа 2023 г.
• Сааринен, Маркку-Юхани О.; Ньюэлл, Дж. Ричард; Маршалл, Бен (09 ноября 2020 г.). Создание современного TRNG: интерфейс источника энтропии для RISC-V (PDF) . Нью-Йорк, штат Нью-Йорк, США: ACM. дои : 10.1145/3411504.3421212 . Архивировано из оригинала 16 марта 2021 г. Проверено 9 сентября 2023 г. {{cite conference}}: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )
• Шиндлер, Вернер (2009). «Генератор случайных чисел для криптографических приложений». Криптографическая инженерия . Бостон, Массачусетс: Springer US. стр. 5–23. дои : 10.1007/978-0-387-71817-0_2 . ISBN  978-0-387-71816-3 .
• Сунар, Берк (2009). «Истинные генераторы случайных чисел для криптографии». Криптографическая инженерия . Бостон, Массачусетс: Springer US. стр. 55–73. дои : 10.1007/978-0-387-71817-0_4 . ISBN  978-0-387-71816-3 .
• Л'Экуйер, Пьер (2017). История генерации единых случайных чисел (PDF) . Зимняя конференция по моделированию 2017 (WSC). Лас-Вегас, Невада, США: IEEE. дои : 10.1109/wsc.2017.8247790 . ISBN  978-1-5386-3428-8 . ISSN   1558-4305 .
• Стипчевич, Марио; Коч, Четин Кая (2014). «Настоящие генераторы случайных чисел». Открытые проблемы математики и вычислительной техники (PDF) . Чам: Международное издательство Springer. стр. 275–315. дои : 10.1007/978-3-319-10683-0_12 . ISBN  978-3-319-10682-3 .
• Эрреро-Коллантес, Мигель; Гарсиа-Эскартин, Хуан Карлос (22 февраля 2017 г.). «Квантовые генераторы случайных чисел». Обзоры современной физики . 89 (1). Американское физическое общество (APS). arXiv : 1604.03304 . Бибкод : 2017RvMP...89a5004H . дои : 10.1103/revmodphys.89.015004 . ISSN   0034-6861 .
• Генерация квантовых случайных чисел: теория и практика . Квантовая наука и технологии. Спрингер Чам . 2020. doi : 10.1007/978-3-319-72596-3 . ISBN  978-3-319-72596-3 .

Общие ссылки

• Браун, Джордж В. (июнь 1949 г.), История миллиона цифр Рэнда , документы, RAND Corporation , заархивировано из оригинала 5 июня 2007 г. , получено 10 мая 2009 г.
• Браун, Бернис (октябрь 1948 г.), Некоторые тесты на случайность миллиона цифр , документы, RAND Corporation , заархивировано из оригинала 05 июня 2007 г. , получено 10 мая 2009 г.
• «Лампа типа 6D4», Справочник по данным электронных трубок , Сильвания, 1957 г.
• Миллион случайных цифр со 100 000 нормальных отклонений , RAND Corporation , январь 2001 г., заархивировано из оригинала 16 декабря 2002 г. , получено 22 декабря 2002 г.
• Гальтон, Фрэнсис (1890), «Кости для статистических экспериментов» , Nature , 42 (1070): 13–4, Бибкод : 1890Natur..42...13G , doi : 10.1038/042013a0 , заархивировано из оригинала 2004–2004 гг. -04 , получено 28 марта 2004 г.
• Случайность и подлинный генератор случайных чисел с функциями самотестирования (PDF) , Япония: LE Tech RNG, заархивировано из оригинала (PDF) 01 марта 2018 г. , получено 20 апреля 2015 г.
• Д. Истлейк, 3-е место; Дж. Шиллер; С. Крокер (июнь 2005 г.). Требования случайности для безопасности . дои : 10.17487/RFC4086 . BCP 106. RFC 4086 . {{citation}}: CS1 maint: numeric names: authors list (link) Best Common Practice. Obsoletes РФК 1750 .

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

• Генератор случайных чисел Intel (PDF) , Intel , 22 апреля 1999 г.
• ProtegoST SG100 , ProtegoST, «Аппаратный генератор случайных чисел «На основе квантово-физического источника случайных чисел из стабилитрона».