Wat is een willekeurige nummer generator?
Willekeurig nummer generator (Engels: random number generator, RNG) — het is een systeem dat is ontworpen om een reeks getallen of symbolen te genereren
waarvan de betekenis niet op voorhand kan worden voorspeld. Een specifieke reeks gegenereerde resultaten kan een bepaalde
patroon dat na het generatieproces zal worden getraceerd, maar dat niet van tevoren kon worden voorzien.
is een apparaat dat willekeurige getallen genereert uit een fysiek proces dat voortdurend verandert op een manier die:
praktisch niet te modelleren. Dergelijke generatoren kunnen gebaseerd zijn op het gebruik van macroscopische willekeurige processen, dat wil zeggen:
op een schaal die metingen en waarnemingen met het blote oog mogelijk maakt, bijvoorbeeld het opgooien van munten, dobbelstenen of
roulette wielen. Hoewel een macroscopisch proces volledig kan worden bepaald volgens de Newtoniaanse mechanica,
een goed ontworpen mechanisme zoals een roulettewiel zal een onvoorspelbaar resultaat opleveren, dat kan worden verklaard
door chaostheorie en de instabiliteit van dynamische systemen als gevolg van het verschil in de beginvoorwaarden van elk
nieuwe poging om het roulettewiel te laten draaien. Het grootste nadeel van generatoren die macroscopische processen gebruiken, is altijd:
lage snelheid, en als gevolg daarvan het onvermogen om in korte tijd een groot aantal waarden te genereren.
Tegenwoordig gebruiken hardware-generators voor willekeurige getallen meestal apparaten op basis van microscopische verschijnselen
die statistisch willekeurige "ruis"-signalen op laag niveau genereren, zoals verschillende ruis (рagelruis, thermische ruis, atmosferische ruis),
het foto-elektrisch effect, waarbij een bundelsplitser betrokken is, en andere kwantumverschijnselen. Dergelijke processen zijn goede bronnen
van entropie omdat hun resultaat in theorie absoluut onmogelijk te voorspellen is, maar vanwege de complexiteit van
implementatie en relatieve traagheid van het werk, het toepassingsgebied van dergelijke generatoren is beperkt tot vakgebieden
met bepaalde vereisten voor de gegenereerde waarden.
In principe worden elektronische hardware-generators voor willekeurige getallen gebruikt in cryptografie om willekeurige cryptografisch te genereren sleutels om veilige gegevensoverdracht te garanderen, bijvoorbeeld in internetcoderingsprotocollen zoals TLS (Engels: Transport Layer Security).
Een alternatief voor hardware (fysieke) generatoren zijn generatoren op basis van algoritmen — pseudotoevalsgenerator (Engels: pseudorandom number generator, PRNG),
die een reeks getallen creëren die op willekeurig lijken, maar dat in feite niet is. De nummers gegenereerd door de PRNG
kunnen niet als echt willekeurig worden beschouwd, omdat ze volledig worden bepaald door een initiële waarde, het zaad van de PRNG. Hoewel
de reeks getallen die wordt gegenereerd door hardware-generators voor willekeurige getallen ligt dichter bij echt willekeurig, pseudo-willekeurig
nummergeneratoren worden in de praktijk vaak op veel gebieden gebruikt vanwege hun snelheid in nummergeneratie, gemak van
implementatie en relatieve goedkoopheid. Er zijn veel methoden om pseudo-willekeurige getallenreeksen te maken,
waaronder de Mersenne Twister, een lineaire congruentiële generator (LCG), Xorshift random number generators, ook
genaamd schuifregistergeneratoren, de Well Equidistributed Long-period Linear (WELL), een vorm van
lineair-feedback schuifregister geoptimaliseerd voor software-implementatie en andere methoden op basis van algoritmen.
voor een geheel getal n.
Deze PRNG is speciaal ontworpen om de meeste tekortkomingen in eerdere PRNG's op te lossen. De belangrijkste voordelen van de mersennetwister:
Generatoren gebaseerd op onvoorspelbare verschijnselen
Om echte willekeurige getallen te genereren, wordt een hardware-generator voor willekeurige getallen (hardware random number generator, HRNG in het Engels) gebruikt of het wordt ook wel generatoren gebaseerd op onvoorspelbare verschijnselen (Engels: true random number generator, TRNG) —
is een apparaat dat willekeurige getallen genereert uit een fysiek proces dat voortdurend verandert op een manier die:
praktisch niet te modelleren. Dergelijke generatoren kunnen gebaseerd zijn op het gebruik van macroscopische willekeurige processen, dat wil zeggen:
op een schaal die metingen en waarnemingen met het blote oog mogelijk maakt, bijvoorbeeld het opgooien van munten, dobbelstenen of
roulette wielen. Hoewel een macroscopisch proces volledig kan worden bepaald volgens de Newtoniaanse mechanica,
een goed ontworpen mechanisme zoals een roulettewiel zal een onvoorspelbaar resultaat opleveren, dat kan worden verklaard
door chaostheorie en de instabiliteit van dynamische systemen als gevolg van het verschil in de beginvoorwaarden van elk
nieuwe poging om het roulettewiel te laten draaien. Het grootste nadeel van generatoren die macroscopische processen gebruiken, is altijd:
lage snelheid, en als gevolg daarvan het onvermogen om in korte tijd een groot aantal waarden te genereren.Tegenwoordig gebruiken hardware-generators voor willekeurige getallen meestal apparaten op basis van microscopische verschijnselen
die statistisch willekeurige "ruis"-signalen op laag niveau genereren, zoals verschillende ruis (рagelruis, thermische ruis, atmosferische ruis),
het foto-elektrisch effect, waarbij een bundelsplitser betrokken is, en andere kwantumverschijnselen. Dergelijke processen zijn goede bronnen
van entropie omdat hun resultaat in theorie absoluut onmogelijk te voorspellen is, maar vanwege de complexiteit van
implementatie en relatieve traagheid van het werk, het toepassingsgebied van dergelijke generatoren is beperkt tot vakgebieden
met bepaalde vereisten voor de gegenereerde waarden.In principe worden elektronische hardware-generators voor willekeurige getallen gebruikt in cryptografie om willekeurige cryptografisch te genereren sleutels om veilige gegevensoverdracht te garanderen, bijvoorbeeld in internetcoderingsprotocollen zoals TLS (Engels: Transport Layer Security).
Pseudotoevalsgenerator
Een alternatief voor hardware (fysieke) generatoren zijn generatoren op basis van algoritmen — pseudotoevalsgenerator (Engels: pseudorandom number generator, PRNG),
die een reeks getallen creëren die op willekeurig lijken, maar dat in feite niet is. De nummers gegenereerd door de PRNG
kunnen niet als echt willekeurig worden beschouwd, omdat ze volledig worden bepaald door een initiële waarde, het zaad van de PRNG. Hoewel
de reeks getallen die wordt gegenereerd door hardware-generators voor willekeurige getallen ligt dichter bij echt willekeurig, pseudo-willekeurig
nummergeneratoren worden in de praktijk vaak op veel gebieden gebruikt vanwege hun snelheid in nummergeneratie, gemak van
implementatie en relatieve goedkoopheid. Er zijn veel methoden om pseudo-willekeurige getallenreeksen te maken,
waaronder de Mersenne Twister, een lineaire congruentiële generator (LCG), Xorshift random number generators, ook
genaamd schuifregistergeneratoren, de Well Equidistributed Long-period Linear (WELL), een vorm van
lineair-feedback schuifregister geoptimaliseerd voor software-implementatie en andere methoden op basis van algoritmen.
Mersennetwister
De mersennetwister is een van de meest populaire pseudo-willekeurige nummergeneratoren, ontwikkeld in 1997 door Makoto Matsumoto (松本 眞) en Takuji Nishimura (西村 ). De naam komt van het feit dat het periodelengte wordt gekozen als een mersennepriemgetallen, het is een priemgetal van de vorm voor een geheel getal n.
Deze PRNG is speciaal ontworpen om de meeste tekortkomingen in eerdere PRNG's op te lossen. De belangrijkste voordelen van de mersennetwister:
- Een zeer lange periode van 219937 — 1
- Slaagt voor veel statistische willekeurigheidstests, waaronder Diehard-tests en de meeste, maar niet alle TestU01-tests
- Heeft een vrije softwarelicentie en patentvrij voor alle varianten behalve CryptMT
- k-gedistribueerd tot 32-bits nauwkeurigheid voor elke 1 ≤ k ≤ 623
- Implementaties genereren over het algemeen sneller willekeurige getallen dan echte (hardware) generatiemethoden