Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Генератор псевдовипадкових чисел



План:


Введення

Генератор псевдовипадкових чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG ) - алгоритм, що породжує послідовність чисел, елементи якої майже незалежні один від одного і підкоряються заданому розподілу (зазвичай рівномірному).

Сучасна інформатика широко використовує псевдовипадкові числа в самих різних додатках - від методу Монте-Карло і імітаційного моделювання до криптографії. При цьому від якості використовуваних ГПСЧ безпосередньо залежить якість отриманих результатів. Ця обставина підкреслює відомий афоризм Роберта Р. Кавью з ORNL (англ.): "генерація випадкових чисел занадто важлива, щоб залишати її на волю випадку".


1. Джерела випадкових чисел

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

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

Генератор псевдовипадкових чисел включений до складу багатьох сучасних процесорів (напр., сімейства x86)

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


2. Детерміновані ГПСЧ

Ніякої детермінований алгоритм не може генерувати повністю випадкові числа, він може тільки апроксимувати деякі їх властивості. Як сказав Джон фон Нейман, "всякий, хто має схильність до арифметичним методам отримання випадкових чисел, грішний поза всяких сумнівів".

Будь ГПСЧ з обмеженими ресурсами рано чи пізно зациклюється - починає повторювати одну і ту ж послідовність чисел. Довжина циклів ГПСЧ залежить від самого генератора і становить близько 2 n / 2, де n - розмір внутрішнього стану в бітах, хоча лінійні конгруентні і LFSR -генератори мають максимальними циклами порядку 2 n. Якщо породжувана ГПСЧ послідовність сходиться до занадто коротким циклам, то такий ГПСЧ стає передбачуваним і непридатним для практичних додатків.

Більшість простих арифметичних генераторів хоча і володіють великою швидкістю, але страждають від багатьох серйозних недоліків:

  • Занадто короткий період / періоди.
  • Послідовні значення не є незалежними.
  • Деякі біти "менш випадкові", ніж інші.
  • Нерівномірний одномірне розподіл.
  • Оборотність.

Зокрема, алгоритм RANDU, десятиліттями використовувався на мейнфреймах, виявився дуже поганим [1] [2], що викликало сумніви в достовірності результатів багатьох досліджень, використовували цей алгоритм.

Найбільш поширені лінійний конгруентний метод, метод Фібоначчі з запізнюваннями, регістр зсуву з лінійної зворотним зв'язком, регістр зсуву з узагальненою зворотним зв'язком.

Із сучасних ГПСЧ широке поширення також отримав " вихор Мерсенна ", запропонований в 1997 році Мацумото і Нісімура. Його перевагами є колосальний період (2 19937 -1), рівномірний розподіл в 623 вимірах (лінійний конгруентний метод дає більш-менш рівномірний розподіл максимум в 5 вимірах), швидка генерація випадкових чисел ( в 2-3 рази швидше, ніж стандартні ГПСЧ, що використовують лінійний конгруентний метод). Однак, існують алгоритми, що розпізнають послідовність, породжувану вихором Мерсенна, як невипадкову.


3. ГПСЧ з джерелом ентропії або ГВЧ

Нарівні з існуючою необхідністю генерувати легко відтворювані послідовності випадкових чисел, також існує необхідність генерувати абсолютно непередбачувані або попросту абсолютно випадкові числа. Такі генератори називаються генераторами випадкових чисел (ГВЧ - англ. random number generator, RNG ). Так як такі генератори найчастіше застосовуються для генерації унікальних симетричних і асиметричних ключів для шифрування, вони найчастіше будуються з комбінації криптостійкості ГПСЧ і зовнішнього джерела ентропії (і саме таку комбінацію тепер і прийнято розуміти під ГВЧ).

Майже всі великі виробники мікрочіпів поставляють апаратні ГВЧ з різними джерелами ентропії, використовуючи різні методи для їх очищення від неминучої передбачуваності. Однак на даний момент швидкість збору випадкових чисел усіма існуючими мікрочіпами (кілька тисяч біт в секунду) не відповідає швидкодії сучасних процесорів.

У сучасних дослідженнях здійснюються спроби використання вимірювання фізичних властивостей об'єктів (наприклад, температури) або навіть квантових флуктуацій вакууму в якості джерела ентропії для ГВЧ. [3]

