Википедија

Генерисање случајних бројева

Генератор случајних бројева (енгл. random number generator, RNG) је рачунарски или физички уређај дизајниран да генерише низ бројева или симбола који се не могу разумно предвидети боље него што би случајношћу.

Када се баци коцкица, добије се случајан број између 1 и 6.

Разне примене случајности су довеле до развоја више различитих метода за генерисање случајних бројева, неке од тих метода су постојале још од древних времена, укључујући коцке, бацање новчића, мешање карата, коришћење стабљика хајдучке траве за прорицање у „Ји ђингу”, и многе друге технике. Због механичке природе ових техника, генерисање великог броја довољно случајних бројева (битно у статистици) захтева пуно посла и/или времена. Тако, резултати би понекад били сакупљани и дистрибуирани као табеле случајних бројева. Данас, након доласка рачунарских генератора случајних бројева, велики број лутрија којима управљају владе су почеле да користе генераторе случајних бројева уместо традиционалнијих метода извлачења. Такође се користе за одређивање шанси модерних слот машина.[1]

Више рачунарских метода постоји за генерисање случајних бројева. Многи не успевају да достигну циљ праве случајности, иако испуњавају, са варирајућим успехом, неке од статистичких тестова случајности намењених да мере колико су непредвидиви њихови резултати (то јест, до ког степена су њихови шаблони приметни). Ипак, пажљиво дизајнирани криптографско осигурани методи генерисања случајних бројева такође постоје, као што су они који су засновани на алгоритму хајдучке траве, Фортуна (ГПНБ), и други.

Практичне примене и употребе уреди

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

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

Генерисање псеудо случајних бројева је битан и чест задатак у програмирању. Док криптографија и одређени нумерички алгоритми захтевају веома висок степен псеудо случајности, многе друге операције захтевају само скромну количину непредвидљивости. Неки прости пример би могао бити приказивање кориснику „Случајни цитат дана”, или одређивање којим путем би се компјутерски контролисан непријатељ кретао у видео игри. Слабији облици случајности се користе у хеш алгоритмима и у прављењу амортизованих претрага и алгоритама за сортирање.

Неке примене које на први поглед изгледају да су прикладне за случајност у ствари нису тако просте. На пример, систем који "случајно" одабира песме за позадинску музику мора само да изгледа случајно, и можда чак има начине да контролише избор музике: прави случајни систем не би имао ограничења да се иста ствар појави два или три пута заредом.

"Прави" наспрам псеудо-случајних бројева уреди

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

Брзина којом ентропија може да буде сакупљена из природних извора зависи од основних физичких појава које се мере. Према томе, за изворе природних појављивања „праве” ентропије се каже да су блокирајући – они су ограничени док није сакупљено довољно захтеване ентропије. На неким системима сличним Јуниксу, укључујући већину Линукс дистрибуција, псеудо датотека /дев/рандом неће допустити читање док није сакупљено довољно ентропије из околине. Због овог блокирања, велика сједињена читања из /дев/рандом, као што је попуњавање хард диска случајним битовима, може често да успори систем који користе овај тип извора ентропије.

Друга метода користи рачунарске алгоритме који могу да произведу дуге низове од наводно случајних резултата, који су у ствари у потпуности одређени мањом почетном вредношћу, позната као семена вредност или кључ. Као резултат, укупни псеудо-случајни низ се може створити ако је семена вредност позната. Овај тип генерисања случајних бројева се често назива псеудо-случајни генератор бројева. Овај тип генератора се не ослања на природно појављивање ентропије, иако може бити периодично убачено семе од стране природних извора. Овај тип генератора не мора да блокира читање, па нису ограничени екстерним догађајима, што чини велика сједињена читања могућим.

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

