Генератор псеудослучајних бројева

Генератор псеудослучајних бројева (ГПСБ), још познат под називом детерминистичким генератором случајних битова,^[1] је алгоритам за генерисање секванци бројева који треба да апроксимирају особине секвенци случајних бројева. Секвенца генерисана овим алгоритмом није стварно случајна, зато што је потпуно одређена релативно малим бројем почетних вредности, које се називају семеном случајних бројева (које могу да задрже стварно случајне вредности). Иако секвенце које су ближе случајним бројевима генерисане хардверским генератором случајних бројева, генератор псеудо случајних бројева су битнији у пракси због своје брзине и моћи репродукције.^[2]

Генератори псеудо случајних бројева су кључни у апликацијама као што су симулатори (на пример Метода Монте Карло), електронске игре (за генерисанје процедура), и криптографију. Криптографске апликације захтевају да излаз буде непредвидив у зависности од ранијих излаза, и деталјније алгоритме, који не наслеђују линеарност простијих генератора псеудо случајних бројева.

Добре статистичке особине су кључни за излаз генератора псеудо случајних бројева. Генерално, пажљива математичка анализа је потребна да би били сигурни да ће генератор псеудо случајних бројева генерисати бројеве који су приближно случајни, да би били примењиви. Џон фон Нојман је упозоравао да не треба такве генераторе не треба поистоветити са генератором стварно случајних бројева, и кроз шалу је рекао #Свако ко разматра да генерисање случајних бројева аритметичким методама је, наравно, грешан.#^[3]

Периодичност

Генератор псеудо случајних бројева може бити покренут од произвољног почетног стања коришћењем стања семена. Увек ће да генерише исту секвенцу када је иницијализован на то стање. Период генератора псеудо случајних бројева је дефинисан на следећи начин: максимум, који је одређен за сва почетна стања, свих дужина непоновљивих префикса секвенце. Период је ограничен бројем стања, најчешће мерених у битовима. Зато што се дужина периоде потенцијално удвостручава са сваким додатим битом стања, лако је направити генератор псеудо случајних бројева са периодама довољно дугим за практичну примену у апликацијама.

Ако унутрашње стање генератора псеудо случајних бројева садржи n битова, његова периода не може бити већа од 2ⁿ а може бити и краћа. За неке генераторе псеудо случајних бројева, дужина периоде се може израчунати без проласка кроз целу периоду. Линеарни регистар померања са повратним подацима често имају тачно 2ⁿ−1 периоду.Линеарно конгруентни генератори имају периоде који се могу израчунати факторисањем. Иако генератори псеудо случајних бројева понављају резултате када дођу до краја њихове периоде, поновљени резултат не указује да се дошло до краја периоде, пошто унутрашње стање може бити веће од његовог излаза; ово је очигледно код генератора псеудо случајних бројева са једнобитним излазом.

Већина алгоритама генератора псеудо случајних бројева производе секванце које су униформално дистрибуиране од стране било ког теста. Једно од кључних питања у криптографији је да ли је могуће да се излаз који је генерисан јако квалитетним генераторима псеудо случајних бројева може разликовати од стварно случајне секвенце, без познавања детаља коришћеног алгоритма и стање на које је иницијализовано. Безбедност већине Криптографских алгоритама који користе генератор псеудо случајних бројева је базирана на претпоставци да је немогуће разазнати секвенцу генерисану генератором псеудо случајних бројева од стварно случајне секвенце. Дизајн генератора псеудо случајних бројева који је адекватан за криптографију је крајње сложен, зато што морају да испуне додатне критеријуме. Величина њене периоде је битан фактор за криптографску адекватност једног генератора псеудо случајних бројева, али не и једини.

Потенцијални проблеми детерминистичких генератора

У пракси излаз већине генератора псеудо случајних бројева испољава грешку која проузрокује да не прође статистичке тест обрасце. Они укључују:

Краћи него очекиване периоде за нека стања семена (које у том контексту могу бити "слаба")
Недостатак униформости дистрибуције великог броја генерисаних бројева
Узајамност узастопних вредности
Слаба димензиона дистрибуција излазних секвенци
Тамо где се одређене вредности појављују, дужине између њих се дистрибуирају другачије од оних који се дистрибуирају у случајним секвенцама

