Псевдослучайно число: методи за генериране, предимства и недостатъци

Псевдослучайно число е специално число, генерирано от специален генератор. Генераторът на псевдослучайни числа (PRNG), известен също като детерминистичен генератор на случайни числа (DRBG), е алгоритъм за генериране на последователност от числа, чиито свойства се доближават до характеристиките на последователностите от случайни числа. Последователността, генерирана от PRNG, не е наистина случайна, тъй като се определя изцяло от начална стойност - наречена начално число на PRNG - която може да включва наистина случайни стойности. Въпреки че последователности, които са по-близки до случайните, могат да бъдат генерирани с помощта на хардуерни генератори на случайни числа, генераторите на псевдослучайни числа са важни на практика заради скоростта на генериране на числата и тяхната възпроизводимост.

Приложение

PRNG са от основно значение за приложения като моделиране (напр. за методите Монте Карло), електронни игри (напр. за процедурно генериране) и криптография. Криптографските приложения изискват изходът да не може да се предвиди от предишната информация. Изискват се по-сложни алгоритми, които не наследяват линейността на простите PRNG.

Изисквания и условия

Добрите статистически свойства са основно изискване за получаване на PRNG. По принцип е необходим внимателен математически анализ, за да се гарантира, че PRNG генерира числа, които са достатъчно близки до случайните, за да отговарят на предвидената употреба.

Джон фон Нойман предупреди да не се тълкува погрешно PRNG като истински генератор на случайни числа и се пошегува, че "всеки, който смята, че аритметичните методи за производство на случайни числа са в състояние на грях".

Използване на

PRNG може да се стартира от произволно начално състояние. Той винаги генерира една и съща последователност, когато е инициализиран с това състояние. Периодът на PRNG се определя, както следва: максимален за всички начални състояния на дължината на неповтарящия се префикс на последователността. Периодът е ограничен от броя на състоянията, обикновено измерван в битове. Тъй като дължината на периода потенциално се удвоява с всеки добавен бит на състоянието, е лесно да се създадат PRNG с достатъчно големи периоди за много практически приложения.

Ако вътрешното състояние на PRNG съдържа n бита, периодът му може да бъде кратък до 2n резултата, като е много по-кратък. За някои PRNG продължителността може да се изчисли, без да се преминава през целия период. Регистрите с линейна обратна връзка (LFSR) обикновено се избират така, че периодите им да са равни на 2n − 1.

Линейните конгруентни осцилатори имат периоди, които могат да бъдат изчислени чрез факториране. Въпреки че PRNG повтарят резултатите си, след като достигнат края на периода, повтарянето на резултата не означава, че е достигнат краят на периода, тъй като вътрешното състояние може да е по-голямо от изходното; това е особено очевидно за PRNG с еднобитов изход.

Възможни грешки

Грешките, открити от дефектни PRNG, варират от невидими (и неизвестни) до очевидни. Пример за това е алгоритъмът за случайни числа RANDU, който се използва от десетилетия в мейнфреймовете. Това е сериозен недостатък, но неговата неадекватност остава незабелязана за дълъг период от време.

В много области научните трудове, в които са използвани случаен подбор, симулации Монте Карло или други методи, базирани на PRNG, са много по-малко надеждни, отколкото биха могли да бъдат получени в резултат на използването на некачествен PRNG. Дори и днес понякога се изисква предпазливост, както показва предупреждението в Международната енциклопедия по статистически науки (2010 г.).

Пример за успешно приложение

Като илюстрация, разгледайте широко използвания език за програмиране Java. Към 2017 г. Java все още разчита на линейния конгруентен генератор (LCG) за своя PRNG.

История

Първият PRNG, който избягва сериозни проблеми и все пак работи доста бързо, е Mersenne Twister (разгледан по-долу), публикуван през 1998 г. Оттогава са разработени и други висококачествени PRNG.

Но историята на псевдослучайните числа не свършва дотук. През втората половина на 20-ти век стандартният клас алгоритми, използвани за PRNG, включва линейни конгруентни генератори. Знаеше се, че качеството на LCG е недостатъчно, но не бяха налични по-добри методи. Press et al (2007) описват резултата по следния начин: "Ако всички научни статии, чиито резултати са съмнителни заради [LCG и свързаните с тях], изчезнат от библиотечните рафтове, на всеки рафт ще има празнина с размерите на юмрука ви.".

Голям напредък в създаването на псевдослучайни генератори е въвеждането на методи, основани на линейна повторяемост в полето на два елемента; такива генератори са свързани с линейни преместващи регистри с обратна връзка. Те са служили основание за изобретения на генератори на псевдослучайни числа.