Док генератор псеудо-случајних бројева базиран само на детерминистичкој логици не може никад бити класификован као „прави” извор случајних бројева у најбуквалнијем смислу речи, у пракси су довољни чак и за захтевне сигурносно-критичне апликације. Пажљиво дизајнирани и имплементирани псеудо-случајни генератори бројева могу да се користе за сигурносно-критичне криптографске сврхе, као што је случај са алгоритмом хајдучке траве и фортуном. Алгоритам хајдучке траве је основа за /дев/рандом извора ентропије на ФрееБСД, Аикс, ОС X, НетБСД и другима. ОпенБСД такође користи псеудо-случајни нумерички алгоритам заснован на ЦхаЦха20 познат као арц4рандом.

Методе генерисања уреди

Физичке методе уреди

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

Физички генератор случајних бројева може да се базира на суштински случајном атомском или субатомском физичком феномену чија непредвидивост може да се прати до закона квантне механике. Извори ентропије укључују радиоактивност, термални шум, статички шум, лавински шум у Зенер диодама, деривација сатова, темпирање покрета у тврдом диску читај/пиши главе, и радио шума. Ипак, физички феномени и алати који се користе да их мере генерално садрже асиметрије и систематске грешке које чине њихов резултат не заиста униформно случајан. Извлачивач случајности, као што је криптографска хеш функција, могу да се користе да се приближи униформној расподели битова из неуниформног случајног извора, мада при нижој брзини битова.

Разни маштовити начини скупљања ове ентропијске информације су осмисљењи. Једна техника је да се покрене хеш функција на једну слику од видео стриминга из непредвидивог извора. Лаваранд је користио ову технику са сликама на којима се налази више лава лампи. ХотБитс мери радиоактивни распад са Гајгер-Милер цевима,[2] док Рандом.орг користи промене у амплитудама атмосферског шума снимљеног нормалним радиом.

Други чест извор ентропије је понашање људских корисника система. Иако се људи не сматрају добрим генератором случајности кад се то од њих захтева, они генеришу случајна понашања прилично добро у контексту играња игара помешаних стратегија. [3] Неки компјутерски софтвери у вези са безбедношћу захтевају да корисник направи подужи низ покрета миша или притиска тастатуре да се направи довољна ентропија потребна за генерисање случајних кључева или да се иницијализује псеудо-случајни генератор бројева.[4]

Рачунарске методе уреди

Већина рачунски генерисаних случајних бројева користи псеудо-случајне генераторе бројева (ПСГБ) који су алгоритми са могућношћу аутоматског генерисања дугачког низа бројева са добрим случајним својствима али се евентуално низ понавља (или количина утрошене меморије расте без граница). Овај тип случајних бројева су довољно добри у многим ситуацијама али нису случајни колико и бацање новчића или коцкица[5]. Низ вредности генерисан оваквим алгоритмима је обично одредјен фиксираном вредношћу која се назива семе (енгл. seed). Један од најраспрострањенијих ПСГБ је линеарни конгруентални генератор, који користи рекурентност

 

да би генерисао бројеве, где су  ,   анд   велики бројеви, и   је следећи у   серији псеудо-случајних бројева. Највећи број бројева које ова формула може произвести је модуло  . Да би се избегла нека не-случајна својства линеарног конгруенталног генератора, неколико таквих генератора бројева са мало друкчијим вредностима коефицијента умнозитеља  , се могу користити паралелно, са „мастер” генератором бројева који одабира између мноштво других генератора.

Метод оловке и папира за генерисање случајних бројева је такозвани метод средњег квадрата којег је за употребу предложио Џон фон Нојман. Иако је дати метод једноставан за имплементацију, његове излазне вредности су ниског квалитета и имају озбиљне недостатке, један од тих недостатака је да дати излазни низ скоро увек конвергира ка нули.

Већина програмских језика садржи функције или датотетеке заглавља са рутинама која обезбеђују генераторе случајних бројева. Они су обично дизајнирани да обезбеде случајан бајт, реч или број у покретном зарезу равномерно расподељен између 0 и 1.

