Апаратний датчик випадкових чисел. Росіяни вигадали «перший у світі» біологічний генератор випадкових чисел
Детерміновані ДПСЛ
Ніякий детермінований алгоритм неспроможна генерувати цілком випадкові числа, може лише апроксимувати деякі властивості випадкових чисел. Як сказав Джон фон Нейман, « кожен, хто живить слабкість до арифметичних методів отримання випадкових чисел, грішний поза всякими сумнівами».
Будь-який ГПСЧ з обмеженими ресурсами рано чи пізно зациклюється - починає повторювати ту саму послідовність чисел. Довжина циклів ГПСЧ залежить від самого генератора і в середньому становить близько 2 n/2 , де n - розмір внутрішнього стану в бітах, хоча лінійні конгруентні і LFSR -генератори мають максимальні цикли порядку 2 n . Якщо ГПСЧ може сходитися до занадто коротких циклів, такий ГПСЧ стає передбачуваним і непридатним.
Більшість простих арифметичних генераторів хоч і мають велику швидкість, але страждають від багатьох серйозних недоліків:
- Занадто короткий період/періоди.
- Послідовні значення є незалежними.
- Деякі біти «менш випадкові», ніж інші.
- Нерівномірний одномірний розподіл.
- Оборотність.
Зокрема, алгоритм мейнфреймах виявився дуже поганим, що викликало сумніви в достовірності результатів багатьох досліджень, які використовували цей алгоритм.
ГПСЧ із джерелом ентропії чи ДСЧ
Нарівні з існуючою необхідністю генерувати послідовності випадкових чисел, що легко відтворюються, також існує необхідність генерувати абсолютно непередбачувані або просто випадкові числа. Такі генератори називаються генераторами випадкових чисел(ДСЛ - англ. random number generator, RNG). Так як такі генератори найчастіше застосовуються для генерації унікальних симетричних та асиметричних ключів для шифрування, вони найчастіше будуються з комбінації криптостійкого ГПСЧ та зовнішнього джерелаентропії (і саме таку комбінацію тепер і заведено розуміти під ДСЛ).
Майже все великі виробникимікрочіпів постачають апаратні ГСЧ з різними джерелами ентропії, використовуючи різні методидля їхнього очищення від неминучої передбачуваності. Однак на даний момент швидкість збору випадкових чисел усіма існуючими мікрочіпами (кілька тисяч біт за секунду) не відповідає швидкодії сучасних процесорів.
У персональних комп'ютерахавтори програмних ГСЧ використовують набагато швидші джерела ентропії, такі як шум звукової карти або лічильник тактів процесора. До появи можливості зчитувати значення лічильника тактів, збирання ентропії було найбільш уразливим місцем ДСЛ. Ця проблема досі повністю вирішена в багатьох пристроях (наприклад, смарт-картах), які таким чином залишаються вразливими. Багато ГСЧ до цих пір використовують традиційні (застарілі) методи збору ентропії на кшталт вимірювання реакції користувача (рух миші тощо), як, наприклад, , або взаємодії між потоками , як, наприклад, Java secure random.
Приклади ДСЛ та джерел ентропії
Декілька прикладів ГСЧ з їх джерелами ентропії та генераторами:
| Джерело ентропії | ДПСЛ | Переваги | Недоліки | |
|---|---|---|---|---|
| /dev/random в Linux | Лічильник тактів процесора, однак збирається лише під час апаратних переривань | LFSR , з хешуванням виходу через | Дуже довго "нагрівається", може надовго "застрявати", або працює як ДПСЧ ( /dev/urandom) | |
| Yarrowвід Брюса Шнайєра | Традиційні (застарілі) методи | AES -256 та | Гнучкий криптостійкий дизайн | Довго «нагрівається», дуже маленький внутрішній стан, дуже залежить від криптостійкості вибраних алгоритмів, повільний, застосуємо виключно для генерації ключів |
| Генератор Леоніда Юр'єва | Шум звукової карти | ? | Швидше за все, хороше та швидке джерело ентропії | Немає незалежного, явно криптостійкого ГПСЧ, доступний виключно у вигляді Windows |
| Microsoft | Вбудований у Windows, не «застряє» | Маленький внутрішній стан, легко передбачуваний | ||
| Взаємодія між потоками | У Java іншого вибору поки немає, великий внутрішній стан | Повільний збір ентропії | ||
| Chaos від Ruptor | Лічильник тактів процесора, збирається безперервно | Хешування 4096-бітового внутрішнього стану на основі нелінійного варіанта Marsaglia-генератора | Поки що найшвидший з усіх, великий внутрішній стан, не «застряє» | |
| RRAND від Ruptor | Лічильник тактів процесора | Зашифровування внутрішнього стану потоковим шифром | Дуже швидкий, внутрішній стан довільного розміру на вибір, не «застряє» |
ДПСЧ у криптографії
Різновидом ГПСЧ є ГПСБ (PRBG) - генератори псевдо-випадкових біт, а також різних потокових шифрів. ГПСЧ, як і потокові шифри, складаються з внутрішнього стану (зазвичай розміром від 16 біт до кількох мегабайт), функції ініціалізації внутрішнього стану ключем або насінням(англ. seed), функції оновлення внутрішнього стану та функції виведення. ДПСЧ поділяються на прості арифметичні, зламані криптографічні та криптостійкі. Їх загальне призначення - генерація послідовностей чисел, які неможливо відрізнити від випадкових обчислювальних методів.
Хоча багато криптостійких ГПСЧ або потокових шифрів пропонують набагато більш «випадкові» числа, такі генератори набагато повільніше звичайних арифметичних і можуть бути непридатні у різноманітних дослідженнях, що вимагають, щоб процесор був вільний для більш корисних обчислень.
У військових цілях і в польових умовах застосовуються лише засекречені синхронні криптостійкі ГПСЧ (потокові шифри), блокові шифри не використовуються. Прикладами відомих криптостійких ГПСЧ є ISAAC, SEAL, Snow, дуже повільний теоретичний алгоритм Блюма, Блюма і Шуба, а також лічильники з криптографічними хеш-функціями або криптостійкими блоковими шифрами замість функції виведення.
Апаратні ГПСЧ
Крім застарілих, добре відомих LFSR-генераторів, що широко застосовувалися як апаратні ГПСЧ у XX столітті, на жаль, дуже мало відомо про сучасні апаратні ГПСЧ (потокові шифри), так як більшість з них розроблено для військових цілей і тримаються в секреті. Майже всі існуючі комерційні апаратні ДПСЧ запатентовані і тримаються в секреті. Апаратні ГПСЧ обмежені строгими вимогами до пам'яті, що витрачається (найчастіше використання пам'яті заборонено), швидкодії (1-2 такту) і площі (кілька сотень FPGA - або
Через нестачу хороших апаратних ГПСЧ виробники змушені застосовувати набагато повільніші, але широко відомі блокові шифри, що є під рукою ( Комп'ютерний огляд № 29 (2003)
Урок 15. Випадок – душа гри
Ви вже навчили черепашку багато чому. Але вона має ще й інші, приховані можливості. Чи може черепашка самостійно зробити щось таке, що здивує вас?
Виявляється, так! У списку датчиків черепашки є датчик випадкових чисел:
випадковий
З випадковими числами ми зустрічаємося часто: кидаючи гральну кістку в дитячій грі, слухаючи в лісі зозулю-провісницю або просто «загадуючи будь-яке число». Датчик випадкових чисел в ЛогоМирах може приймати значення будь-якого цілого позитивно числа від 0 до заданої в якості параметра межі значень.
Саме число, зазначене як параметр датчика випадкових чисел, не випадає ніколи.
Наприклад, випадковий датчик 20 може виявитися будь-яким цілим числом від 0 до 19, включаючи 19, датчик випадковий 1000 - будь-яким цілим числом від 0 до 999, включаючи 999.
Ви, мабуть, здивуєтеся, де тут гра - одні числа. Але не забувайте, що в ЛогоМирах за допомогою чисел можна задати і форму черепашки, і товщину перу, що пише, і його розмір, і колір, і багато іншого. Головне – правильно вибрати межу значень. Межі зміни основних параметрів черепашки наведено у таблиці.
Датчик випадкових чисел можна використовувати як параметр будь-якої команди, наприклад вперед, праворучі т.п.
Завдання 24.Використання датчика випадкових чисел
Організуйте за допомогою датчика випадкових чисел одну із запропонованих нижче ігор і запустіть черепашку.
Гра 1: «Різнокольоровий екран»
1. Помістіть черепашку у центр екрана.
2. Наберіть у Рюкзаку команди та задайте режим Багато разів:
новий колір випадковий 140 крась чекай 10
Команда фарбуйвиконує самі дії, як і інструмент Заливка в графічному редакторі.
3. Озвучте сюжет.
Гра 2: «Веселий маляр» 1. Змініть гру № 1, розкресливши екран лініями на довільні ділянки з безперервними межами:
2. Доповніть інструкцію в Рюкзаку черепашки випадковими поворотами та переміщеннями:
праворуч випадковий 360
вперед випадковий 150
Задайте в Рюкзаку інструкцію переміщення черепашки ( вперед 60) з опущеним пером товщиною 60 випадкового кольору (0-139) під невеликим кутом ( новий_курс 10).Гра 4: "Полювання"
Розробте сюжет, в якому червона черепашка полює на чорну. Чорна черепашка рухається випадковою траєкторією, а напрям руху червоної черепашки управляється бігунком.
Запитання для самоконтролю
1. Що таке датчик випадкових чисел?
2. Який параметр має датчик випадкових чисел?
3. Що означає межа значень?
4. Чи випадає колись саме число, вказане як параметр?
У програмному забезпеченні практично всіх ЕОМ є вбудована функція генерації послідовності псевдовипадкових квазірівномірно розподілених чисел. Проте щодо статистичного моделювання до генерації випадкових чисел пред'являються підвищені вимоги. Якість результатів такого моделювання залежить від якості генератора рівномірно розподілених випадкових чисел, т.к. ці числа є також джерелами (вихідними даними) отримання інших випадкових величин із заданим законом розподілу.
На жаль, ідеальних генераторів немає, а список їх відомих властивостей поповнюється переліком недоліків. Це призводить до ризику використання комп'ютерного експерименту поганого генератора. Тому перед проведенням комп'ютерного експерименту необхідно оцінити якість вбудованої в ЕОМ функції генерації випадкових чисел, або вибрати відповідний алгоритм генерації випадкових чисел.
Для застосування в обчислювальній фізиці генератор повинен мати наступні властивості:
Обчислювальною ефективністю - це якнайменше час обчислення чергового циклу і обсяг пам'яті для роботи генератора.
Великою довжиною Lвипадкової послідовності чисел. Цей період повинен включати принаймні необхідну для статистичного експерименту безліч випадкових чисел. Крім того, небезпека становить навіть наближення до кінця L, що може призвести до невірних результатів статистичного експерименту.
Критерій достатньої довжини псевдовипадкової послідовності вибирають з таких міркувань. Метод Монте-Карло полягає в багаторазовому повторенні розрахунків вихідних параметрів системи, що моделюється, що знаходиться під впливом вхідних параметрів, що флуктують із заданими законами розподілу. Основою реалізації методу є генерація випадкових чисел з рівномірнимрозподілом в інтервалі , у тому числі формуються випадкові числа із заданими законами розподілу. Далі проводиться підрахунок ймовірності події, що моделюється, як відношення числа повторів модельних дослідів з благополучним результатом до загального повторення дослідів при заданих вихідних умовах (параметрах) моделі.
Для надійного, у статистичному сенсі, обчислення цієї ймовірності кількість повторень досвіду можна оцінити за такою формулою:
де 
- функція, зворотна функції нормального розподілу, 
- довірча ймовірність помилки 
виміру ймовірності.
Отже, щоб помилка не виходила за довірчий інтервал з довірчою ймовірністю, наприклад =0,95 треба, щоб число повторень досвіду було менше:
(2.2)
Наприклад, для 10% помилки (
=0,1) отримаємо 
, а для 3% помилки (
=0,03) вже отримаємо 
.
Для інших вихідних умов моделі нова серія повторень дослідів повинна проводитись на іншій псевдовипадковій послідовності. Тому або функція генерації псевдовипадкової послідовності повинна мати параметр, що її змінює (наприклад, R 0 ), або її довжина має бути не менше:
де K - число вихідних умов (точок на кривій визначається методом Монте-Карло), N - Число повторень модельного досвіду при заданих вихідних умовах, L - Довжина псевдовипадкової послідовності.
Тоді кожна серія з N повторень кожного досвіду буде проводитися на своєму відрізку псевдовипадкової послідовності.
Відтворюваність. Як зазначено вище, бажано мати параметр, що змінює генерацію псевдовипадкових чисел. Зазвичай це R 0 . Тому дуже важливо, щоб змінаR 0 не псувало якості (тобто статистичних параметрів) генератора випадкових чисел.
Хорошими статистичними властивостями. Це найважливіший показник якості генератора випадкових чисел. Проте його не можна оцінити будь-яким одним критерієм чи тестом, т.к. не існує необхідних та достатніх критеріїв випадковості кінцевої послідовності чисел. Найбільше, що можна сказати про псевдовипадкову послідовність чисел це те, що вона “виглядає” як випадкова. Жодний статистичний критерій не є надійним індикатором точності. Щонайменше необхідно використовувати кілька тестів, що відображають найбільш важливі сторони якості генератора випадкових чисел, тобто. ступеня його наближення до ідеального генератора.
Тому, крім тестування генератора, надзвичайно важливою є перевірка його за допомогою типових завдань, що допускають незалежну оцінку результатів аналітичними чи чисельними методами.
Можна сказати, що уявлення про надійність псевдовипадкових чисел створюється в процесі їх використання з ретельною перевіркою результатів завжди, коли це можливо.
Розрізняють три принципово різних способуотримання чисел, що використовуються як випадкові: фізичний, табличний та алгоритмічний.
Вважається, що перша спроба створити фізичний датчик випадкових чисел відноситься до 3500 до н.е. і пов'язана з настільною гроюсенет, давньоєгипетська світська розвага. Згідно з сучасними реконструкціями правил гри для визначення набраної кожним гравцем кількості очок та черговості ходів у цій грі використовувалися чотири плоскі палички, одна сторона яких була білою, інша – чорною. Палички кидали одночасно і в залежності від комбінації кольорів, що випала, визначали додаткові можливостігравців. На початку XX ст. послідовності випадкових чисел імітувалися вручну - за допомогою кидань монети або гральної кістки, розкладання гральних карт, рулетки, вилучення куль з урни і т.д. Сучасні фізичні (апаратні) датчики являють собою спеціальні пристрої, що генерують випадкові числа на основі перетворення випадкових шумів природного або штучного походження(тепловий шум, дробовий ефект в електронних лампах, радіоактивний розпад тощо). Наприклад, машина ERNIE 4 (electronic random number indicator equipment),
- 1 Іноді, хоч і рідко, до стандартних відносять розподіл, що задається таблицею 0 1 ... 8 9
- 0,1 0,1 ... 0,1 0,1/ за допомогою якої визначають виграли номери в щомісячній Британській лотереї, як джерело випадкових величин використовує тепловий шум транзисторів. У фізичного способуодержання послідовності випадкових чисел є особливості, які для імітаційної моделі є недоліками. До них відносяться, в першу чергу, необхідність спеціальних заходів щодо забезпечення стабільності джерела сигналу, що перетворюється на випадкові числа, і неможливість відтворення отриманої послідовності випадкових чисел.
Таблиці випадкових чисел позбавлені зазначених недоліків. Пояснимо, що розуміємо під таблицею випадкових чисел. Припустимо, що ми здійснили Nнезалежних дослідів, у яких отримали випадкові цифри а, а 2 ,осдг. Запис цих цифр (у порядку появи та у формі прямокутної таблиці) дасть так звану таблицю випадкових цифр. Використовується вона в такий спосіб. У результаті розрахунків нам може знадобитися або випадкова цифра, або випадкове число. Якщо потрібна випадкова цифра, ми можемо взяти будь-яку цифру з цієї таблиці. Те саме стосується випадку випадкового числа - для кожного розряду можна вибрати будь-яку цифру. Якщо нам знадобиться випадкове число 0 k чергових цифр сц, а 2 , ос/, і вважати, що 8 = (Хоцо^.-.о^. При цьому у разі «ідеальної» таблиці випадкових цифр вибирати цифри з неї можна випадковим чином, можна поспіль, можна використовувати будь-який алгоритм вибору, який залежить від значень цифр таблиці, починати з будь-якого місця таблиці, читати у напрямі.
Перші таблиці випадкових чисел отримано з допомогою рулеток. Такі таблиці кілька разів видавалися у вигляді книжок. Одна з найвідоміших таблиць, опублікована в 1927 р., містила понад 40 000 випадкових цифр, «довільно взятих зі звітів про перепис».
Історична довідка
Леонард Тіппет (Leonard Henry Caleb Tippett, 1902-1985) - англійський статистик, учень К. Пірсона та Р. Фішера. У 1965-1966 pp. - Президент Королівського статистичного товариства. З його ім'ям пов'язані деякі важливі результати теорії екстремальних значень, наприклад розподіл Фішера - Типпета і теорема Фішера - Типпета - Гнеденко.
Пізніше були сконструйовані спеціальні пристрої (машини), що механічно виробляють випадкові числа. Першу таку машину 1939 р. використовували М. Дж. Кендалл і Б. Бебінгтон-Сміт під час створення таблиць, які включають 100 тис. випадкових цифр. У 1955 р. компанія RAND Corporationопублікувала добре відомі таблиці з мільйоном випадкових цифр, одержаних іншою машиною такого типу. Практичне застосуваннятаблиць випадкових чисел обмежується нині, зазвичай, завданнями, у яких використовуються методи випадкового відбору
вибірок, наприклад, у соціологічних дослідженнях або під час проведення статистичного приймального контролю якості штучної продукції різного призначення.
Це цікаво
У Росії її діє ГОСТ 18321-73 (СТ РЕВ 1934-79), встановлює правила відбору одиниць продукції вибірку під час проведення статистичного приймального контролю якості, статистичних методіваналізу та регулювання технологічних процесівдля всіх видів штучної продукції виробничо-технічного призначення та товарів народного споживання. У ньому, зокрема, зазначається, що з відборі одиниць продукції вибірку «використовують таблиці випадкових чисел по СТ РЕВ 546-77».
багаторазово застосовувати; усі числа легко відтворюються; та запас чисел у такій послідовності обмежений. Однак послідовність псевдовипадкових чисел має очевидну перевагу перед таблицею: існують прості формулидля розрахунку псевдовипадкового числа, у своїй отримання кожного числа витрачається всього 3-5 команд, а програма розрахунку займає у накопичувачі лише кілька осередків.
Алгоритмів отримання послідовностей псевдовипадкових чисел існує багато, реалізації таких алгоритмів, які називаються датчиками (генераторами) псевдовипадкових чисел, досить докладно описані у спеціальній літературі. Вкажемо кілька найвідоміших алгоритмів.
- Tippett L. Random sampling numbers. London: Cambridge University Press, 1927.
- Див: Кнут Д. Е. Мистецтво програмування. 3-тє вид. М.: Вільямс, 2000. Т. 2. Гол. 3.Випадкові числа.
19.09.2017, Вт, 13:18, Мск , Текст: Валерія Шмирова
Компанія "Код безпеки", розробник криптографічного комплексу "Континент", отримала патент на біологічний датчик випадкових чисел. Це саме біологічний датчик, оскільки в основі випадковості лежить реакція користувача на показане зображення. Компанія запевняє, що такі технології у світі не патентувалися.
Отримання патенту
Компанія "Код безпеки" отримала патент на технологію біологічного датчика випадкових чисел. За словами розробників, під час створення технології було використано «новий підхід до вирішення завдання генерації випадкових чисел з використанням комп'ютера та людини». Розробка вже використовується в ряді продуктів, у тому числі в Континент-АП, Secret Net Studio, Континент TLS і Jinn, а також в криптографічній бібліотеці SCrypt.
Як пояснили представники компанії, робота над датчиком ведеться вже третій рік. Вона складається з наукової частини, реалізації та експериментальної частини. За наукову частину в компанії відповідають три особи, у розробці брала участь вся команда програмістів, а тестування та експерименти проводилися всім колективом, що складає кілька сотень людей.
Можливості технології
Новий датчик може генерувати випадкові послідовності на персональних пристроях - для цього не потрібні додаткові прилади або апаратні надбудови. Він може застосовуватися при шифруванні даних та в будь-яких сферах, де виникає потреба у випадкових двійкових послідовностях. За словами розробників, з його допомогою набагато швидше створюються ключі шифрування на мобільних пристроях. Ця властивість може бути використана для шифрування даних або формування електронного підпису.
Як пояснила Аліса Коренєва, системний аналітик «Код безпеки», створений компанією датчик генерує випадкові послідовності ґрунтуючись на швидкості та точності реагування руки користувача на зміну зображення на екрані ПК або планшета. Для введення використовуються миша або тачскрін. Виглядає це так: екраном хаотично рухаються кола, деякі їх параметри змінюються з часом. У деякі моменти часу користувач реагує зміни зображення. З урахуванням особливостей його моторики це відбивається у довільній масі бітів.
Генерувати випадкові числові послідовності можна спираючись на спонтанні реакції людини
Поза криптографією датчик може бути використаний для генерації випадкових чисел комп'ютерних іграхчи для вибору переможців конкурсів.
Наукова новизна
Як пояснили CNews у компанії, в основі багатьох відомих способівПобудови датчиків випадкових чисел лежать або фізичні закони та явища, або детерміновані алгоритми. Послідовності можна генерувати за допомогою комп'ютера - у цьому випадку за основу випадковості взято нестабільність роботи деяких частин комп'ютера та невизначеність апаратних перешкод.
Новизна технології «Коду безпеки» полягає в тому, що джерелом випадковості є реакція людини на зображення, що змінюється, який виводиться на дисплей пристрою. Саме тому в назві винаходу є слово «біологічний». Компанія повідомляє, що ні вона, ні Роспатент не знайшли в Росії та у світі запатентованих аналогів технології. Однак загалом такі методики відомі: наприклад, послідовність можна генерувати, спираючись на такі дії користувача, як кліки або рухи мишею або натискання клавіш на клавіатурі.
За словами Коренєвої, команда розробки проаналізувала різні способигенерації випадкових послідовностей Як з'ясувалося, у багатьох випадках відсутні обґрунтовані оцінки продуктивності генерації, або статистичних властивостей згенерованих послідовностей, або і того і іншого. Це з труднощами обгрунтування вже придуманої технології. «Код безпеки» стверджує, що у своєму дослідженні отримав обґрунтовані оцінки швидкості генерації, зміг обґрунтувати хороші ймовірнісні характеристики та статистичні властивості та оцінив ентропію, що вноситься діями людини.
Продукти, де використовується технологія
«Континент» - це апаратно-програмний комплекс, призначений для шифрування даних. Використовується у російському держсекторі, наприклад, у Казначействі. Складається з міжмережевого екрану та інструментарію для створення VPN. Було створено компанією НДП «Інформзахист», зараз його розробкою займається ТОВ «Код Безпеки».
Конкретно сервер доступу «Континент» і система криптозахисту інформації «Континент-АП» є модульом захищеного віддаленого доступу з використанням алгоритмів ГОСТ, а «Континент TLS VPN» - це система забезпечення захищеного віддаленого доступу до веб-додатків також з використанням алгоритмів шифрування ГОСТ.
Secret Net Studio - це комплексне рішення для захисту робочих станцій та серверів на рівні даних, додатків, мережі, операційної системита периферійного обладнання, яке також розробляє «Код безпеки». Jinn-Client призначений для криптографічного захисту інформації для створення електронного підпису та довіреної візуалізації документів, а Jinn-Server – це програмно-апаратний комплекс для побудови систем юридично значущого електронного документообігу.
Криптографічна бібліотека SCrypt, в якій також використовується новий датчик, була розроблена «Код безпеки» для більш зручного застосуваннякриптографічних алгоритмів у різних продуктах. Це єдиний програмний код, який перевірив помилки. Бібліотека підтримує криптографічні алгоритми хешування, електронного підпису, шифрування.
Чим займається «Код безпеки»
"Код безпеки" - російська компанія, яка займається розробкою ПЗ та апаратури. Заснована в 2008 р. Сфера застосування продукції - захист інформаційних системта приведення їх у згоду з міжнародними та галузевими стандартами, у тому числі захист конфіденційної інформації, аж до держтаємниці. «Код безпеки» має дев'ять ліцензій Федеральної служби з технічного та експортного контролю (ФСТЕК) Росії, Федеральної служби безпеки (ФСБ) Росії та Міністерства оборони.
Штат компанії налічує близько 300 фахівців, реалізацією продукції займаються 900 авторизованих партнерів у всіх регіонах Росії та країнах СНД. Клієнтська база «Коду безпеки» налічує близько 32 тис. державних та комерційних організацій.