Wat is een willekeurige nummer generator?
Een willekeurige getallengenerator (RNG) is een systeem dat toevalsgetallen of pseudotoevalsgetallen produceert. Of het volgende getal daadwerkelijk voorspeld kan worden, hangt af van het type generator. Sommige generatoren maken gebruik van een fysiek proces, sommige berekenen hun getallen met een algoritme, en sommige algoritmen zijn zo gebouwd dat zelfs iemand die hun resultaten heeft gezien, niet kan voorspellen wat er daarna komt. Willekeurig lijken en onvoorspelbaar zijn, zijn twee verschillende eigenschappen, en het grootste deel van dit artikel gaat over dat verschil.
Hardwarematige toevalsgeneratoren
Een hardwarematige toevalsgenerator (HRNG), ook wel een echte toevalsgenerator (TRNG) genoemd, ontleent zijn getallen aan een fysiek proces. De oudste werken voor onze ogen: een opgeworpen munt, een geworpen dobbelsteen, een roulettewiel. De mechanica beschrijft elk daarvan volledig, maar een goed gemaakt wiel is in de praktijk toch onvoorspelbaar, omdat minieme verschillen in hoe elke draai begint uitgroeien tot totaal verschillende uitkomsten.
Moderne hardwaregeneratoren meten in plaats daarvan microscopische verschijnselen: hagelruis en thermische ruis in elektronische circuits, atmosferische ruis, kwantumeffecten. Dit zijn goede bronnen van entropie — onvoorspelbaarheid die gemeten kan worden — maar een fysieke bron is van nature niet perfect: hij kan ongelijke kansen vertonen, in de loop van de tijd afwijken en uitvallen, waardoor de kwaliteit ervan beoordeeld en bewaakt moet worden, en de waarden waar nodig verder moeten worden verwerkt, zoals beschreven in normen zoals NIST SP 800-90B. Hardwarebronnen worden gebruikt waar de garantie het zwaarst weegt — vooral in de cryptografie, waar ze het onvoorspelbare startmateriaal leveren voor de sleutels achter protocollen zoals Transport Layer Security (TLS).
Pseudotoevalsgeneratoren
Het alternatief voor een fysiek apparaat is een algoritme. Een pseudotoevalsgenerator (PRNG) produceert een reeks die er willekeurig uitziet, maar volledig wordt bepaald door een beginwaarde, de seed. Geef dezelfde seed aan hetzelfde algoritme en je krijgt elke keer dezelfde reeks. Dat is een zwakte overal waar een resultaat onvoorspelbaar moet zijn en de seed of de interne toestand kan worden geraden of gereconstrueerd, en een kracht waar een resultaat reproduceerbaar moet zijn — een simulatie of een test kan dan exact opnieuw worden uitgevoerd. PRNG's zijn ook snel, goedkoop en eenvoudig te implementeren, waardoor de meeste software erop vertrouwt. Bekende algoritmen zijn onder meer de lineaire congruente generator (LCG), de xorshift-generatoren en de Mersenne Twister.
Mersenne Twister
De Mersenne Twister, in 1997 gepubliceerd door Makoto Matsumoto en Takuji Nishimura, is een van de meest gebruikte pseudotoevalsgeneratoren en de standaard in veel programmeertalen. Zijn naam dankt hij aan zijn periode — de lengte van de reeks voordat deze zich herhaalt — die in de standaardvariant, MT19937, het Mersenne-priemgetal 219937 − 1 is. Hij doorstaat de meeste statistische tests op willekeurigheid en is goed geschikt voor simulaties. Hij is echter niet ontworpen om geheimen te bewaren: uit 624 opeenvolgende 32-bits waarden kan iedereen de interne toestand reconstrueren en elke volgende waarde voorspellen, dus hij mag niet worden gebruikt voor sleutels, wachtwoorden of iets anders dat onvoorspelbaar moet blijven.
Cryptografisch veilige generatoren en entropie
Veel toepassingen hebben beide eigenschappen tegelijk nodig: de snelheid van een algoritme en de onvoorspelbaarheid van een fysieke bron. Het antwoord is een cryptografisch veilige pseudotoevalsgenerator (CSPRNG). Dit is nog steeds een PRNG, maar dan een die zo is gebouwd dat het zien van een deel van de waarden geen praktische mogelijkheid biedt om de rest te voorspellen, en die wordt gevoed, en regelmatig opnieuw gevoed, vanuit een bron van echte entropie. Een seed uit een fysieke bron maakt een gewone PRNG niet veilig; het algoritme moet ervoor ontworpen zijn. Een fysieke bron zoals thermische ruis of de timing van hardware-gebeurtenissen levert een kleine hoeveelheid echte willekeur, en de CSPRNG maakt daar een lange reeks waarden van, die hij veel sneller levert. Deze combinatie is wat een besturingssysteem biedt aan de programma's die erop draaien, en het is wat in de praktijk tegenwoordig meestal wordt bedoeld met "willekeurige getallengenerator". Daarmee worden encryptiesleutels, sessietokens en wachtwoorden gemaakt.
Willekeurige getallen in de browser
JavaScript geeft een webpagina twee ingebouwde manieren om willekeurige waarden te verkrijgen, en ze behoren tot verschillende klassen. Math.random() is een gewone PRNG: de taalstandaard laat het algoritme over aan elke browser en belooft niets over veiligheid — prima voor een animatie, ongeschikt voor een trekking die iemand zou kunnen aanvechten. De andere is de Web Crypto API. De methode crypto.getRandomValues() retourneert cryptografisch veilige willekeurige waarden, gegenereerd door een CSPRNG die wordt gevoed met de entropie van het besturingssysteem.
Onze online willekeurige getallengenerator gebruikt de Web Crypto API voor elke trekking, en de getallen worden gegenereerd in je browser in plaats van op een server. Dezelfde bron drijft de andere generatoren op deze site aan, of je nu dobbelstenen gooit, kop of munt gooit of een wachtwoord genereert.
Van willekeurige bits naar een getal in jouw bereik
Een cryptografisch veilige generator is slechts de helft van een eerlijke trekking. Hij levert ruwe bits, en het programma moet ze nog omzetten in een getal binnen jouw bereik — en dit is waar ongelijke kansen kunnen binnensluipen. Stel dat de bron de waarden 0 tot en met 9 met gelijke kansen levert en je een getal van 0 tot en met 5 nodig hebt. De rest nemen na deling door 6 lijkt natuurlijk, maar 0, 1, 2 en 3 kunnen dan elk op twee manieren vallen en 4 en 5 slechts op één manier, waardoor elk van de getallen 0 tot en met 3 een kans van 20% heeft, en 4 en 5 elk slechts 10%. Een manier om deze afwijking weg te nemen is de waarden die niet passen te verwerpen en opnieuw te trekken; de artikelen over willekeurige getallen gaan hier dieper op in.
Nog twee dingen verrassen mensen vaak. Herhalingen zijn normaal: wanneer een geheel getal van 1 tot en met 10 onafhankelijk wordt getrokken en elk getal even waarschijnlijk is, heeft het zojuist getrokken getal dezelfde kans van 1 op 10 om opnieuw te vallen als elk ander getal. Een trekking zonder herhalingen is een ander soort trekking, niet een meer willekeurige. En een eerlijke generator alleen maakt een hele procedure nog niet eerlijk: de deelnemerslijst en het aantal pogingen doen er net zoveel toe, zoals ons artikel over hoe je een winnaar kiest van je winactie uitlegt.