Getallengenerator

Een willekeurige getallengenerator (Random Number Generator of RNG) is een systeem dat een onvoorspelbaar getal genereert, zonder dat er een patroon te herkennen is uit eerder gegenereerde reeksen. Deze willekeurige getallen kunnen worden geproduceerd door een geavanceerd algoritme of een specifiek hardwareapparaat.

Het gebruik van willekeurige getallengeneratoren

Willekeurige getallen zijn essentieel voor uiteenlopende toepassingen, van alledaagse software tot complexe computerspellen. Een website gebruikt bijvoorbeeld een willekeurige getallengenerator om wisselende banners of willekeurige advertenties weer te geven. Binnen de cryptografie is een betrouwbare RNG bovendien cruciaal voor het aanmaken van unieke encryptiesleutels.

Daarnaast wordt het genereren van willekeurige getallen gebruikt voor het maken van CAPTCHA's, gegevensencryptie, het genereren van 'salt' voor veilige wachtwoordopslag, wachtwoordgeneratoren, het schudden van kaarten in online casino's, steekproeven, simulaties en geautomatiseerde besluitvorming.

In de wereld van videogames is het RNG-algoritme onmisbaar. Speel je een missie in een game opnieuw, dan zorgt de willekeurige getallengenerator ervoor dat de ervaring nooit exact hetzelfde is. De lay-out van de locatie blijft misschien gelijk, maar de gebieden waar vijanden verschijnen, weersomstandigheden en de obstakels die je tegenkomt veranderen continu. Dit houdt de gameplay dynamisch en spannend.

Verschil tussen een willekeurige en een niet-willekeurige reeks

Neem bijvoorbeeld de volgende reeks getallen: 1 , 2 , 3 , 4 , 5. Is deze reeks willekeurig?

Een willekeurige variabele neemt een specifieke waarde aan als resultaat van een proces of test. De kern van willekeur is dat je onmogelijk met zekerheid kunt voorspellen welke waarde dit zal zijn vóórdat deze verschijnt.

Stel dat de bovenstaande reeks is ontstaan door simpelweg de bovenste rij van een toetsenbord in te toetsen. In dat geval is de combinatie absoluut niet willekeurig; na de 5 kun je immers met grote zekerheid voorspellen dat het volgende getal een 6 zal zijn. Een reeks is pas écht willekeurig als er geen enkele afhankelijkheid is tussen de opeenvolgende symbolen of getallen.

De basisvoorwaarde voor een eerlijke en correcte random number generator is dat elk mogelijk getal een exact gelijke waarschijnlijkheid heeft om uit het systeem te rollen. Dit vereist volledige onafhankelijkheid: het nieuwe getal mag op geen enkele manier beïnvloed worden door de willekeurigheidsfactor van de getallen die eraan voorafgingen.

Stel dat je met een zuivere, zeszijdige dobbelsteen gooit. Elk getal van 1 tot en met 6 heeft exact dezelfde kans om bovenop te belanden. Ongeacht je vorige worp, is de kans op een specifiek getal bij de tweede, honderdste of duizendste worp altijd identiek.

De opeenvolging van decimalen in het getal Pi wordt vaak als willekeurig beschouwd. Stel dat onze denkbeeldige generator getallen baseert op de binaire representatie van Pi, beginnend bij een willekeurig, onbekend punt. Zo'n generator zou hoogstwaarschijnlijk slagen voor statistische willekeurigheidstests (de 'volgende bit test'). Toch is deze aanpak cryptografisch onveilig. Als een cryptograaf of hacker ontdekt welk bit van Pi momenteel wordt gebruikt, kan hij de gehele reeks — zowel uit het verleden als in de toekomst — feilloos berekenen.

Om dit soort systemen rigoureus te testen, heeft het Amerikaanse National Institute of Standards and Technology (NIST) het "Statistical Test Package for Random and Pseudorandom Number Generators for Cryptographic Applications" voorgesteld. Dit pakket bevat 15 statistische tests die de mate van willekeur meten van bits die door hardware- of softwaregeneratoren zijn geproduceerd.

