Getallengenerator

Een willekeurige getallengenerator is een proces om telkens als het nodig is een willekeurig getal te krijgen, zonder de mogelijkheid om een patroon te definiëren uit eerder gegenereerde getallen. Dit getal kan gegenereerd worden door een algoritme of een hardware apparaat.

Het gebruik van willekeurige getallengeneratoren

Het genereren van willekeurige getallen is nodig voor verschillende taken, van computerspellen tot gewone toepassingen. Het systeem gebruikt bijvoorbeeld een willekeurige getallengenerator om een willekeurige banner of een willekeurige advertentie-eenheid op een website weer te geven. In de cryptografie worden willekeurige getallen ook gebruikt om een uniek cijfer of sleutel te maken.

Het genereren van willekeurige getallen wordt gebruikt om getallen of tekst te genereren voor captcha, encryptie, het genereren van salt voor het opslaan van wachtwoorden, een wachtwoordgenerator, een volgorde van kaarten in een online casino, besluitvorming, steekproeven en simulatie.

Het algoritme van de willekeurige getallengenerator wordt vaak gebruikt in videospellen. Zelfs als je op hetzelfde niveau speelt in een spel, zal het niet elke keer precies hetzelfde zijn als je een missie probeert te voltooien. Misschien zijn de verschillen niet te zien in de locatie of missie. Ze zullen echter wel te zien zijn in het aantal vijanden dat nadert en de gebieden waar ze verschijnen, de klimaatveranderingen en de verschillende obstakels die je tegenkomt. Dit maakt het spel spannender.

Verschil tussen een willekeurige en een niet-willekeurige reeks

Laat er een reeks getallen zijn: 1 , 2 , 3 , 4 , 5. Is het willekeurig?

Een willekeurige variabele is een variabele die een van een aantal waarden aanneemt als resultaat van een proef. En je kunt niet nauwkeurig voorspellen dat een bepaalde waarde zal optreden voordat ze verschijnt.

Laten we zeggen dat de gegeven getallen werden verkregen door op een van de bovenste rijen van het toetsenbord te typen. In dit geval blijkt dat deze combinatie niet willekeurig is omdat, na 5, het volgende getal, 6, met grote waarschijnlijkheid kan worden voorspeld. De reeks is alleen willekeurig als er geen afhankelijkheid is tussen de symbolen.

De basisvoorwaarde, die uiterst belangrijk is voor het correcte en eerlijke principe van de random number generator, is een absoluut gelijke waarschijnlijkheid van elk mogelijk getal dat uit dit systeem kan vallen. Dit duidt op volledige onafhankelijkheid van de randomheidsfactor en onafhankelijkheid van welke andere getallen er voor of na het willekeurige getal uitkwamen.

Stel bijvoorbeeld dat je voor het eerst met een zeszijdige dobbelsteen gooit. In dat geval kan absoluut elk getal van 1 tot 6 eruit vallen met dezelfde waarschijnlijkheid. Ongeacht het getal dat je gooit, kun je de dobbelsteen opnieuw gooien met dezelfde kans op hetzelfde getal bij de tweede, honderdste of duizendste worp.

De opeenvolging van cijfers in het getal Pi wordt verondersteld willekeurig te zijn. Stel dat onze denkbeeldige generator gebaseerd is op de output van de bitrepresentatie van het getal Pi, beginnend vanaf een onbekend punt. Zo'n generator zou waarschijnlijk slagen voor de "volgende bit test" omdat het getal Pi een willekeurige reeks is. Maar deze aanpak is cryptografisch niet betrouwbaar. Stel dat een cryptograaf bepaalt welk bit van het getal Pi op dat moment in gebruik is. In dat geval kan hij ook alle vorige en volgende bits berekenen.

Het Amerikaanse National Institute of Standards and Technology heeft het "Statistical Test Package for Random and Pseudorandom Number Generators for Cryptographic Applications" voorgesteld. Het bevat 15 statistische testen die als doel hebben om de mate van willekeur van bits te bepalen die gegenereerd zijn door hardware of software generatoren.

De typen willekeurige getalgeneratoren

Er zijn twee soorten willekeurige getallengeneratoren (RNG): echte willekeurige getallengeneratoren (TRNG) en pseudo-willekeurige getallengeneratoren (PRNG). TRNG's gebruiken fysische fenomenen om getallen te genereren, terwijl PRNG's wiskundige algoritmen gebruiken.

Een echt willekeurig getalgenerator algoritme wordt gemaakt met een hardware apparaat dat minuscule fysische processen gebruikt om willekeurige getallen te genereren, namelijk entropie. Entropie is pure, ongefilterde chaos.

Echte willekeurige getallengeneratoren gebruiken natuurkundige fenomenen zoals:

• radioactiviteit,
• thermische ruis,
• elektromagnetische ruis,
• "kwantummechanica, en andere fenomenen. Een echte RNG wordt wereldwijd veel gebruikt in beveiligingssystemen en sommige vormen van encryptie.

Echte willekeurige getallengeneratoren gebruiken entropiebronnen om entropie op te bouwen en de initiële waarde (seed) te verkrijgen die random number generators nodig hebben.

Het algoritme van de pseudo-willekeurige getallengenerator wordt gebruikt in gebieden zonder beveiligingsproblemen. Willekeur helpt om herhaling te voorkomen en het proces aantrekkelijker te maken voor de eindgebruiker. Het implementeren van de technologie van pseudo-willekeurige getallengeneratoren is goedkoper en sneller omdat er geen hardware voor nodig is en het gemakkelijk in programmacode kan worden ingebouwd. Hoewel het proces niet volledig willekeurig is en wordt bepaald op basis van een algoritme, is het meer geschikt voor spellen en programma's.

De PRNG gebruikt één enkele beginwaarde, waaruit de pseudo-willekeurigheid volgt. Tegelijkertijd genereert de echte random getalgenerator altijd een random getal door een random waarde van hoge kwaliteit te hebben die aan het begin wordt geleverd door verschillende bronnen van entropie.

Het genereren van pseudo-willekeurige getallen heeft nadelen. Ze werken omdat ze willekeurig zijn voor het ongeoefende oog. Stel echter dat je de beginwaarde voor een bepaalde reeks PRNGs zou kennen. In dat geval zou je kunnen voorspellen welke getallen de volgende zouden zijn.

Liefhebbers van snelle videogames maken vaak misbruik van deze kwetsbaarheid - ze noemen het manipulatie van de PRNG. Ze laten het spel voorspelbaar lopen zodat ze er zo snel mogelijk doorheen kunnen. Gelukkig brengt dit geen kritieke problemen met zich mee.

Maar er zijn momenten waarop het voorspellen van willekeurige getallen veel kritischer is. Bijvoorbeeld bij het maken van beveiligingssleutels.

Als de aanvaller achter de beginwaarde komt die wordt gebruikt om RSA-sleutels in TLS-certificaten te maken, kan hij mogelijk netwerkverkeer ontsleutelen. Dit betekent dat hij wachtwoorden en andere persoonlijke informatie die over het internet verstuurd wordt, kan bemachtigen.

In deze situaties is een veiligere manier nodig om willekeurige getallen te verkrijgen, namelijk een echte willekeurige getallengenerator.

Google generator

Google heeft zijn eigen tool om willekeurige getallen te genereren op basis van JavaScript. Deze tool kan handig zijn bij het spelen van spelletjes met vrienden en familie. Je kunt deze generator vinden als je in Google de zoekopdracht "random number generator" intypt.

De lineaire convergentiemethode

Een van de populairste algoritmen voor pseudo-willekeurige getallengeneratoren is de Lineaire Congruente Methode. Het wordt gebruikt in eenvoudige gevallen en heeft geen cryptografische kracht. Derrick Henry Lemaire stelde de lineaire congruente methode voor in 1949.

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

m > 0, modulo

0 ≤ a ≤ m, de vermenigvuldigingsfactor

0 ≤ c ≤ m, de toename

0 ≤ X₀ ≤ m, het begingetal

De reeks willekeurige getallen zelf wordt gegenereerd met de formule:

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

Het is de moeite waard om op te merken dat deze methode afhankelijk is van de keuze van de parameters.

Bijvoorbeeld voor de volgende set:

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

krijgen we een korte repetitieve reeks van

3, 5, 1, 3, 5, 1

wat er niet willekeurig uitziet.

Maar het is de moeite waard om de parameters te veranderen in iets anders:

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

En de spreiding van de resultaten wordt onvoorspelbaarder. Je moet de getallen voor dit algoritme met speciale zorg kiezen.

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 congruente methode een statistisch goede pseudo-willekeurige getallenreeks genereert, is deze niet cryptografisch robuust. Generatoren gebaseerd op de lineaire congruente methode zijn voorspelbaar, dus je kunt ze niet gebruiken in cryptografie.

Generatoren gebaseerd op de lineaire congruente methode werden voor het eerst gekraakt door Jim Reeds in 1977 en daarna door Joan Boyar in 1982. Ze slaagde er ook in om kwadratische en kubische generatoren te kraken. Hiermee bewezen ze de onbruikbaarheid van generatoren gebaseerd op congruente methoden voor cryptografie. Generatoren gebaseerd op de lineaire congruente methode behouden echter hun nut voor niet-cryptografische toepassingen, bijvoorbeeld voor simulaties. Ze zijn efficiënt en vertonen goede statistische prestaties in de meeste empirische tests.

Moderne hardwarerandwoordgeneratoren

QRBG121

