Псевдовипадкове число: методи отримання, переваги і недоліки

Псевдовипадкове число-це особлива цифра, створювана спеціальним генератором. Генератор таких чисел (PRNG), також відомий як детермінований генератор випадкових бітів (DRBG), є алгоритмом для створення послідовності чисел, властивості яких наближають характеристики послідовностей випадкових чисел. Послідовність, що генерується PRNG, не є справді випадковою, оскільки вона повністю визначається початковим значенням, яке називається початковим числом PRNG, яке може включати справді випадкові значення. Хоча послідовності, ближчі до випадкових, можуть бути створені за допомогою апаратних генераторів випадкових чисел, генератори псевдовипадкових чисел на практиці важливі для швидкості генерації чисел та їх відтворюваності.

Застосування

PRNG є центральними в таких додатках, як моделювання (наприклад, для методу Монте-Карло), електронні ігри (наприклад, для процедурної генерації) та криптографія. Криптографічні програми вимагають, щоб Вихідні дані не були передбачуваними з попередньої інформації. Потрібні більш складні алгоритми, які не успадковують лінійність простих PRNG.

Вимоги та умови

Хороші статистичні властивості є центральною вимогою для отримання PRNG. Загалом, необхідний ретельний математичний аналіз, щоб мати впевненість у тому, що RNG генерує числа, які досить близькі до випадкових, щоб відповідати передбачуваному використанню.

Джон фон Нойман попередив про неправильне тлумачення PRNG як справді випадкового генератора і пожартував, що «кожен, хто розглядає арифметичні методи отримання випадкових цифр, звичайно, перебуває у стані гріха».

Використання

PRNG може бути запущений з довільного початкового стану. Він завжди буде генерувати однакову послідовність при ініціалізації з цим станом. Період PRNG визначається наступним чином: максимум по всіх початкових станах довжини безповторного префікса послідовності. Період обмежений кількістю станів, які зазвичай вимірюються в бітах. Оскільки тривалість періоду потенційно подвоюється з кожним доданим бітом "стану" , легко створити PRNG з періодами, достатньо великими для багатьох практичних застосувань.

Якщо внутрішній стан PRNG містить N бітів, його період може бути не більше 2n результатів, він набагато коротший. Для деяких PRNG тривалість може бути розрахована без обходу всього періоду. Регістри зсуву лінійного зворотного зв`язку (LFSR) зазвичай вибираються так, щоб мати періоди, рівні 2n − 1.

Лінійні конгруентні генератори мають періоди, які можна обчислити за допомогою факторингу. Хоча RNG будуть повторювати свої результати після того, як вони досягнуть кінця періоду, повторний результат не означає, що кінець періоду був досягнутий, оскільки його внутрішні стан може бути більшим, ніж вихід; це особливо очевидно для 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, який він використовував, метод "середнього квадрата" і здійснив процес отримання псевдовипадкових чисел в кілька сотень разів швидше, ніж відбувається зчитування чисел з перфокарт.

Метод середнього квадрата з тих пір був витіснений більш складними генераторами.

Новаторський метод

Нещодавнє нововведення-поєднати середній квадрат із послідовністю Вейля. Цей метод забезпечує високу якість продукції протягом тривалого періоду. Він допомагає отримувати кращі формули псевдовипадкових чисел.