Квалитет случајности ових функција датотека заглавља варира од у потпуности предвидивих излазних вредности до криптографски сигурних вредности. Уобичајен генератор случајних бројева у многим језицима, укључујући Пајтон, Руби, Р, ИДЛ и ПХП је заснован на алгоритму Мерсенне Тwистер и није довољан за криптографске намене, као што је и речено у документацији набројаних програмских језика. Такве функције датотека заглавља обично имају лоша статистичка својства и неке ће понављати шаблоне након само неколико десетина хиљада покушаја. Ове функције се обично иницијализирају користећи часовник самог рачунара као семе, пошто такав часовник обично израчунава време у милисекундама, што је далеко више од прецизности човека. Дате функције могу да обезбеде довољно случајности за неке задатке (нпр. видео игре) али су неприкладне за задатке који захтевају случајност високог квалитета, као што је случај у криптографији, статистици и нумеричкој анализи.

Извори случајних бројева много вишег квалитета су доступни на већини оперативних система; нпр. /дев/рандом на многим Јуникс базираним оперативним системима као што су, Линукс, ОС X, ИРИКС и Соларис, или ЦрyптГенРандом за Wиндоwс. Већина програмских језика, укључујући горе наведене, обезбеђују начине за генерисање високо квалитетних случајних бројева.

Генерисање из расподеле вероватноће уреди

Постоји неколико метода генерисања случајног броја базираних на расподели вероватноће. Ове методе укључују трансформисање (униформног) случајног броја на неки начин. Због овога, дате методе раде подједнако добро и приликом генерисања псеудо-случајних бројева и „правих” случајних бројева. Једна метода, која се назива метода инверзије, укључује интегрисање до површине веће или једнаке случајном броју (која би требала да буде генерисана измедју 0 и 1 ради правилне расподеле). Друга метода, која се назива метода прихватања-одбијања, укључује одабирање   и   вредности и тестирања да ли је функција од   већа од вредности  . Ако јесте, прихвата се вредност  , у сурпотном   вредност се одбија и алгоритам се покреће поново.[тражи се извор][6]

Ручне методе уреди

Генерисање случајних бројева се може обавити од стране људи, разне улазне вредности се прикупљају од крајњих корисника и користе као извор за генерацију случајности. Медутим, већина истраживања су пронашла да људи имају неки степен предвидивости приликом покушаја генерисања случајног низа нпр. бројева или слова.[7]. Тако да овај приступ није у широкој употреби.

Накнадно процесирање и статистичке провере уреди

Чак и када је дат извор вероватно случајних бројева (дат од стране генератора заснованих на квантној механици), добијање бројева који су у потпуности случајни захтева обазривост. Поред тога, понашање ових генератора се често мења уједно са температуром, волтажом напајања, старошћу уређаја или услед других спољашњих фактора. Слично томе, софтверски баг у алгоритму за генерисање псеудо-случајних бројева, или хардверски баг у хардверу на коме генератор ради, може бити компликован за откривање.

Генерисани случајни бројеви су понекад изложени статистичким проверама пре употребе да би се гарантовало да основни извор још увек ради, а онда се тај низ бројева и накнадно процесуира да би се побољшала његова статистичка својства. Пример би био TRNG9803[8] уређај за генерисање слуцајних бројева, који користи величину ентропије као хардверски тест, а онда накнадно процесуира случајни низ померачко регистарским шифрантом. Обично је тешко користити статистичке тестове ради валидације генерисаних случајних бројева. Ванг и Никол [9] су предложили методу статистичког тестирања базираног на дистанци како би се установиле слабости неких генератора случајности.

Остала разматрања уреди