По-специално, изобретението на Mersen Twister от 1997 г. избягва много от проблемите с по-ранните генератори. Периодът на Мерсенския туистър е 219937−1 итерации (≈4,3 × 106001). доказано равномерно разпределение в (до) 623 измерения (за 32-битови стойности), а по време на въвеждането му е бил по-бърз от други статистически базирани генератори, генериращи псевдослучайни последователности от числа.

През 2003 г. Джордж Марсалия представя фамилия генератори на ксоршифти, също базирани на линейно повторение. Такива генератори са изключително бързи и - в комбинация с нелинейна работа - преминават строги статистически тестове.

През 2006 г. беше разработена фамилия генератори WELL. Генераторите WELL подобряват в известен смисъл качеството на Twister Mersenne, който има твърде голямо пространство на състоянията и много бавно възстановяване от него, като генерира псевдослучайни числа с голям брой нули.

Криптография

PRNG, подходящ за криптографски приложения, се нарича криптографски защитен PRNG (CSPRNG). Изискването към CSPRNG е нападателят, който не знае началното число, да има само малко предимство при разграничаването на изходната последователност на генератора от случайната последователност. С други думи, докато от PRNG се изисква да премине само определени статистически тестове, CSPRNG трябва да премине всички статистически тестове, които са ограничени до полиномиално време по отношение на размера на семената.

Въпреки че доказателството на това свойство е извън сегашното ниво на теорията на изчислителната сложност, убедително доказателство може да бъде предоставено чрез свеждане на CSPRNG до проблем, който се счита за сложен, подобно на факторизацията на цели числа. Като цяло може да отнеме години преглед, преди даден алгоритъм да бъде сертифициран като CSPRNG.

Доказано е, че е вероятно NSA да е вмъкнала асиметрична задна врата в сертифицирания от NIST генератор на псевдослучайни числа Dual_EC_DRBG.

Алгоритми за псевдослучайни числа

Повечето алгоритми за PRNG произвеждат последователности, които са равномерно разпределени чрез някой от няколко теста. Това е отворен въпрос. Това е един от основните въпроси в теорията и практиката на криптографията: има ли начин да се разграничи изходът на висококачествен PRNG от наистина случайна последователност? При тази настройка разпознаващото устройство знае, че е използван или известен PRNG алгоритъм (но не и състоянието, с което е инициализиран), или е използван наистина случаен алгоритъм. Тя трябва да прави разлика между двете.

Сигурността на повечето криптографски алгоритми и протоколи, използващи PRNG, се основава на предположението, че е невъзможно да се разграничи прилагането на подходящ PRNG от използването на наистина случайна последователност. Най-простите примери за тази зависимост са поточните шифри, които най-често работят, като изключват или изпращат съобщения с обикновен текст с изхода на PRNG, създавайки шифров текст. Проектирането на подходящи от криптографска гледна точка PRNG е изключително трудно, тъй като те трябва да отговарят на допълнителни критерии. Размерът на периода е важен фактор за криптографската пригодност на PRNG, но не е единственият.

Ранна компютърна PRNG, предложена от Джон фон Нойман през 1946 г., известна като метод на средните квадрати. Алгоритъмът е следният: взема се произволно число, прави се квадрат, премахват се средните цифри на полученото число като "случайно число", след което това число се използва като начално число за следващата итерация. Например, ако числото 1111 се раздели на квадрати, ще се получи 1234321, което може да се запише като 01234321, а 8-цифрено число е квадрат на 4-цифрено число. Това дава 2343 като "случайно" число. Резултатът от повторението на тази процедура е 4896 и т.н. Фон Нойман използва 10-цифрени числа, но процесът е същият.

Недостатъци на "средния квадрат

Проблемът с метода "среден квадрат" е, че всички последователности се повтарят, някои от тях много бързо, например: 0000. Фон Нойман е знаел това, но е смятал, че подходът е достатъчен за целите му, и се е притеснявал, че математическите "поправки" просто ще скрият грешките, а няма да ги отстранят.

Фон Нойман смята, че хардуерните генератори на случайни и псевдослучайни числа са неподходящи: ако не записват генерирания изход, те не могат да бъдат проверени по-късно за грешки. Ако запишат резултатите си, ще изчерпат ограничената памет на компютъра и съответно способността му да чете и записва числа. Ако числата бяха написани на карти, писането и четенето им щеше да отнеме много повече време. На компютъра ENIAC той използва метода на "средния квадрат" и извършва процеса на получаване на псевдослучайни числа няколкостотин пъти по-бързо от четенето на числа от перфокарти.

Оттогава методът на средния квадрат е заменен от по-усъвършенствани генератори.

Иновативен метод

Неотдавнашно нововъведение - комбиниране на средния квадрат с последователността на Вайл. Този метод осигурява високо качество на продукцията за дълъг период от време. Той помага да се получат най-добрите формули за псевдослучайни числа.