Gjenerimi i numrave të rastësishëm

Zarat janë një shembull i një gjeneruesi mekanik të numrave të rastësishëm. Kur mbështillet një kub kub, fitohet një numër i rastësishëm nga 1 në 6.

Gjenerimi i numrave të rastësishëm është një proces përmes të cilit, shpesh duke përdorur një gjenerator të numrave të rastësishëm (RNG), një sekuencë numrash ose simbolesh gjenerohen që nuk mund të parashikohen në mënyrë të arsyeshme më mirë se rastësia e vërtetë. Kjo do të thotë se sekuenca e veçantë e rezultateve do të përmbajë disa modele të dallueshme në pamje të pasme, por të pamundura për t'u parashikuar. Gjeneratorët e vërtetë të numrave të rastësishëm mund të jenë gjeneratorë harduerikë të numrave të rastësishëm (HRNG), ku çdo gjenerim është një funksion i vlerës aktuale të atributit të një mjedisi fizik që ndryshon vazhdimisht në një mënyrë që është praktikisht e pamundur të modelohet. Kjo është në kundërshtim me "gjeneratorët e numrave të rastësishëm të quajtur" të bërë nga gjeneratorët pseudorandom (PRNG), të cilët gjenerojnë numra që duket se janë të rastësishëm, por në fakt janë të paracaktuar - këto gjenerata mund të riprodhohen thjesht duke ditur gjendjen e PRNG.

Aplikime të ndryshme të rastësisë kanë çuar në zhvillimin e metodave të ndryshme për gjenerimin e të dhënave të rastësishme. Disa prej tyre kanë ekzistuar që nga kohërat e lashta, duke përfshirë shembuj të mirënjohur si hedhja e zareve, rrokullisja e monedhave, përzierja e letrave të lojës, përdorimi i kërcellit të yarrow për hamendje në I Ching, si dhe teknika të tjera të panumërta. Për shkak të natyrës mekanike të këtyre metodave, gjenerimi i sasive të mëdha të numrave të vërtetë të rastësishëm (të rëndësishëm në statistika) kërkonte shumë punë dhe kohë. Kështu, rezultatet ndonjëherë do të mblidheshin dhe shpërndaheshin si tabela me numra të rastësishëm.

Ekzistojnë disa metoda llogaritëse për gjenerimin e numrave pseudorandom. Të gjitha këto metoda nuk arrijnë qëllimin e rastësisë së vërtetë, megjithatë disa prej tyre mund të përmbushin, me sukses të ndryshëm, disa nga testet statistikore për rastësi që synojnë të matin se sa të paparashikueshme janë rezultatet e tyre (të dallueshme modeli). Kjo në përgjithësi i bën ato të papërdorshme për aplikacione të tilla si kriptografia. Megjithatë, ekzistojnë gjithashtu gjeneratorë të numrave pseudorandom të sigurt kriptografik të dizajnuar me kujdes (CSPRNGS), me veçori të veçanta të krijuara posaçërisht për përdorim në kriptografi.

Aplikime dhe përdorime praktike

Gjeneratorët e numrave të rastësishëm kanë aplikime në lojërat e fatit, në analizën statistikore, në simulimet kompjuterike, në Kriptografia, në dizajnimin plotësisht të rastësishëm dhe në fusha të tjera ku prodhimi i një rezultati të paparashikueshëm është i dëshirueshëm. Në përgjithësi, në aplikacionet ku paparashikueshmëria është një veçori kryesore, si për shembull në aplikacionet e sigurisë, gjeneratorët e harduerit përgjithësisht preferohen mbi algoritmet pseudorandom, aty ku është e mundur.

Gjeneratorët e numrave pseudorandom janë shumë të dobishëm në zhvillimin e simulimeve të metodës Monte Carlo, pasi korrigjimi lehtësohet nga aftësia për të ekzekutuar përsëri të njëjtën sekuencë numrash të rastësishëm duke u nisur nga e njëjta farë e rastësishme. Ato gjithashtu përdoren në kriptografi - për sa kohë që fara është e fshehtë. Dërguesi dhe marrësi mund të gjenerojnë të njëjtin grup numrash automatikisht për t'i përdorur si çelësa.

