# Pseudotoevalsgenerator

Een pseudotoevalsgenerator, (Engels: pseudorandom number generator (PRNG)), is een algoritme voor het genereren van pseudotoevalsgetallen, dat wil zeggen een opeenvolging van ogenschijnlijk willekeurige getallen zonder enige samenhang. Deze methode staat ook bekend als deterministisch willekeurige bit-generator (DRBG). Een pseudotoevalsgenerator wordt gebruikt als getallen naar verwachting ongeveer onafhankelijk van elkaar zijn en het mogelijk is om groepen getallen te vinden die een bepaalde regel (groepsgedrag) volgen.
De output die de pseudotoevalsgenerator geeft, is helemaal niet willekeurig, omdat hij volledig wordt bepaald door een relatief kleine verzameling van initiële waarden, de zogenoemde PRNG-toestand. John von Neumann zei hierover: "Iedereen die rekenkundige methoden voor de productie van willekeurige getallen bestudeert, begaat natuurlijk een zonde." Hoewel rijen die meer lijken op echte toevalsgetallen, gegenereerd kunnen worden door toevalsgetalgeneratoren in hardware, zijn pseudotoevalsgeneratoren van belang niet alleen vanwege hun snelheid maar juist vanwege hun reproduceerbaarheid.
Pseudotoevalsgeneratoren zijn ontwikkeld, omdat het weliswaar moeilijk is "echte" toevalsgetallen te genereren, maar in de meeste situaties juist pseudotoevalsgetallen nodig zijn in plaats van echte toevalsgetallen. Pseudotoevalsgeneratoren zijn eenvoudig te implementeren voor computers, en zijn dus gemakkelijk en effectief toe te passen.
Pseudotoevalsgetallen zijn van belang in de praktijk van simulaties (bijvoorbeeld van fysische systemen met de Monte Carlo methode) en staan centraal in de praktijk van de cryptografie en procedurele generatie. De meeste pseudowillekeurige algoritmes proberen een output te produceren die uniform verdeeld is. Een groot aantal generatoren maakt gebruik van lineaire congruentie. Andere zijn geïnspireerd op de Fibonacci-reeks door de toevoeging van twee eerdere waarden of maken gebruik van schuifregisters waarin het vorige resultaat wordt geïnjecteerd na een tussenverwerking. Recente voorbeelden van cryptografische pseudotoevalsgeneratoren zijn Blum Blum Shub (BBS), Fortuna (PRNG), Yarrow en de mersennetwister.
Zorgvuldige wiskundige analyse is nodig om de mate van willekeur van een pseudotoevalsgetal te bepalen. Robert R. Coveyou van Oak Ridge National Laboratory schreef in een artikel: "Het genereren van willekeurige getallen is te belangrijk om aan het toeval over te laten."

## Historische ontwikkeling van pseudotoevalsgeneratoren

De ontwikkeling van algoritmes voor het genereren van pseudowillekeurige getallen is gekoppeld aan de ontwikkeling van de cryptografie. Het militaire en economische belang van deze wetenschap heeft in de loop van de geschiedenis veel onderzoek gemotiveerd.
Encrypties die tot in de negentiende eeuw werden gebruikt, waren afhankelijk van de geheimhouding van de gebruikte methoden. Tegenwoordig zijn deze methoden niet meer praktisch, omdat er veel statistische theorieën zijn die het generatiealgoritme kunnen achterhalen uit de resultaten. Daarnaast kunnen encryptietechnologieën niet langer geheim worden gehouden. In 1883 gaf de Nederlandse linguïst en cryptograaf Auguste Kerckhoffs een fundamentele regel van de moderne cryptografie: de veiligheid van een cryptografisch systeem mag niet van de geheimhouding van het encryptiesysteem maar slechts van de geheimhouding van de sleutel afhangen. Deze regel, gepaard met de ontwikkeling van algoritmen voor de encryptie van berichten, markeert het begin van de opkomst van de pseudotoevalsgeneratoren.
Het belang van pseudotoevalsgeneratoren is echter beperkt gebleven, omdat de fysieke manier van berekening onhandig is bij de lange, repetitieve berekeningen die nodig zijn. De opkomst van pseudotoevalsgeneratoren is pas echt begonnen vanaf 1946, toen John von Neumann zijn “Middle square generator” publiceerde. Het was tijdens de jaren die volgden het meest populaire en ook het snelste algoritme dat werd gebruikt. In 1948 voerde Derrick Henry Lehmer lineaire congruentiegeneratoren in, die in 1958 werden verbeterd door G.J. Mitchell en D.P. Moore. Uiteindelijk zijn ze zeer populair geworden en worden ze in de meest basale encryptiefuncties gebruikt.
Deze eerste pseudotoevalsgeneratoren zijn erg populair, ondanks hun relatief slechte statistische eigenschappen en ondanks dat ze niet voldoen aan de behoeften van cryptografen. Meer recent werden algoritmen ontwikkeld die sterker waren ten opzichte van statistische analyse, zoals het mersennetwisteralgoritme (1997) of de methode van Fibonacci.
Maar geen enkele pseudotoevalsgenerator kan een resultaat produceren dat echt vrij is van enige statistische analyse. Vooral omdat de startwaarde in theorie zelf willekeurig moet zijn en het algoritme niet kan worden gebruikt om zichzelf te initialiseren. Huidige cryptografische generatoren zijn dus verplicht om een zekere mate van willekeur toe te voegen, die niet wordt opgewekt op een deterministische manier. Er wordt nu gekeken in de richting van gemengde generatoren. Zij moeten een algoritme voor het genereren van willekeurige getallen bezitten, en op een fysieke productiemanier willekeur kunnen initialiseren.

