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

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

Краткая история развития

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

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

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

Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер была включена программа, которая генерировала случайные числа, используя шум резистора . Идея создания этой программы принадлежала А. Тьюрингу . А в 1957 году была изобретена машина , четвёртая версия которой была представлена в 2004 году. Это устройство изначально предназначено для генерации номеров выигрышных облигаций в британской лотерее .

Устройство

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

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

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

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

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

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

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

• Тепловой шум в резисторе , из которого после усиления получается генератор случайных напряжений. В частности, генератор чисел в компьютере был основан на этом явлении .
• , измеренный радиоприёмником; сюда же можно отнести и приём частиц, прилетающих на Землю из космоса, которые регистрируются приёмником, а их количество в разные промежутки времени случайно. Веб-сервис Random.org использует данный подход.
• — явление, заключающееся в том, что ход разных часов не будет абсолютно совпадать .

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

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

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

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

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

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

Проблемы

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

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

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

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

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

Профессор биофизики Шноль Симон Эльевич обнаружил в исследованиях 1985—2002 годов закономерное изменение тонкой структуры статистических распределений, отражающих результаты измерений, получаемых при изучении процессов различной природы. Показал, что форма соответствующих гистограмм в одно и то же местное время с высокой вероятностью сходна при измерениях процессов разной природы в разных географических пунктах и что она изменяется с периодом, равным звёздным суткам (23 час. 56 мин.), из чего сделал вывод о фундаментальной космофизической природе этого явления.

См. также

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

Примечания

Литература

• Бобнев М. П. «Генерирование случайных сигналов и измерение их параметров». — М. : Энергия, 1966. — 120 с.
• Henk C. A. va Tilborg. . — США : Springer Science+Business Media , 2005. — С. —514. — 684 с. — 45 000 экз. — ISBN 978-0-387-23473-1 .
• Schindler W. (англ.) // Naccache D., Paar C., Cetin K. Koc Cryptographic Hardware and Embedded Systems — CHES 2001 : сборник. — 2001. — P. 103 . — ISBN 3-540-42521-7 . — ISSN .
• 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. — P. 175—190 . — ISBN 978-3-642-21039-6 .