Metodat e gjenerimit

Metodat fizike

Metodat më të hershme për gjenerimin e numrave të rastësishëm, të tilla si zari, rrotat e monedhave dhe ruletë, përdoren ende sot, kryesisht në lojëra dhe lojëra të fatit, pasi ato janë të njohura për të qenë shumë të ngadalta për shumicën e aplikacioneve në statistikë dhe kriptografi.

Një gjenerator fizik i numrave të rastësishëm mund të bazohet në një fenomen fizik thelbësisht të rastësishëm atomik ose nënatomik, paparashikueshmëria e të cilit mund të gjurmohet në ligjet e mekanikës kuantike. Burimet e entropisë përfshijnë zbërthimin radioaktiv, zhurmën termike, zhurmën e goditjes, zhurmën e ortekut në diodat Zener, lëvizjen e orës, kohën e lëvizjeve aktuale të kokës së leximit-shkrimit të diskut dhe zhurmën e radios. Megjithatë, fenomenet fizike dhe mjetet e përdorura për matjen e tyre në përgjithësi shfaqin asimetri dhe paragjykime sistematike që i bëjnë rezultatet e tyre jo uniformisht të rastësishme. Një ekstraktues rastësie, si një funksion hash kriptografik, mund të përdoret për t'iu qasur një shpërndarjeje uniforme të biteve nga një burim jo i njëtrajtshëm i rastësishëm, megjithëse me një shpejtësi më të ulët të biteve.

Prezentimi i burimeve të entropisë fotonike me brez të gjerë, si kaosi optik dhe zhurma e përforcuar e emetimit spontan, ka kontribuar në zhvillimin e gjeneratorit fizik të numrave të rastësishëm. Ndër ta, kaosi optik ka një potencial të lartë për të prodhuar numra të rastësishëm fizikisht me shpejtësi të lartë për shkak të gjerësisë së brezit të lartë dhe amplitudës së madhe. Një prototip i një gjeneratori bit fizik të rastësishëm me shpejtësi të lartë, në kohë reale, i bazuar në një lazer kaotik u ndërtua në vitin 2013.

Janë gjetur metoda të ndryshme kreative për të mbledhur këtë informacion entropik. Një teknikë është ekzekutimi i një funksioni hash kundër një kornize transmetimi video nga një burim i paparashikueshëm. Lavarand ka përdorur këtë metodë duke përdorur imazhe të një numri të ndryshëm të llambave. HotBits përdor zbërthimin radioaktiv me tuba Geiger-Muller, ndërsa Random.org përdor ndryshime në amplitudën e zhurmës atmosferike të regjistruar me një radio normale.

Demonstrimi i një gjeneruesi të thjeshtë të numrave të rastësishëm bazuar në vendin dhe kur klikohet një buton

Një burim tjetër i zakonshëm i entropisë është sjellja e përdoruesve njerëzorë të sistemit. Ndërsa njerëzit nuk konsiderohen gjeneratorë të mirë të rastësisë sipas kërkesës, ata gjenerojnë sjellje të rastësishme mjaft mirë në kontekstin e lojërave me strategji të përzier. Disa softuer kompjuterik të lidhur me sigurinë kërkojnë që përdoruesi të bëjë një seri të gjatë lëvizjesh të miut ose hyrjeve të tastierës për të krijuar entropi të mjaftueshme të nevojshme për të gjeneruar çelësa të rastësishëm ose për të inicializuar gjeneratorët e numrave pseudorandom.

Metodat llogaritëse

Shumica e numrave të rastësishëm të gjeneruar nga kompjuteri përdorin PRNG (Pseudorandom Number Generators), të cilët janë algoritme që mund të prodhojnë numra të gjatë me veti të mira të rastësishme, por përfundimisht sekuenca përsëritet (ose përdorimi i kujtesës rritet pa kufi). Këta numra të rastësishëm janë të dobishëm në shumë situata, por nuk janë aq të rastësishëm sa numrat e krijuar nga zhurma elektromagnetike atmosferike e përdorur si burim entropie. Seria e vlerave të gjeneruara nga algoritmet e tilla përgjithësisht përcaktohet nga një numër fiks i quajtur farë. Një nga PRNG-të më të zakonshme është gjeneratori kongruent linear, i cili përdor përsëritjen për të krijuar numra të rastësishëm.