Дефекти који се јављају код неисправног ГПСБ-ова варијају од оних који су неприметни (и непозанти) до оних који су јако очигледни. Пример је рецимо РАНДУ алгоритам за случајние бројеве који се користио деценијама за мејнфрејм рачунаре. Био је јако оштећен, али његова исправност је прошла неприметно дуго времена.

У Разним пољима, доста истраживања налик овима из 21 века која се ослањају на случајну селекцију или на Монте Карло симулатор, или у било ком облику ослањају на ГПСБ-ве, су мање поуздана него да су користили ГПСБ-ве слабог квалитета. Чак је и данас потребна опрезност, као што је илустриовано на следећем упозорењу, које је дато из Интернационалне Енциклопедије Статичке Науке (2010).^[4]

Листа често коришћених генератора који би се требало одбацити (дуго)... Погледајте нормално стање (ГПСБ) вашег омиљеног софтвера и спремите се да га замените ако треба. Последња препорука се давала сваки пут последљих 40 година. Штавише, она је остала на снази и данас после 40 година.

Као илустрација, размотрите јако коришћен програмски језик Јава. Од 2016. годинем Јава још увек зависи од линеарно конгруетног генератора(ЛКГ) због његовог ГПСБ-а^[5] који није криптографски заштићен, али су ЛКГ још увек слабог квалитета – погледајте даље испод.

Први ГПСБ који је избегао велике проблеме и још увек ради сасвим брзо је Мерсенов Твистер,^[6] који је обављен 1998. године. Од тада се производе ГПСБ-ови високог квалитета.

Генератори базирани на линеарној рекуретности

У другој половини 20. века, стандардну класу алгоритама коришћену за ГПСБ су чинили линеарно конгруетни генератори. Знало се да је квалитет ЛКГ био неадекватан, али се није знало за боље методе. Штампа et al.(2007) је описала резултате на следећи начин: ``Да су све научне новине чији су резултати у недоумици због (ЛКГ-ова или слично) нестале са полица библиотека, постајала би рупа на свакој полици величине ваше песнице``.^[7] Огроман напредак у конструкцији генератора за пседуслучајне бројеве се постигао коришћенем технике на линеарној рекуретности на пољу два елемента: као на пример генератори везани за линеарне регистре са повратним подацима. Мерсенов Твистер, изум из 1997. године, је практично избегавао разне проблеме везане за раније генераторе.

Следећа је ВЕЛ фамилија генератора.^[8] ВЕЛ генератори на неки начин побољшавају квалитет Мерсеновог Твистера – који има превелики размак стања и јако спор темпо опоравка од стања размака са великим бојем нулама.

Године 2003, Џорџ Марсаглија је увео фамилију xorshift генератора,^[9] again based on a linear recurrence. Such generators are extremely fast and, combined with a nonlinear operation, they pass strong statistical tests.^[10] који су опет били базирани на линеарној рекуретности. Такви генератори су екстремно брзи и у комбинацији са не линеарним опрецијама пролазе ригурозне статичке тестове.

Криптогорафски заштићени пседуослучајни генератори бројева

ГПСБ који би био погодан за криптографске апликације се зове криптографски засштићен ГПСБ(КЗГПСБ). Док је ГПСБ-у неопходно само да прође одређене статичке тестове, КЗГПСБ мора проћи све статичке тестове који су ограничени у полиномијалном времену величине семена. Иоако се овако не може доказати, може се добити солидан доказ тако што ће се КЗГПСБ свести на математички проблем који је сматран тешким, као рецимо разлагање целих бројева на просте факторе.^[11]

Неке класе КЗГПСБ укључују следеће:

Стрим шифре
Блокиране шифре које броје^[12] или повратни мод за излаз
ГПСБГО-обе који су дизајнирани специјално за криптографско заштићене, као рецимо Мајкрософтова функционалност програмског интефекса за криптографксе апликације зване CryptGenRandom, Yarrow алгоритам(инкопорисан у Mac OS X и FreeBSD) и Фортуна
Комбинација ГПСБ-ова који покушавају да споје неколико ГПСБ примитивних алгоритама са циљем да уклоне све што није случајно.
Специјални дизајн базиран на тешким математичким претпоставкама. Примери су рецимо генертор Micali-Schnorr и Blum Blum Shub алгоритам, који пружају снажан безбедносни доказ. Овакви алгоритми су обично спори за разлику од традиционално изграђених, и непрактични за већину апликација.

