Аппаратный генератор случайных чисел: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Номинирование статьи в добротные с помощью гаджета QA (v. 1413484651) |
Яй (обсуждение | вклад) орфография, пунктуация, стилевые правки, оформление |
||
(не показано 6 промежуточных версий 1 участника) | |||
Строка 2: | Строка 2: | ||
[[Файл:Sun-crypto-accelerator-1000.jpg|thumb|справа|Эта [[карта расширения]] использует аппаратный генератор случайных чисел для создания [[Ключ (криптография)|криптографических ключей]] для зашифровки данных, передаваемых по сети]] |
[[Файл:Sun-crypto-accelerator-1000.jpg|thumb|справа|Эта [[карта расширения]] использует аппаратный генератор случайных чисел для создания [[Ключ (криптография)|криптографических ключей]] для зашифровки данных, передаваемых по сети]] |
||
'''Аппаратный генератор случайных чисел '''('''Генератор истинно случайных чисел''') — устройство, которое генерирует последовательность [[случайное число|случайных чисел]] на основе измеряемых параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных [[источник энтропии|источников энтропии]], таких как [[тепловой шум]], [[фотоэффект|фотоэлектрический эффект]], [[квант|квантовые явления]] и т.д. Эти процессы |
'''Аппаратный генератор случайных чисел '''('''Генератор истинно случайных чисел''') — устройство, которое генерирует последовательность [[случайное число|случайных чисел]] на основе измеряемых параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных [[источник энтропии|источников энтропии]], таких как [[тепловой шум]], [[фотоэффект|фотоэлектрический эффект]], [[квант|квантовые явления]] и т.д. Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные числа проверяются с помощью [[Тестирование псевдослучайных последовательностей|специальных статистических тестов]]. |
||
Аппаратные генераторы случайных чисел |
Аппаратные генераторы случайных чисел главным образом применяются для проведения [[Метод Монте-Карло|статистических испытаний]] и в [[Криптография |криптографии]], где они используются для создания [[Ключ (криптография)|криптографический ключей]] для зашифрованной передачи данных. Также такие аппараты широко используются в [[интернет-казино]] для имитации, например, рулетки. Но из-за сложности реализации и относительной медленности использование подобных генераторов зависит от потребностей конкретной предметной области и от устройства самого генератора. |
||
== Краткая история развития == |
== Краткая история развития == |
||
[[Файл:ERNIE1 2012.JPG|мини|справа|ERNIE 1 |
[[Файл:ERNIE1 2012.JPG|мини|справа|ERNIE 1]] |
||
[[Файл:Revolving lottery machine,kaitenshiki-cyusenki,japan.JPG|мини|слева|200px|[[Лототрон]] в Японии]] |
[[Файл:Revolving lottery machine,kaitenshiki-cyusenki,japan.JPG|мини|слева|200px|[[Лототрон]] в Японии]] |
||
Простая [[игральная кость]], широко использовавшаяся в [[Азартные игры|азартных играх]] в прошлом и в [[Настольная игра |настольных играх]] в настоящее время, является простейшим ИГСЧ. В 1890 году английский исследователь [[Гальтон, Фрэнсис|Фрэнсис Гальтон]] описал способ использования игровых костей для генерации случайных чисел в научных целях |
Простая [[игральная кость]], широко использовавшаяся в [[Азартные игры|азартных играх]] в прошлом и в [[Настольная игра |настольных играх]] в настоящее время, является простейшим ИГСЧ. В 1890 году английский исследователь [[Гальтон, Фрэнсис|Фрэнсис Гальтон]] описал способ использования игровых костей для генерации случайных чисел в научных целях<ref>{{книга |
||
| автор = {{nobr|Гальтон Ф.}} |
| автор = {{nobr|Гальтон Ф.}} |
||
| заглавие = «Dice for statistical experiments» журнал «Nature» |
| заглавие = «Dice for statistical experiments» журнал «Nature» |
||
Строка 17: | Строка 17: | ||
| страниц = 43 |
| страниц = 43 |
||
| ref = Гальтон |
| ref = Гальтон |
||
}}</ref> |
}}</ref>. |
||
Дальнейшим развитием аппаратных генераторов случайных чисел можно считать специальные устройства — [[ |
Дальнейшим развитием аппаратных генераторов случайных чисел можно считать специальные устройства — [[лототрон]]ы, использующиеся для генерации чисел в [[лото]] и [[Кено (игра)|кено]]. Они главным образом состоят из барабана, перемешивающего шары с числами, и устройства, извлекающего их из него поочерёдно. Однако такой метод генерации является очень медленным и непригодным для автоматической генерации больших массивов данных<ref>[https://www.google.com/patents/US4786056| "Патент «Random number generator»"]</ref>. |
||
Для прикладных задач были необходимы большие массивы данных. В 1939 [[Кендалл, Морис Джордж|М. Ж. Кендалл]] и Б. Бабингтон-Смит построили первую машину, генерирующую случайные числа для построения |
Для прикладных задач были необходимы большие массивы данных. В 1939 [[Кендалл, Морис Джордж|М. Ж. Кендалл]] и Б. Бабингтон-Смит построили первую машину, генерирующую случайные числа для построения {{iw|Таблица случайных чисел|таблицы|en|Random number table}}, содержащей 100 000 случайных чисел. А через 16 лет корпорацией [[RAND (корпорация)|RAND]], с использованием специальных устройств, была построена таблица из миллиона случайных чисел. Несмотря на оживление табличного метода в 1996 году {{iw|Марсалья, Джордж|Дж. Марсальей|en|George Marsaglia}}, построившим 650 Мбайт случайных чисел, круг применимости таких таблиц очень узок<ref>{{книга |
||
| автор = {{ |
| автор = [[Кнут, Дональд Эрвин{{!}}Кнут Д. Э.]] |
||
| заглавие = «Искусство программирования. Том 2. Получисленные алгоритмы» |
| заглавие = «Искусство программирования. Том 2. Получисленные алгоритмы» |
||
| год = 2011 |
| год = 2011 |
||
Строка 28: | Строка 28: | ||
| страниц = 832 |
| страниц = 832 |
||
| ISBN = 978-5-8459-0081-4 |
| ISBN = 978-5-8459-0081-4 |
||
}}</ref> |
}}</ref>. |
||
Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер |
Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер {{iw|Ferranti Mark 1}} была включена программа, идея которой принадлежала [[Тьюринг, Алан|А. Тьюрингу]], генерирующая случайные числа, используя шум [[резистор]]а<ref name="Tur">{{книга |
||
| автор = {{nobr|Turing A.}} |
| автор = {{nobr|Turing A.}} |
||
| заглавие = «Programmers' Handbook for the Manchester Electronic Computer Mark II» |
| заглавие = «Programmers' Handbook for the Manchester Electronic Computer Mark II» |
||
Строка 36: | Строка 36: | ||
| страницы = 25 |
| страницы = 25 |
||
| страниц = 110 |
| страниц = 110 |
||
}}</ref> А в 1957 году была изобретена машина |
}}</ref>. А в 1957 году была изобретена машина {{iw|Premium Bond|ERNIE (Electronic Random Number Indicator Equipment)|en|Premium Bond}}, четвёртая версия которой была представлена в 2004 году. Это устройство изначально предназначено для генерации номеров выигрышных облигаций в британской лотерее<ref>[http://www.i-programmer.info/history/machines/6317-ernie-a-random-number-generator.html| "История ERNIE"]</ref>. |
||
==Устройство== |
==Устройство== |
||
Аппаратные генераторы случайных чисел могут быть основаны на макроскопических [[Случайный процесс|случайных процессах]] |
Аппаратные генераторы случайных чисел могут быть основаны на макроскопических [[Случайный процесс|случайных процессах]] с использованием таких предметов, как монетка, игральная кость или колесо рулетки. Наличие непредсказуемости в данных объясняется теорией неустойчивых [[Динамическая система|динамических систем]] и [[Теория хаоса|теории хаоса]]. Даже полностью определённые [[Законы Ньютона|уравнениями Ньютона]] макроскопические системы на практике имеют непредсказуемый выход, поскольку он зависит от микроскопических деталей начальных условий<ref>{{книга |
||
| автор = {{nobr|Панкратов С.}} |
| автор = {{nobr|Панкратов С.}} |
||
| заглавие = «Законы непредсказуемы» журнал «Наука и жизнь» |
| заглавие = «Законы непредсказуемы» журнал «Наука и жизнь» |
||
Строка 50: | Строка 50: | ||
| issn = 0028-1263 |
| issn = 0028-1263 |
||
| ref = Панкратов |
| ref = Панкратов |
||
}}</ref> |
}}</ref>. |
||
===Генераторы, использующие физические случайные процессы === |
===Генераторы, использующие физические случайные процессы === |
||
Устройства, основанные на [[Макроскопический масштаб| |
Устройства, основанные на [[Макроскопический масштаб|макроскопических]] случайных процессах, не могут обеспечить скорость получения случайных чисел, достаточную для прикладных задач. Поэтому в основе современных АГСЧ лежит источник [[шум]]а, из которого [[Оцифровка|извлекаются]] случайные [[бит]]ы. Источники шума разделяют на два типа: имеющие [[Квантовая физика|квантовую]] природу и не использующие квантовые явления.{{sfn|Бобнев|1966|c=7-14}} {{sfn|Henk|2005}} |
||
Следствием квантовой физики является тот факт, что некоторые природные явления (например, [[радиоактивный распад]] атомов) абсолютно случайны |
Следствием квантовой физики является тот факт, что некоторые природные явления (например, [[радиоактивный распад]] атомов) абсолютно случайны и не могут быть в принципе предсказаны (одним из первых опытов, доказывающих вероятностную природу некоторых явлений, можно считать [[опыт Дэвиссона — Джермера]]). Также из [[Статистическая механика|статистической механики]] следует, что при температуре, не равной [[Абсолютный нуль температуры|абсолютному нулю]], каждая система имеет случайные [[Флуктуация|флуктуации]] своих параметров. |
||
Поскольку некоторые квантово-механические процессы абсолютно случайны, они являются «золотым стандартом» для АГСЧ. Явления, использующиеся в генераторах включают: |
Поскольку некоторые квантово-механические процессы абсолютно случайны, они являются «золотым стандартом» для АГСЧ. Явления, использующиеся в генераторах, включают: |
||
*[[Дробовой шум]] — это шум в электрических цепях, вызванный [[ |
*[[Дробовой шум]] — это шум в электрических цепях, вызванный [[дискретность]]ю [[Электрон|носителей электрического заряда]]. Также этим термином называют шум в [[Оптика|оптических]] приборах, вызванный дискретностью [[Фотон|переносчика света]]. В данном случае, в качестве источника шума используют [[фотоэлектронный умножитель]] или электровакуумные [[фотоэлемент]]ы{{sfn|Бобнев|1966|c=7-14}}. |
||
*[[Радиоактивный распад]] используется в качестве источника шума, поскольку для него характерна случайность каждого отдельного акта распада. В результате на |
*[[Радиоактивный распад]] используется в качестве источника шума, поскольку для него характерна случайность каждого отдельного акта распада. В результате на приёмник (например, [[счетчик Гейгера]] или [[Сцинтилляторы|сцинтилляционный счетчик]]) в различные промежутки времени попадает разное количество [[Частица|частиц]]{{sfn|Бобнев|1966|c=7-14}}. |
||
*[[Спонтанное параметрическое рассеяние]] также может быть использовано в генераторах случайных чисел.<ref>{{книга|автор=Marandi A., Leindecker N. C., Vodopyanov K. L., Byer |journal=Opt. Express|volume=20|год=2012|название=All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators|doi=10.1364/OE.20.019322|ссылка=http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-20-17-19322}}</ref> |
*[[Спонтанное параметрическое рассеяние]] также может быть использовано в генераторах случайных чисел.<ref>{{книга|автор=Marandi A., Leindecker N. C., Vodopyanov K. L., Byer |journal=Opt. Express|volume=20|год=2012|название=All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators|doi=10.1364/OE.20.019322|ссылка=http://www.opticsinfobase.org/oe/abstract.cfm?uri=oe-20-17-19322}}</ref> |
||
Неквантовые явления проще детектировать, но АГСЧ, основанные на них, будут сильно зависеть от [[Температура|температуры]] (например, величина [[Тепловой шум|теплового шума]] пропорциональна температуре окружающей среды). Среди процессов, использующихся в АГСЧ, можно отметить: |
Неквантовые явления проще детектировать, но АГСЧ, основанные на них, будут сильно зависеть от [[Температура|температуры]] (например, величина [[Тепловой шум|теплового шума]] пропорциональна температуре окружающей среды). Среди процессов, использующихся в АГСЧ, можно отметить: |
||
*[[Тепловой шум]] в [[резистор]]е, из которого после усиления получается генератор случайных напряжений. В частности генератор чисел компьютере |
* [[Тепловой шум]] в [[резистор]]е, из которого после усиления получается генератор случайных напряжений. В частности, генератор чисел в компьютере {{iw|Ferranti Mark 1}} был основан на этом явлении<ref name="Tur"></ref>. |
||
* |
* {{iw|Атмосферный шум|||Atmospheric noise}}, измеренный радиоприёмником; сюда же можно отнести и приём частиц, [[Космические лучи|прилетающих]] на [[Земля|Землю]] из космоса, которые регистрируются приёмником, а их количество в разные промежутки времени случайно. |
||
* |
* {{iw|Разница в скорости хода часов|||Clock drift}} — явление, заключающееся в том, что ход разных часов не будет абсолютно совпадать<ref>{{книга|автор=Velichko S. |год=1996|название=Random-number generator prefers imperfect clocks|ссылка=http://edn.com/design/other/4340990/EDN-Access-11-21-96-Random-number-generator-prefers-imperfect-clock}}</ref>. |
||
Существует несколько подходов для получения последовательности случайных [[бит]] из физического [[Случайный процесс|случайного процесса]]. Один из них заключается в том, что полученный [[Шум|сигнал-шум]] усиливается, [[Фильтр (электроника)|фильтруется]] и |
Существует несколько подходов для получения последовательности случайных [[бит]]ов из физического [[Случайный процесс|случайного процесса]]. Один из них заключается в том, что полученный [[Шум|сигнал-шум]] усиливается, [[Фильтр (электроника)|фильтруется]] и подаётся на вход быстродействующего [[компаратор]]а напряжений, чтобы получить [[Цифровой сигнал|логический сигнал]]. Промежутки времени между появлениями сигнала на выходе компаратора будут случайными, что позволяет создать последовательность случайных чисел. В таких системах необходимо принимать во внимание, что помимо используемого генератора шума его могут вносить и другие компоненты системы (например, [[Линия электропередачи|силовая линия]]), что может сильно повлиять на последовательность битов{{sfn | Shcindler|2001|c=103}}{{sfn |Henk|2005}}. |
||
Другой подход заключается в том, что случайный сигнал |
Другой подход заключается в том, что случайный сигнал подаётся на вход [[Аналого-цифровой преобразователь|аналого-цифрового преобразователя]] (могут использоваться как специальные устройства, так и аудиовход компьютера), в результате [[Оцифровка|оцифрованный сигнал]] будет представлять собой последовательность случайных чисел, которая может быть [[Цифровая обработка сигналов|программно обработана]]. Также существуют методы объединения быстродействующего [[Генератор псевдослучайных чисел|генератора псевдослучайных чисел]] с медленным аппаратным генератором. {{sfn | Shcindler|2001|c=103}} {{sfn|Henk|2005}} |
||
===Генераторы, использующие другие явления=== |
===Генераторы, использующие другие явления=== |
||
Генераторы случайных чисел, использующие физические случайные процессы, позволяют получить хорошие случайные числа, но их производство относительно сложно и дорого (в особенности это касается АГСЧ, основанных на [[ |
Генераторы случайных чисел, использующие физические случайные процессы, позволяют получить хорошие случайные числа, но их производство относительно сложно и дорого (в особенности это касается АГСЧ, основанных на [[Радиоактивный распад|радиоактивном распаде]]), но существуют и более доступные [[Источник энтропии|источники случайности]]: |
||
*Измерение времени между нажатиями на кнопки [[Клавиатура|клавиатуры]] или [[Мышь|мыши]] |
* Измерение времени между нажатиями на кнопки [[Клавиатура|клавиатуры]] или [[Мышь|мыши]] и последующее взятие нескольких [[Порядок байтов|наименее значимых битов]]. К недостаткам данного метода следует отнести малую скорость генерации и необходимость наличия [[Пользователь|пользователя]]<ref name="Callas">{{cite web |
||
|url = https://www.merrymeet.com/jon/usingrandom.html |
|url = https://www.merrymeet.com/jon/usingrandom.html |
||
|title = Using and Creating Cryptographic-Quality Random Numbers |
|title = Using and Creating Cryptographic-Quality Random Numbers |
||
Строка 78: | Строка 79: | ||
|accessdate = 2014-10-09 |
|accessdate = 2014-10-09 |
||
|lang = en |
|lang = en |
||
}} |
}}</ref>. |
||
*Использование шума со встроенного [[микрофон]]а в компьютере. Но помимо [[Белый шум|белого шума]] в [[спектр]]е будут присутствовать такие паразитные составляющие, как шум в [[Электрическая сеть|электрической сети]] на 60 [[Герц (единица измерения)|Гц]] шум от [[вентилятор]]а в компьютере и др.<ref name="Callas"></ref> |
* Использование шума со встроенного [[микрофон]]а в компьютере. Но помимо [[Белый шум|белого шума]] в [[спектр]]е будут присутствовать такие паразитные составляющие, как шум в [[Электрическая сеть|электрической сети]] на 60 [[Герц (единица измерения)|Гц]], шум от [[вентилятор]]а в компьютере и др.<ref name="Callas"></ref> |
||
*Использование [[Компьютерная сеть|сети]] или [[интернет]]а, например, время между принятыми [[Пакет (сетевые технологии)|пакетами]] или [[контрольная сумма]] новостей предыдущей недели |
* Использование [[Компьютерная сеть|сети]] или [[интернет]]а, например, время между принятыми [[Пакет (сетевые технологии)|пакетами]] или [[контрольная сумма]] новостей предыдущей недели<ref name="Callas"></ref>. |
||
К наиболее необычным генераторам следует отнести работы, которые используют цифровые [[Видеокамера|видеокамеры]], снимающие [[Макроскопический масштаб|макроскопические явления]]. Например, команда из [[Silicon Graphics]] использовала видеозапись [[Лавовая лампа|лавовой лампы]] для генерации случайных чисел, так как воск в лампе хаотически меняет свои формы. Также в качестве объекта |
К наиболее необычным генераторам следует отнести работы, которые используют цифровые [[Видеокамера|видеокамеры]], снимающие [[Макроскопический масштаб|макроскопические явления]]. Например, команда из [[Silicon Graphics]] использовала видеозапись [[Лавовая лампа|лавовой лампы]] для генерации случайных чисел, так как воск в лампе хаотически меняет свои формы. Также в качестве объекта съёмки могут быть использованы пузыри в [[аквариум]]е или ленты в потоке воздуха от [[вентилятор]]а<ref> [https://www.google.com/patents/US5732138| "Патент «Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system»"]</ref>. |
||
==Проблемы== |
==Проблемы== |
||
Основная проблема аппаратных генераторов случайных чисел |
Основная проблема аппаратных генераторов случайных чисел — это их относительная медленность по сравнению с [[Генератор псевдослучайных чисел|генераторами псевдослучайных последовательностей]]. Также многие из них выходят из строя незаметно (например, уменьшение [[Радиоактивный распад|радиоактивности]] вещества со временем), поэтому их необходимо [[Тестирование псевдослучайных последовательностей|тестировать]] перед каждым использованием (многие из них тестируются в [[Система реального времени|реальном времени]]){{sfn|Henk|2005}}. |
||
Другая проблема, связанная с аппаратными генераторами случайных чисел, — это смещение последовательности выходных [[бит]] (когда одних чисел в последовательности больше чем других, например единиц больше, чем нулей в [[Двоичная система счисления|двоичной системе]]). Она вызвана особенностями физических процессов, используемых в генераторах шума. Данная проблема решается с помощью специальных алгоритмов, которые позволяют выровнять число нулей и единиц |
Другая проблема, связанная с аппаратными генераторами случайных чисел, — это смещение последовательности выходных [[бит]]ов (когда одних чисел в последовательности больше, чем других, например единиц больше, чем нулей в [[Двоичная система счисления|двоичной системе]]). Она вызвана особенностями физических процессов, используемых в генераторах шума. Данная проблема решается с помощью специальных алгоритмов, которые позволяют выровнять число нулей и единиц{{sfn|Claudio A. Ardagna, Jianying Zhou|2011}}{{sfn|Henk|2005}}. |
||
[[Нейман, Джон фон|Нейман]] одним из первых предложил простой [[алгоритм]] для исправления слабого смещения в последовательности. Алгоритм заключается в том, что биты рассматриваются парами |
[[Нейман, Джон фон|Дж. Нейман]] одним из первых предложил простой [[алгоритм]] для исправления слабого смещения в последовательности. Алгоритм заключается в том, что биты рассматриваются парами: если в паре два одинаковых значения, то пара отбрасывается, если биты разные, то вместо пары записывается только первый бит в этой паре. Недостаток этого алгоритма заключается в том, что около 75 % битов отбрасываются, и в результате сильно падает скорость генерации случайных бит{{sfn|Claudio A. Ardagna, Jianying Zhou|2011}}. |
||
Другой метод заключается в использовании [[Криптографическая хеш-функция|криптографических хеш-функций]] (например, [[MD5]] или [[SHA-1]]), так они удовлетворяют строгим требованиям криптографической стойкости. Но несмотря на относительную быстроту этого метода, их трудно воспроизвести [[Аппаратное обеспечение|аппаратным способом]] из-за нелинейности хеш-функций |
Другой метод заключается в использовании [[Криптографическая хеш-функция|криптографических хеш-функций]] (например, [[MD5]] или [[SHA-1]]), так как они удовлетворяют строгим требованиям криптографической стойкости. Но, несмотря на относительную быстроту этого метода, их трудно воспроизвести [[Аппаратное обеспечение|аппаратным способом]] из-за нелинейности хеш-функций и из-за сильной зависимости такого генератора от качества самой хеш-функции{{sfn|Claudio A. Ardagna, Jianying Zhou|2011}}. |
||
Также для уменьшения смещения используются [[Криптографически стойкий генератор псевдослучайных чисел|криптографически стойкие генераторы псевдослучайной последовательности]], поток |
Также для уменьшения смещения используются [[Криптографически стойкий генератор псевдослучайных чисел|криптографически стойкие генераторы псевдослучайной последовательности]], поток битов которых с помощью операции [[XOR]] складывается с потоком битов из аппаратного генератора. Главное достоинство данного метода заключается в том, что он может быть реализован полностью аппаратно, например на [[FPGA]]{{sfn|Claudio A. Ardagna, Jianying Zhou|2011}}. |
||
== См. также == |
== См. также == |
Версия от 02:02, 29 октября 2014
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/74/Sun-crypto-accelerator-1000.jpg/220px-Sun-crypto-accelerator-1000.jpg)
Аппаратный генератор случайных чисел (Генератор истинно случайных чисел) — устройство, которое генерирует последовательность случайных чисел на основе измеряемых параметров протекающего физического процесса. Работа таких устройств часто основана на использовании надёжных источников энтропии, таких как тепловой шум, фотоэлектрический эффект, квантовые явления и т.д. Эти процессы в теории абсолютно непредсказуемы, на практике же получаемые из них случайные числа проверяются с помощью специальных статистических тестов.
Аппаратные генераторы случайных чисел главным образом применяются для проведения статистических испытаний и в криптографии, где они используются для создания криптографический ключей для зашифрованной передачи данных. Также такие аппараты широко используются в интернет-казино для имитации, например, рулетки. Но из-за сложности реализации и относительной медленности использование подобных генераторов зависит от потребностей конкретной предметной области и от устройства самого генератора.
Краткая история развития
Простая игральная кость, широко использовавшаяся в азартных играх в прошлом и в настольных играх в настоящее время, является простейшим ИГСЧ. В 1890 году английский исследователь Фрэнсис Гальтон описал способ использования игровых костей для генерации случайных чисел в научных целях[1].
Дальнейшим развитием аппаратных генераторов случайных чисел можно считать специальные устройства — лототроны, использующиеся для генерации чисел в лото и кено. Они главным образом состоят из барабана, перемешивающего шары с числами, и устройства, извлекающего их из него поочерёдно. Однако такой метод генерации является очень медленным и непригодным для автоматической генерации больших массивов данных[2].
Для прикладных задач были необходимы большие массивы данных. В 1939 М. Ж. Кендалл и Б. Бабингтон-Смит построили первую машину, генерирующую случайные числа для построения таблицы[англ.], содержащей 100 000 случайных чисел. А через 16 лет корпорацией RAND, с использованием специальных устройств, была построена таблица из миллиона случайных чисел. Несмотря на оживление табличного метода в 1996 году Дж. Марсальей[англ.], построившим 650 Мбайт случайных чисел, круг применимости таких таблиц очень узок[3].
Гораздо большее распространение получили генераторы случайных чисел, генерирующие их в реальном времени. В 1951 году в компьютер Ferranti Mark 1[англ.] была включена программа, идея которой принадлежала А. Тьюрингу, генерирующая случайные числа, используя шум резистора[4]. А в 1957 году была изобретена машина ERNIE (Electronic Random Number Indicator Equipment)[англ.], четвёртая версия которой была представлена в 2004 году. Это устройство изначально предназначено для генерации номеров выигрышных облигаций в британской лотерее[5].
Устройство
Аппаратные генераторы случайных чисел могут быть основаны на макроскопических случайных процессах с использованием таких предметов, как монетка, игральная кость или колесо рулетки. Наличие непредсказуемости в данных объясняется теорией неустойчивых динамических систем и теории хаоса. Даже полностью определённые уравнениями Ньютона макроскопические системы на практике имеют непредсказуемый выход, поскольку он зависит от микроскопических деталей начальных условий[6].
Генераторы, использующие физические случайные процессы
Устройства, основанные на макроскопических случайных процессах, не могут обеспечить скорость получения случайных чисел, достаточную для прикладных задач. Поэтому в основе современных АГСЧ лежит источник шума, из которого извлекаются случайные биты. Источники шума разделяют на два типа: имеющие квантовую природу и не использующие квантовые явления.[7] [8]
Следствием квантовой физики является тот факт, что некоторые природные явления (например, радиоактивный распад атомов) абсолютно случайны и не могут быть в принципе предсказаны (одним из первых опытов, доказывающих вероятностную природу некоторых явлений, можно считать опыт Дэвиссона — Джермера). Также из статистической механики следует, что при температуре, не равной абсолютному нулю, каждая система имеет случайные флуктуации своих параметров.
Поскольку некоторые квантово-механические процессы абсолютно случайны, они являются «золотым стандартом» для АГСЧ. Явления, использующиеся в генераторах, включают:
- Дробовой шум — это шум в электрических цепях, вызванный дискретностью носителей электрического заряда. Также этим термином называют шум в оптических приборах, вызванный дискретностью переносчика света. В данном случае, в качестве источника шума используют фотоэлектронный умножитель или электровакуумные фотоэлементы[7].
- Радиоактивный распад используется в качестве источника шума, поскольку для него характерна случайность каждого отдельного акта распада. В результате на приёмник (например, счетчик Гейгера или сцинтилляционный счетчик) в различные промежутки времени попадает разное количество частиц[7].
- Спонтанное параметрическое рассеяние также может быть использовано в генераторах случайных чисел.[9]
Неквантовые явления проще детектировать, но АГСЧ, основанные на них, будут сильно зависеть от температуры (например, величина теплового шума пропорциональна температуре окружающей среды). Среди процессов, использующихся в АГСЧ, можно отметить:
- Тепловой шум в резисторе, из которого после усиления получается генератор случайных напряжений. В частности, генератор чисел в компьютере Ferranti Mark 1[англ.] был основан на этом явлении[4].
- Атмосферный шум[англ.], измеренный радиоприёмником; сюда же можно отнести и приём частиц, прилетающих на Землю из космоса, которые регистрируются приёмником, а их количество в разные промежутки времени случайно.
- Разница в скорости хода часов[англ.] — явление, заключающееся в том, что ход разных часов не будет абсолютно совпадать[10].
Существует несколько подходов для получения последовательности случайных битов из физического случайного процесса. Один из них заключается в том, что полученный сигнал-шум усиливается, фильтруется и подаётся на вход быстродействующего компаратора напряжений, чтобы получить логический сигнал. Промежутки времени между появлениями сигнала на выходе компаратора будут случайными, что позволяет создать последовательность случайных чисел. В таких системах необходимо принимать во внимание, что помимо используемого генератора шума его могут вносить и другие компоненты системы (например, силовая линия), что может сильно повлиять на последовательность битов[11][8].
Другой подход заключается в том, что случайный сигнал подаётся на вход аналого-цифрового преобразователя (могут использоваться как специальные устройства, так и аудиовход компьютера), в результате оцифрованный сигнал будет представлять собой последовательность случайных чисел, которая может быть программно обработана. Также существуют методы объединения быстродействующего генератора псевдослучайных чисел с медленным аппаратным генератором. [11] [8]
Генераторы, использующие другие явления
Генераторы случайных чисел, использующие физические случайные процессы, позволяют получить хорошие случайные числа, но их производство относительно сложно и дорого (в особенности это касается АГСЧ, основанных на радиоактивном распаде), но существуют и более доступные источники случайности:
- Измерение времени между нажатиями на кнопки клавиатуры или мыши и последующее взятие нескольких наименее значимых битов. К недостаткам данного метода следует отнести малую скорость генерации и необходимость наличия пользователя[12].
- Использование шума со встроенного микрофона в компьютере. Но помимо белого шума в спектре будут присутствовать такие паразитные составляющие, как шум в электрической сети на 60 Гц, шум от вентилятора в компьютере и др.[12]
- Использование сети или интернета, например, время между принятыми пакетами или контрольная сумма новостей предыдущей недели[12].
К наиболее необычным генераторам следует отнести работы, которые используют цифровые видеокамеры, снимающие макроскопические явления. Например, команда из Silicon Graphics использовала видеозапись лавовой лампы для генерации случайных чисел, так как воск в лампе хаотически меняет свои формы. Также в качестве объекта съёмки могут быть использованы пузыри в аквариуме или ленты в потоке воздуха от вентилятора[13].
Проблемы
Основная проблема аппаратных генераторов случайных чисел — это их относительная медленность по сравнению с генераторами псевдослучайных последовательностей. Также многие из них выходят из строя незаметно (например, уменьшение радиоактивности вещества со временем), поэтому их необходимо тестировать перед каждым использованием (многие из них тестируются в реальном времени)[8].
Другая проблема, связанная с аппаратными генераторами случайных чисел, — это смещение последовательности выходных битов (когда одних чисел в последовательности больше, чем других, например единиц больше, чем нулей в двоичной системе). Она вызвана особенностями физических процессов, используемых в генераторах шума. Данная проблема решается с помощью специальных алгоритмов, которые позволяют выровнять число нулей и единиц[14][8].
Дж. Нейман одним из первых предложил простой алгоритм для исправления слабого смещения в последовательности. Алгоритм заключается в том, что биты рассматриваются парами: если в паре два одинаковых значения, то пара отбрасывается, если биты разные, то вместо пары записывается только первый бит в этой паре. Недостаток этого алгоритма заключается в том, что около 75 % битов отбрасываются, и в результате сильно падает скорость генерации случайных бит[14].
Другой метод заключается в использовании криптографических хеш-функций (например, MD5 или SHA-1), так как они удовлетворяют строгим требованиям криптографической стойкости. Но, несмотря на относительную быстроту этого метода, их трудно воспроизвести аппаратным способом из-за нелинейности хеш-функций и из-за сильной зависимости такого генератора от качества самой хеш-функции[14].
Также для уменьшения смещения используются криптографически стойкие генераторы псевдослучайной последовательности, поток битов которых с помощью операции XOR складывается с потоком битов из аппаратного генератора. Главное достоинство данного метода заключается в том, что он может быть реализован полностью аппаратно, например на FPGA[14].
См. также
Примечания
- ↑ Гальтон Ф. «Dice for statistical experiments» журнал «Nature». — 1890. — С. 13-14. — 43 с.
- ↑ "Патент «Random number generator»"
- ↑ Кнут Д. Э. «Искусство программирования. Том 2. Получисленные алгоритмы». — 2011. — С. 12-14. — 832 с. — ISBN 978-5-8459-0081-4.
- ↑ 1 2 Turing A. «Programmers' Handbook for the Manchester Electronic Computer Mark II». — 1952. — С. 25. — 110 с.
- ↑ "История ERNIE"
- ↑ Панкратов С. «Законы непредсказуемы» журнал «Наука и жизнь». — М.: Правда, 1988. — С. 75-77. — 172 с.
- ↑ 1 2 3 Бобнев, 1966, с. 7-14.
- ↑ 1 2 3 4 5 Henk, 2005.
- ↑ 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.
- ↑ Velichko S. Random-number generator prefers imperfect clocks. — 1996.
- ↑ 1 2 Shcindler, 2001, с. 103.
- ↑ 1 2 3 Callas J. Using and Creating Cryptographic-Quality Random Numbers (англ.) (3 июня 1996). Дата обращения: 9 октября 2014.
- ↑ "Патент «Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system»"
- ↑ 1 2 3 4 Claudio A. Ardagna, Jianying Zhou, 2011.
Литература
- Бобнев М. П. «Генерирование случайных сигналов и измерение их параметров». — М.: Энергия, 1966. — 120 с.
- Henk C. A. va Tilborg. Encyclopedia of Cryptography and Security. —
США: 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. — P. 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. — P. 175-190. — ISBN 978-3-642-21039-6.
Статья является кандидатом в добротные статьи с 17 октября 2014. |