## Periodiciteit

Een pseudotoevalsgenerator kan gestart worden vanuit een willekeurige beginsituatie met bijbehorende begintoestand of startwaarde. Bij dezelfde startwaardes zal altijd dezelfde reeks getallen geproduceerd worden. De maximale lengte van de reeks voordat die zich begint te herhalen, wordt bepaald door de grootte van de startwaarde, gemeten in bits. Omdat de lengte van de maximale periode potentieel verdubbelt wanneer aan de startwaarde een bit wordt toegevoegd, is het gemakkelijk om pseudotoevalsgeneratoren te maken met periodes die lang genoeg zijn voor vele praktische toepassingen.
Als de beginwaarde van een pseudotoevalsgenerator n bits bevat, kan de periode niet langer dan $2^{n}$ worden. Lineaire Feedback Schuifregisters (LFSRs) hebben meestal periodes van exact $2^{n}-1$. Lineaire congruentiegeneratoren hebben periodes die berekend kunnen worden door middel van factorisatie. Mixen van beide methodes hebben periodes van gemiddeld ongeveer $2^{n/2}$. Mixen die omkeerbaar zijn (permutaties) hebben periodes van gemiddeld $2^{n-1}$ en de periode zal altijd de originele begintoestand bevatten. Hoewel pseudotoevalsgeneratoren hun reeks zullen herhalen na het bereiken van het einde van een periode, impliceert een herhaald resultaat niet dat het einde van de periode is bereikt, aangezien de begintoestand groter kan zijn dan de output. Dit is met name duidelijk te zien bij pseudotoevalsgeneratoren met een output van 1 bit.
De meeste pseudotoevalsgeneratoren produceren getallenreeksen die uniform verdeeld zijn. Een open vraag die centraal staat in de theorie en praktijk van cryptografie is of er een manier bestaat om de output van een pseudotoevalsgenerator van hoge kwaliteit van een werkelijk willekeurige volgorde te onderscheiden, zonder te weten welk algoritme gebruikt is en wat de begintoestand was. De veiligheid van de meeste cryptografische algoritmen en protocollen met behulp van pseudotoevalsgeneratoren is gebaseerd op de veronderstelling dat het onhaalbaar is om onderscheid te maken tussen het gebruik van een geschikte pseudotoevalsgenerator en het gebruik van een werkelijk willekeurige volgorde.

## Problemen