Показало се највероватније да је НСА убацио асиметрична задња врата у НИСТ потвређени генератор за псеудослучајне бројеве DUAL_EC_DRBG.^[13]

БСИ критерија евалуације

Немачка федерација за заштиту инфромација је поставила 4 критеријума за квалитет детерминистичких генератора за псеудо случајне бројеве.^[14] Овде су сажети:

К1 – Секвенца случајних бројева са ниском вероватноћом да садржи идентичне узастопне елементе.
К2 – Секвенца бројева која се не може разликовати од „правих случајних“ бројева према специфичним статичким тестовима. Тестови су монобитни тестови (исти број нула и јединица у секвенци), покер тест (специјална инстанца од чи-коцкастог теста), тестови на пролазе (броји фреквенцију пролаза различитих дужина), тестови на дуге пролазе (гледа да ли постоји било какав пролаз дужине 34 или више у 20 000 битова секвенце) – ове из БСИ^[14] и НИСТ,^[15] и аутокоректион тестови У суштини, ови захтеви су тестлалп ће добро бит секвенца: има нуле и јединице подједнако често; после секвенце од н нула (или јединица), следећи бит јединицу (или нулу) са пола вероватноће; и било која изабрана подсеквенца не садржи о следећем елементу или елементима у секвенци.
К3 – требало би бити немогуће за било ког нападача да процени, или пгодои, из било које дате подсеквенце, било које претходне или будуће вредности у секвенци; нити било какво унутрашње стање генератора.
К4 - требало би бити немогуће за било ког нападача да процени, или погоди из унутрашњег стања генератора, било које претходне бројеве у секвенци или било које претходно унутрашње стање генератора.

За апликације базиране на криптографији, било који генератор који задовољава К3 и К4 стандарде је прихватљив.

Математичка дефиниција

Дати су:

$P$ – дистрибуција вероватноће на $\left(\mathbb {R} ,{\mathfrak {B}}\right)$ (где је ${\mathfrak {B}}$ стандардно Борелово поље на реалној правој)
${\mathfrak {F}}$ – непразан скуп Борелових скупова ${\mathfrak {F}}\subseteq {\mathfrak {B}}$ , нпр ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ . Ако ${\mathfrak {F}}$ није дефинисано, могло би бити или ${\mathfrak {B}}$ или $\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ , у зависности од контекста.
$A\subseteq \mathbb {R}$ – непразан скуп (не неопходно Борелов скуп). Често $A$ је скуп између $P$ -ове подршке и њене унутрашњости, на пример, ако је $P$ униформна дистрибуција на интервалу $\left(0,1\right]$ , $A$ може бити $\left(0,1\right]$ . Ако $A$ није дефинисано, претпоставља се да је скуп који се састоји у подршци од $P$ и садржи унутрашњост, у зависности од контекста.

Функцију $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ (где је $\mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ скуп позитивних целих бројева) називамо генератором псеудо-случајних бројева за $P$ дато ${\mathfrak {F}}$ које узима вредности у $A$ акко:

$f\left(\mathbb {N} _{1}\right)\subseteq A$
$\forall E\in {\mathfrak {F}}\quad \forall 0<\varepsilon \in \mathbb {R} \quad \exists N\in \mathbb {N} _{1}\quad \forall N\leq n\in \mathbb {N} _{1},\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon$

( $\#S$ означава број елемената у бесконачном скупу $S$ .)

Може се доказати да ако је $f$ генератор псеудо-случајних бројева за униформну дистрибуцију на $\left(0,1\right)$ и ако је $F$ Функција дистрибуције неке дате дистрибуције вероватноће $P$ , онда $F^{*}\circ f$ је генератор псеудо случајних бројева за $P$ , где $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ је перцентил од $P$ , нпр $F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}$ . Интуитивно, арбитрарна дистрибуција се може симулирати помоћу симулације стандардне униформне дистрибуције.

Рани приступи

Један рани генератор псеудо случајних бројева, који се заснива на рачунару, који је предложен од стране Џона фон Нојмана 1946. године, је познат као метода са средњим квадратом. Алгоритам тече овако: узме се било који број, дигне се на квадрат, уклоне се средње цифре резултијућег броја, које представљају насумични број, онда се тај број искористи као семе за следећу итерацију. На пример, квадрирање броја "1111" ствара број "1234321", који може да се запише као "01234321", осмоцифрени број који је квадрат једног четвороцифреног броја. Одавде се добија насумичан број "2343". Ако поновимо поступак, добијамо 4896 и тако даље. Фон Нојман је користио десетобитне бројеве, али је процес био исти.

