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

Псевдовипадкове число - це особлива цифра, створювана спеціальним генератором. Генератор таких чисел (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.

генератор bbs

Алгоритми псевдовипадкових чисел

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

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

псевдовипадкові числа

Ранній комп’ютерний PRNG, запропонований Джоном фон Нейманом в 1946 році, відомий як метод середніх квадратів. Алгоритм наступний: візьміть будь-яке число, зведіть його в квадрат, видаліть середні цифри отриманого числа як “випадкове число”, а потім за допомогою це число в якості початкового для наступної ітерації. Наприклад, зведення в квадрат числа 1111 дає 1234321, яке можна записати як 01234321, 8-значний номер є квадратом 4-значного. Це дає 2343 як “випадкове” число. Результат повторення цієї процедури - 4896 і так далі. Фон Нейман використовував 10-значні числа, але процес був таким же.

Недоліки "середнього квадрата"

Проблема з методом “середнього квадрата” полягає в тому, що всі послідовності в кінцевому підсумку повторюються, деякі - дуже швидко, наприклад: 0000. Фон Нейман знав про це, але він знайшов підхід, достатній для своїх цілей, і турбувався, що математичні “ виправлення “будуть просто приховувати помилки, а не видаляти їх.

суть генератора

Фон Нейманом вважав апаратні генератори випадкових і псевдовипадкових чисел невідповідними: якщо вони не записують згенерований висновок, то не можуть бути пізніше перевірені на помилки. Якби вони записували свої результати, то вичерпали б обмежену доступну пам’ять комп’ютера і, відповідно, здатність комп’ютера читати і записувати числа. Якби числа були записані на картках, їм знадобилося б набагато більше часу, щоб писати і читати. На комп’ютері ENIAC, який він використовував, метод “середнього квадрата” і здійснив процес отримання псевдовипадкових чисел в кілька сотень разів швидше, ніж відбувається зчитування чисел з перфокарт.

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

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

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



ЩЕ ПОЧИТАТИ