Generator av pseudoslumptal

En pseudoslumptalsgenerator ( PRNG ), även känd som en deterministisk slumpbitsgenerator ( DRBG ), är en algoritm för att generera en sekvens av tal vars egenskaper approximerar egenskaperna hos sekvenser av slumptal . Den PRNG-genererade sekvensen är inte riktigt slumpmässig , eftersom den bestäms helt av ett initialt värde, som kallas PRNG:s frö (som kan innehålla verkligt slumpmässiga värden). Även om sekvenser som är närmare verkligt slumpmässiga kan genereras med hjälp av slumptalsgeneratorer för hårdvara, är pseudoslumptalsgeneratorer viktiga i praktiken för deras hastighet i talgenerering och deras reproducerbarhet.

PRNG:er är centrala i applikationer som simuleringar (t.ex. för Monte Carlo-metoden ), elektroniska spel (t.ex. för procedurgenerering ) och kryptografi . Kryptografiska applikationer kräver att utdata inte är förutsägbara från tidigare utdata, och mer utarbetade algoritmer , som inte ärver linjäriteten hos enklare PRNGs, behövs.

Goda statistiska egenskaper är ett centralt krav för produktionen av en PRNG. I allmänhet krävs noggrann matematisk analys för att kunna lita på att en PRNG genererar siffror som är tillräckligt nära slumpmässiga för att passa den avsedda användningen. John von Neumann varnade för misstolkningen av en PRNG som en verkligt slumpgenerator och skämtade att "Alla som överväger aritmetiska metoder för att producera slumpmässiga siffror är naturligtvis i ett tillstånd av synd."

Potentiella problem

I praktiken uppvisar utdata från många vanliga PRNG: er artefakter som får dem att misslyckas med statistiska mönsterdetekteringstest. Dessa inkluderar:

Kortare perioder än förväntat för vissa frötillstånd (sådana frötillstånd kan kallas "svaga" i detta sammanhang);
Brist på enhetlig distribution för stora kvantiteter genererade nummer;
Korrelation av successiva värden;
Dålig dimensionsfördelning av utdatasekvensen;
Avstånden mellan var vissa värden förekommer fördelas annorlunda än de i en slumpmässig sekvensfördelning.

Defekter som uppvisas av felaktiga PRNG:er sträcker sig från omärkliga (och okända) till mycket uppenbara. Ett exempel var RANDU- slumptalsalgoritmen som använts i decennier på stordatorer . Det var allvarligt defekt, men dess otillräcklighet förblev oupptäckt under mycket lång tid.

På många områden var forskningsarbete före 2000-talet som förlitade sig på slumpmässigt urval eller Monte Carlo -simuleringar, eller på andra sätt förlitade sig på PRNG:er, mycket mindre tillförlitligt än idealiskt som ett resultat av användning av PRNG:er av dålig kvalitet. Även idag krävs ibland försiktighet, vilket illustreras av följande varning i International Encyclopedia of Statistical Science ( 2010).

Listan över allmänt använda generatorer som bör kasseras är mycket längre [än listan över bra generatorer]. Lita inte blint på programvaruleverantörerna. Kontrollera standard-RNG för din favoritprogramvara och var redo att byta ut den om det behövs. Denna sista rekommendation har gjorts om och om igen under de senaste 40 åren. Kanske förvånansvärt, det är fortfarande lika relevant idag som det var för 40 år sedan.

Som en illustration, betrakta det flitigt använda programmeringsspråket Java . Fram till 2020 förlitade Java sig fortfarande på en linjär kongruentialgenerator (LCG) för sin PRNG, som är av låg kvalitet (se vidare nedan). Java-stödet uppgraderades med Java 17 .

En välkänd PRNG för att undvika stora problem och ändå köra ganska snabbt är Mersenne Twister (diskuteras nedan), som publicerades 1998. Andra PRNG:er av högre kvalitet, både när det gäller beräknings- och statistisk prestanda, utvecklades före och efter detta datum; dessa kan identifieras i listan över pseudoslumptalsgeneratorer .

Generatorer baserade på linjära upprepningar

Under andra hälften av 1900-talet bestod standardklassen av algoritmer som användes för PRNGs linjära kongruentiella generatorer . Kvaliteten på LCG var känd för att vara otillräcklig, men bättre metoder var inte tillgängliga. Press et al. (2007) beskrev resultatet så här: "Om alla vetenskapliga artiklar vars resultat är tveksamma på grund av [LCG och relaterade] skulle försvinna från bibliotekshyllorna, skulle det finnas en lucka på varje hylla ungefär lika stor som din knytnäve."

Ett stort framsteg i konstruktionen av pseudoslumpgeneratorer var introduktionen av tekniker baserade på linjära upprepningar på tvåelementfältet; sådana generatorer är relaterade till skiftregister med linjär återkoppling .