Als een pseudotoevalsgenerator wordt uitgevoerd op een deterministische computer, wordt het automatisch een deterministisch algoritme. De output is onvermijdelijk onderworpen aan een karakteristiek kenmerk dat ontbreekt bij echte willekeurige volgorde: de periodiciteit. Een niet-periodieke generator is niet onmogelijk, maar vereist meer geheugen om niet terug te keren in dezelfde staat. Om dit theoretische obstakel te omzeilen kan de generator starten in een bepaalde toestand (de startwaarde). Het zal echter steeds hetzelfde resultaat produceren als de startwaarde hetzelfde blijft – wat als een voordeel kan worden beschouwd onder bepaalde voorwaarden, met name in termen van reproduceerbaarheid. Daarnaast is het aantal bruikbare startwaarden niet oneindig en kan de generator slechts een beperkt aantal verschillende reeksen getallen produceren.
Ter verbetering van de kwaliteit van de output, kunnen we “willekeurige” componenten introduceren uit de imperfecties van het systeem, zoals de tijd tussen aanzetten van de computer en de toegang tot de harde schijf. Deze waarden zijn echter begrensd door intervallen en / of gedeeltelijk voorspelbaar. Het systeem is nog steeds pseudowillekeurig.
De lengte van de maximale periode tot een herhaling wordt elke keer een beetje groter als er bits aan de interne toestand worden toegevoegd. Het is gemakkelijk om pseudowillekeurige generatoren te bouwen met een periode langer dan een computer zou kunnen berekenen. Zo heeft de mersennetwister een wiskundig bewezen periode van $2^{19937}-1$, een astronomisch getal.
Het blijft een onbeantwoorde vraag of het mogelijk is om onderscheid te maken tussen een pseudowillekeurig, algoritmisch gegenereerd getal en een perfect willekeurig getal. En dit zou dan moeten kunnen zonder de startwaarde van de generator te weten. In de cryptografie gaan de meeste deskundigen ervan uit dat dit onmogelijk is met de huidige rekenkracht. Dit principe wordt gebruikt bij stroomvercijferingsalgoritmen zoals RC4, waarbij een XOR-bewerking de pseudowillekeurige getallen combineert met gegeven getallen.
In principe hebben de meeste generatoren wiskundige problemen die gedetecteerd kunnen worden met statistische analyse. De kwaliteit van de output wordt vaak verhoogd ten koste van de productiesnelheid. Bij het kiezen van een generator moeten deze parameters worden overwogen. De volgende problemen kunnen optreden:
* Kortere periode met bepaalde startwaarden (deze startwaarden worden zwak genoemd);
* Kwaliteit van de generator varieert sterk, afhankelijk van de startwaarde;
* Onvolmaakte distributie, gebrek aan uniformiteit;
* Slechte dimensionale verdeling van de volgorde van de output;
* Of het tegenovergestelde: perfecte distributie, perfecte uniformiteit;
* Opeenvolgende waarden zijn niet onafhankelijk;
* Bepaalde delen van de output zijn minder willekeurig (bijvoorbeeld, bit nummer 8 is vaak 1).
Gebreken variëren van belangrijk tot bijna onzichtbaar. Het algoritme RANDU, dat al veel decennia gebruikt werd, zou systematische fouten vertonen en enkele resultaten die zijn verkregen kunnen niet volledig worden gevalideerd. Soms maakt een praktische toepassing het mogelijk om het probleem op te sporen (bv. een fysieke simulatie met volledig onverwachte resultaten). Maar het is beter om te testen voordat het algoritme in gebruik wordt genomen zodat fouten op tijd kunnen worden ontdekt.

## Voorbeelden van bekende algoritmen
### Middle-square method

De middle-square method is een op de computer gebaseerde PNRG methode. Deze werd in 1946 door John von Neumann bedacht. De methode werkt als volgt: begin met een willekeurig getal, kwadrateer het en neem de middelste cijfers van het resulterende getal. Dat getal is dan te gebruiken als startwaarde voor de volgende iteratie.

### Voorbeeld

Neem het getal 1234 als startwaarde.
* Kwadrateren geeft $1234^{2}=1522756$. Dit kan worden geschreven als 01522756, een 8-cijferig getal dat het kwadraat is van een 4-cijferig getal.
* Pak de middelste vier cijfers: 5227. Dit is de startwaarde voor de volgende iteratie.
* $5227^{2}=27321529$. De nieuwe startwaarde is dus 3215.
Von Neumann gebruikte voor deze methode 10-cijferige getallen, maar het principe was hetzelfde.
Een probleem met de middle-square method is dat de kwaliteit van de output afhankelijk is van de startwaarde. Zo produceert het getal “0000” altijd dezelfde reeks en vormt het een soort absorberende toestand of attractor van het algoritme. Von Neumann was zich hiervan bewust, maar hij was bang dat wiskundige oplossingen de fouten slechts zouden verbergen in plaats van ze te verwijderen.
Von Neumann gebruikt zijn methode op de ENIAC computer. Hij verkreeg een generatie die 200 keer sneller was dan de resultaten die verkregen werden bij het lezen van nummers met ponskaarten. Volgens Von Neumann konden generatoren op basis van dit materiaal niet naar behoren functioneren, omdat ze de resultaten niet op konden slaan en ze dus niet gecontroleerd konden worden. Als ze de gegenereerde output wel zouden bewaren, dan zouden zij het beperkte computergeheugen uitputten en daarmee dus ook de mogelijkheid van de computer om nummers te kunnen genereren en te lezen. De middle-square method is verdrongen door de opkomst van meer uitgebreide generatoren, zoals de Monte-Carlosimulatie.

### Fibonaccimethode

Deze methode is gebaseerd op de rij van Fibonacci, modulo de maximale gewenste waarde:
$X_{n}\equiv (X_{n-1}+X_{n-2}){\bmod {m}}\;\;{\mbox{met}}\;X_{0}\;{\mbox{en}}\;X_{1}\;{\mbox{als input.}}$
Je kunt ook een variant gebruiken:
$X_{n}\equiv (X_{n-1}+X_{n-k}){\bmod {m}}\;\;{\mbox{met}}\;X_{1},...,X_{k-1}\;{\mbox{als input.}}$
De kwaliteit van de generator hangt af van de waarde van $k$ en de startwaarden. Deze generator is zeer eenvoudig te implementeren en verbruikt weinig middelen.

