Hvað er slembitöluvél?
Slembitöluvél (RNG) er kerfi sem framleiðir slembitölur eða gervislembitölur. Hvort raunverulega sé hægt að spá fyrir um næstu tölu fer eftir gerð vélarinnar. Sumar vélar nýta eðlisfræðilegt ferli, sumar reikna tölurnar með reikniriti og sum reiknirit eru þannig hönnuð að jafnvel sá sem hefur séð niðurstöður þeirra getur ekki séð fyrir hvað kemur næst. Að virðast handahófskennt og að vera ófyrirsjáanlegt eru ólíkir eiginleikar, og stærstur hluti þessarar greinar fjallar um þann mun.
Vélbúnaðarslembitöluvélar
Vélbúnaðarslembitöluvél (HRNG), einnig nefnd sannur slembitölugjafi (TRNG), fær tölur sínar úr eðlisfræðilegu ferli. Elstu dæmin virka fyrir augum okkar: peningur sem er kastað, teningur sem er kastað eða rúllettuhjól. Aflfræðin getur lýst hverju þeirra til fulls, en vandað hjól er samt ófyrirsjáanlegt í reynd, vegna þess að örsmáar breytingar á því hvernig hver snúningur hefst verða að gjörólíkum niðurstöðum.
Nútímalegir vélbúnaðargjafar mæla hins vegar örsmá fyrirbæri: skotsuð (shot noise) og varmasuð í rafrásum, andrúmsloftssuð og skammtafræðileg áhrif. Þetta eru góðar uppsprettur óreiðu (entropy) — ófyrirsjáanleika sem hægt er að mæla — en eðlisfræðileg uppspretta er ekki fullkomin í eðli sínu: hún getur verið bjöguð, getur rekið til og getur bilað. Því þarf að meta og fylgjast með gæðum hennar og vinna úr gildunum frekar eftir þörfum, sem er það sem staðlar á borð við NIST SP 800-90B lýsa. Vélbúnaðaruppsprettur eru notaðar þar sem áreiðanleikinn skiptir mestu máli — sérstaklega í dulritun, þar sem þær leggja til ófyrirsjáanlegt upphafsefni fyrir lykla á bak við samskiptareglur á borð við Transport Layer Security (TLS).
Gervislembitöluvélar
Valkosturinn við líkamlegan búnað er reiknirit. Gervislembitöluvél (PRNG) býr til röð sem virðist tilviljunarkennd en ræðst algjörlega af upphafsgildi sem nefnist fræ (seed). Ef sama fræ er gefið sama reikniriti fæst nákvæmlega sama röð í hvert skipti. Þetta er veikleiki þar sem niðurstaðan verður að vera ófyrirsjáanleg og hægt er að giska á fræið eða innra ástandið, en styrkur þar sem niðurstaðan verður að vera endurtakanleg — til dæmis þegar keyra þarf hermun eða prófun aftur með nákvæmlega sömu niðurstöðu. PRNG eru einnig hröð, ódýr og einföld í uppsetningu, og þess vegna treystir flestur hugbúnaður á þau. Meðal þekktra reiknirita eru línulegur samleifargjafi (LCG), xorshift-vélar og Mersenne Twister.
Mersenne Twister
Mersenne Twister, sem Makoto Matsumoto og Takuji Nishimura gáfu út árið 1997, er ein útbreiddasta gervislembitöluvélin og sjálfgefin í mörgum forritunarmálum. Nafn hennar kemur frá lotu hennar — lengd raðarinnar áður en hún endurtekur sig — sem í hefðbundnu útgáfunni, MT19937, er Mersenne-frumtalan 219937 − 1. Hún stenst flest tölfræðileg próf um slembi og hentar vel í hermun. Hún var hins vegar ekki hönnuð til að geyma leyndarmál: út frá 624 samfelldum 32-bita gildum getur hver sem er endurbyggt innra ástand hennar og séð fyrir öll gildi sem á eftir koma, svo hana má alls ekki nota fyrir lykla, lykilorð eða neitt annað sem verður að vera ófyrirsjáanlegt.
Dulritunarfræðilega öruggar vélar og óreiða
Mörg forrit þurfa hvort tveggja í senn: hraða reiknirits og ófyrirsjáanleika eðlisfræðilegrar uppsprettu. Svarið er dulritunarfræðilega örugg gervislembitöluvél (CSPRNG). Hún er enn PRNG, en smíðuð þannig að það að sjá hluta af gildum hennar veitir enga raunhæfa leið til að spá fyrir um afganginn, og hún fær fræ, og nýtt fræ reglulega, úr uppsprettu raunverulegrar óreiðu. Fræ úr líkamlegri uppsprettu gerir venjulegt PRNG ekki öruggt; reikniritið sjálft verður að vera hannað fyrir það. Líkamleg uppspretta eins og varmasuð eða tímasetning vélbúnaðaratburða gefur lítið magn af sönnu slembi, og CSPRNG framleiðir úr því langa röð gilda mun hraðar. Þessi samsetning er það sem stýrikerfi býður forritum sem keyra á því, og það er það sem „slembitöluvél“ þýðir venjulega í reynd í dag. Hún býr til dulkóðunarlykla, setulykla og lykilorð.
Slembitölur í vafranum
JavaScript veitir vefsíðu tvær innbyggðar leiðir til að fá slembigildi, og þær tilheyra ólíkum flokkum. Math.random() er venjulegt PRNG: staðall málsins skilur reikniritið eftir fyrir hvern vafra og lofar engu um öryggi — ágætt fyrir hreyfimynd, en ónothæft fyrir útdrátt sem einhver kynni að vefengja. Hin leiðin er Web Crypto API. Aðferð hennar crypto.getRandomValues() skilar dulritunarfræðilega sterkum slembigildum sem framleidd eru af CSPRNG sem fær fræ úr óreiðu stýrikerfisins.
Slembitöluvél okkar á netinu notar Web Crypto API fyrir hvern útdrátt, og tölurnar eru framleiddar í vafranum þínum frekar en á netþjóni. Sama uppspretta knýr önnur verkfæri á þessum vef, hvort sem þú vilt kasta teningum, kasta peningi eða búa til lykilorð.
Frá slembibitum til tölu á þínu bili
Dulritunarfræðilega örugg vél er aðeins helmingurinn af sanngjörnum útdrætti. Hún skilar hráum bitum, og forritið verður enn að breyta þeim í tölu á þínu bili — og þar getur bjögun læðst inn. Segjum að uppsprettan gefi gildin 0 til 9 með jöfnum líkum og þú þurfir tölu frá 0 til 5. Að taka leifina eftir deilingu með 6 virðist eðlilegt, en tölurnar 0, 1, 2 og 3 geta þá hver komið upp á tvo vegu en 4 og 5 aðeins á einn veg. Þar af leiðandi hefur hver talnanna 0 til 3 20% líkur, en 4 og 5 aðeins 10% líkur hvor. Ein leið til að fjarlægja bjögunina (modulo bias) er að henda gildum sem passa ekki og draga aftur; í hlutanum leiðbeiningar um slembitöluvélar er farið nánar í þetta.
Tvennt annað kemur fólki á óvart. Endurtekningar eru eðlilegar: þegar heiltala frá 1 til 10 er dregin sjálfstætt og hver tala er jafnlíkleg, hefur talan sem var rétt að koma upp sömu 1 af 10 líkum á að koma aftur og hver önnur. Útdráttur án endurtekninga er annars konar útdráttur, ekki handahófskenndari. Og sanngjörn vél ein og sér gerir allt ferlið ekki sanngjarnt: listi þátttakenda og fjöldi tilrauna skipta jafn miklu máli, eins og grein okkar um hvernig á að velja vinningshafa af handahófi útskýrir.