1997 års uppfinning av Mersenne Twister undvek många av problemen med tidigare generatorer. Mersenne Twister har en period av 2 ^{19 937} −1 iterationer (≈4,3 × 10 ⁶⁰⁰¹ ), har visat sig vara jämnfördelad i (upp till) 623 dimensioner (för 32-bitars värden), och var igång vid tidpunkten för introduktionen snabbare än andra statistiskt rimliga generatorer.

År 2003 introducerade George Marsaglia familjen xorshift -generatorer, återigen baserad på en linjär upprepning. Sådana generatorer är extremt snabba och i kombination med en olinjär operation klarar de starka statistiska tester.

2006 utvecklades WELL -familjen av generatorer. WELL-generatorerna förbättrar på något sätt kvaliteten på Mersenne Twister, som har ett för stort tillståndsutrymme och en mycket långsam återhämtning från tillståndsutrymmen med ett stort antal nollor.

Kryptografiska PRNG:er

En PRNG som är lämplig för kryptografiska applikationer kallas en kryptografiskt säker PRNG (CSPRNG). Ett krav för en CSPRNG är att en motståndare som inte känner till fröet endast har en försumbar fördel när det gäller att skilja generatorns utdatasekvens från en slumpmässig sekvens. Med andra ord, medan en PRNG bara krävs för att klara vissa statistiska test, måste en CSPRNG klara alla statistiska tester som är begränsade till polynomtid i storleken på fröet. Även om ett bevis på denna egenskap är bortom den nuvarande teknikens ståndpunkt inom beräkningskomplexitetsteori, kan starka bevis tillhandahållas genom att reducera CSPRNG till ett problem som antas vara svårt , såsom heltalsfaktorisering . I allmänhet kan det krävas flera års granskning innan en algoritm kan certifieras som en CSPRNG.

Vissa klasser av CSPRNG inkluderar följande:

stream chiffer
blockera chiffer som körs i räknare- eller utmatningsläge
: er som har utformats specifikt för att vara kryptografiskt säkra , såsom Microsofts kryptografiska applikationsprogrammeringsgränssnittsfunktion CryptGenRandom , Yarrow- algoritmen (inkorporerad i Mac OS X och FreeBSD ) och Fortuna
kombinations-PRNG:er som försöker kombinera flera primitiva PRNG-algoritmer med målet att ta bort all detekterbar icke-slumpmässighet
specialdesigner baserade på matematiska hårdhetsantaganden: exempel inkluderar Micali–Schnorr-generatorn , Naor-Reingold pseudoslumpfunktionen och Blum Blum Shub -algoritmen, som ger ett starkt säkerhetsbevis (sådana algoritmer är ganska långsamma jämfört med traditionella konstruktioner och opraktiska för många applikationer )
generiska PRNG: även om det har visats att en (kryptografiskt) säker PRNG kan konstrueras generiskt från vilken enkelriktad funktion som helst , är denna generiska konstruktion extremt långsam i praktiken, så den är främst av teoretiskt intresse.

Det har visat sig vara troligt att NSA har infogat en asymmetrisk bakdörr i den NIST -certifierade pseudoslumptalsgeneratorn Dual_EC_DRBG .

De flesta PRNG-algoritmer producerar sekvenser som är likformigt fördelade genom något av flera tester. Det är en öppen fråga, och en central för teorin och praktiken av kryptografi , om det finns något sätt att skilja produktionen av en högkvalitativ PRNG från en verkligt slumpmässig sekvens. I den här inställningen vet särskiljaren att antingen den kända PRNG-algoritmen användes (men inte tillståndet med vilken den initierades) eller att en verkligt slumpmässig algoritm användes, och måste skilja mellan de två. Säkerheten för de flesta kryptografiska algoritmer och protokoll som använder PRNG är baserad på antagandet att det är omöjligt att skilja användning av en lämplig PRNG från användning av en verkligt slumpmässig sekvens. De enklaste exemplen på detta beroende är strömchiffer , som (oftast) fungerar genom att exklusiva eller -ing av klartexten i ett meddelande med utdata från en PRNG, vilket producerar chiffertext . Utformningen av kryptografiskt adekvata PRNG:er är extremt svår eftersom de måste uppfylla ytterligare kriterier. Storleken på dess period är en viktig faktor i den kryptografiska lämpligheten för en PRNG, men inte den enda.

BSI utvärderingskriterier

Det tyska förbundskontoret för informationssäkerhet ( tyska : Bundesamt für Sicherheit in der Informationstechnik, BSI) har fastställt fyra kriterier för kvaliteten på deterministiska slumptalsgeneratorer. De sammanfattas här:

