Псевдовипадкове число — це особлива цифра, що створюється спеціальним генератором. Генератор таких чисел (PRNG), також відомий як генератор детермінованих випадкових бітів (DRBG), являє собою алгоритм для створення послідовності чисел, властивості якої апроксимують характеристики послідовностей випадкових чисел. Генерована PRNG послідовність не є випадковою, оскільки вона повністю визначається початковим значенням, званим початковим числом PRNG, яке може включати в себе дійсно випадкові значення. Хоча послідовності, які ближче до випадковим, можуть створюватися з використанням апаратних генераторів випадкових чисел, генератори псевдовипадкових чисел на практиці важливі для швидкості генерації чисел і їх відтворюваності.
Застосування
PRNG є центральними в таких додатках, як моделювання (наприклад, для методу Монте-Карло), електронні ігри (наприклад, для процедурної генерації) і криптографія. Криптографічні програми вимагають, щоб вихідні дані не були передбачуваними з більш ранньої інформації. Потрібні більш складні алгоритми, які не успадковують лінійність простих PRNG.
Вимоги та умови
Хороші статистичні властивості є центральним вимогою для отримання PRNG. Загалом, необхідний ретельний математичний аналіз, щоб мати впевненість у тому, що ГВЧ генерує числа, які досить близькі до випадковим, щоб відповідати передбачуваному використанню.
Джон фон Нейман попередив про неправильної інтерпретації PRNG як дійсно випадкового генератора і пожартував, що «будь-хто, хто розглядає арифметичні методи отримання випадкових цифр, звичайно, знаходиться в стані гріха».
Використання
PRNG може бути запущений з довільного початкового стану. Він завжди буде генерувати одну і ту ж послідовність при ініціалізації з цим станом. Період PRNG визначається наступним чином: максимум по всіх початкових станів довжини безповторного префікса послідовності. Період обмежений числом станів, зазвичай вимірюються в бітах. Оскільки довжина періоду потенційно подвоюється з кожним доданим бітом «стану», легко створювати PRNG з періодами, достатньо великими для багатьох практичних застосувань.
Якщо внутрішній стан PRNG містить n бітів, його період може бути не більш 2n результатів, він набагато коротше. Для деяких PRNG тривалість може бути розрахована без обходу всього періоду. Регістри зсуву з лінійним зворотним зв’язком (LFSR) зазвичай вибираються так, щоб мати періоди, рівні 2n − 1.
Лінійні конгруентні генератори мають періоди, які можна розрахувати за допомогою факторингу. Хоча ГСЧП будуть повторювати свої результати після того, як вони досягнуть кінця періоду, повторний результат не означає, що кінець періоду був досягнутий, так як його внутрішній стан може бути більше, ніж вихід; це особливо очевидно для PRNG з однобитовым висновком.
Можливі помилки
Помилки, виявлені дефектними PRNG, варіюються від непомітних (і невідомих) до очевидних. Прикладом може служити алгоритм випадкових чисел RANDU, який десятиліттями використовувався на мэйнфреймах. Це був серйозний недолік, але його неадекватність залишалася непоміченою протягом довгого періоду часу.
У багатьох областях дослідницькі роботи, в яких використовувався випадковий відбір, моделювання за методом Монте-Карло або інші способи, засновані на ГСЧП, набагато менш надійні, ніж це могло бути в результаті використання ГНПГ низької якості. Навіть сьогодні іноді потрібна обережність, про що свідчить попередження, наведене у Міжнародній енциклопедії статистичної науки (2010).
Приклад успішного застосування
В якості ілюстрації розглянемо широко використовується мова програмування Java. Станом на 2017 рік, Java все ще покладається на лінійний конгруэнтный генератор (LCG) для свого PRNG.
Історія
Першим PRNG, який уникнув серйозних проблем і все ще працював досить швидко, був Mersenne Twister (обговорюваний нижче), інформацію про який опублікували в 1998 році. З тих пір були розроблені інші високоякісні PRNG.
Але історія псевдовипадкових чисел цим не вичерпується. У другій половині 20-го століття стандартний клас алгоритмів, використовуваних для PRNG, включав лінійні конгруентні генератори. Було відомо, що якість LCG неадекватно, але кращі методи були недоступні. Press et al (2007) описав результат наступним чином: «Якщо б всі наукові статті, результати яких викликають сумніви з-за [LCG і пов’язаних з ними] зникли з бібліотечних полиць, на кожній полиці був би проміжок розміром з кулак».
Основним досягненням у створенні генераторів псевдовипадкових стало впровадження методів, заснованих на лінійних рекурентних в двухэлементном полі; такі генератори пов’язані з лінійними регістрами зсуву зі зворотнім зв’язком. Вони послужили основою для винаходу датчиків псевдовипадкових чисел.
Зокрема, винахід 1997 року Мерсена Твістера дозволило уникнути багатьох проблем з більш ранніми генераторами. Mersenne Twister має період 219937-1 ітерацій (≈4,3 × 106001). Доведено, що він рівномірно розподілений в (до) 623 вимірах (для 32-бітних значень), і на момент його впровадження працював швидше, ніж інші статистично обґрунтовані генератори, що створюють псевдовипадкові послідовності чисел.
У 2003 році Джордж Марсаглия представив сімейство генераторів ксоршифтов, заснованих також на лінійному повторенні. Такі генератори надзвичайно швидкі і — в поєднанні з нелінійної операцією — вони проходять суворі статистичні тести.
У 2006 році було розроблено сімейство генераторів WELL. Генератори WELL в деякому сенсі покращують якість Twister Mersenne, який має занадто великий простір станів і дуже повільне відновлення з них, генерують псевдовипадкові числа c великою кількістю нулів.
Криптографія
PRNG, підходящий для криптографічних додатків, називається криптографічно захищеним PRNG (CSPRNG). Вимога до CSPRNG полягає в тому, що зловмисник, який не знає початкового числа, має лише незначну перевагу в розрізненні вихідний послідовності генератора від випадкової послідовності. Іншими словами, в той час як PRNG потрібно тільки для проходження певних статистичних тестів, CSPRNG повинен пройти всі статистичні тести, які обмежені поліноміальним часом у розмірі насіння.
Хоча доказ цього властивості виходить за рамки сучасного рівня теорії обчислювальної складності, переконливі докази можуть бути надані шляхом відомості CSPRNG до проблеми, яка вважається складною, подібно цілочисельний факторизації. Загалом, можуть знадобитися роки огляду, перш ніж алгоритм може бути сертифікований як CSPRNG.
Було показано, що цілком ймовірно АНБ вставило асиметричний чорний хід у сертифікований NIST генератор псевдовипадкових чисел Dual_EC_DRBG.
Алгоритми псевдовипадкових чисел
Більшість алгоритмів PRNG виробляють послідовності, які рівномірно розподілені будь-яким з декількох тестів. Це відкрите питання. Він один з центральних в теорії і практиці криптографії: чи є спосіб відрізнити вихід високоякісного PRNG від дійсно випадкової послідовності? У цій настройці розпізнавач знає, що використовувався відомий алгоритм PRNG (але не стан, з яким він був ініціалізований), або застосовувався дійсно випадковий алгоритм. Він повинен розрізняти їх.
Безпека більшості криптографічних алгоритмів та протоколів, що використовують PRNG, заснована на припущенні, що неможливо відрізнити застосування відповідного PRNG від використання дійсно випадкової послідовності. Найпростішими прикладами цієї залежності є потокові шифри, які найчастіше працюють, виключаючи або відправляючи відкритий текст повідомлення з виходом PRNG, створюючи зашифрований текст. Розробка криптографічно адекватних PRNG надзвичайно складна, оскільки вони повинні відповідати додатковим критеріям. Розмір його періоду є важливим чинником криптографічного придатності PRNG, але не єдиним.
Ранній комп’ютерний PRNG, запропонований Джоном фон Нейманом в 1946 році, відомий як метод середніх квадратів. Алгоритм наступний: візьміть будь-яке число, зведіть його в квадрат, видалите середні цифри отриманого числа як «випадкове число», потім введіть це число в якості початкового для наступної ітерації. Наприклад, зведення в квадрат числа 1111 дає 1234321, яке можна записати як 01234321, 8-значне число є квадратом 4-значного. Це дає 2343 як «випадкове число. Результат повторення цієї процедури — 4896 і так далі. Фон Нейман використовував 10-значні числа, але процес був таким же.
Недоліки «середнього квадрата»
Проблема з методом «середнього квадрата» полягає в тому, що всі послідовності в кінцевому підсумку повторюються, деякі — дуже швидко, наприклад: 0000. Фон Нейман знав про це, але він знайшов підхід, достатній для своїх цілей, і турбувався, що математичні «виправлення» будуть просто приховувати помилки, а не видаляти їх.
Фон Нейманн визнав апаратні генератори випадкових і псевдовипадкових чисел невідповідними: якщо вони не записують згенерований висновок, то не може бути пізніше перевірені на помилки. Якщо б вони записували свої результати, то вичерпали б обмежену доступну пам’ять комп’ютера і, відповідно, здатність комп’ютера читати і записувати числа. Якби числа були записані на картках, їм знадобилося б набагато більше часу, щоб писати і читати. На комп’ютері ENIAC, який він використовував, метод «середнього квадрата» і здійснив процес отримання псевдовипадкових чисел в кілька сотень разів швидше, ніж відбувається зчитування чисел з перфокарт.
Метод середнього квадрата з тих пір був витіснений більш складними генераторами.
Новаторський метод
Недавнє нововведення — об’єднати середній квадрат з послідовністю Вейля. Цей метод забезпечує високу якість продукції протягом тривалого періоду. Він допомагає отримувати кращі формули псевдовипадкових чисел.
