Псевдослучайно число е специално число, генерирано от специален генератор. Генераторът на детерминирани произволни битове (PRNG), известен също като генератор на детерминирани произволни битове (DRBG), е алгоритъм за генериране на поредица от числа, чиито свойства се доближават до характеристиките на последователностите от произволни числа. Генерираната PRNG последователност не е наистина произволна, тъй като се определя изцяло от начална стойност, наречена PRNG семка, която може да включва наистина произволни стойности. Въпреки че последователности, които са по-близки до произволни, могат да бъдат генерирани с помощта на хардуерни генератори на произволни числа, генераторите на псевдослучайни числа са важни на практика за скоростта на генериране на числа и тяхната възпроизводимост.
Заявление
PRNG са централни за приложения като симулация (напр. за Монте Карло), електронни игри (напр. за процедурно генериране) и криптография. Криптографските приложения изискват изходаданните не бяха предвидими от по-ранна информация. Необходими са по-сложни алгоритми, които не наследяват линейността на простите PRNG.
Условия
Добрите статистически свойства са основно изискване за получаване на PRNG. Като цяло е необходим внимателен математически анализ, за да сте сигурни, че RNG генерира числа, които са достатъчно близки до произволни, за да бъдат подходящи за предвидената употреба.
Джон фон Нойман предупреди да не се тълкува погрешно PRNG като истински произволен генератор и се пошегува, че "Всеки, който разглежда аритметични методи за генериране на произволни числа, със сигурност е в състояние на грях."
Използвайте
PRNG може да се стартира от произволно първоначално състояние. Той винаги ще генерира една и съща последователност, когато се инициализира с това състояние. Периодът на PRNG се дефинира, както следва: максимум за всички начални състояния на дължината на префикса на неповтарящата се последователност. Периодът е ограничен от броя на състоянията, обикновено се измерва в битове. Тъй като дължината на периода потенциално се удвоява с всеки добавен бит за "състояние", е лесно да се създават PRNG с периоди, достатъчно големи за много практически приложения.
Ако вътрешното състояние на PRNG съдържа n бита, периодът му може да бъде не повече от 2n резултата, той е много по-кратък. За някои PRNG продължителността може да се изчисли, без да се заобикаля целия период. Обикновено регистрите за смяна на линейна обратна връзка (LFSRs).са избрани така, че да имат периоди, равни на 2n − 1.
Линейните конгруентни генератори имат периоди, които могат да бъдат изчислени с помощта на факторинг. Въпреки че ПЧП ще повтори резултатите си след като достигнат края на периода, повторен резултат не означава, че краят на периода е достигнат, тъй като вътрешното му състояние може да е по-голямо от изхода; това е особено очевидно за PRNGs с еднобитов изход.
Възможни грешки
Грешките, открити от дефектни PRNG, варират от фини (и неизвестни) до очевидни. Пример е алгоритъмът за произволни числа RANDU, който се използва на мейнфреймове от десетилетия. Това беше сериозен недостатък, но неговата неадекватност остана незабелязана за дълъг период от време.
В много области изследователските проучвания, които са използвали произволен подбор, симулации на Монте Карло или други методи, базирани на RNG, са много по-малко надеждни, отколкото биха могли да бъдат резултат от лошо качество на GNPG. Дори днес понякога се изисква предпазливост, както се вижда от предупреждението в Международната енциклопедия на статистическите науки (2010).
Успешен казус
Като илюстрация, разгледайте широко използвания език за програмиране Java. От 2017 г. Java все още разчита на линейния конгруентен генератор (LCG) за своя PRNG.
История
Първата PRNG, която избягва сериозни проблеми и продължава да работи доста бързо,беше Mersenne Twister (обсъден по-долу), който беше публикуван през 1998 г. Оттогава са разработени други висококачествени PRNG.
Но историята на псевдослучайните числа не свършва дотук. През втората половина на 20-ти век стандартният клас алгоритми, използвани за PRNG, включваше линейни конгруентни генератори. Качеството на LCG беше известно като недостатъчно, но не бяха налични по-добри методи. Press et al (2007) описват резултата по следния начин: „Ако всички научни статии, чиито резултати са под съмнение поради [LCGs и свързаните], изчезнат от рафтовете на библиотеката, на всеки рафт ще има празнина с размера на юмрука ви.“
Основното постижение при създаването на псевдослучайни генератори е въвеждането на методи, базирани на линейно рекурентно поле в двуелементно поле; такива осцилатори са свързани към регистри за смяна на линейна обратна връзка. Те послужиха като основа за изобретяването на сензори за псевдослучайни числа.
По-специално, изобретението от 1997 г. на Mersen Twister избягва много от проблемите с по-ранните генератори. Mersenne Twister има период от 219937−1 итерации (≈4,3 × 106001). Доказано е, че е равномерно разпределен в (до) 623 измерения (за 32-битови стойности) и към момента на въвеждането му е бил по-бърз от други статистически звукови генератори, които произвеждат псевдослучайни числа.
През 2003 г. Джордж Марсалия представи семейство генератори на xorshift, също базирани на линейно повторение. Тези генератори са изключителноса бързи и - в комбинация с нелинейна операция - преминават строги статистически тестове.
През 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 той използва метода „среден квадрат“и извършва процеса на получаване на псевдослучайни числа няколкостотин пъти по-бързо от четенето на числа от перфокарти.
Средният квадрат оттогава е заменен от по-сложни генератори.
Иновативен метод
Наскоро нововъведение е комбинирането на средния квадрат с последователността на Weil. Този метод осигурява висококачествени продукти вътредълъг период. Помага да получите най-добрите формули за псевдослучайни числа.
