stringtranslate.com

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

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

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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для снижения затрат и повышения надежности квантовых генераторов случайных чисел были реализованы [37] онлайн-сервисы. [26]

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

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

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

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

Проблемы

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

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

Атаки

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

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

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

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

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

Рекомендации

  1. ^ abcd Turan et al. 2018, с. 64.
  2. ^ аб Шиндлер 2009, с. 7.
  3. ^ аб Стипчевич и Коч 2014, с. 279.
  4. ^ аб Сунар 2009, с. 56.
  5. ^ Эрреро-Коллантес и Гарсия-Эскартин 2017, стр. 8.
  6. ^ Ячак, Марцин М.; Йозвяк, Петр; Немчук, Якуб; Ячак, Януш Э. (2021). «Квантовые генераторы случайных чисел». Научные отчеты . 11 (1): 16108. doi : 10.1038/s41598-021-95388-7 . ПМЦ  8352985 . ПМИД  34373502.
  7. ^ Ма, Сюнфэн; Юань, Сяо; Цао, Чжу; Ци, Бин; Чжан, Чжэнь (2016). «Квантовая генерация случайных чисел». npj Квантовая информация . 2 (1): 1–9. arXiv : 1510.08957 . дои : 10.1038/npjqi.2016.21 .
  8. ^ ab Herrero-Collantes & Garcia-Escartin 2017, стр. 4.
  9. ^ Туран и др. 2018, с. 6.
  10. ^ Сааринен, Ньюэлл и Маршалл, 2020.
  11. ^ Темпл 2016, с. 90.
  12. ^ Эрреро-Коллантес и Гарсия-Эскартин 2017, стр. 6.
  13. ^ Эрреро-Коллантес и Гарсия-Эскартин 2017, стр. 7.
  14. ^ abcde L'Ecuyer 2017.
  15. ^ Гальтон, Фрэнсис (1890). «Кости для статистических экспериментов» (PDF) . Природа . 42 (1070): 13–14. Бибкод : 1890Natur..42...13G. дои : 10.1038/042013a0 . S2CID  4038609. Архивировано (PDF) из оригинала 4 марта 2016 года . Проверено 14 мая 2014 г.
  16. ^ Кендалл, М.Г. и Б. Бэбингтон-Смит. 1938. «Случайность и другие числа случайной выборки». Журнал Королевского статистического общества 101: 147–166.
  17. ↑ Браун, Джордж В. (январь 1949 г.), P-113, Papers, Rand Corporation, заархивировано из оригинала 5 июня 2007 г. , получено 10 мая 2009 г..
  18. ^ Кобин, Карри (1947), «Генератор электрического шума», Труды IRE (сентябрь 1947): 875–9
  19. ^ Отчет о монографии, Rand Corporation, январь 2001 г., заархивировано из оригинала 15 апреля 2018 г. , получено 29 января 2009 г..
  20. ^ Шнайер, Брюс (1 ноября 1995 г.). «Другие потоковые шифры и настоящие генераторы случайных последовательностей». Прикладная криптография (второе изд.). John Wiley & Sons, Inc. с. 423. ИСБН 978-0-471-11709-4.
  21. ^ Сунар 2009, с. 57.
  22. ^ Стипчевич и Коч 2014, стр. 279–280.
  23. ^ Стипчевич и Коч 2014, с. 280.
  24. ^ Стипчевич и Коч 2014, с. 286.
  25. ^ аб Стипчевич и Коч 2014, стр. 288–289.
  26. ^ ab Herrero-Collantes & Garcia-Escartin 2017, стр. 2.
  27. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 10–13.
  28. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 13–14.
  29. ^ Эрреро-Коллантес и Гарсия-Эскартин 2017, стр. 15.
  30. ^ Эрреро-Коллантес и Гарсия-Эскартин 2017, стр. 17.
  31. ^ Эрреро-Коллантес и Гарсия-Эскартин 2017, стр. 20.
  32. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 20–21.
  33. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 21–22.
  34. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 23–24.
  35. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 24–25.
  36. ^ Эрреро-Коллантес и Гарсия-Эскартин, 2017, стр. 27–28.
  37. ^ Хуан, Лейлей; Чжоу, Хунъи; Фэн, Кай; Се, Чхонджин (07.07.2021). «Квантовая облачная платформа случайных чисел». npj Квантовая информация . ООО «Спрингер Сайенс энд Бизнес Медиа». 7 (1). дои : 10.1038/s41534-021-00442-x . ISSN  2056-6387.
  38. ^ Туран и др. 2018.
  39. ^ Туран и др. 2018, стр. 25–27.
  40. ^ Маркеттос, А. Теодор; Мур, Саймон В. (2009). «Атака частотной инжекцией на генераторы истинных случайных чисел на основе кольцевых генераторов». Конспекты лекций по информатике (PDF) . Берлин, Гейдельберг: Springer Berlin Heidelberg. п. 317–331. дои : 10.1007/978-3-642-04138-9_23. ISBN 978-3-642-04137-2. ISSN  0302-9743.

Источники

Общие ссылки

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