Эта статья является кандидатом в добротные статьи

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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Эта карта расширения использует аппаратный генератор случайных чисел для создания криптографических ключей для зашифровки данных, передаваемых по сети

Аппаратный генератор случайных чисел (Генератор истинно случайных чисел) — устройство, которое генерирует последовательность случайных чисел на основе измеряемых параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных источников энтропии, таких как тепловой шум, фотоэлектрический эффект, квантовые явления и т.д. Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные числа проверяются с помощью специальных статистических тестов.

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

Краткая история развития[править | править вики-текст]

ERNIE 1
Лототрон в Японии

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

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

Для прикладных задач были необходимы большие массивы данных. В 1939 М. Ж. Кендалл и Б. Бабингтон-Смит построили первую машину, генерирующую случайные числа для построения таблицы[en], содержащей 100 000 случайных чисел. А через 16 лет корпорацией RAND, с использованием специальных устройств, была построена таблица из миллиона случайных чисел. Несмотря на оживление табличного метода в 1996 году Дж. Марсальей[en], построившим 650 Мбайт случайных чисел, круг применимости таких таблиц очень узок[3].

Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер Ferranti Mark 1[en] была включена программа, которая генерировала случайные числа, используя шум резистора. Идея создания этой программы принадлежала А. Тьюрингу[4]. А в 1957 году была изобретена машина ERNIE (Electronic Random Number Indicator Equipment)[en], четвёртая версия которой была представлена в 2004 году. Это устройство изначально предназначено для генерации номеров выигрышных облигаций в британской лотерее[5].

Устройство[править | править вики-текст]

Аппаратные генераторы случайных чисел могут быть основаны на макроскопических случайных процессах с использованием таких предметов, как монетка, игральная кость или колесо рулетки. Наличие непредсказуемости в данных объясняется теорией неустойчивых динамических систем и теории хаоса. Даже полностью определённые уравнениями Ньютона макроскопические системы на практике имеют непредсказуемый выход, поскольку он зависит от микроскопических деталей начальных условий[6].

Генераторы, использующие физические случайные процессы[править | править вики-текст]

Устройства, основанные на макроскопических случайных процессах, не могут обеспечить скорость получения случайных чисел, достаточную для прикладных задач. Поэтому в основе современных АГСЧ лежит источник шума, из которого извлекаются случайные биты. Источники шума разделяют на два типа: имеющие квантовую природу и не использующие квантовые явления.[7] [8]

Следствием законов квантовой физики является тот факт, что некоторые природные явления (например, радиоактивный распад атомов) абсолютно случайны и не могут быть в принципе предсказаны (одним из первых опытов, доказывающих вероятностную природу некоторых явлений, можно считать опыт Дэвиссона — Джермера). Также из статистической механики следует, что при температуре, не равной абсолютному нулю, каждая система имеет случайные флуктуации своих параметров.

Поскольку некоторые квантово-механические процессы абсолютно случайны, они являются «золотым стандартом» для АГСЧ. Явления, использующиеся в генераторах, включают:

Неквантовые явления проще детектировать, но АГСЧ, основанные на них, будут сильно зависеть от температуры (например, величина теплового шума пропорциональна температуре окружающей среды). Среди процессов, использующихся в АГСЧ, можно отметить:

Существует несколько подходов для получения последовательности случайных битов из физического случайного процесса. Один из них заключается в том, что полученный сигнал-шум усиливается, фильтруется и подаётся на вход быстродействующего компаратора напряжений, чтобы получить логический сигнал. Промежутки времени между появлениями сигнала на выходе компаратора будут случайными, что позволяет создать последовательность случайных чисел. В таких системах необходимо принимать во внимание, что помимо используемого генератора шума его могут вносить и другие компоненты системы (например, силовая линия), что может сильно повлиять на последовательность битов[11][8].

Другой подход заключается в том, что случайный сигнал подаётся на вход аналого-цифрового преобразователя (могут использоваться как специальные устройства, так и аудиовход компьютера), в результате оцифрованный сигнал будет представлять собой последовательность случайных чисел, которая может быть программно обработана. Также существуют методы объединения быстродействующего генератора псевдослучайных чисел с медленным аппаратным генератором. [11] [8]

Генераторы, использующие другие явления[править | править вики-текст]

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

К наиболее необычным генераторам следует отнести работы, которые используют цифровые видеокамеры, снимающие макроскопические явления. Например, команда из Silicon Graphics использовала видеозапись лавовой лампы для генерации случайных чисел, так как воск в лампе хаотически меняет свои формы. Также в качестве объекта съёмки могут быть использованы пузыри в аквариуме или ленты в потоке воздуха от вентилятора[13].

