stringtranslate.com

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

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

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

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

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

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

Использует

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

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

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

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

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

История

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

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

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

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

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

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

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

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

Генератор случайных чисел на основе электрических шумов

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

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

Генератор случайных чисел на основе хаоса

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

Генератор случайных чисел на основе автономных генераторов

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

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

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

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

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

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

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

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

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

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

Проблемы

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

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

Атаки

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

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

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

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

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

Ссылки

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

Источники

Общие ссылки

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