Случајни бројеви равномерно расподељени између 0 и 1 могу бити коришћени за генерисање случајних бројева било које жељене расподељености њиховим провлачењем кроз инверзну функцију расподеле жељене расподеле (погледати Инверсе_трансформ_самплинг). Инверзне функције расподеле се такође називају квантилне функције. Да би се генерисао пар статистички независних нормално расподељених случајних бројева (x, y), прво је потребно генерисати поларне координате (р, ϴ), где је р~χ22 и θ~униформно(0,2π) (погледати Бокс-Милер трансформацију).

Неки 0 до 1 генератори случајних бројева укључују 0 али искључују 1, док други укључују или искључују оба.

Излази већег броја независних генератора случајних бројева се могу комбиновати (на пример, употребом битовске операције ексклузивне дисјункције) да би се обезбедила случајност бројева која је добра бар толико колико је добар најбољи од појединачних генератора случајних бројева. Ово се још и назива бељење софтвера.

Рачунски и хардверски генератори случајних бројева се некада комбинују ради одражавања квалитета оба типа. Рачунски генератори обично генеришу псеудо-случајне бројеве много брже него хардверски генератори, док хардверски генератори могу генерисати „праву случајност”.

Слабо дискрепантни низови као алтернатива уреди

Нека израчунавања која користе генераторе случајних бројева се могу сажети на израчунавања коначне или средње вредности, као што су израчунавања интеграла Монте Карловом методом. За овакве проблеме могуће је наћи прецизнија решења употребом низова мале недоследности који се још називају квази-случајним бројевима. Такви низови имају одређени образац који равномерно попуњава празнине, квалитативно говорећи; прави случајни низ може имати, а обично и има, веће празнине.

Активности и демонстрирања уреди

Наведене странице обезбеђују узорке случајних бројева:

  1. СОЦР садржи бројне интерактивне активности и демонстрације генерисања случајних бројева употребом Јава аплета.
  2. Квантна Оптичка Група (енгл. The Quantum Optics Group) на АНУ генерише случајне бројеве пореклом из квантног вакуума. Ви можете скинути примерак случајних бројева посетом њихове странице истраживања квантних генератора случајних бројева.
  3. Рандом.Орг Архивирано на сајту Wayback Machine (5. јун 2020) генерише случајне бројеве чији је извор случајност у атмосферском шуму. Посетите њихову страницу Архивирано на сајту Wayback Machine (24. фебруар 2011) да бисте добили узорак.
  4. Qуантум Рандом Бит Генератор Сервице на Институту Руђер Бошковић прикупља случајност из квантног процеса емисије фотона у полупроводницима. Они обезбеђују разноврсне начине прикупљања податакам, укључујуци и датотеке заглавља за неколико програмских језика.

Бекдор уреди

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

Сматра се да је Државна безбедносна служба (енгл. National Security Agency / NSA) уметнула бекдор у НИСТ-ов криптографски безбедан генератор бројева Дуал_ЕЦ_ДРБГ. Ако се на пример SSL веза формира користећи овај генератор случајних бројева, онда би по Метју Грину то омогућило НСА да одреди стање генератора случајних бројева, и тиме евентуално буде у стању да очита све податке послате преко SSL везе.[10] Иако је било очигледно да је Дуал_ЕЦ_ДРБГ био јако лош и могуће је да је био бекдорован још дуго пре него што је NSA бекдор био потврђен 2013, дати алгоритам је видео значајну употребу у пракси до 2013, на пример од стране истакнуте безбедносне компаније RSA Security[11]. Потом је било и оптужби да је RSA Обезбеђење намерно укључило НСА бекдор у своју продукцију. RSA је порекла намерно укључивање бекдора у своје производе.[12]

Такође је било теоретисано да се хардверски генератори случајних бројева могу тајно модификовати да имају мањи степен ентропије него што је наведено, што би довело до тога да енкрипција користећи хардверске генераторе случајних бројева буде подлежна нападима. Један од таквих метода који је публикован ради модификовањем чипа, што би било неприметно оптичком обрнутом-инжењерингу.[13] На пример, за генерисање случајних бројева на Линуксу, сматра се неприхватљивим да се користи Интелов РдРанд хардвер генератор случајних бројева без мешања РдРанд излаза са другим изворима ентропије да би се неутралисао било који бекдор у хардверском генератору случајних бројева, посебно након открића НСА-овог Булран програма.[14][15]

