Апаратний генератор випадкових чисел
Апаратний генератор випадкових чисел (генератор істинно випадкових чисел) — пристрій, який генерує послідовність випадкових чисел на основі вимірюваних параметрів фізичного процесу, що протікає. Робота таких пристроїв часто заснована на використанні надійних джерел ентропії, таких як тепловий шум, фотоефект, квантові явища тощо. Ці процеси теоретично абсолютно непередбачувані, на практиці ж одержувані з них випадкові числа можна перевірити за допомогою спеціальних статистичних тестів.
Апаратні генератори випадкових чисел головним чином застосовують щоб проводити статистичні випробування і в криптографії, де їх використовують щоб створювати криптографічні ключі для зашифрованої передачі даних. Також такі апарати широко використовуються в інтернет-казино для імітації, наприклад, рулетки. Але через складність реалізації й відносну повільність використання подібних генераторів залежить від потреб конкретної предметної області й від будови самого генератора.
Коротка історія розвитку ред.
Прості гральні кубики, що були в широкому вжитку в азартних іграх раніше і в настільних іграх тепер, є найпростішим істинним генератором випадкових чисел. 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].
Наслідком законів квантової фізики є той факт, що деякі природні явища (наприклад, радіоактивний розпад атомів) абсолютно випадкові і їх неможливо в принципі передбачити (одним з перших дослідів, що доводять імовірнісну природу деяких явищ, можна вважати Дослід Девіссона — Джермера). Крім того, зі статистичної механіки випливає, що при температурі, яка не дорівнює абсолютному нулю, кожна система має випадкові флуктуації своїх параметрів.
Оскільки деякі квантово-механічні процеси абсолютно випадкові, вони є «золотим стандартом» для АГВЧ. Явища, що використовуються в генераторах, включають:
- Дробовий шум — це шум в електричних ланцюгах, що викликаний дискретністю носіїв електричного заряду. Також цим терміном називають шум в оптичних приладах, що викликаний дискретністю переносника світла. В нашому випадку, як джерело шуму використовують фотоелектронний помножувач або електровакуумні фотоелементи [7].
- Радіоактивний розпад використовують як джерело шуму, оскільки для нього характерна випадковість кожного окремого акту розпаду. У результаті на приймач (наприклад, лічильник Гейгера або сцинтиляційний лічильник) у різні проміжки часу потрапляє різна кількість частинок [9].
- Спонтанне параметричне розсіяння також можна використовувати в генераторах випадкових чисел[10].
Неквантові явища простіше виявити, але АГВЧ, що засновані на них, будуть сильно залежати від температури (наприклад, величина теплового шуму пропорційна до температури навколишнього середовища). Серед процесів, що застосовують для створення АГВЧ, можна відзначити:
- Тепловий шум у резисторі, з якого після посилення виходить генератор випадкової напруги. Зокрема, генератор чисел у комп'ютері Ferranti Mark 1[en] ґрунтувався на цьому явищі[4].
- Атмосферний шум, що його виміряв радіоприймач; сюди ж можна віднести й прийом космічних променів за допомогою приймача, кількість яких у різні проміжки часу випадкова.
- Різниця в швидкості ходу годинника[en] — явище, яке полягає в тому, що хід різних годинників не буде абсолютно збігатися[11].
Див. також ред.
Примітки ред.
- ↑ Гальтон Ф.. «Dice for statistical experiments» журнал «Nature». — 1890. — С. 13-14.
- ↑ «Патент „Random number generator“»[недоступне посилання]
- ↑ Кнут Д. Э. «Искусство программирования. Том 2. Получисленные алгоритмы». — 2011. — С. 12-14. — ISBN 978-5-8459-0081-4.
- ↑ а б Turing A.. «Programmers' Handbook for the Manchester Electronic Computer Mark II». — 1952. — С. 25.
- ↑ «Історія ERNIE». Архів оригіналу за 24 вересня 2015. Процитовано 23 вересня 2015.
- ↑ Панкратов С.. «Законы непредсказуемы» журнал «Наука и жизнь». — М. : Правда, 1988. — С. 75-77.
- ↑ а б Бобнев, 1966, с. 7-14.
- ↑ Henk, 2005.
- ↑ Бобнев, 1 966, с. 7-14.
- ↑ Marandi A., Leindecker N. C., Vodopyanov K. L., Byer. All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators. — Vol. 20. — DOI:
- ↑ Velichko S. Random-number generator prefers imperfect clocks. — 1996.
Література ред.
- Бобнев М. П.. «Генерирование случайных сигналов и измерение их параметров». — М. : Энергия, 1966. — 120 с.
- Henk C. A. va Tilborg. Encyclopedia of Cryptography and Security. — USA : Springer Science+Business Media, 2005. — С. 509-514. — 45000 прим. — ISBN 978-0-387-23473-1.
- Schindler W. Efficient Online Test for True Random Numbers Generators // Cryptographic Hardware and Embedded Systems - CHES 2001 : сборник. — 2001. — P. 103. — ISSN 0302-9743. — ISBN 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 // Information Security Theory and Practice. Security and Privacy of Mobile Devices in Wireless Communication : сборник. — 2011. — P. 175-190. — ISBN 978-3-642-21039-6.