De typen willekeurige getalgeneratoren

Grofweg zijn er twee soorten willekeurige getallengeneratoren (RNG): True Random Number Generators (TRNG - echte willekeurige getallengeneratoren) en Pseudo-Random Number Generators (PRNG - pseudo-willekeurige getallengeneratoren). TRNG's maken gebruik van fysieke fenomenen, terwijl PRNG's gebaseerd zijn op wiskundige algoritmen.

Een echte willekeurige getallengenerator werkt met hardwareapparatuur die microscopische fysieke processen meet om zogenaamde entropie te verzamelen. Entropie staat hierbij voor pure, ongefilterde chaos.

Echte willekeurige getallengeneratoren maken gebruik van natuurkundige fenomenen zoals:

• radioactiviteit,
• thermische ruis,
• elektromagnetische ruis,
• kwantummechanica, en andere onvoorspelbare processen.

Een echte RNG wordt wereldwijd veel toegepast in hoogwaardige beveiligingssystemen en complexe vormen van encryptie. Ze verzamelen entropie uit de bovengenoemde bronnen om een onvoorspelbare beginwaarde (de seed) te creëren, die de basis vormt voor het willekeurige getal.

Het algoritme van een pseudo-willekeurige getallengenerator (PRNG) wordt vooral gebruikt voor toepassingen waarbij veiligheid geen kritieke rol speelt. Hier zorgt de willekeur voor variatie en voorkomt het dat processen voorspelbaar en saai worden voor de eindgebruiker. PRNG-technologie is goedkoper en sneller te implementeren, omdat het geen speciale hardware vereist en eenvoudig als programmacode kan worden ingebouwd. Hoewel dit proces deterministisch is (gebaseerd op een algoritme) en dus niet 100% willekeurig, is het perfect voor games en reguliere programma's.

Een PRNG gebruikt één enkele seed, waaruit vervolgens de pseudo-willekeurige getallenreeks voortvloeit. Een echte willekeurige getallengenerator genereert daarentegen voortdurend nieuwe willekeurige waarden, continu gevoed door hoogwaardige entropiebronnen.

Het genereren van pseudo-willekeurige getallen kent echter kwetsbaarheden. Voor het ongetrainde oog lijken de getallen willekeurig, maar als een aanvaller de initiële beginwaarde (seed) van een PRNG-reeks weet te achterhalen, kan diegene de volledige reeks toekomstige getallen perfect voorspellen.

'Speedrunners' in videogames maken vaak handig gebruik van deze eigenschap — dit noemen ze PRNG-manipulatie. Hierdoor kunnen ze het spelverloop naar hun hand zetten en levels in recordtijd uitspelen. Binnen de gamewereld levert dit gelukkig geen kritieke problemen op.

Er zijn echter situaties waarin het voorspellen van willekeurige getallen desastreuze gevolgen kan hebben. Bijvoorbeeld bij het genereren van cryptografische beveiligingssleutels.

Als een hacker de beginwaarde ontcijfert die gebruikt is om RSA-sleutels in TLS-certificaten te maken, kan hij in theorie versleuteld netwerkverkeer onderscheppen en ontsleutelen. Dit betekent dat wachtwoorden en andere persoonlijke gegevens die over het internet worden verstuurd, in gevaar zijn.

Voor dergelijke kritieke toepassingen is een absoluut onvoorspelbaar systeem vereist: de echte willekeurige getallengenerator (TRNG).

Google generator

Google biedt een ingebouwde tool voor het genereren van willekeurige getallen, gebaseerd op JavaScript. Deze eenvoudige tool is perfect voor alledaags gebruik, zoals het trekken van lootjes of spelen van bordspellen met familie en vrienden. Je vindt deze generator simpelweg door in Google de zoekopdracht "random number generator" in te typen.

De lineaire congruentiemethode

Een van de bekendste algoritmen voor pseudo-willekeurige getallengeneratoren is de lineaire congruentiemethode (LCG). Dit algoritme wordt veel gebruikt voor relatief simpele toepassingen, maar mist cryptografische veiligheid. Derrick Henry Lehmer introduceerde de lineaire congruentiemethode in 1949.