Референце уреди

  1. ^ „Интродуцтион то Слот Мацхинес”. слотсвариатионс.цом. Архивирано из оригинала 12. 03. 2010. г. Приступљено 14. 5. 2010. 
  2. ^ Wалкер, Јохн. „ХотБитс: Генуине Рандом Нумберс”. Приступљено 27. 6. 2009. 
  3. ^ Халприн, Ран; Наор, Мони. „Гамес фор Еxтрацтинг Рандомнесс” (ПДФ). Департмент оф Цомпутер Сциенце анд Апплиед Матхематицс, Wеизманн Институте оф Сциенце. Приступљено 27. 6. 2009. [мртва веза]
  4. ^ ТруеЦрyпт Фоундатион. „ТруеЦрyпт Бегиннер'с Туториал, Парт 3”. Приступљено 27. 6. 2009. 
  5. ^ „РАНДОМ.ОРГ - Труе Рандом Нумбер Сервице”. www.рандом.орг. Архивирано из оригинала 24. 02. 2011. г. Приступљено 14. 1. 2016. 
  6. ^ Тхе Нумерицал Алгоритхмс Гроуп. „Г05 – Рандом Нумбер Генераторс” (ПДФ). НАГ Либрарy Мануал, Марк 23. Приступљено 9. 2. 2012. 
  7. ^ W. А. Wагенаар (1972). „Генератион оф рандом сеqуенцес бy хуман субјецтс: а цритицал сурвеy оф тхе литературе”. Псyцхологицал Буллетин. 77 (1): 65—72. дои:10.1037/х0032060. 
  8. ^ Дöмстедт, Б. (2009). „ТРНГ9803 Труе Рандом Нумбер Генератор”. Мануфацтурер: www.ТРНГ98.се. 
  9. ^ Wанг, Yонгге (2014). „Статистицал Пропертиес оф Псеудо Рандом Сеqуенцес анд Еxпериментс wитх ПХП анд Дебиан ОпенССЛ”. Цомпутер Сецуритy - ЕСОРИЦС 2014. Лецтуре Нотес ин Цомпутер Сциенце. 8712. Хеиделберг: Спрингер ЛНЦС. стр. 454—471. ИСБН 978-3-319-11202-2. дои:10.1007/978-3-319-11203-9_26. 
  10. ^ Греен, маттхеw (18. 9. 2013). „Тхе Манy Флаwс оф Дуал_ЕЦ_ДРБГ”. 
  11. ^ Греен, Маттхеw (20. 9. 2013). „РСА wарнс девелоперс нот то усе РСА продуцтс”. 
  12. ^ „Wе дон'т енабле бацкдоорс ин оур црyпто продуцтс, РСА теллс цустомерс”. Арс Тецхница. 20. 9. 2013. 
  13. ^ „Ресеарцхерс цан слип ан ундетецтабле тројан инто Интел'с Ивy Бридге ЦПУс”. Арс Тецхница. 18. 9. 2013. 
  14. ^ Тхеодоре Тс'о. „И ам со глад I ресистед прессуре фром Интел енгинеерс то лет /дев/рандом релy онлy он тхе РдРанд инструцтион.”. Гоогле Плус. 
  15. ^ Тхеодоре Тс'о. „Ре: [ПАТЦХ] /дев/рандом: Инсуффициент оф ентропy он манy арцхитецтурес”. ЛWН. 

Литература уреди

Спољашње везе уреди

Преузето из „https://sr.wikipedia.org/w/index.php?title=Generisanje_slučajnih_brojeva&oldid=27673396”