$X_{n+1}=(aX_{n}+b)\,{\textrm {mod}}\,m$

për të gjeneruar numra, ku a, b dhe m janë numra të plotë të mëdhenj, dhe $X_{n+1}$ është tjetri në X si një seri numrash pseudorandom. Numri maksimal i numrave që formula mund të prodhojë është moduli, m . Lidhja e përsëritjes mund të zgjerohet në matrica për të pasur periudha shumë më të gjata dhe veti statistikore më të mira. Për të shmangur disa veçori jo të rastësishme të një gjeneratori të vetëm linear kongruencial, disa gjeneratorë të tillë të numrave të rastësishëm me vlera paksa të ndryshme të koeficientit të shumëzuesit, a, mund të përdoren paralelisht, me një gjenerator të numrave të rastësishëm "master" që zgjedh nga disa. gjeneratorë të ndryshëm.

Nga njerëzit

Gjenerimi i numrave të rastësishëm mund të kryhet gjithashtu nga njerëzit, duke mbledhur inpute të ndryshme nga përdoruesit përfundimtarë dhe duke i përdorur ato si një burim për rastësim. Megjithatë, shumica e studimeve zbulojnë se subjektet njerëzore kanë një mënyrë të caktuar jo të rastësisë kur përpiqen të prodhojnë një sekuencë të rastësishme, si për shembull shifra ose shkronja. Ata mund të ndërrojnë shumë midis zgjedhjeve kur krahasohen me një gjenerator të mirë të numrave të rastësishëm; prandaj, kjo qasje nuk përdoret gjerësisht.

Kontrollet pas përpunimit dhe statistikore

Edhe duke pasur parasysh një burim numrash të rastësishëm të besueshëm (ndoshta nga një gjenerator hardueri me bazë mekanike kuantike), marrja e numrave që janë plotësisht të paanshëm është e kujdesshme. Përveç kësaj, sjellja e këtyre gjeneratorëve shpesh ndryshon me temperaturën, tensionin e furnizimit me energji elektrike, vjetërsinë e pajisjes ose ndërhyrje të tjera të jashtme. Dhe një gabim në softuerin e një rutine numrash pseudorandom, ose një defekt në harduerin ku funksionon, mund të jetë po aq i vështirë për t'u zbuluar.

Numrat e rastësishëm të gjeneruar shpesh nënshtrohen testeve statistikore përpara përdorimit për të siguruar që burimi bazë ende funksionon, dhe më pas përpunohen për të përmirësuar vetitë e tyre statistikore. Një shembull i kësaj është gjeneratori i numrave të rastësishëm të harduerit TRNG9803, i cili përdor një matje entropie si një test harduer, dhe më pas përpunon sekuencën e rastësishme me një shifër të rrymës së regjistrit të zhvendosjes. Në përgjithësi, është e vështirë të përdoren teste statistikore për të vërtetuar numrat e rastësishëm të gjeneruar. Wang dhe Nicol propozuan një teknikë të testimit statistikor të bazuar në distancë që përdoret për të identifikuar dobësitë e disa gjeneratorëve të rastit. Li dhe Wang propozuan një metodë të testimit të numrave të rastësishëm bazuar në burime të entropisë kaotike lazer duke përdorur vetitë e lëvizjes Brownian.

Sekuencat me mospërputhje të ulët si një alternativë