K1 – Det bör finnas en stor sannolikhet att genererade sekvenser av slumptal skiljer sig från varandra.
K2 – En talföljd är omöjlig att skilja från "verkligt slumpmässiga" tal enligt specificerade statistiska tester. Testerna är monobit- testet (lika antal ettor och nollor i sekvensen), pokertest (en speciell instans av chi-kvadrattestet ), körningstest (räknar frekvensen av körningar av olika längder), långkörningstest (kontrollerar om det finns någon körning med längden 34 eller mer i 20 000 bitar av sekvensen) – både från BSI och NIST och autokorrelationstestet . I huvudsak är dessa krav ett test av hur bra en bitsekvens: har nollor och ettor lika ofta; efter en sekvens av n nollor (eller ettor), nästa bit en etta (eller noll) med sannolikhet en halv; och varje vald undersekvens innehåller ingen information om nästa element i sekvensen.
K3 – Det borde vara omöjligt för en angripare (för alla praktiska ändamål) att beräkna, eller på annat sätt gissa, från en given undersekvens, några tidigare eller framtida värden i sekvensen, inte heller något inre tillstånd hos generatorn.
K4 – Det borde vara omöjligt, för alla praktiska ändamål, för en angripare att beräkna, eller gissa från ett inre tillstånd hos generatorn, eventuella tidigare tal i sekvensen eller tidigare inre generatortillstånd.

För kryptografiska applikationer är endast generatorer som uppfyller K3- eller K4-standarderna acceptabla.

Matematisk definition

Given:

$P$ – en sannolikhetsfördelning på ${\displaystyle \left(\mathbb {R} ,{\mathfrak {B}}\right)} ($ där ${\mathfrak {B }}$ är standard Borel inställd på den verkliga linjen)
${\mathfrak {F}}$ – en icke-tom samling av Borel-mängder ${\mathfrak {F}}\subseteq {\mathfrak {B}}$ , t.ex. ${\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}$ Om ${\mathfrak {F}}$ inte anges, kan det vara antingen ${\mathfrak {B}}$ eller ${\displaystyle \left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}} ,$ beroende på sammanhang.
$A\subseteq \mathbb {R}$ – en icke-tom uppsättning (inte nödvändigtvis en Borel-mängd). Ofta $A$ en uppsättning mellan $P$ :s stöd och dess inre ; till exempel, om $P$ är den enhetliga fördelningen på intervallet $\left(0,1\right]$ , kan $A$ vara $\left(0,1\right]$ Om $A$ inte specificeras, antas det vara någon uppsättning som ingår i stödet för $P$ och som innehåller dess inre, beroende på sammanhanget.

Vi kallar en funktion $f:\mathbb {N} _{1}\rightarrow \mathbb {R}$ (där $\ mathbb {N} _{1}=\left\{1,2,3,\dots \right\}$ är uppsättningen positiva heltal) en pseudo-slumptalsgenerator för $P$ givet ${\ displaystyle {\mathfrak {F}}}$ tar värden i $A$ om och endast om :

$f\left(\mathbb {N} _{1}\right)\subseteq A$
$\forall E\in {\mathfrak {F}}\quad \forall \varepsilon >0\quad \exists N\in \mathbb {N} _{1}\quad \forall n\geq N, \quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n} }-P(E)\right|<\varepsilon$

( $\#S$ anger antalet element i den finita mängden $S$ .)

Det kan visas att om $f$ är en pseudo-slumptalsgenerator för den enhetliga fördelningen på $\left(0,1\right)$ och om $F$ är CDF för någon given sannolikhetsfördelning $P$ , då är $F^{*}\circ f$ en pseudoslumptalsgenerator för $P$ , där $F^{*}:\left(0,1\right)\rightarrow \mathbb {R}$ är percentilen för $P$ , dvs $F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\ höger\}$ . Intuitivt kan en godtycklig fördelning simuleras från en simulering av den enhetliga standardfördelningen.

Tidiga närmar sig

En tidig datorbaserad PRNG, som föreslogs av John von Neumann 1946, är känd som medelkvadratmetoden . Algoritmen är som följer: ta valfritt tal, kvadrera det, ta bort mittsiffrorna i det resulterande numret som "slumptalet", använd sedan det numret som frö för nästa iteration. Att till exempel kvadrera talet "1111" ger "1234321", som kan skrivas som "01234321", ett 8-siffrigt tal är kvadraten på ett 4-siffrigt tal. Detta ger "2343" som det "slumpmässiga" numret. Upprepa denna procedur ger "4896" som nästa resultat, och så vidare. Von Neumann använde 10-siffriga nummer, men processen var densamma.

Ett problem med metoden "mellanfyrkant" är att alla sekvenser så småningom upprepar sig själva, vissa mycket snabbt, till exempel "0000". Von Neumann var medveten om detta, men han fann att tillvägagångssättet var tillräckligt för sina syften och var orolig för att matematiska "fixar" helt enkelt skulle dölja fel snarare än att ta bort dem.