### Lineaire congruentiegeneratoren

In 1948 introduceerde Derrick Henry Lehmer lineaire congruentiegeneratoren in een gereduceerde vorm (geen waardetoename $c$). Lineaire congruentiegeneratoren werden gegeneraliseerd en op grote schaal gebruikt. Ze zijn gebaseerd op een eenvoudige recursieve formule:
$X_{n+1}\equiv (a\cdot X_{n}+c){\bmod {m}}$
met startwaarde $X_{0}$. In het algemeen is de startwaarde een priemgetal, maar de exacte beperkingen hiervoor zijn afhankelijk van het algoritme. Sommige startwaarden kunnen leiden tot gedegenereerde reeksen.
De periode van deze generator is maximaal $m$. De periode is dus relatief kort, omdat $m$ vaak wordt gekozen op de manier dat woorden op hun lengte worden geordend op de computer. Maar deze methode heeft een voordeel: we weten de criteria voor de getallen $a$, $c$ en $m$, die zullen worden toegestaan om een maximale periode (gelijk aan $m$) te verkrijgen.

### Mersennetwister

De mersennetwister is in 1997 uitgevonden door Makoto Matsumoto en Takuji Nishimura en is vooral bekend om zijn kwaliteit. Met een periode van $2^{19937}-1$ iteraties, verdeelt de mersennetwister de getallen uniform over 623 dimensies (voor 32-bit getallen) en blijkt hij sneller te zijn dan de meeste zwakkere statistische methoden. Het is echter mogelijk om de output van de Mersenne-twister te analyseren en dan te beseffen dat de output niet geheel willekeurig is. Tot op heden zijn de enige negatieve effecten gerelateerd aan cryptografie, de mersennetwister is dus geen cryptografische generator.

### Cryptografisch beveiligde pseudotoevalsgeneratoren

Een PRNG geschikt voor cryptografische toepassingen wordt een cryptografisch veilige PRNG (CSPRNG) genoemd. Een vereiste voor een CSPRNG is dat iemand die de begintoestand niet weet slechts een verwaarloosbaar voordeel heeft in het onderscheiden van de gegenereerde output en een aantal willekeurige getallenreeksen. Met andere woorden, terwijl een PRNG alleen bepaalde statistische toetsen moet kunnen doorstaan, moet een CSPRNG erin slagen alle statistische toetsen te doorstaan die zijn beperkt tot de polynomiale tijd in mate van de begintoestand. Hoewel zo’n eigenschap niet aangetoond kan worden, kan een sterk bewijs worden geleverd door de CSPRNG naar een bekend complexiteitsprobleem te herleiden (bv. ontbinden in priemfactoren). In het algemeen kunnen jaren van onderzoek nodig zijn voordat een algoritme kan worden gecertificeerd als een CSPRNG.
Generatoren die veilig genoeg zijn:
* Yarrow
* Fortuna
* Blum Blum Shub (veilig maar traag)
* ISAAC

## Toepassingen

De pseudotoevalsgeneratoren zijn van groot belang in diverse gebieden. Bijvoorbeeld bij de uitwisseling van informatie via draadloze netwerken. Hiervoor wordt een mechanisme vereist dat de vertrouwelijkheid van de items die uitgewisseld worden het best mogelijk kan behouden. Een ander voorbeeld van een toepassing van pseudotoevalsgeneratoren zijn cryptosystemen. Cryptoanalyse is een opkomend vakgebied en toont een hoog niveau van betrouwbaarheid in de methoden die gebruikt worden bij encryptie. Het meest eenvoudige voorbeeld van deze methoden is stroomvercijfering, waarbij tekst bit-voor-bit, of woord-voor-woord, in cijfertekst wordt omgezet. Dit proces staat bekend om zijn snelheid en zijn concurrentiepositie ten opzichte van andere methoden, omdat het minder gevoelig is voor fouten tijdens de transmissie.
Pseudotoevalsgeneratoren vinden hun toepassing ook in het global positioning system gps. Het doel is het meten van een afstand tussen twee apparaten, namelijk een gps-satelliet en de ontvanger. Deze meting wordt uitgevoerd door het genereren van een pseudo-willekeurige reeks op dezelfde snelheid op elk apparaat, aangenomen dat deze zal worden gesynchroniseerd. De reeks van de satelliet wordt dan gemoduleerd en verzonden naar de ontvanger, die het vergelijkt met zijn eigen reeks. Er is een tijdsverschil tussen de twee ketens en dit verschil komt overeen met de looptijd van de informatie tussen de satelliet en de ontvanger. Het is voldoende om dit verschil te meten en te vermenigvuldigen met de snelheid van elektromagnetische golven in de lucht om de gewenste afstand te krijgen.