Disa llogaritje që përdorin një gjenerator numrash të rastësishëm mund të përmblidhen si llogaritja e një vlere totale ose mesatare, siç është llogaritja e integraleve me metodën Monte Carlo. Për probleme të tilla, mund të jetë e mundur të gjendet një zgjidhje më e saktë duke përdorur të ashtuquajturat sekuenca me mospërputhje të ulët, të quajtura gjithashtu numra kuazirandom. Sekuenca të tilla kanë një model të caktuar që plotëson boshllëqet në mënyrë të barabartë, duke folur në mënyrë cilësore; një sekuencë vërtet e rastësishme mund, dhe zakonisht bën, të lërë boshllëqe më të mëdha.

Dyer të pasme

Për shkak se shumë kriptografi varet nga një gjenerator numrash të rastësishëm kriptografikisht të sigurt për krijimin e çelësit dhe nonce kriptografik, nëse një gjenerator numrash të rastësishëm mund të bëhet parashikueshmë, ai mund të përdoret si një prapavijë nga një sulmues për të thyer enkriptimin.

NSA raportohet se ka futur një derë të pasme në gjeneratorin e numrave pseudorandom, të certifikuar nga NIST, të sigurt kriptografik, Dual EC DRBG. Nëse për shembull krijohet një lidhje SSL duke përdorur këtë gjenerator të numrave të rastësishëm, atëherë sipas Matthew Green, kjo do të lejonte NSA të përcaktojë gjendjen e gjeneruesit të numrave të rastësishëm dhe në këtë mënyrë të jetë në gjendje të lexojë të gjitha të dhënat e dërguara përmes lidhjes SSL. Edhe pse ishte e qartë se Dual_EC_DRBG ishte një gjenerator numrash pseudorandom shumë të varfër dhe ndoshta me dyer të pasme shumë kohë përpara se porta e pasme e NSA të konfirmohej në 2013, ai kishte parë përdorim të konsiderueshëm në praktikë deri në vitin 2013, për shembull nga kompania e shquar e sigurisë RSA Security. Më pas ka pasur akuza se RSA Security me vetëdije ka futur një derë të pasme të NSA në produktet e saj, ndoshta si pjesë e programit Bullrun. RSA ka mohuar të ketë futur me vetëdije një backdoor në produktet e saj.

Leximi më tej

• Donald Knuth (1997). "Chapter 3 – Random Numbers". The Art of Computer Programming. Vëll. 2: Seminumerical algorithms (bot. 3).
•  Kroese, D. P.; Taimre, T.; Botev, Z.I. (2011). "Chapter 1 – Uniform Random Number Generation". Handbook of Monte Carlo Methods. New York: John Wiley & Sons. fq. 772. ISBN 978-0-470-17793-8.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Chapter 7. Random Numbers". Numerical Recipes: The Art of Scientific Computing (bot. 3rd). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Arkivuar nga origjinali më 11 gusht 2011. Marrë më 23 mars 2024.
• NIST SP800-90A, B, C series on random number generation.
• M. Tomassini; M. Sipper; M. Perrenoud (tetor 2000). "On the generation of high-quality random numbers by two-dimensional cellular automata". IEEE Transactions on Computers. 49: 1146–1151. doi:10.1109/12.888056.

Linqe te jashtme

• RASTËSISHME. ORG Shërbimi i vërtetë i numrave të rastësishëm
• Gjenerues kuantik i numrave të rastësishëm në ANU
• Random and Pseudorandom
• jRand Arkivuar 1 prill 2017 tek Wayback Machine një kornizë të bazuar në Java për gjenerimin e sekuencave simuluese, duke përfshirë sekuencat pseudoranome të numrave
• Gjeneruesit e numrave të rastësishëm në NAG Fortran Library.
• Randomness Beacon në NIST, duke transmetuar bit-vargje me entropi të plotë në blloqe prej 512 bitësh çdo 60 sekonda. Projektuar për të ofruar paparashikueshmëri, autonomi dhe qëndrueshmëri.
• Një thirrje sistemi për numra të rastit: getrandom(), një artikull LWN.net që përshkruan një thirrje të dedikuar të sistemit Linux.
• Vetitë statistikore të sekuencave pseudo të rastësishme dhe eksperimenteve me PHP dhe Debian OpenSSL
• Gjenerator i sekuencave të rastësishme bazuar në zhurmën e ortekut