Back

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




                                     

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

Генератор псеудослучајних бројева, још познат под називом детерминистичким генератором случајних битова, је алгоритам за генерисање секванци бројева који треба да апроксимирају особине секвенци случајних бројева. Секвенца генерисана овим алгоритмом није стварно случајна, зато што је потпуно одређена релативно малим бројем почетних вредности, које се називају семеном случајних бројева. Иако секвенце које су ближе случајним бројевима генерисане хардверским генератором случајних бројева, генератор псеудо случајних бројева су битнији у пракси због своје брзине и моћи репродукције.

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

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

                                     

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

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

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

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

                                     

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

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

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

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

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

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

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

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

                                     

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

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

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

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



                                     

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

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

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

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

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

                                     

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

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

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

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

                                     

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

Дати су:

  • P {\displaystyle P} – дистрибуција вероватноће на R, B {\displaystyle \left\mathbb {R},{\mathfrak {B}}\right} где је B {\displaystyle {\mathfrak {B}}} стандардно Борелово поље на реалној правој
  • F {\displaystyle {\mathfrak {F}}} – непразан скуп Борелових скупова F ⊆ B {\displaystyle {\mathfrak {F}}\subseteq {\mathfrak {B}}}, нпр F = { − ∞, t": t ∈ R } {\displaystyle {\mathfrak {F}}=\left\{\left-\infty,t\right":t\in \mathbb {R} \right\}}. Ако F {\displaystyle {\mathfrak {F}}} није дефинисано, могло би бити или B {\displaystyle {\mathfrak {B}}} или { − ∞, t": t ∈ R } {\displaystyle \left\{\left-\infty,t\right":t\in \mathbb {R} \right\}}, у зависности од контекста.
  • ∀ E ∈ F ∀ 0 < ε ∈ R ∃ N ∈ N 1 ∀ N ≤ n ∈ N 1, | # { i ∈ { 1, 2, …, n }: f i ∈ E } n − P E | < ε {\displaystyle \forall E\in {\mathfrak {F}}\quad \forall 0
  • A ⊆ R {\displaystyle A\subseteq \mathbb {R} } – непразан скуп не неопходно Борелов скуп. Често A {\displaystyle A} је скуп између P {\displaystyle P} -ове подршке и њене унутрашњости, на пример, ако је P {\displaystyle P} униформна дистрибуција на интервалу називамо генератором псеудо-случајних бројева за P {\displaystyle P} дато F {\displaystyle {\mathfrak {F}}} које узима вредности у A {\displaystyle A} акко:

    • f N 1 ⊆ A {\displaystyle f\left\mathbb {N} _{1}\right\subseteq A}

Users also searched:

...