У персональних комп'ютерах автори програмних ГВЧ використовують набагато більш швидкі джерела ентропії, такі, як шум звукової карти або лічильник тактів процесора. Збір ентропії був найбільш вразливим місцем ГВЧ. Ця проблема досі повністю не вирішена в багатьох пристроях (наприклад, смарт-картах), які таким чином залишаються вразливими. Багато ГВЧ використовують традиційні випробувані, хоча й повільні, методи збору ентропії зразок вимірювання реакції користувача (рух миші і т. п.), як, наприклад, в PGP і Yarrow [4], або взаємодії між потоками, як, наприклад, в Java SecureRandom.


3.1. Приклад найпростішого ГВЧ з джерелом ентропії

Якщо в якості джерела ентропії використовувати поточний час, то для отримання натурального числа від 0 до N достатньо обчислити залишок від ділення поточного часу в мілісекундах на число N +1. Недоліком цього ГВЧ є те, що протягом однієї мілісекунди він видає одне і те ж число.

3.2. Приклади ГВЧ і джерел ентропії

Джерело ентропії ГПСЧ Переваги Недоліки
/ Dev / random в UNIX / Linux Лічильник тактів процесора, однак збирається тільки під час апаратних переривань LFSR, з хешуванням виходу через SHA-1 Є у всіх Unix, надійне джерело ентропії Дуже довго "нагрівається", може надовго "застрявати", або працює як ГПСЧ (/ dev / urandom)
Yarrow від Брюса Шнайера [4] Традиційні методи AES -256 і SHA-1 маленького внутрішнього стану Гнучкий криптостійкий дизайн Повільний
Microsoft CryptoAPI Поточний час, розмір жорсткого диска, розмір вільної пам'яті, номер процесу і NETBIOS-ім'я комп'ютера MD5 -хеш внутрішнього стану розміром в 128 біт Вбудований в Windows, не "застряє" Сильно залежить від використовуваного криптопровайдером (CSP).
Java SecureRandom Взаємодія між потоками SHA-1 -хеш внутрішнього стану (1024 біт) Велике внутрішній стан Повільний збір ентропії
Chaos від Ruptor [5] Лічильник тактів процесора, збирається безперервно Хешування 4096-бітового внутрішнього стану на основі нелінійного варіанту Marsaglia-генератора Поки найшвидший з усіх, великий внутрішній стан, не "застряє" Оригінальна розробка, властивості приведені тільки за твердженням автора
RRAND від Ruptor [6] Лічильник тактів процесора Зашіфровиванія внутрішнього стану потоковим шифром EnRUPT в authenticated encryption режимі (aeRUPT) Дуже швидкий, внутрішній стан довільного розміру за вибором, не "застряє" Оригінальна розробка, властивості приведені тільки за твердженням автора. Шифр EnRUPT не є криптостійкості.

4. ГПСЧ в криптографії

Різновидом ГПСЧ є ГПСБ (PRBG) - генератори псевдо-випадкових біт, а також різних поточних шифрів. ГПСЧ, як і потокові шифри, складаються з внутрішнього стану (зазвичай розміром від 16 біт до декількох мегабайт), функції ініціалізації внутрішнього стану ключем або зерном ( англ. seed ), Функції оновлення внутрішнього стану і функції виводу. ГПСЧ підрозділяються на прості арифметичні, зламані криптографічні та криптостійкі. Їх загальне призначення - генерація послідовностей чисел, які неможливо відрізнити від випадкових обчислювальними методами.

Хоча багато криптостійкі ГПСЧ або потокові шифри пропонують набагато більше "випадкові" числа, такі генератори набагато повільніше звичайних арифметичних і можуть бути непридатні у всякого роду дослідженнях, що вимагають, щоб процесор був вільний для більш корисних обчислень.

У військових цілях і в польових умовах застосовуються тільки засекречені синхронні криптостійкі ГПСЧ (потокові шифри), блокові шифри не використовуються. Прикладами відомих криптостійкості ГПСЧ є RC4, ISAAC, SEAL, Snow, зовсім повільний теоретичний алгоритм Блюма, Блюма і Шуба, а також лічильники з криптографічними хеш-функціями або криптостійкості блоковими шифрами замість функції виводу.


4.1. Приклади криптостійкості ГПСЧ

4.1.1. Циклічне шифрування

У даному випадку використовується спосіб генерації ключа сесії з майстер-ключа. Лічильник з періодом N використовується в якості входу в шифруючий пристрій. Наприклад, у разі використання 56-бітного ключа DES може використовуватися лічильник з періодом 256. Після кожного створеного ключа значення лічильника підвищується на 1. Таким чином, псевдослучайная послідовність, отримана за даною схемою, має повний період: кожне вихідне значення Х0, Х1, ... XN-1 засноване на різних значеннях лічильника, тому Х0 ≠ X1 ≠ XN-1. Так як майстер-ключ є секретним, легко показати, що будь секретний ключ не залежить від знання одного або більше попередніх секретних ключів.