Het willekeurigheidseffect in het apparaat is afhankelijk van het kwantumfysische proces van fotonemissie in halfgeleiders en de daaropvolgende detectie van individuele fotonen. In dit proces worden fotonen willekeurig gedetecteerd, onafhankelijk van elkaar, en de tijdsinformatie van de gedetecteerde fotonen wordt gebruikt om bits te genereren.

Lavalampen

In het kantoor van CloudFlare in San Francisco staan random number generators die "lavalampen" worden genoemd. Zo'n lamp is een glazen vat gevuld met transparante olie en doorschijnende paraffine. Paraffine is iets zwaarder dan olie, maar wanneer het lichtjes wordt verwarmd, wordt het lichter en drijft het omhoog.

De beweging van de vloeistoffen wordt gevolgd door verschillende camera's die snapshots maken. De snapshots worden omgezet in getallen, waaruit vervolgens encryptiesleutels worden gegenereerd.

De andere twee kantoren van CloudFlare gebruiken verschillende manieren om willekeurige waarden te krijgen. In Londen registreert een camera de bewegingen van drie chaotische slingers. In Singapore wordt een geigerteller gebruikt die het radioactieve verval van een klein stukje uranium meet. In het laatste geval wordt uranium gebruikt als "gegevensbron" omdat radioactieve straling wordt gekenmerkt door de willekeurigheid van elke vervalhandeling.

HotBits

HotBits is een site die echte willekeurige getallen levert die gegenereerd worden door een geigerteller die voor iedereen ioniserende straling registreert. Je vult op de site een aanvraagformulier in met het aantal willekeurige bytes en kiest de gewenste methode om de gegevens te verkrijgen. Zodra de willekeurige getallen aan de klant zijn geleverd, worden ze onmiddellijk uit het systeem verwijderd.

Vacuüm Kwantumfluctuaties

In tegenstelling tot zijn naam ("vacuus"-leeg) kan het vacuüm niet als leeg worden beschouwd. Volgens het onzekerheidsprincipe van Heisenberg worden er voortdurend virtuele deeltjes geboren en sterven ze ook weer.

Canadese natuurkundigen hebben een snelle en structureel eenvoudige random getalgenerator ontworpen op basis van vacuümfluctuaties. De generator bestaat uit een gepulste laser met een hoge stralingsfrequentie, een medium met een hoge brekingsindex (diamant) en een detector. Bij het passeren van de diamant vertoont elke puls op de sensor andere kenmerken, afhankelijk van de vacuümveldfluctuaties die op het pad van de fotonen voorkomen. In het spectrum van de verstrooide straling verschijnen spectraallijnen. Door de onvoorspelbaarheid van de vacuümfluctuaties verschillen deze lijnen telkens op onvoorspelbare wijze.

Koolstofnanobuisgenerator

Deze methode combineert compactheid met gegenereerde thermische ruis.

De onderzoekers bouwden een random getalgenerator uit een statische random access geheugencel die bedrukt was met speciale inkten die halfgeleidende koolstofnanobuisjes bevatten. De geheugencel gebruikt thermische ruisfluctuaties om willekeurige bits te genereren. De koolstofnanobuisgenerator kan worden geprint op flexibele plastic substraten, waardoor deze kan worden geïntegreerd in kleine, flexibele elektronische apparaten, draagbare sensoren, wegwerplabels en slimme kledingitems.

Cubes en de Electronic Frontier Foundation (EFF)

Het bedrijf heeft een eenvoudige manier voorgesteld om veilige wachtwoorden te maken met behulp van een fysieke willekeurige getallengenerator. Het is gebaseerd op dobbelstenen.

Je gooit bijvoorbeeld met vijf dobbelstenen tegelijk en schrijft de resulterende getallen op. De dobbelstenen zijn van links naar rechts als volgt gerangschikt: 63131. Vervolgens open je een lange lijst met woorden op de EFF website om het corresponderende woord naast 63131 te vinden. Dat woord is "turbofan". Je kunt deze procedure meerdere keren herhalen. Bijvoorbeeld vijf keer. Je kunt eindigen met een zin van vijf woorden. Laten we zeggen: "turbofan purge unfitting try pruning". Als je weet hoe je de regels van mnemonics moet gebruiken, kun je zinnen als deze onthouden.

Een Quantum Random Number Generator van een Nokia-smartphone

In 2014 creëerde de Universiteit van Genève een QRNG-apparaat dat de camera van de Nokia N9-smartphone gebruikte.

De smartphonecamera telde het aantal fotonen dat elke pixel raakte. De lichtbron was een standaard LED. Elke pixel in de 8 MP camera detecteerde ongeveer 400 fotonen in korte tijd. Het totale aantal fotonen op alle pixels werd vervolgens omgezet in een reeks willekeurige getallen.