Ano ang random number generator?
Ang random number generator (RNG) ay isang sistema na gumagawa ng mga random o pseudorandom na numero. Kung ang susunod na numero ay talagang mahuhulaan ay nakasalalay sa uri ng generator. Ang ilang mga generator ay kumukuha mula sa isang pisikal na proseso, ang ilan ay kinakalkula ang kanilang mga numero gamit ang isang algorithm, at ang ilang mga algorithm ay binuo upang kahit na ang isang nakakita sa kanilang output ay hindi mahuhulaan kung ano ang susunod na darating. Ang magmukhang random at ang pagiging hindi mahuhulaan ay magkaibang mga katangian, at karamihan sa artikulong ito ay tungkol sa pagkakaibang iyon.
Mga hardware random number generator
Ang isang hardware random number generator (HRNG), na tinatawag ding true random number generator (TRNG), ay kumukuha ng mga numero nito mula sa isang pisikal na proseso. Ang mga pinakaluma ay gumagana sa harap mismo ng ating mga mata: isang inihagis na barya, isang pinagulong na dice, isang roulette wheel. Ganap na inilalarawan ng mechanics ang bawat isa sa kanila, ngunit ang isang mahusay na pagkagawa ng gulong ay nananatiling hindi mahuhulaan sa pagsasanay, dahil ang maliliit na pagkakaiba sa kung paano nagsisimula ang bawat pag-ikot ay lumalaki sa ganap na magkakaibang mga resulta.
Sa halip, sinusukat ng mga modernong hardware generator ang mga microscopic phenomena: shot noise at thermal noise sa mga electronic circuit, atmospheric noise, mga quantum effect. Ang mga ito ay magagandang mapagkukunan ng entropy — hindi mahuhulaan na maaaring masukat — ngunit ang isang pisikal na pinagmulan ay hindi perpekto ayon sa kalikasan: maaari itong magkaroon ng hindi pantay na pagkakataon, maaari itong magbago sa paglipas ng panahon at maaari itong mabigo, kaya ang kalidad nito ay kailangang suriin at subaybayan, at ang output nito ay kailangang iproseso pa kung kinakailangan, na siyang inilalarawan ng mga pamantayan tulad ng NIST SP 800-90B. Ang mga hardware source ay ginagamit kung saan ang garantiya ay pinakamahalaga — higit sa lahat sa cryptography, kung saan nagbibigay sila ng hindi mahuhulaang panimulang materyal para sa mga key sa likod ng mga protocol tulad ng Transport Layer Security (TLS).
Mga pseudorandom number generator
Ang alternatibo sa isang pisikal na aparato ay isang algorithm. Ang isang pseudorandom number generator (PRNG) ay gumagawa ng isang sequence na mukhang random ngunit ganap na tinutukoy ng isang paunang halaga na tinatawag na seed. Ibigay ang parehong seed sa parehong algorithm at makukuha mo ang parehong sequence sa bawat pagkakataon. Iyon ay isang kahinaan saanman ang isang resulta ay dapat na hindi mahuhulaan at ang seed o ang panloob na estado ay maaaring mahulaan o mabuo muli, at isang kalakasan saanman ang isang resulta ay dapat na maulit — ang isang simulation o isang pagsubok ay maaaring patakbuhin muli nang eksakto. Ang mga PRNG ay mabilis din, mura at madaling ipatupad, kung kaya't karamihan sa software ay umaasa sa kanila. Kabilang sa mga kilalang uri ang linear congruential generator (LCG), ang mga xorshift generator at ang Mersenne Twister.
Mersenne Twister
Ang Mersenne Twister, na inilathala noong 1997 nina Makoto Matsumoto at Takuji Nishimura, ay isa sa mga pinakalawak na ginagamit na pseudorandom number generator at ang default sa maraming programming language. Ang pangalan nito ay nagmula sa period nito — ang haba ng sequence bago ito umulit — na sa karaniwang variant, MT19937, ay ang Mersenne prime 219937 − 1. Pumapasa ito sa karamihan ng mga pagsusuring istadistika ng randomness at angkop para sa mga simulation. Gayunpaman, hindi ito idinisenyo upang magtago ng mga lihim: mula sa 624 na magkakasunod na 32-bit na output, kahit sino ay maaaring muling buuin ang panloob na estado nito at hulaan ang bawat halaga na kasunod, kaya hindi ito dapat gamitin para sa mga key, password o anumang bagay na dapat manatiling hindi mahuhulaan.
Mga cryptographically secure generator at entropy
Maraming application ang nangangailangan ng parehong bagay nang sabay: ang bilis ng isang algorithm at ang hindi mahuhulaan ng isang pisikal na pinagmulan. Ang sagot ay isang cryptographically secure pseudorandom number generator (CSPRNG). Ito ay isa pa ring PRNG, ngunit binuo upang ang pagkakita sa bahagi ng output nito ay hindi nagbibigay ng praktikal na paraan upang mahulaan ang natitira, at ito ay binibigyan ng seed, at regular na binibigyan muli ng seed, mula sa isang mapagkukunan ng tunay na entropy. Ang isang seed mula sa isang pisikal na pinagmulan ay hindi nagiging sanhi upang maging ligtas ang isang ordinaryong PRNG; ang algorithm ay kailangang idisenyo para dito. Ang isang pisikal na pinagmulan tulad ng thermal noise o ang tiyempo ng mga kaganapan sa hardware ay nagbibigay ng maliit na halaga ng tunay na randomness, at mula rito ay mas mabilis na kumukuha ang CSPRNG ng mahabang sequence ng mga value. Ang kumbinasyong ito ang iniaalok ng isang operating system sa mga programang tumatakbo dito, at ito ang karaniwang ibig sabihin ng "random number generator" sa pagsasanay ngayon. Gumagawa ito ng mga encryption key, session token at mga password.
Mga random na numero sa browser
Nagbibigay ang JavaScript sa isang web page ng dalawang built-in na paraan upang makakuha ng mga random value, at nabibilang sila sa iba't ibang klase. Ang Math.random() ay isang ordinaryong PRNG: iniiwan ng pamantayan ng wika ang algorithm sa bawat browser at walang ipinapangako tungkol sa seguridad — mainam para sa isang animation, hindi angkop para sa isang draw na maaaring tutulan ng isang tao. Ang isa pa ay ang Web Crypto API. Ang pamamaraang crypto.getRandomValues() nito ay nagbabalik ng mga cryptographically strong na random value, na ginawa ng isang CSPRNG na binigyan ng seed gamit ang entropy ng operating system.
Ang aming online na generator ng random na numero ay gumagamit ng Web Crypto API para sa bawat draw, at ang mga numero ay ginagawa sa iyong browser sa halip na sa isang server. Ang parehong pinagmulan ay nagpapatakbo sa iba pang mga generator sa site na ito, kung ikaw man ay magpagulong ng Dice Roller, maghagis ng barya sa Pagtapon ng Barya o bumuo ng password gamit ang generator ng password.
Mula sa mga random bit patungo sa isang numero sa iyong saklaw
Ang isang cryptographically secure na generator ay kalahati lamang ng isang patas na draw. Naghahatid ito ng mga hilaw na bit, at kailangan pa ring gawing numero ng programa ang mga ito sa iyong saklaw — at dito maaaring pumasok ang hindi pantay na pagkakataon (modulo bias). Ipagpalagay na ang pinagmulan ay nagbibigay ng mga halagang 0 hanggang 9 na may pantay na pagkakataon at kailangan mo ng numero mula 0 hanggang 5. Ang pagkuha ng natira pagkatapos maghati sa 6 ay mukhang natural, ngunit ang 0, 1, 2 at 3 ay maaaring lumabas sa dalawang paraan at ang 4 at 5 sa isa lamang, kaya ang bawat isa sa mga numerong 0 hanggang 3 ay may 20% na pagkakataon, at ang 4 at 5 ay may 10% lamang bawat isa. Ang isang paraan upang alisin ang pagkiling ay itapon ang mga halagang hindi kasya at mag-draw muli; ang mga materyales sa random na numero ay nagpapaliwanag nito nang detalyado.
Dalawa pang bagay ang ikinagugulat ng mga tao. Normal ang pag-uulit: kapag ang isang buong numero mula 1 hanggang 10 ay nakuha nang independyente at ang bawat numero ay may pantay na posibilidad, ang numerong kakakuha pa lamang ay may parehong 1 sa 10 pagkakataon na lumabas muli tulad ng iba pa. Ang isang draw na walang pag-uulit ay ibang uri ng draw, hindi isang mas random na draw. At ang isang patas na generator lamang ay hindi gumagawa sa buong pamamaraan na maging patas: ang listahan ng mga kalahok at ang bilang ng mga pagsubok ay mahalaga rin, tulad ng ipinapaliwanag ng aming gabay sa paano pumili ng mananalo sa paligsahan.