Mikä on satunnaislukugeneraattori?
Satunnaislukugeneraattori (RNG) on järjestelmä, joka tuottaa satunnaisia tai pseudosatunnaisia lukuja. Se, voidaanko seuraava luku todella ennustaa, riippuu generaattorin tyypistä. Jotkin generaattorit perustuvat fysikaaliseen prosessiin, toiset laskevat lukunsa algoritmilla, ja tietyt algoritmit on rakennettu siten, ettei edes aiemmat tulokset nähnyt henkilö pysty ennustamaan seuraavaa lukua. Satunnaiselta näyttäminen ja ennalta-arvaamattomuus ovat eri ominaisuuksia, ja suurin osa tästä artikkelista käsittelee juuri tätä eroa.
Laitteistopohjaiset satunnaislukugeneraattorit
Laitteistopohjainen satunnaislukugeneraattori (HRNG), jota kutsutaan myös todelliseksi satunnaislukugeneraattoriksi (TRNG), johtaa lukunsa fysikaalisesta prosessista. Vanhimmat niistä toimivat suoraan silmiemme edessä: heitetty kolikko, pyöritetty noppa tai rulettipyörä. Mekaniikan lait kuvaavat niitä jokaista täydellisesti, mutta laadukas rulettipyörä on käytännössä silti arvaamaton, sillä pienetkin erot pyöräytyksen alussa johtavat täysin erilaisiin lopputuloksiin.
Nykyaikaiset laitteistogeneraattorit mittaavat sen sijaan mikroskooppisia ilmiöitä: elektronisten piirien raekohinaa ja lämpökohinaa, ilmakehän kohinaa tai kvantti-ilmiöitä. Nämä ovat hyviä entropian lähteitä — mitattavissa olevaa ennalta-arvaamattomuutta —, mutta fysikaalinen lähde ei ole luonnostaan täydellinen: siinä voi esiintyä vääristymää, se voi ajautua ja vikaantua. Siksi sen laatua on arvioitava ja valvottava, ja sen tuloksia tarvittaessa jatkokäsiteltävä, kuten esimerkiksi standardi NIST SP 800-90B kuvaa. Laitteistolähteitä käytetään siellä, missä takeilla on eniten merkitystä — ennen kaikkea kryptografiassa, jossa ne tarjoavat arvaamattoman lähtömateriaalin sellaisten protokollien taustalla oleville avaimille kuin Transport Layer Security (TLS).
Pseudosatunnaislukugeneraattorit
Vaihtoehto fyysiselle laitteelle on algoritmi. Pseudosatunnaislukugeneraattori (PRNG) tuottaa sarjan, joka näyttää satunnaiselta, mutta jonka määrää täysin alkuarvo, jota kutsutaan siemenluvuksi (seed). Kun samalle algoritmille annetaan sama siemenluku, saadaan joka kerta täsmälleen sama lukusarja. Tämä on heikkous aina, kun tuloksen on oltava ennalta-arvaamaton ja siemenluku tai sisäinen tila voidaan arvata tai rekonstruoida, ja vahvuus silloin, kun tuloksen on oltava toistettavissa — simulaatio tai testi voidaan ajaa uudelleen täsmälleen samalla tavalla. PRNG:t ovat myös nopeita, edullisia ja helppoja toteuttaa, minkä vuoksi useimmat ohjelmistot luottavat niihin. Tunnettuja algoritmeja ovat muun muassa lineaarinen kongruenssigeneraattori (LCG), xorshift-generaattorit ja Mersenne Twister.
Mersenne Twister
Makoto Matsumoton ja Takuji Nishimuran vuonna 1997 julkaisema Mersenne Twister on yksi laajimmin käytetyistä pseudosatunnaislukugeneraattoreista ja oletusvalinta monissa ohjelmointikielissä. Sen nimi tulee sen jaksosta — sarjan pituudesta ennen sen toistumista —, joka vakiovariantissa MT19937 on Mersennen alkuluku 219937 − 1. Se läpäisee useimmat satunnaisuuden tilastolliset testit ja soveltuu hyvin simulaatioihin. Sitä ei kuitenkaan suunniteltu pitämään salaisuuksia: kuka tahansa voi rekonstruoida sen sisäisen tilan 624 peräkkäisestä 32-bittisestä tuloksesta ja ennustaa kaikki sitä seuraavat arvot, joten sitä ei saa käyttää avaimiin, salasanoihin tai mihinkään muuhun, jonka on pysyttävä arvaamattomana.
Kryptografisesti turvalliset generaattorit ja entropia
Monet sovellukset tarvitsevat molempia asioita samanaikaisesti: algoritmin nopeutta ja fysikaalisen lähteen ennalta-arvaamattomuutta. Ratkaisu on kryptografisesti turvallinen pseudosatunnaislukugeneraattori (CSPRNG). Se on edelleen eräänlainen PRNG, mutta rakennettu siten, ettei osan sen tuloksista näkeminen tarjoa mitään käytännön keinoa ennustaa loppuja, ja siihen syötetään ja päivitetään säännöllisesti siemenluku todellisesta entropialähteestä. Fysikaalisesta lähteestä peräisin oleva siemenluku ei tee tavallisesta PRNG:stä turvallista; itse algoritmin on oltava sitä varten suunniteltu. Fysikaalinen lähde, kuten lämpökohina tai laitteistotapahtumien ajoitus, tarjoaa pienen määrän aitoa satunnaisuutta, ja CSPRNG tuottaa siitä huomattavasti nopeammin pitkän arvojonon. Tämä yhdistelmä on se, mitä käyttöjärjestelmä tarjoaa siinä ajettaville ohjelmille, ja mitä ”satunnaislukugeneraattorilla” käytännössä nykyään useimmiten tarkoitetaan. Se tuottaa salausavaimia, istuntotunnisteita ja salasanoja.
Satunnaisluvut selaimessa
JavaScript tarjoaa verkkosivulle kaksi sisäänrakennettua tapaa saada satunnaisia arvoja, ja ne kuuluvat eri luokkiin. Math.random() on tavallinen PRNG: kielen standardi jättää algoritmin kunkin selaimen päätettäväksi eikä lupaa mitään turvallisuudesta — sopii animaatioon, mutta ei arvontaan, jonka joku saattaisi riitauttaa. Toinen on Web Crypto API. Sen crypto.getRandomValues() -metodi palauttaa kryptografisesti turvallisia satunnaislukuja, jotka tuottaa käyttöjärjestelmän entropialla alustettu CSPRNG.
Satunnaislukugeneraattorimme käyttää Web Crypto API:a jokaiseen arvontaan, ja luvut tuotetaan selaimessasi palvelimen sijaan. Sama lähde ohjaa tämän sivuston muita generaattoreita, halusitpa heittää noppaa, heittää kruunaa ja klaavaa tai luoda salasanan.
Satunnaisista biteistä luvuksi valitsemallasi välillä
Kryptografisesti turvallinen generaattori on vasta puolet reilusta arvonnasta. Se tuottaa raakoja bittejä, ja ohjelman on silti muutettava ne luvuksi valitsemallasi välillä — ja juuri tähän voi hiipiä vääristymää. Oletetaan, että lähde antaa arvot 0–9 yhtä suurella todennäköisyydellä ja tarvitset luvun väliltä 0–5. Jakojäännöksen ottaminen luvulla 6 jakamisen jälkeen tuntuu luontevalta, mutta luvut 0, 1, 2 ja 3 voivat tällöin syntyä kahdella eri tavalla ja 4 ja 5 vain yhdellä; siten kullakin luvuista 0–3 on 20 %:n mahdollisuus, ja luvuilla 4 ja 5 kummallakin vain 10 %. Yksi tapa poistaa tämä vääristymä on hylätä sopimattomat arvot ja arpoa uudelleen; satunnaislukugeneraattorin oppaat käsittelevät tätä yksityiskohtaisesti.
Kaksi muuta asiaa yllättää usein ihmisiä. Toistot ovat normaaleja: kun kokonaisluku väliltä 1–10 arvotaan itsenäisesti ja jokainen luku on yhtä todennäköinen, juuri arvotulla luvulla on täsmälleen sama 1 kymmenestä mahdollisuus tulla uudelleen kuin millä tahansa muulla. Arvonta ilman toistoja on vain erilainen arvontatapa, ei satunnaisempi. Eikä tasapuolinen generaattori yksinään tee koko menettelystä reilua: osallistujaluettelo ja yritysten määrä merkitsevät aivan yhtä paljon, kuten artikkelimme siitä, miten arpoa kilpailun voittaja satunnaisesti, selittää.