1. Генератори, що використовують фізичні випадкові процеси [ правити | правити код ]
2. Генератори, що використовують інші явища [ правити | правити код ]

open wikipedia design.

Апаратний генератор випадкових чисел (генератор істинно випадкових чисел) - пристрій, що генерує послідовність випадкових чисел на основі вимірюваних, хаотично змінюються параметрів протікає фізичного процесу. Робота таких пристроїв часто заснована на використанні надійних джерел ентропії , таких як теплової шум , дробовий шум , фотоелектричний ефект , квантові явища і т. д. Ці процеси в теорії абсолютно непередбачувані, на практиці ж одержувані з них випадкові числа перевіряються за допомогою спеціальних статистичних тестів .

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

проста гральна кістка , Що широко використовувалася в азартних іграх в минулому і в настільних іграх в даний час, є найпростішим істинним генератором випадкових чисел. У 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] .

наслідком законів квантової фізики є той факт, що деякі природні явища (наприклад, радіоактивний розпад атомів) абсолютно випадкові і не можуть бути в принципі передбачити (одним з перших дослідів, які доводять вірогідну природу деяких явищ, можна вважати досвід Девіссона - Джермера ). також з статистичної механіки випливає, що при температурі, що не дорівнює абсолютного нуля , Кожна система має випадкові флуктуації своїх параметрів.

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

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

• тепловий шум в резистори , З якого після посилення виходить генератор випадкових напружень. Зокрема, генератор чисел в комп'ютері Ferranti Mark 1 [En] був заснований на цьому явищі [4] .
• атмосферне шум [En] , Виміряний радіоприймачем; сюди ж можна віднести і прийом частинок, прилітають на землю з космосу, які реєструються приймачем, а їх кількість в різні проміжки часу випадково. Веб-сервіс Random.org використовує даний підхід.
• Різниця в швидкості ходу годинника [En] - явище, яке полягає в тому, що хід різних годин не буде абсолютно збігатися [10] .

Існує кілька підходів для отримання послідовності випадкових бітів з фізичного випадкового процесу . Один з них полягає в тому, що отриманий сигнал-шум посилюється, фільтрується і подається на вхід швидкодіючого компаратора напруг, щоб отримати логічний сигнал . Тривалість станів компаратора будуть випадковими, що дозволяє створити послідовність випадкових чисел, вимірюючи тривалості цих станів. У таких системах необхідно брати до уваги, що, крім використовуваного генератора шуму, його можуть вносити й інші компоненти системи (наприклад, силова лінія ), Що може сильно вплинути на статистичні параметри генерується послідовності бітів [11] [8] .

Інший підхід полягає в тому, що випадковий сигнал подається на вхід аналого-цифрового перетворювача (Можуть використовуватися як спеціальні пристрої, так і аудіовхід комп'ютера), в результаті оцифрований сигнал буде являти собою послідовність випадкових чисел, яка може бути програмно оброблена . Також існують методи об'єднання швидкодіючого генератора псевдовипадкових чисел з повільним апаратним генератором [11] [8] .

Генератори, що використовують інші явища [ правити | правити код ]

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

До найбільш незвичайним генераторів слід віднести роботи, які використовують цифрові відеокамери , що знімають макроскопічні явища . Наприклад, команда з 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 с. - ISBN 978-5-8459-0081-4 .
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 , С. 7-14.
8. ↑ 1 2 3 4 5 Henk, 2005 .
9. ↑ Marandi A., Leindecker NC, Vodopyanov KL, 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. , С. 103.
12. ↑ Callas J. Using and Creating Cryptographic-Quality Random Numbers (Англ.) (Недоступна посилання) (3 June 1996). Дата обігу 9 жовтня 2014. Читальний зал 14 березня 2015 року.
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 CA va Tilborg. Encyclopedia of Cryptography and Security. - США США : Springer Science + Business Media , 2005. - С. 509-514. - 684 с. - 45 000 прим. - ISBN 978-0-387-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 3-540-42521-7 . - ISSN 0302-9743 .
• 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 .