Псевдовипадкове число - це

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

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

детерміновані ГПСЧ

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

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

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

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

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

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

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

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

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

Кілька прикладів ГСЧ з їх джерелами ентропії і генераторами:

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

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

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

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

апаратні ГПСЧ

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

Через нестачу хороших апаратних ГПСЧ виробники змушені застосовувати наявні під рукою набагато повільніші, але широко відомі блокові шифри (