Von Neumann bedömde hårdvarugeneratorer för slumptal som olämpliga, för om de inte spelade in den genererade utsignalen kunde de inte senare testas för fel. Om de spelade in sin produktion skulle de tömma de begränsade datorminnen som då fanns tillgängliga, och så datorns förmåga att läsa och skriva siffror. Om siffrorna skrevs på kort skulle de ta mycket längre tid att skriva och läsa. På ENIAC -datorn han använde genererade metoden "mellan kvadrat" siffror i en takt som är hundra gånger snabbare än att läsa in siffror från hålkort .

Mellankvadratmetoden har sedan ersatts av mer utarbetade generatorer.

En ny innovation är att kombinera mellantorget med en Weyl-sekvens . Den här metoden ger högkvalitativ produktion under en lång period (se metoden för medelkvadrat ) .

Olikformiga generatorer

Tal valda från en olikformig sannolikhetsfördelning kan genereras med en enhetlig fördelning PRNG och en funktion som relaterar de två fördelningarna.

Först behöver man den kumulativa fördelningsfunktionen $F(b)$ för målfördelningen $f(b)$ :

F(b)=\int _{-\infty }^{b}f(b')db'

Observera att $0=F(-\infty )\leq F(b)\leq F(\infty )=1$ . Genom att använda ett slumptal c från en enhetlig fördelning som sannolikhetstäthet att "passera förbi", får vi

F(b)=c

så att

b=F^{-1}(c)

är ett tal slumpmässigt valt från fördelningen $f(b)$ . Detta är baserat på den inversa transformsamplingen .

Till exempel, inversen av kumulativ gaussisk distribution $\operatorname {erf} ^{-1}(x)$ med en idealisk enhetlig PRNG med intervall (0, 1) som indata ${\ displaystyle x}$ skulle producera en sekvens av (endast positiva) värden med en gaussisk fördelning; dock

När man använder praktiska talrepresentationer måste de oändliga "svansarna" av fördelningen trunkeras till ändliga värden.
Upprepad omberäkning av $\operatorname {erf} ^{-1}(x)$ bör reduceras med hjälp av t.ex. ziggurat-algoritm för snabbare generering.

Liknande överväganden gäller för att generera andra olikformiga distributioner som Rayleigh och Poisson .

Se även

Bibliografi

Barker E., Kelsey J. , Rekommendation för generering av slumptal med hjälp av deterministiska slumpmässiga bitgeneratorer , NIST SP800-90A , januari 2012
Brent RP , "Some long-period slumptal generators using shifts and xors", ANZIAM Journal , 2007; 48:C188–C202
Gentle JE (2003), Random Number Generation och Monte Carlo Methods, Springer.
Hörmann W., Leydold J., Derflinger G. (2004, 2011), Automatic Nonuniform Random Variate Generation , Springer-Verlag.
Knuth DE Konsten att programmera , Volym 2: Seminumeriska algoritmer , tredje upplagan. Addison-Wesley, 1997. ISBN 0-201-89684-2 . Kapitel 3. [Omfattande täckning av statistiska test för icke-slumpmässighet.]
Luby M., Pseudorandomness and Cryptographic Applications , Princeton Univ Press, 1996. ISBN 9780691025469
von Neumann J., "Various techniques used in connection with random digits," i AS Householder, GE Forsythe, och HH Germond, red., Monte Carlo Method , National Bureau of Standards Applied Mathematics Series, 12 (Washington, DC: US Government Tryckeriet, 1951): 36–38.
Peterson, Ivars (1997). The Jungles of Randomness: en matematisk safari . New York: John Wiley & Sons. ISBN 0-471-16449-6 .
Press WH, Teukolsky SA, Vetterling WT, Flannery BP (2007), Numeriska recept ( Cambridge University Press ).
Viega J. , " Praktisk generering av slumptal i programvara ", i Proc. 19:e årliga konferensen om datorsäkerhetsapplikationer, december 2003.

externa länkar

TestU01 : En gratis, toppmodern ( GPL ) C++ Random Number Test Suite.
DieHarder : En gratis ( GPL ) C slumptalstestsvit.
" Generera slumpmässiga tal " (i inbyggda system ) av Eric Uner (2004)
" Analys av Linux Random Number Generator " av Zvi Gutterman, Benny Pinkas och Tzachy Reinman (2006)
" Bättre pseudoslumpgeneratorer " av Parikshit Gopalan, Raghu Meka, Omer Reingold , Luca Trevisan och Salil Vadhan ( Microsoft Research , 2012)
på YouTube av Stephan Lavavej (Microsoft, 2013)
Wsphynx en enkel online slumptalsgenerator. Slumptal genereras av Javascript pseudorandom number generators (PRNGs) algoritmer