Çfarë është një gjenerues numrash rastësorë?
Një gjenerues numrash rastësorë (RNG) është një sistem që prodhon numra rastësorë ose pseudorastësorë. Nëse numri tjetër mund të parashikohet vërtet, kjo varet nga lloji i gjeneruesit. Disa gjenerues bazohen në një proces fizik, disa i llogaritin numrat me anë të një algoritmi, dhe disa algoritme janë ndërtuar në mënyrë të tillë që as dikush që ka parë rezultatet e tyre të mëparshme nuk mund të parashikojë se çfarë vjen më pas. Të dukesh rastësor dhe të jesh i paparashikueshëm janë veti të ndryshme, dhe pjesa më e madhe e këtij artikulli i kushtohet pikërisht këtij dallimi.
Gjeneruesit harduerikë të numrave rastësorë
Një gjenerues harduerik i numrave rastësorë (HRNG), i quajtur gjithashtu gjenerues i vërtetë i numrave rastësorë (TRNG), i nxjerr numrat e tij nga një proces fizik. Më të vjetrit funksionojnë para syve tanë: një monedhë e hedhur në erë, një zar i hedhur, një rrotë rulete. Ligjet e mekanikës e përshkruajnë plotësisht secilin prej tyre, megjithatë një rrotë e punuar mirë mbetet e paparashikueshme në praktikë, sepse ndryshimet e vogla në mënyrën se si nis secili rrotullim shndërrohen në përfundime krejtësisht të ndryshme.
Gjeneruesit modernë harduerikë masin në vend të kësaj fenomene mikroskopike: zhurmën termike dhe zhurmën e shkrepjes (shot noise) në qarqet elektronike, zhurmën atmosferike, efektet kuantike. Këto janë burime të mira entropie — paparashikueshmërie që mund të matet —, por një burim fizik nuk është i përsosur nga natyra: ai mund të shfaqë njëanshmëri, mund të ndryshojë me kalimin e kohës dhe mund të dështojë, prandaj cilësia e tij duhet të vlerësohet dhe monitorohet, dhe rezultatet e tij të përpunohen më tej kur është e nevojshme, siç përshkruajnë standardet si NIST SP 800-90B. Burimet harduerike përdoren aty ku garancia ka më shumë rëndësi — mbi të gjitha në kriptografi, ku ato ofrojnë materialin fillestar të paparashikueshëm për çelësat pas protokolleve si Transport Layer Security (TLS).
Gjeneruesit e numrave pseudorastësorë
Alternativa ndaj një pajisjeje fizike është një algoritem. Një gjenerues i numrave pseudorastësorë (PRNG) prodhon një varg që duket rastësor, por përcaktohet plotësisht nga një vlerë fillestare (seed). Jepini të njëjtën vlerë fillestare të njëjtit algoritem dhe do të merrni të njëjtin varg çdo herë. Kjo është një dobësi kudo ku një rezultat duhet të jetë i paparashikueshëm dhe vlera fillestare ose gjendja e brendshme mund të merret me mend ose të rindërtohet, dhe një përparësi kudo ku një rezultat duhet të jetë i riprodhueshëm — një simulim ose një testim mund të përsëritet ekzaktësisht. Gjeneruesit PRNG janë gjithashtu të shpejtë, me kosto të ulët dhe të lehtë për t'u zbatuar, prandaj shumica e programeve mbështeten tek ata. Ndër familjet e njohura përfshihen gjeneruesi kongruencial linear (LCG), gjeneruesit xorshift dhe Mersenne Twister.
Mersenne Twister
Mersenne Twister, i publikuar në vitin 1997 nga Makoto Matsumoto dhe Takuji Nishimura, është një nga gjeneruesit më të përdorur të numrave pseudorastësorë dhe zgjedhja e paracaktuar në shumë gjuhë programimi. Emri i tij vjen nga perioda e tij — gjatësia e vargut përpara se të fillojë të përsëritet —, e cila në variantin standard, MT19937, është numri i thjeshtë i Mersenne 219937 − 1. Ai kalon shumicën e testeve statistikore të rastësisë dhe përshtatet mirë për simulime. Megjithatë, ai nuk u krijua për të ruajtur sekrete: nga 624 rezultate të njëpasnjëshme 32-bitëshe, çdokush mund të rindërtojë gjendjen e tij të brendshme dhe të parashikojë çdo vlerë që pason, prandaj ai nuk duhet të përdoret për çelësa, fjalëkalime apo çdo gjë tjetër që duhet të mbetet e paparashikueshme.
Gjeneruesit e sigurt kriptografikisht dhe entropia
Shumë zbatime kanë nevojë për të dyja gjërat njëherësh: shpejtësinë e një algoritmi dhe paparashikueshmërinë e një burimi fizik. Zgjidhja është një gjenerues i numrave pseudorastësorë i sigurt kriptografikisht (CSPRNG). Ai mbetet një PRNG, por i ndërtuar në mënyrë të tillë që njohja e një pjese të rezultateve të tij nuk jep asnjë mundësi praktike për të parashikuar pjesën tjetër, dhe vlera e tij fillestare merret dhe përtërihet rregullisht nga një burim i vërtetë entropie. Një vlerë fillestare nga një burim fizik nuk e bën të sigurt një PRNG të zakonshëm; algoritmi duhet të jetë projektuar posaçërisht për këtë. Një burim fizik, siç është zhurma termike ose koha midis ngjarjeve harduerike, ofron një sasi të vogël rastësie të vërtetë, dhe CSPRNG nxjerr prej saj, shumë më shpejt, një varg të gjatë vlerash. Ky kombinim është ajo që një sistem operativ u ofron programeve që ekzekutohen në të, dhe është ajo që zakonisht nënkupton sot në praktikë «gjeneruesi i numrave rastësorë». Ai prodhon çelësa shifrimi, tokena sesioni dhe fjalëkalime.
Numrat rastësorë në shfletues
JavaScript i jep një faqeje interneti dy mënyra të integruara për të marrë vlera rastësore, dhe ato i përkasin klasave të ndryshme. Math.random() është një PRNG i zakonshëm: standardi i gjuhës ia lë zgjedhjen e algoritmit çdo shfletuesi dhe nuk garanton siguri — i përshtatshëm për një animacion, por i papërshtatshëm për një short që dikush mund ta kundërshtojë. Tjetra është Web Crypto API. Metoda e saj crypto.getRandomValues() kthen vlera rastësore të forta kriptografikisht, të prodhuara nga një CSPRNG që ushqehet me entropinë e sistemit operativ.
Gjeneruesi ynë i numrave rastësorë në internet përdor Web Crypto API për çdo tërheqje, dhe numrat prodhohen në shfletuesin tuaj e jo në një server. I njëjti burim fuqizon edhe gjeneruesit e tjerë në këtë faqe, pavarësisht nëse hidhni zare, hidhni një monedhë apo gjeneroni një fjalëkalim.
Nga bitet rastësore te një numër në intervalin tuaj
Një gjenerues i sigurt kriptografikisht është vetëm gjysma e një shorti të drejtë. Ai ofron bite të papërpunuara, dhe programi duhet t'i shndërrojë ato në një numër brenda intervalit tuaj — dhe pikërisht këtu mund të hyjë njëanshmëria. Supozoni se burimi jep vlerat nga 0 deri në 9 me shanse të barabarta dhe ju nevojitet një numër nga 0 deri në 5. Marrja e mbetjes pas pjesëtimit me 6 duket e natyrshme, por numrat 0, 1, 2 dhe 3 mund të bien në dy mënyra, ndërsa 4 dhe 5 vetëm në një mënyrë, kështu që secili nga numrat 0 deri në 3 ka 20% shans, ndërsa 4 dhe 5 vetëm 10% secili. Një mënyrë për të hequr prirjen e pabarabartë (modulo bias) është të hidhen poshtë vlerat që nuk përshtaten dhe të bëhet tërheqja sërish; materialet tona për numrat rastësorë e shpjegojnë këtë me hollësi.
Dy gjëra të tjera i habisin shpesh njerëzit. Përsëritjet janë normale: kur një numër i plotë nga 1 deri në 10 tërhiqet në mënyrë të pavarur dhe çdo numër ka të njëjtën gjasë, numri sapo i tërhequr ka të njëjtin shans 1 në 10 për të rënë përsëri, ashtu si çdo numër tjetër. Një short pa përsëritje është një lloj tjetër zgjedhjeje, jo më rastësor. Dhe një gjenerues i drejtë i vetëm nuk e bën të drejtë të gjithë procedurën: lista e pjesëmarrësve dhe numri i përpjekjeve kanë po aq rëndësi, siç shpjegon artikulli ynë se si të zgjidhni një fitues konkursi.