Een pseudo-willekeurig getal is een speciaal getal dat wordt gegenereerd door een speciale generator. De Deterministic Random Bit Generator (PRNG), ook bekend als de Deterministic Random Bit Generator (DRBG), is een algoritme voor het genereren van een reeks getallen waarvan de eigenschappen de kenmerken van willekeurige reeksen van getallen benaderen. De gegenereerde PRNG-reeks is niet echt willekeurig, omdat deze volledig wordt bepaald door een seed-waarde die de PRNG-seed wordt genoemd en die echt willekeurige waarden kan bevatten. Hoewel reeksen die dichter bij willekeurig liggen kunnen worden gegenereerd met behulp van hardwaregeneratoren voor willekeurige getallen, zijn pseudo-willekeurige nummergeneratoren in de praktijk belangrijk voor de snelheid van het genereren van getallen en hun reproduceerbaarheid.
Toepassing
PRNG's staan centraal in toepassingen zoals simulatie (bijvoorbeeld voor Monte Carlo), elektronische spellen (bijvoorbeeld voor procedurele generatie) en cryptografie. Cryptografische toepassingen vereisen dat de uitvoerde gegevens waren niet voorspelbaar op basis van eerdere informatie. Er zijn complexere algoritmen nodig die niet de lineariteit van eenvoudige PRNG's erven.
Algemene voorwaarden
Goede statistische eigenschappen zijn een centrale vereiste voor het verkrijgen van een PRNG. Over het algemeen is een zorgvuldige wiskundige analyse nodig om er zeker van te zijn dat de RNG getallen genereert die dicht genoeg bij willekeur liggen om geschikt te zijn voor het beoogde gebruik.
John von Neumann waarschuwde voor het verkeerd interpreteren van PRNG als een echt willekeurige generator en grapte dat "Iedereen die rekenkundige methoden voor het genereren van willekeurige getallen overweegt, is zeker in een staat van zonde."
Gebruik
PRNG kan worden gestart vanuit een willekeurige beginstatus. Het zal altijd dezelfde reeks genereren wanneer het met deze status wordt geïnitialiseerd. De PRNG-periode wordt als volgt gedefinieerd: maximum over alle begintoestanden van de lengte van het niet-herhalende sequentievoorvoegsel. De periode wordt beperkt door het aantal toestanden, meestal gemeten in bits. Omdat de periodelengte mogelijk verdubbelt met elke "state" bit toegevoegd, is het gemakkelijk om PRNG's te maken met perioden die groot genoeg zijn voor veel praktische toepassingen.
Als de interne toestand van de PRNG n bits bevat, kan de periode niet meer dan 2n resultaten zijn, deze is veel korter. Voor sommige PRNG's kan de duur worden berekend zonder de hele periode te omzeilen. Linear Feedback Shift Registers (LFSR's) zijn meestal:worden zo gekozen dat de perioden gelijk zijn aan 2n − 1.
Lineaire congruente generatoren hebben perioden die kunnen worden berekend met factoring. Hoewel de PPP zijn resultaten zal herhalen nadat ze het einde van de periode hebben bereikt, betekent een herhaald resultaat niet dat het einde van de periode is bereikt, aangezien de interne status groter kan zijn dan de output; dit is vooral duidelijk voor PRNG's met enkelbits uitvoer.
Mogelijke fouten
Fouten gevonden door defecte PRNG's variëren van subtiele (en onbekende) tot voor de hand liggende. Een voorbeeld is het RANDU-algoritme voor willekeurige getallen, dat al tientallen jaren op mainframes wordt gebruikt. Het was een ernstige tekortkoming, maar de tekortkoming ervan bleef lange tijd onopgemerkt.
Op veel gebieden zijn onderzoeksstudies die gebruik hebben gemaakt van willekeurige selectie, Monte Carlo-simulaties of andere methoden op basis van RNG veel minder betrouwbaar dan het resultaat van GNPG van slechte kwaliteit. Zelfs vandaag de dag is voorzichtigheid soms geboden, zoals blijkt uit de waarschuwing in de International Encyclopedia of Statistical Science (2010).
Succesvolle casestudy
Beschouw als voorbeeld de veelgebruikte Java-programmeertaal. Vanaf 2017 vertrouwt Java nog steeds op de Linear Congruential Generator (LCG) voor zijn PRNG.
Geschiedenis
De eerste PRNG om ernstige problemen te voorkomen en toch behoorlijk snel te werken,was de Mersenne Twister (hieronder besproken), die in 1998 werd gepubliceerd. Sindsdien zijn er andere hoogwaardige PRNG's ontwikkeld.
Maar de geschiedenis van pseudo-willekeurige getallen houdt daar niet op. In de tweede helft van de 20e eeuw omvatte de standaardklasse van algoritmen die voor PRNG's werden gebruikt lineaire congruente generatoren. Het was bekend dat de kwaliteit van de LCG onvoldoende was, maar betere methoden waren er niet. Press et al (2007) beschreven het resultaat als volgt: "Als alle wetenschappelijke artikelen waarvan de resultaten twijfelachtig zijn vanwege [LCG's en gerelateerde] uit de bibliotheekplanken zouden verdwijnen, zou er op elke plank een opening zijn ter grootte van je vuist."
De belangrijkste prestatie bij het maken van pseudo-willekeurige generatoren was de introductie van methoden op basis van lineair recurrent in een veld met twee elementen; dergelijke oscillatoren zijn gekoppeld aan schuifregisters met lineaire terugkoppeling. Ze dienden als basis voor de uitvinding van pseudo-willekeurige nummersensoren.
Met name de uitvinding van Mersen Twister uit 1997 voorkwam veel van de problemen met eerdere generatoren. De Mersenne Twister heeft een periode van 219937-1 iteraties (-4,3 × 106001). Het is bewezen dat het uniform is verdeeld in (tot) 623 dimensies (voor 32-bits waarden), en op het moment van zijn introductie was het sneller dan andere statistisch verantwoorde generatoren die pseudo-willekeurige nummerreeksen produceren.
In 2003 introduceerde George Marsaglia een familie van xorshift-generatoren, ook gebaseerd op lineaire herhaling. Deze generatoren zijn extreemzijn snel en - in combinatie met een niet-lineaire werking - doorstaan ze strenge statistische tests.
In 2006 werd de WELL-generatorfamilie ontwikkeld. WELL-generatoren verbeteren in zekere zin de kwaliteit van Twister Mersenne, die een te grote toestandsruimte heeft en zeer langzaam herstelt, waardoor pseudo-willekeurige getallen met veel nullen worden gegenereerd.
Cryptografie
PRNG geschikt voor cryptografische toepassingen wordt cryptografisch veilige PRNG (CSPRNG) genoemd. De vereiste voor een CSPRNG is dat een aanvaller die de seed niet kent, slechts een marginaal voordeel heeft bij het onderscheiden van de outputreeks van de generator van een willekeurige reeks. Met andere woorden, terwijl een PRNG alleen moet slagen voor bepaalde statistische tests, moet een CSPRNG alle statistische tests doorstaan die beperkt zijn tot polynomiale tijd in zaadgrootte.
Hoewel het bewijs van deze eigenschap het huidige niveau van computationele complexiteitstheorie te boven gaat, kan sterk bewijs worden geleverd door de CSPRNG te reduceren tot een probleem dat als moeilijk wordt beschouwd, zoals factorisatie van gehele getallen. Over het algemeen kunnen jaren van beoordeling nodig zijn voordat een algoritme kan worden gecertificeerd als een CSPRNG.
Er is aangetoond dat het waarschijnlijk is dat de NSA een asymmetrische achterdeur heeft geplaatst in de NIST-gecertificeerde Dual_EC_DRBG pseudo-willekeurige nummergenerator.
Pseudo-willekeurige algoritmencijfers
De meeste PRNG-algoritmen produceren reeksen die gelijkmatig worden verdeeld door een van de verschillende tests. Dit is een open vraag. Het is een van de centrale punten in de theorie en praktijk van cryptografie: is er een manier om de uitvoer van een hoogwaardige PRNG te onderscheiden van een echt willekeurige reeks? In deze instelling weet de resolver dat ofwel een bekend PRNG-algoritme is gebruikt (maar niet de status waarmee het is geïnitialiseerd), of dat er een echt willekeurig algoritme is gebruikt. Hij moet ze onderscheiden.
De beveiliging van de meeste cryptografische algoritmen en protocollen die PRNG's gebruiken, is gebaseerd op de veronderstelling dat het onmogelijk is om onderscheid te maken tussen het gebruik van een geschikte PRNG en het gebruik van een echt willekeurige reeks. De eenvoudigste voorbeelden van deze afhankelijkheid zijn stroomcoderingen, die meestal werken door het tekstbericht met een PRNG-uitvoer weg te laten of te verzenden, waardoor de cijfertekst wordt geproduceerd. Het ontwerpen van cryptografisch geschikte PRNG's is buitengewoon moeilijk omdat ze aan aanvullende criteria moeten voldoen. De grootte van de periode is een belangrijke factor in de cryptografische geschiktheid van een PRNG, maar niet de enige.
Een vroege computer-PRNG, voorgesteld door John von Neumann in 1946, staat bekend als de gemiddelde kwadratenmethode. Het algoritme is als volgt: neem een willekeurig getal, kwadratisch, verwijder de middelste cijfers van het resulterende getal als een "willekeurig getal", gebruik dit getal vervolgens als het startnummer voor de volgende iteratie. Bijvoorbeeld, het kwadrateren van het getal 1111 geeft:1234321, dat kan worden geschreven als 01234321, is een 8-cijferig getal het kwadraat van een 4-cijferig getal. Dit geeft 2343 als een "willekeurig" getal. Het resultaat van het herhalen van deze procedure is 4896, enzovoort. Von Neumann gebruikte 10-cijferige nummers, maar het proces was hetzelfde.
Nadelen van het "middelste vierkant"
Het probleem met de "mean square"-methode is dat alle reeksen zich uiteindelijk herhalen, sommige heel snel, bijvoorbeeld: 0000. Von Neumann wist hiervan, maar hij vond een benadering die voldoende was voor zijn doeleinden, en was bang dat de wiskundige "correcties" zouden de fouten gewoon verbergen in plaats van ze te verwijderen.
Von Neumann vond hardware random en pseudo-random number generators ongeschikt: als ze de gegenereerde output niet registreren, kunnen ze later niet op fouten worden gecontroleerd. Als ze hun resultaten zouden opschrijven, zouden ze het beperkte beschikbare geheugen van de computer uitputten en daarmee het vermogen van de computer om getallen te lezen en te schrijven. Als getallen op kaarten zouden worden geschreven, zou het schrijven en lezen ervan veel langer duren. Op de ENIAC-computer gebruikte hij de "middle square"-methode en voerde het proces uit om pseudo-willekeurige getallen honderden keren sneller te verkrijgen dan het lezen van getallen van ponskaarten.
Mean square is sindsdien vervangen door complexere generatoren.
Innovatieve methode
Een recente innovatie is om het gemiddelde kwadraat te combineren met de Weil-reeks. Deze methode zorgt voor producten van hoge kwaliteit binnenlange periode. Het helpt om de beste pseudo-willekeurige getalformules te krijgen.