4.1.2. ANSI X9.17

ГПСЧ зі стандарту ANSI X9.17 використовується в багатьох додатках фінансової безпеки і PGP. В основі цього ГПСЧ лежить потрійний DES. Генератор ANSI X9.17 складається з наступних частин:

  1. Вхід: генератором керують два псевдовипадкових входу. Один є 64-бітовим представленням поточних дати і часу, які змінюються кожного разу при створенні числа. Іншою є 64-бітовим вихідним значенням. Воно ініціалізується деяким довільним значенням і змінюється в ході генерації послідовності псевдовипадкових чисел.
  2. Ключі: генератор використовує три модулі потрійного DES. Всі три використовують одну і ту ж пару 56-бітних ключів, яка тримається в секреті і застосовується тільки при генерації псевдовипадкового числа.
  3. Вихід: вихід складається з 64-бітного псевдовипадкового числа і 64-бітного значення, яке буде використовуватися в якості початкового значення при створенні наступного числа.
  • DTi - значення дати і часу на початок i-ої стадії генерації.
  • Vi - початкове значення для i-ой стадії генерації.
  • Ri - псевдовипадкове число, створене на i-ої стадії генерації.
  • K1, K2 - ключі, що використовуються на кожній стадії.

Тоді:

 Ri = EDEK1, K2 [EDEK1, K2 [DTi] Vi] Vi +1 = EDEK1, K2 [EDEK1, K2 [DTi] Ri] 

Схема включає використання 112-бітного ключа і трьох EDE-шифрування. На вхід даються два псевдовипадкових значення: значення дати і часу і початкове значення поточної ітерації, на виході виходять початкове значення для наступної ітерації і чергове псевдовипадкове значення. Навіть якщо псевдовипадкове число Ri буде скомпрометована, обчислити Vi +1 з Ri не є можливим за розумний час, і, отже, наступне псевдовипадкове значення Ri +1, так як для отримання Vi +1 додатково виконуються три операції EDE.


5. Апаратні ГПСЧ

Крім застарілих, добре відомих LFSR-генераторів, широко застосовувалися в якості апаратних ГПСЧ в XX столітті, на жаль, дуже мало відомо про сучасних апаратних ГПСЧ (поточних шифрах), так як більшість з них розроблено для військових цілей і тримаються в секреті. Майже всі існуючі комерційні апаратні ГПСЧ запатентовані і також тримаються в секреті. Апаратні ГПСЧ обмежені строгими вимогами до расходуемой пам'яті (найчастіше використання пам'яті заборонено), швидкодії (1-2 такти) і площі (декілька сотень FPGA - або ASIC -осередків). Через таких суворих вимог до апаратних ГПСЧ дуже важко створити криптостійкий генератор, тому досі всі відомі апаратні ГПСЧ були зламані. Прикладами таких генераторів є Toyocrypt і LILI-128, які обидва є LFSR-генераторами, і обидва були зламані за допомогою алгебраїчних атак.

Через нестачу хороших апаратних ГПСЧ виробники змушені застосовувати наявні під рукою набагато повільніші, але широко відомі блокові шифри ( DES, AES) і хеш-функції (SHA-1) в поточних режимах.


Примітки

  1. Дональд Кнут. Глава 3.3. Спектральний критерій / / Мистецтво програмування. Указ. соч. - С. 129-130.
  2. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerical Recipes in C: The Art of Scientific Computing. - 2nd ed. - Cambridge University Press, 1992. - P. 277. - ISBN 0-521-43108-5
  3. З квантового вакууму отримали випадкові числа - lenta.ru/news/2012/04/16/randomiser /
  4. 1 2 Yarrow - www.schneier.com / yarrow.html
  5. Index of / crypto / chaos - cryptolib.com / crypto / chaos /
  6. Index of / crypto / rrand - cryptolib.com / crypto / rrand /

Література

  • Дональд Е. Кнут. Глава 3. Випадкові числа / / Мистецтво програмування = The Art of Computer Programming. - 3-е изд. - М .: Вільямс, 2000. - Т. 2. Получісленние алгоритми. - 832 с. - 7000 екз. - ISBN 5-8459-0081-6 (рос.) ISBN 0-201-89684-2 (англ.)

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Генератор
Генератор сигналів
Магнітогідродинамічний генератор
Генератор документації
Генератор фракталів
Кварцовий генератор
Генератор тактових імпульсів
Генератор змінного струму
Генератор Ван де Граафа
© Усі права захищені
написати до нас