Проблемы[править | править вики-текст]

Основная проблема аппаратных генераторов случайных чисел — это их относительная медленная по сравнению с генераторами псевдослучайных последовательностей работа. Также многие из них выходят из строя незаметно (например, из-за уменьшения радиоактивности вещества со временем), поэтому их необходимо тестировать перед каждым использованием (многие из них тестируются в реальном времени)[8].

Другая проблема, связанная с аппаратными генераторами случайных чисел, — это смещение последовательности выходных битов (когда одних чисел в последовательности больше, чем других, например единиц больше, чем нулей в двоичной системе). Она вызвана особенностями физических процессов, используемых в генераторах шума. Данная проблема решается с помощью специальных алгоритмов, которые позволяют выровнять число нулей и единиц[14][8].

Дж. Нейман одним из первых предложил простой алгоритм для исправления слабого смещения в последовательности. Алгоритм заключается в том, что биты рассматриваются парами: если в паре два одинаковых значения, то пара отбрасывается, если биты разные, то вместо пары записывается только первый бит в этой паре. Недостаток этого алгоритма заключается в том, что около 75 % битов отбрасываются, и в результате сильно падает скорость генерации случайных бит[14].

Другой метод заключается в использовании криптографических хеш-функций (например, MD5 или SHA-1), так как они удовлетворяют строгим требованиям криптографической стойкости. Но, несмотря на относительную быстроту этого метода, их трудно воспроизвести аппаратным способом из-за нелинейности хеш-функций и из-за сильной зависимости такого генератора от качества самой хеш-функции[14].

Также для уменьшения смещения используются криптографически стойкие генераторы псевдослучайной последовательности, поток битов которых с помощью операции XOR складывается с потоком битов из аппаратного генератора. Главное достоинство данного метода заключается в том, что он может быть реализован полностью аппаратно, например на FPGA[14].

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Гальтон Ф. «Dice for statistical experiments» журнал «Nature». — 1890. — С. 13-14. — 43 с.
  2. "Патент «Random number generator»"
  3. Кнут Д. Э. «Искусство программирования. Том 2. Получисленные алгоритмы». — 2011. — С. 12-14. — 832 с.
  4. 1 2 Turing A. «Programmers' Handbook for the Manchester Electronic Computer Mark II». — 1952. — С. 25. — 110 с.
  5. "История ERNIE"
  6. Панкратов С. «Законы непредсказуемы» журнал «Наука и жизнь». — М.: Правда, 1988. — С. 75-77. — 172 с.
  7. 1 2 3 Бобнев, 1966
  8. 1 2 3 4 5 Henk, 2005
  9. Marandi A., Leindecker N. C., Vodopyanov K. L., Byer All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators. — 2012. — Vol. 20. — DOI:10.1364/OE.20.019322
  10. Velichko S. Random-number generator prefers imperfect clocks. — 1996.
  11. 1 2 Shcindler, 2001
  12. 1 2 3 Callas J. Using and Creating Cryptographic-Quality Random Numbers (англ.) (3 June 1996). Проверено 9 октября 2014.
  13. "Патент «Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system»"
  14. 1 2 3 4 Claudio A. Ardagna, Jianying Zhou, 2011

Литература[править | править вики-текст]

  • Бобнев М. П. «Генерирование случайных сигналов и измерение их параметров». — М.: Энергия, 1966. — 120 с.
  • Henk C. A. va Tilborg Encyclopedia of Cryptography and Security. — СШАFlag of the United States.svg США: Springer Science+Business Media, 2005. — С. 509-514. — 684 с. — 45 000 экз. — ISBN 978-0387-23473-1.
  • Schindler W. Efficient Online Test for True Random Numbers Generators (англ.) // Naccache D., Paar C., Cetin K. Koc Cryptographic Hardware and Embedded Systems - CHES 2001 : сборник. — 2001. — С. 103. — ISBN 0302-9743. — ISSN 3-540-42521-7.
  • Siew-Hwee Kwok, Yen-Ling Ee, Guanhan Chew, Kanghong Zheng, Khoongming Khoo, Chik-How Tan A Comparison of Post-Processing Techniques for Biased Random Number Generators (англ.) // Claudio A. Ardagna, Jianying Zhou Information Security Theory and Practice. Security and Privacy of Mobile Devices in Wireless Communication : сборник. — 2011. — С. 175-190. — ISBN 978-3-642-21039-6.