Що таке генератор випадкових чисел?
Генератор випадкових чисел (англ. Random number generator, часто скорочується як RNG, ГВЧ) — це пристрій призначений для генерації послідовності чисел або символів, значення яких неможливо попередньо передбачити.
Конкретна послідовність зегенерованих результатів може містити певну закономірність, яка буде прослідковуватися після процесу генерації, але яку не можна було передбачити заздалегідь.
пристрої, які створюють випадкові значення, ґрунтуючись на властивостях фізичних процесів, що хаотично змінюються.
Такі системи можуть бути побудовані на використанні макроскопічних випадкових процесів,
тобто в масштабі, що дозволяє проводити вимірювання та спостереження неозброєним оком, наприклад, підкидання монети, гральних кубиків або лототрону.
Незважаючи на те, що згідно з ньютонівськими законами механіки, макроскопічний процес може бути повністю визначений,
добре сконструйований механізм, такий як колесо американської рулетки, видаватиме непередбачуваний результат,
який можна пояснити теорією хаосу та нестійкістю динамічних систем через різницю в початкових умовах кожної нової спроби.
Основним недоліком генераторів з використанням макроскопічних процесів завжди була їхня повільна швидкість роботи,
і як результат — нездатності генерувати велику кількість значень за невеликий проміжок часу.
Сьогодні апаратні генератори випадкових чисел, як правило, використовують пристрої на основі мікроскопічних явищ,
які генерують випадкові низькорівневі сигнали, такі як різні шуми (дробовий, тепловий, атмосферний), фотоелектричний ефект та інші квантові явища.
Подібні процеси є хорошими джерелами ентропії, тому що в теорії їх результат абсолютно неможливо спрогнозувати,
але через складність реалізації та відносну повільність роботи, сфера використання таких генераторів
обмежується предметними областями з певними вимогами до генерованих значень.
Зазвичай генератори істинно випадкових чисел застосовуються в криптографії для створення випадкових криптографічних ключів, щоб забезпечити безпечну передачу даних, наприклад, в інтернет-протоколах шифрування, таких як протокол захисту транспортного рівня (англ. Transport layer security — TLS).
Альтернативою апаратним (фізичним) генераторам виступають генератори на основі алгоритмів — генератори
псевдовипадкових чисел (ГПВЧ, англ. Pseudorandom number generator — PRNG),
які створюють послідовність чисел із властивостями схожими на випадкову послідовність.
Числа згенеровані ГПВЧ не можна вважати істинно випадковими, оскільки вони залежать від початкового значення,
яке не є випадковим, але наявність ряду переваг перед фізичними генераторами, серед яких: швидкодія,
простота та відносна дешевизна реалізації, роблять такі типи генераторів широко застосовуваним у багатьох сферах.
Існує багато методів створення псевдовипадкової послідовності числа, серед них можна виділити вихор Мерсенна
(англ. Mersenne Twister), лінійний конгруентний метод (англ. linear congruential generator — LCG),
Xorshift або генератори регістрів зсуву (англ. shift-register generator), WELL (англ. Well Equidistributed Long-period Linear),
який є різновидом регістру зсуву з лінійним зворотнім зв'язком та інші не апаратні методи.
, де n — натуральне число. Цей генератор був розроблений спеціально,
щоб вирішити основні недоліки тогочасних ГПВЧ, тому він має низку вагомих переваг:
Апаратний генератор випадкових чисел
Для генерації дійсно випадкових чисел використовують апаратні генератори випадкових чисел (англ. Hardware random number generator — HRNG), або їх ще називають генераторами істинно випадкових чисел (англ. True random number generator — TRNG) —
пристрої, які створюють випадкові значення, ґрунтуючись на властивостях фізичних процесів, що хаотично змінюються.
Такі системи можуть бути побудовані на використанні макроскопічних випадкових процесів,
тобто в масштабі, що дозволяє проводити вимірювання та спостереження неозброєним оком, наприклад, підкидання монети, гральних кубиків або лототрону.
Незважаючи на те, що згідно з ньютонівськими законами механіки, макроскопічний процес може бути повністю визначений,
добре сконструйований механізм, такий як колесо американської рулетки, видаватиме непередбачуваний результат,
який можна пояснити теорією хаосу та нестійкістю динамічних систем через різницю в початкових умовах кожної нової спроби.
Основним недоліком генераторів з використанням макроскопічних процесів завжди була їхня повільна швидкість роботи,
і як результат — нездатності генерувати велику кількість значень за невеликий проміжок часу.Сьогодні апаратні генератори випадкових чисел, як правило, використовують пристрої на основі мікроскопічних явищ,
які генерують випадкові низькорівневі сигнали, такі як різні шуми (дробовий, тепловий, атмосферний), фотоелектричний ефект та інші квантові явища.
Подібні процеси є хорошими джерелами ентропії, тому що в теорії їх результат абсолютно неможливо спрогнозувати,
але через складність реалізації та відносну повільність роботи, сфера використання таких генераторів
обмежується предметними областями з певними вимогами до генерованих значень.Зазвичай генератори істинно випадкових чисел застосовуються в криптографії для створення випадкових криптографічних ключів, щоб забезпечити безпечну передачу даних, наприклад, в інтернет-протоколах шифрування, таких як протокол захисту транспортного рівня (англ. Transport layer security — TLS).
Генератор псевдовипадкових чисел
Альтернативою апаратним (фізичним) генераторам виступають генератори на основі алгоритмів — генератори
псевдовипадкових чисел (ГПВЧ, англ. Pseudorandom number generator — PRNG),
які створюють послідовність чисел із властивостями схожими на випадкову послідовність.
Числа згенеровані ГПВЧ не можна вважати істинно випадковими, оскільки вони залежать від початкового значення,
яке не є випадковим, але наявність ряду переваг перед фізичними генераторами, серед яких: швидкодія,
простота та відносна дешевизна реалізації, роблять такі типи генераторів широко застосовуваним у багатьох сферах.
Існує багато методів створення псевдовипадкової послідовності числа, серед них можна виділити вихор Мерсенна
(англ. Mersenne Twister), лінійний конгруентний метод (англ. linear congruential generator — LCG),
Xorshift або генератори регістрів зсуву (англ. shift-register generator), WELL (англ. Well Equidistributed Long-period Linear),
який є різновидом регістру зсуву з лінійним зворотнім зв'язком та інші не апаратні методи.
Вихор Мерсенна
Найпоширенішим універсальним ГПВЧ на сьогоднішній день вважається вихор Мерсенна, який був розроблений у 1997 році японськими вченими Макото Мацумото (яп. 松本 眞) і Такудзі Нісімурою (яп. 西村 拓士). Назва методу походить від того, що довжина його періоду обрана як просте число Мерсен (Mersenne prime) — число виду, де n — натуральне число. Цей генератор був розроблений спеціально,
щоб вирішити основні недоліки тогочасних ГПВЧ, тому він має низку вагомих переваг:
- Довгий період 219937 — 1
- Успішно проходить багато тестів на статистичну випадковість, включаючи тести Diehard
- Має дозвільну ліцензію вільного ПЗ (англ. Permissive free software licence) і не містить патентів для всіх варіантів, крім CryptMT
- k-розподіл з 32-бітною точністю для кожного 1 ≤ k ≤ 623
- Реалізації зазвичай генерують випадкові числа швидше, ніж істинні методи генерації