Om getallen met deze methode te genereren, moeten we vier parameters bepalen:

m > 0, de modulus

0 ≤ a ≤ m, de vermenigvuldigingsfactor

0 ≤ c ≤ m, de toename

0 ≤ X₀ ≤ m, het begingetal (de seed)

De reeks willekeurige getallen zelf wordt gegenereerd met de volgende formule:

Xₙ₊₁ = (aXₙ + c) mod m

Het is belangrijk om op te merken dat de effectiviteit van deze methode extreem afhankelijk is van de geselecteerde parameters.

Kies je bijvoorbeeld de volgende set waarden:

X₀ = 3, a = 4, c = 5, m = 6

dan resulteert dit in een korte, zich herhalende reeks van:

3, 5, 1, 3, 5, 1

Dit patroon ziet er totaal niet willekeurig uit.

Als we de parameters echter wijzigen naar:

X₀ = 2, a = 85, c = 507, m = 1356

dan wordt de spreiding van de resultaten aanzienlijk onvoorspelbaarder. De startwaarden voor dit algoritme moeten dus met uiterste zorg worden gekozen.

2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365, 344, 1271, 62, 353, 680, 1355, 422, 1121, 872, 47, 434, 785, 788, 1043, 1022, 593, 740, 1031, 2, 677, 1100, 443, 194, 725, 1112, 107, 110, 365...

Hoewel de lineaire congruentiemethode statistisch gezien een bruikbare pseudo-willekeurige reeks oplevert, is deze cryptografisch zeer zwak. Generatoren op basis van de lineaire congruentiemethode zijn inherent voorspelbaar en mogen daarom nooit in de cryptografie worden gebruikt.

De kwetsbaarheid van LCG-generatoren werd wiskundig aangetoond door Jim Reeds in 1977 en verder uitgewerkt door Joan Boyar in 1982 (zij wist overigens ook kwadratische en kubische generatoren te kraken). Hun onderzoeken bewezen definitief de onbruikbaarheid van congruentiemethoden voor cryptografie. Desondanks blijven LCG's zeer waardevol voor niet-cryptografische doeleinden, zoals computersimulaties. Ze werken razendsnel, gebruiken weinig geheugen en vertonen goede statistische prestaties in de meeste empirische tests.

Moderne hardware willekeurige getallengeneratoren

QRBG121

De willekeur van dit geavanceerde apparaat is gebaseerd op een kwantumfysisch proces: de emissie van fotonen in halfgeleiders en de daaropvolgende detectie van individuele fotonen. Omdat fotonen volledig willekeurig en onafhankelijk van elkaar worden uitgezonden en gedetecteerd, vormt de exacte tijdsinformatie van deze detecties een perfecte entropiebron om willekeurige bits te genereren.

Lavalampen

Op het hoofdkantoor van webbeveiligingsbedrijf Cloudflare in San Francisco staat een muur vol 'lavalampen' die fungeren als random number generator. Een lavalamp is een glazen vat gevuld met transparante olie en gekleurde paraffine (was). Paraffine is zwaarder dan olie, maar door verwarming zet het uit, wordt het lichter en stijgt het op in onvoorspelbare, chaotische bubbels.

De willekeurige beweging van deze vloeistoffen wordt constant gefilmd door camera's. De ruwe videobeelden (snapshots) worden vervolgens door een algoritme omgezet in databits, waaruit onkraakbare encryptiesleutels worden gegenereerd.

Cloudflare gebruikt in andere kantoren nog meer creatieve TRNG-methoden. In Londen registreert een camera de chaotische bewegingen van een drievoudige slinger. In Singapore meet een geigerteller het radioactieve verval van een onschadelijk stukje uranium. Radioactief verval (straling) is wiskundig gezien een van de meest zuivere vormen van natuurlijke willekeur.

HotBits