Проблем са овом методом је то да се све секвенце евентуално понављају, неке веома брзо, попут "0000". Фон Нојман је био свестан тога, али је сматрао да је тај приступ задовољавао његове потребе, и бринуо се да би "математичке поправке" сакриле грешке, а не уклониле.

Фон Нојман је сматрао да су хардверски генератори случајних бројева неприкладни, јер нису могли да забележе генерисани излаз, премда нису могли бити тестирани. Да су забележавали излазе, они би потрошили сву ограничену рачунарску меморију која је тада била доступна и онеспособили рачунар да чита и пише бројеве. Да су бројеви записивани на картицама, време читања и писања би било много дуже. На ENIAC рачунару је користио бројеве генерисане овом методом сто пута већом брзином него читање са бушених картица.

Метода средњег квадрата је од тада замењена сложенијим генераторима.

Неуједначени генератори

Бројеви који потичу из неуједначене дистрибуције вероватноће могу се генерисати генератором псеудо случајних бројева за уједначену расподелу и помоћу функције која ствара релацију имеђу те две расподеле.

Прво нам је потребна функција расподеле $F(b)$ циљне расподеле $f(b)$ :

F(b)=\int _{-\infty }^{b}f(b')db'

Приметимо да је $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ . Коришћењем насумичног броја c из уједначене расподеле како густина вероватноће "пролази", добијамо:

F(b)=c

тако да

b=F^{-1}(c)

је број насумично одабран из расподеле $f(b)$ .

На пример, инверз кумулативне нормалне расподеле $\operatorname {erf} ^{-1}(x)$ са идеалним уједначеним генератором псеудо случајних бројева са доменом (0, 1), улаз $x$ би произвео (само позитивну) секванцу вредности са нормалном расподелом; међутим:

када се користе практичне репрезентације бројева, бесконачни "репови" расподеле морају бити заокружени на коначне вредности.
Изновна израчунавања $\operatorname {erf} ^{-1}(x)$ би требало свести на нешто као зигурат алгоритам за брже израчунавање.

Слична разматрања се примењују на генерисање других неуједначених расподела као што су Рејли и расподела.

Референце

^ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (2012). „Recommendation for Key Management” (PDF). NIST Special Publication 800-57. NIST. Приступљено 19. 8. 2013.
^ „Pseudorandom number generators”. Khan Academy. Приступљено 11. 1. 2016.
^ Von Neumann, John (1951). „Various techniques used in connection with random digits” (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36—38.
^ L'Ecuyer P. (2010), "Uniform random number generators", International Encyclopedia of Statistical Science (editor – Lovric M.) Springer.
^ Random.java at OpenJDK.
^ Matsumoto, Makoto; Nishimura, Takuji (1998). „Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator”. ACM Transactions on Modeling and Computer Simulation. ACM. 8 (1): 3—30. doi:10.1145/272991.272995.
^ Press et al. (2007) §7.1
^ Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006). „Improved long-period generators based on linear recurrences modulo 2”. ACM Transactions on Mathematical Software. 32 (1): 1—16. doi:10.1145/1132973.1132974.
^ Marsaglia, George (2003). „Xorshift RNGs”. Journal of Statistical Software. 8 (14).
^ S.Vigna. „xorshift*/xorshift+ generators and the PRNG shootout”.
^ Yan 2007, стр. 73.
^ Ferguson, Niels; Schneier, Bruce; Kohno, Tadayoshi (2010). „Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator” (PDF).
^ Matthew Green. „The Many Flaws of Dual_EC_DRBG”.
^ ^а ^б Schindler, Werner (2. 12. 1999). „Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators” (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. стр. 5—11. Архивирано из оригинала (PDF) 19. 01. 2018. г. Приступљено 19. 8. 2013.
^ „Security requirements for cryptographic modules”. FIPS. NIST. 11. 1. 1994. стр. 4.11.1 Power—Up Tests. Архивирано из оригинала 27. 5. 2013. г. Приступљено 19. 8. 2013.

Литература

Yan, Song Y. (2007). Cryptanalytic Attacks on RSA. Springer. стр. 73. ISBN 978-0-387-48741-0.
Barker E., Kelsey J., Recommendation for Random Number Generation Using Deterministic Random Bit Generators, NIST SP800-90A, January 2012
Brent R.P., "Some long-period random number generators using shifts and xors", ANZIAM Journal, 2007; 48:C188–C202
Gentle J.E. (2003), Random Number Generation and Monte Carlo Methods, Springer.
Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation, Springer-Verlag.
Knuth, Donald (1997). The Art of Computer Programming. Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley. ISBN 978-0-201-89684-8. Chapter 3. [Extensive coverage of statistical tests for non-randomness.]
Luby M. (1996). Pseudorandomness and Cryptographic Applications. Princeton Univ Press. ISBN 9780691025469.
Matthews R., "Maximally Periodic Reciprocals", Bulletin of the Institute of Mathematics and its Applications, 28: 147-148, 1992.
von Neumann J., "Various techniques used in connection with random digits," in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, 12 (Washington, D.C.: U.S. Government Printing Office, 1951): 36-38.
Peterson, Ivars (1997). The Jungles of Randomness : a mathematical safari. New York: John Wiley & Sons. ISBN 978-0-471-16449-4.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. (2007), Numerical Recipes (Cambridge University Press).
Viega J., "Practical Random Number Generation in Software", in Proc. 19th Annual Computer Security Applications Conference, Dec. 2003.

Спољашње везе

TestU01: A free, state-of-the-art (GPL) C++ Random Number Test Suite.
DieHarder: A free (GPL) C Random Number Test Suite.
"Generating random numbers" (in embedded systems) by Eric Uner (2004)
"Analysis of the Linux Random Number Generator" by Zvi Gutterman, Benny Pinkas, and Tzachy Reinman (2006)
"Better pseudorandom generators" by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan (Microsoft Research, 2012)

[1] Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (2012). „Recommendation for Key Management” (PDF). NIST Special Publication 800-57. NIST. Приступљено 19. 8. 2013.

[2] „Pseudorandom number generators”. Khan Academy. Приступљено 11. 1. 2016.

[3] Von Neumann, John (1951). „Various techniques used in connection with random digits” (PDF). National Bureau of Standards Applied Mathematics Series. 12: 36—38.

[4] L'Ecuyer P. (2010), "Uniform random number generators", International Encyclopedia of Statistical Science (editor – Lovric M.) Springer.

[5] Random.java at OpenJDK.

[6] Matsumoto, Makoto; Nishimura, Takuji (1998). „Mersenne twister: a 623-dimensionally equi-distributed uniform pseudo-random number generator”. ACM Transactions on Modeling and Computer Simulation. ACM. 8 (1): 3—30. doi:10.1145/272991.272995.

[7] Press et al. (2007) §7.1

[8] Panneton, François; L'Ecuyer, Pierre; Matsumoto, Makoto (2006). „Improved long-period generators based on linear recurrences modulo 2”. ACM Transactions on Mathematical Software. 32 (1): 1—16. doi:10.1145/1132973.1132974.

[9] Marsaglia, George (2003). „Xorshift RNGs”. Journal of Statistical Software. 8 (14).

[10] S.Vigna. „xorshift*/xorshift+ generators and the PRNG shootout”.

[FOOTNOTEYan200773-11] Yan 2007, стр. 73.

[12] Ferguson, Niels; Schneier, Bruce; Kohno, Tadayoshi (2010). „Cryptography Engineering: Design Principles and Practical Applications, Chapter 9.4: The Generator” (PDF).

[13] Matthew Green. „The Many Flaws of Dual_EC_DRBG”.

[bsi_ais20-14] а ^б Schindler, Werner (2. 12. 1999). „Functionality Classes and Evaluation Methodology for Deterministic Random Number Generators” (PDF). Anwendungshinweise und Interpretationen (AIS). Bundesamt für Sicherheit in der Informationstechnik. стр. 5—11. Архивирано из оригинала (PDF) 19. 01. 2018. г. Приступљено 19. 8. 2013.

[15] „Security requirements for cryptographic modules”. FIPS. NIST. 11. 1. 1994. стр. 4.11.1 Power—Up Tests. Архивирано из оригинала 27. 5. 2013. г. Приступљено 19. 8. 2013.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]