Et pseudo-tilfeldig tall er et spesielt tall generert av en spesiell generator. Den Deterministic Random Bit Generator (PRNG), også kjent som Deterministic Random Bit Generator (DRBG), er en algoritme for å generere en sekvens av tall hvis egenskaper tilnærmer egenskapene til tilfeldige tallsekvenser. Den genererte PRNG-sekvensen er ikke virkelig tilfeldig, siden den er helt bestemt av en frøverdi k alt PRNG-frø, som kan inkludere virkelig tilfeldige verdier. Selv om sekvenser som er nærmere tilfeldig kan genereres ved hjelp av maskinvare tilfeldige tallgeneratorer, er pseudo-tilfeldige tallgeneratorer viktige i praksis for hastigheten på tallgenerering og deres reproduserbarhet.
Application
PRNG-er er sentrale i applikasjoner som simulering (f.eks. for Monte Carlo), elektroniske spill (f.eks. for prosedyregenerering) og kryptografi. Kryptografiske applikasjoner krever at utgangendataene var ikke forutsigbare fra tidligere informasjon. Det kreves mer komplekse algoritmer som ikke arver lineariteten til enkle PRNG-er.
Vilkår og betingelser
Gode statistiske egenskaper er et sentr alt krav for å få en PRNG. Generelt er det nødvendig med nøye matematisk analyse for å være sikker på at RNG genererer tall som er nær nok tilfeldige til å være passende for den tiltenkte bruken.
John von Neumann advarte mot å feiltolke PRNG som en virkelig tilfeldig generator og spøkte med at "Alle som vurderer aritmetiske metoder for å generere tilfeldige tall er absolutt i en tilstand av synd."
Bruk
PRNG kan startes fra en vilkårlig starttilstand. Den vil alltid generere den samme sekvensen når den initialiseres med denne tilstanden. PRNG-perioden er definert som følger: maksimum over alle starttilstander av lengden til det ikke-repeterende sekvensprefikset. Perioden er begrenset av antall tilstander, vanligvis målt i biter. Fordi periodelengden potensielt dobles med hver "state"-bit lagt til, er det enkelt å lage PRNG-er med perioder som er store nok for mange praktiske bruksområder.
Hvis den interne tilstanden til PRNG inneholder n biter, kan perioden ikke være mer enn 2n resultater, den er mye kortere. For noen PRNG-er kan varigheten beregnes uten å omgå hele perioden. Linear Feedback Shift Registers (LFSRs) er vanligvisvelges slik at de har perioder lik 2n − 1.
Lineære kongruensielle generatorer har perioder som kan beregnes ved hjelp av factoring. Selv om PPP vil gjenta sine resultater etter at de når slutten av perioden, betyr ikke et gjentatt resultat at slutten av perioden er nådd, siden dens interne tilstand kan være større enn produksjonen; dette er spesielt tydelig for PRNG-er med enkeltbitutgang.
Mulige feil
Feil funnet av defekte PRNG-er varierer fra subtile (og ukjente) til åpenbare. Et eksempel er RANDU tilfeldig tallalgoritme, som har blitt brukt på stormaskiner i flere tiår. Det var en alvorlig mangel, men dens utilstrekkelighet gikk ubemerket hen i lang tid.
I mange områder er forskningsstudier som har brukt tilfeldig utvalg, Monte Carlo-simuleringer eller andre metoder basert på RNG mye mindre pålitelige enn det som kan være resultatet av GNPG av dårlig kvalitet. Selv i dag kreves det noen ganger forsiktighet, noe som fremgår av advarselen i International Encyclopedia of Statistical Science (2010).
Vellykket kasusstudie
Som en illustrasjon, tenk på det mye brukte programmeringsspråket Java. Fra og med 2017 er Java fortsatt avhengig av Linear Congruential Generator (LCG) for sin PRNG.
Historie
Den første PRNG som unngår alvorlige problemer og fortsatt kjører ganske fort,var Mersenne Twister (diskutert nedenfor), som ble utgitt i 1998. Siden den gang har andre PRNG-er av høy kvalitet blitt utviklet.
Men historien til pseudo-tilfeldige tall slutter ikke der. I andre halvdel av 1900-tallet inkluderte standardklassen av algoritmer som ble brukt for PRNG-er lineære kongruensielle generatorer. Kvaliteten på LCG var kjent for å være utilstrekkelig, men bedre metoder var ikke tilgjengelig. Press et al (2007) beskrev resultatet som følger: "Hvis alle vitenskapelige artikler hvis resultater er i tvil på grunn av [LCG og relaterte] forsvant fra bibliotekets hyller, ville det være et gap på størrelse med knyttneven din på hver hylle."
Hovedprestasjonen i opprettelsen av pseudo-tilfeldige generatorer var introduksjonen av metoder basert på lineær tilbakevending i et to-element felt; slike oscillatorer er koblet til lineære tilbakemeldingsskiftregistre. De fungerte som grunnlaget for oppfinnelsen av sensorer for pseudo-tilfeldige tall.
Spesielt 1997-oppfinnelsen av Mersen Twister unngikk mange av problemene med tidligere generatorer. Mersenne Twister har en periode på 219937−1 iterasjoner (≈4,3 × 106001). Det har vist seg å være jevnt fordelt i (opptil) 623 dimensjoner (for 32-bits verdier), og var på tidspunktet for introduksjonen raskere enn andre statistisk forsvarlige generatorer som produserer pseudo-tilfeldige tallsekvenser.
I 2003 introduserte George Marsaglia en familie med xorshift-generatorer også basert på lineær repetisjon. Disse generatorene er ekstremter raske og – kombinert med en ikke-lineær operasjon – består de strenge statistiske tester.
I 2006 ble WELL-generatorfamilien utviklet. WELL-generatorer forbedrer på en måte kvaliteten til Twister Mersenne, som har en altfor stor tilstandsplass og veldig langsom utvinning fra dem, og genererer pseudo-tilfeldige tall med mange nuller.
Kryptografi
PRNG egnet for kryptografiske applikasjoner kalles kryptografisk sikker PRNG (CSPRNG). Kravet til en CSPRNG er at en angriper som ikke kjenner frøet kun har en marginal fordel i å skille generatorens utgangssekvens fra en tilfeldig sekvens. Med andre ord, mens en PRNG bare kreves for å bestå visse statistiske tester, må en CSPRNG bestå alle statistiske tester som er begrenset til polynomtid i frøstørrelse.
Selv om beviset for denne egenskapen er utenfor det nåværende nivået av beregningskompleksitetsteori, kan sterke bevis gis ved å redusere CSPRNG til et problem som anses som vanskelig, som heltallsfaktorisering. Generelt kan det være nødvendig med mange års gjennomgang før en algoritme kan sertifiseres som en CSPRNG.
Det har vist seg at det er sannsynlig at NSA har satt inn en asymmetrisk bakdør i den NIST-sertifiserte Dual_EC_DRBG pseudo-tilfeldige tallgeneratoren.
Pseudo-tilfeldige algoritmertall
De fleste PRNG-algoritmer produserer sekvenser som er jevnt fordelt av en av flere tester. Dette er et åpent spørsmål. Det er en av de sentrale i teorien og praksisen til kryptografi: er det en måte å skille utgangen av en høykvalitets PRNG fra en virkelig tilfeldig sekvens? I denne innstillingen vet resolveren at enten en kjent PRNG-algoritme ble brukt (men ikke tilstanden den ble initialisert med), eller en virkelig tilfeldig algoritme ble brukt. Han må skille mellom dem.
Sikkerheten til de fleste kryptografiske algoritmer og protokoller som bruker PRNG-er er basert på antakelsen om at det er umulig å skille mellom bruken av en passende PRNG og bruken av en virkelig tilfeldig sekvens. De enkleste eksemplene på denne avhengigheten er strømchiffer, som oftest fungerer ved å utelate eller sende klartekstmeldingen med en PRNG-utgang, og produsere chifferteksten. Å designe kryptografisk tilstrekkelige PRNG-er er ekstremt vanskelig, da de må oppfylle flere kriterier. Størrelsen på perioden er en viktig faktor for den kryptografiske egnetheten til en PRNG, men ikke den eneste.
En tidlig PC-PRNG foreslått av John von Neumann i 1946 er kjent som middelkvadratmetoden. Algoritmen er som følger: ta et hvilket som helst tall, kvadrat det, fjern de midterste sifrene i det resulterende tallet som et "tilfeldig tall", og bruk deretter dette tallet som startnummer for neste iterasjon. For eksempel gir det å kvadrere tallet 11111234321, som kan skrives som 01234321, er et 8-sifret tall kvadratet av et 4-sifret tall. Dette gir 2343 som et "tilfeldig" tall. Resultatet av å gjenta denne prosedyren er 4896, og så videre. Von Neumann brukte 10-sifrede tall, men prosessen var den samme.
Ulemper med "midtfirkanten"
Problemet med "mean square"-metoden er at alle sekvenser til slutt gjentas, noen veldig raskt, for eksempel: 0000. Von Neumann visste om dette, men han fant en tilnærming tilstrekkelig for sine formål, og bekymret for at matematiske "korrigeringer" ville bare skjule feilene i stedet for å fjerne dem.
Von Neumann fant tilfeldige og pseudo-tilfeldige tallgeneratorer for maskinvare uegnet: hvis de ikke registrerer den genererte utgangen, kan de ikke sjekkes for feil senere. Hvis de skulle skrive ned resultatene, ville de tømme datamaskinens begrensede tilgjengelige minne og dermed datamaskinens evne til å lese og skrive tall. Hvis tall ble skrevet på kort, ville de ta mye lengre tid å skrive og lese. På ENIAC-datamaskinen brukte han "midtfirkantet"-metoden og utførte prosessen med å skaffe pseudo-tilfeldige tall flere hundre ganger raskere enn å lese tall fra hullkort.
Mean square har siden blitt erstattet av mer komplekse generatorer.
Innovativ metode
En ny innovasjon er å kombinere den gjennomsnittlige kvadraten med Weil-sekvensen. Denne metoden sikrer høykvalitetsprodukter innenlang periode. Det hjelper å få de beste pseudo-tilfeldige tallformlene.