HotBits is een online dienst die échte willekeurige getallen levert. Deze getallen worden gegenereerd met behulp van een geigerteller die het tijdstip van ioniserende stralingsverval meet. Via de website vul je een aanvraagformulier in voor de benodigde hoeveelheid willekeurige bytes en kies je de gewenste ophaalmethode. Zodra deze cryptografisch veilige data naar de gebruiker is verzonden, wordt de reeks onmiddellijk en permanent uit het HotBits-systeem gewist.

Vacuüm Kwantumfluctuaties

Hoewel de term "vacuüm" leegte suggereert, is een vacuüm in de kwantummechanica allesbehalve leeg. Volgens de onzekerheidsrelatie van Heisenberg verschijnen en verdwijnen er continu zogenaamde virtuele deeltjes in de ruimte.

Canadese natuurkundigen hebben een structureel eenvoudige, maar extreem snelle RNG ontwikkeld die gebruikmaakt van deze vacuümfluctuaties. Het systeem bestaat uit een gepulste laser met een hoge frequentie, een diamant (een medium met een hoge brekingsindex) en een lichtdetector. Wanneer de laserpulsen door de diamant reizen, veranderen de eigenschappen van de fotonen microscopisch, afhankelijk van de willekeurige vacuümveldfluctuaties op dat exacte moment. Hierdoor verschijnen er spectraallijnen in de verstrooide straling. Door de immense onvoorspelbaarheid van vacuümfluctuaties wijken deze lijnen telkens op onvoorspelbare wijze af, wat resulteert in een perfecte willekeurige output.

Koolstofnanobuisgenerator

Deze innovatieve methode combineert een extreem compact formaat met de onvoorspelbaarheid van thermische ruis.

Onderzoekers printten een willekeurige getallengenerator op een statische RAM-geheugencel met behulp van speciale inkt die halfgeleidende koolstofnanobuisjes bevat. Deze slimme geheugencel versterkt en meet fluctuaties in thermische ruis om willekeurige bits te genereren. De koolstofnanobuisgenerator kan moeiteloos worden geprint op flexibele plastic substraten. Dit maakt het de ideale RNG voor kleine, flexibele elektronische apparaten, draagbare sensoren (wearables), goedkope wegwerplabels en slimme kleding.

Dobbelstenen en de Electronic Frontier Foundation (EFF)

De EFF (Electronic Frontier Foundation) heeft een verrassend simpele methode gepromoot om veilige, sterke wachtwoorden te creëren waarbij je zelf een fysieke willekeurige getallengenerator bent: met behulp van dobbelstenen.

Je gooit simpelweg met vijf dobbelstenen tegelijk en noteert de uitslag. Liggen de dobbelstenen van links naar rechts op 6-3-1-3-1, dan zoek je dat nummer op in de speciale "Diceware" woordenlijst op de EFF-website. Bij het nummer 63131 hoort bijvoorbeeld het Engelse woord "turbofan". Herhaal deze procedure meerdere keren (bijvoorbeeld vijf keer) en je krijgt een wachtwoordzin (passphrase) van vijf volledig willekeurige woorden. Bijvoorbeeld: "turbofan purge unfitting try pruning". Met behulp van ezelsbruggetjes zijn dit soort zinnen uitstekend te onthouden door mensen, maar nagenoeg onmogelijk te kraken door computers.

Een Quantum Random Number Generator van een Nokia-smartphone

In 2014 wisten onderzoekers van de Universiteit van Genève met succes een Quantum Random Number Generator (QRNG) te creëren door simpelweg de camera van een Nokia N9-smartphone in te zetten.

De lichtgevoelige beeldsensor van de camera telde exact het aantal fotonen dat elke individuele pixel raakte. Een standaard LED-lampje diende hierbij als lichtbron. In een ultrakort tijdsbestek detecteerde elke pixel van deze 8 megapixel camera gemiddeld zo'n 400 fotonen. Omdat de emissie van licht een kwantumproces is, was dit precieze aantal telkens anders. De gebundelde fotondata van alle pixels werd vervolgens door een algoritme verwerkt tot een perfecte, onvoorspelbare reeks willekeurige getallen.