Pseudo-tilfældig talgenerator ( PRNG , engelsk pseudorandom number generator , PRNG ) er en algoritme , der genererer en række tal , hvis elementer er næsten uafhængige af hinanden og adlyder en given fordeling (normalt diskret uniform ).
Moderne computervidenskab gør udstrakt brug af pseudo-tilfældige tal i en række forskellige applikationer, fra Monte Carlo og simulering til kryptografi . Samtidig afhænger kvaliteten af de opnåede resultater direkte af kvaliteten af de brugte PRNG'er. Denne omstændighed understreges af den velkendte aforisme fra ORNL -matematikeren Robert Caviu: " Generering af tilfældige tal er for vigtig til at overlades til tilfældighederne ."
Kilder til rigtige tilfældige tal er ekstremt svære at finde. Fysiske støj [1] såsom ioniserende stråling hændelsesdetektorer , skudstøj i en modstand eller kosmisk stråling [2] kan være sådanne kilder. Sådanne enheder bruges dog sjældent i netværkssikkerhedsapplikationer. Brutale angreb på sådanne enheder forårsager også vanskeligheder.
Fysiske kilder til tilfældige tal har en række ulemper:
Samtidig kan tilfældige tal opnået fra en fysisk kilde bruges som et genererende element (engelsk frø) til software PRNG'er. Sådanne kombinerede generatorer bruges i kryptografi, lotterier, spilleautomater. [3]
John von Neumann anså det for uacceptabelt at bruge fysiske tilfældige talgeneratorer i computerteknologi, da hvis det blev nødvendigt at kontrollere beregninger, ville gentagelse af tidligere handlinger kræve gengivelse af et tilfældigt tal, mens generering af et nyt tilfældigt tal er uacceptabelt. Foreløbig registrering og lagring af genererede tilfældige tal ville indebære muligheden for at læse dem. Datalæsemekanismen var et af de svageste led i 1940'ernes computere. John von Neumann gav følgende middelkvadratmetode [ 4] til at opnå ti-cifrede pseudo-tilfældige tal:
Et ti-cifret tal kvadreres, derefter tages et ti-cifret tal fra midten af kvadratet på tallet, som igen kvadreres, og så videre.For eksempel, for 4-cifrede tal, startende fra 1234, får vi , hvor vi tager de midterste 4 cifre (tilføj et nul i begyndelsen, hvis det er nødvendigt). Så kvadrerer vi det resulterende tal , og så videre. Ulempen ved denne metode er det begrænsede sæt af PSCH på grund af det faktum, at sekvensen sløjfer - .
I 1951 foreslog D. G. Lemer en lineær kongruent metode , [5] hvis essens er at specificere en sekvens af heltal ved hjælp af en rekursiv formel hvor er heltal og opfylder følgende betingelser: . Ulempen ved denne metode er afhængigheden af , da , samt det faktum, at PFC'en sløjfer.
De fleste af de deterministiske PRNG'er svarer til strukturen foreslået af P. Lecuer 1994:i]1 [ ,. Normalt er generatorens tilstand givet af den rekursive formel for . Generator output værdi ; er en sekvens af pseudo-tilfældige tal. Da det er endeligt, skal der eksistere nogle endelige og sådan at . Dette betyder, at betingelserne og vil være opfyldt for alle , fordi funktionerne og er deterministiske. Således viser det sig, at sekvensen er periodisk. PRNG- perioden kaldes minimum positive . [3]
De mest almindelige er den lineære kongruentielle metode , Fibonacci-metoden med forsinkelser , skifteregistret med lineær feedback , skifteregistret med generaliseret feedback .
Af moderne PRNG'er er " Mersenne-hvirvelen " foreslået i 1997 af Matsumoto og Nishimura også blevet udbredt . Dens fordele er en kolossal periode (2 19937 −1), en ensartet fordeling i 623 dimensioner (den lineære kongruentielle metode giver en mere eller mindre ensartet fordeling i maksimalt 5 dimensioner), hurtig generering af tilfældige tal (2-3 gange hurtigere end standard PRNG'er ved hjælp af lineær kongruent metode). Der er dog algoritmer, der genkender sekvensen genereret af Mersenne-hvirvelen som ikke-tilfældig.
En pseudo-tilfældig talgenerator er inkluderet i mange moderne processorer , for eksempel er RdRand inkluderet i IA-32-instruktionssættet. [6]
En variation af PRNG er GPSB (PRBG) - generatorer af pseudo-tilfældige bits, såvel som forskellige stream-cifre .
Det følgende er en liste over generatorer, der historisk har skilt sig ud inden for pseudo-tilfældig talgenerering, enten på grund af deres historiske betydning eller fordi de var en innovativ model for deres epoker. Desuden, på trods af at dette er en PRNG, kan nogle af dem være anvendelige inden for kryptografi.
Algoritme | Forfatterne | Links | Beskrivelse | |
---|---|---|---|---|
mellem firkantet | John von Neumman | 1946 | [7] | PRNG, som anses for lav kvalitet, men af stor historisk betydning som en af de første algoritmer. |
Lehmer Generator / Lineær kongruentiel metode | D.H. Lehmer | 1951 | [otte] | Det er også kendt som metoden til multiplikative lineære kongruenser og har været meget indflydelsesrig på dette forskningsområde. Den er også kendt som den lineære kongruentielle metode, hvis grundlag er blevet forbedret over tid. |
Lag Fibonacci Generator | GJ Mitchell; D.P. Moore | 1958 | [9] | En meget indflydelsesrig algoritme i studiet af processer til generering af tilfældige tal, der inspirerer andre senere store forfattere såsom G. Marsaglia, skaberen af en kvalitetstest af tilfældige tal kaldet "Diehard", for eksempel. |
Linear Feedback Shift Register (LFSR) / Tausworthe Oscillator | R. C. Tausworth | 1965 | [ti] | En generator, hvis design påvirkede mange andre efterfølgende PRNG'er. Derfor er det meget historisk vigtigt. Også kendt som Tausworthe-generatoren. |
Wichmann & Hill Generator | B.A. Wichmann; D.I. Hill | 1982 | [elleve] | En kombination af tre små LCG'er velegnet til 16-bit processorer. Udbredt i mange programmer, for eksempel blev det brugt i Excel 2003 og nogle senere versioner til RAND-funktionen i Excel og var standardgeneratoren i Python indtil version 2.2. |
Regel 30 | Wolfram, Stephen | 1983 | [12] | Generator baseret på cellulære automater. |
Blum-Blum-Shub Generator | Bloom, Manuel ; L. Blum; M. Shub | 1986 | [13] | Det betragtes som en af de mest sikre generatorer fra et kryptografisk synspunkt, hovedsageligt på grund af inkorporeringen af forskning og begreber taget fra talteori i dens formel. For denne Blum-algoritme blev Manuel tildelt Alan Turing-prisen i 1995. |
park-miller generator | SK Park; KW Miller | 1988 | [fjorten] | En konkret implementering af Lehmer-generatoren, meget brugt, fordi den er inkluderet i C++ som minstd_rand0-funktionen siden C++11. |
AGERN | RS Wikramaratna | 1989 | [femten] | Dens navn kommer fra det engelske akronym ACORN, som står for ″Additive Congruent Random Number″. |
MIXMAX | GK Savvidy; NG Ter-Arutyunyan-Savvidy | 1991 | [16] | Dette er en generator, der tilhører klassen af matrixkongruente lineære generatorer, en generalisering af metoden for lineære kongruenser. Logikken i MIXMAX-familien af generatorer er baseret på resultaterne af ergodisk teori og klassisk mekanik. |
Tilføj-med-bære | G. Marsaglia | 1991 | [17] | Ændring af Fibonacci generatorer med forsinkelse. |
Træk-med-lån fra | G. Marsaglia; A. Zaman | 1991 | [17] | Algoritme afledt af Fibonacci-generatorer med forsinkelse. |
ISAAC | RJ Jenkins Jr. | 1993 | [atten] | Cryptographically Secure Cryptographic Data Generator (CSPRNG) udviklet af Robert J. Jenkins. |
Mersenne Twister, MT | M. Matsumoto; T. Nishimura | 1996 | [19] | Dette er sandsynligvis den bedst kendte generator på denne liste, hovedsageligt fordi det er en algoritme implementeret i RAND-funktionen i Python og R programmeringssprogene, foruden dens stærke tilstedeværelse i elektroniske spil såsom Pro Evolution Soccer (PES). |
Xorshift | G. Marsaglia | 2003 | [tyve] | Dette er en meget hurtig undertype af LFSR-generatorer. Marsaglia foreslog også en xorwow-generator som en forbedring, hvor outputtet fra xorshift-generatoren summeres med en Weyl-sekvens. xorwow-generatoren er standardgeneratoren i nVidia CUDA API CURAND-biblioteket til GPU'er. |
Fortuna algoritme | Schneier, Bruce ; Nils Ferguson | 2003 | [21] | Algoritmen betragtes som kryptografisk sikker. CSPRNG, kendt for at være indlejret i Apple-systemer og produkter. |
Godt ligefordelt lang periode lineær (GOD) | F. Panneton; P. L'Ecuyer; M. Matsumoto | 2006 | [22] | En algoritme kendt som en tilføjelse til Mersenne Twister (MT), der bevidst søger at skjule dens svagheder. |
Advanced Randomization System (ARS) | J. Salmon; M. Moraes; R. Dror; D. Shaw | 2011 | [23] | En forenklet version af AES-blokchifferet, der giver meget høj ydeevne på et system, der understøtter AES-NI. |
Threefry | J. Salmon, M. Moraes, R. Dror og D. Shaw | 2011 | [23] | En forenklet version af Threefish-blokchifferet, der er egnet til GPU-implementering. |
Philox (Philox) | J. Salmon, M. Moraes, R. Dror og D. Shaw | 2011 | [23] | Forenkling og modifikation af blokchifferet Threefish med tilføjelse af S-box. |
Permuted Congruential Generator (PCG) | M.E. O'Neill | 2014 | [24] | Model opnået ved hjælp af den lineære kongruentielle metode. |
Random Cycle Bit Generator (RCB) | R. Cookman | 2016 | [25] | RCB'en beskrives som en bitmønstergenerator designet til at overvinde nogle af manglerne ved Mersenne Twist (MT) og den korte periode/bitlængdebegrænsning af shift/modulus-generatorer. |
Middle Square Weyl Sequence RNG | B. Widynski | 2017 | [26] | En variation af John von Neumanns oprindelige middelkvadratmetode. |
Xoroshiro128+ | D. Blackman; S. Vigna | 2018 | [27] | Ændring af G. Marsaglias Xorshift generator, en af de hurtigste generatorer på moderne 64-bit processorer. Relaterede generatorer er xoroshiro128**, xoshiro256+ og xoshiro256***. |
64-bit MELG (MELG-64) | S. Harase; T. Kimoto | 2018 | [28] | Implementering af 64-bit lineære F2 generatorer med primær Mersenne periode. |
Firkanter RNG | B. Widynski | 2020 | [29] | En kontrabaseret version af Middle Square Weyl Sequence RNG. Designet ligner Philox, men meget hurtigere. |
Itamaraca (Ita) | D.H. Pereira | 2021 | [tredive] | Kendt som den første PRNG-algoritme baseret på den absolutte værdifunktion. Itamaracá er også en enkel og hurtig model, der genererer aperiodiske sekvenser af tilfældige tal. |
En alternativ løsning er at oprette et sæt af et stort antal tilfældige tal og udgive det i en slags ordbog , kaldet en " engangsblok ". Men selv sådanne sæt giver en meget begrænset kilde til tal sammenlignet med det antal, der kræves af netværkssikkerhedsapplikationer. Selvom disse sæt giver statistisk tilfældighed, er de ikke sikre nok, da en angriber kunne få en kopi af ordbogen.
Ingen deterministisk algoritme kan generere helt tilfældige tal, den kan kun tilnærme nogle af deres egenskaber. Som John von Neumann sagde , " Enhver, der har en svaghed for de aritmetiske metoder til at opnå tilfældige tal, er en synder uden tvivl ."
Enhver PRNG med begrænsede ressourcer sætter sig før eller siden fast - den begynder at gentage den samme sekvens af tal. Længden af PRNG-cyklusser afhænger af selve generatoren og er omkring , hvor er størrelsen af den interne tilstand i bit, selvom lineære kongruente og LFSR -generatorer har maksimale ordrecyklusser [31] . Hvis den genererede PRNG-sekvens konvergerer til for korte cyklusser, bliver en sådan PRNG forudsigelig og uegnet til praktiske anvendelser.
De fleste simple aritmetiske generatorer, selvom de er hurtige, lider af mange alvorlige mangler:
Især RANDU- algoritmen , som har været brugt på mainframe-computere i årtier , viste sig at være meget dårlig [32] [33] , hvilket rejste tvivl om pålideligheden af resultaterne af mange undersøgelser, der bruger denne algoritme.
Sammen med behovet for at generere let reproducerbare sekvenser af tilfældige tal, er der også behov for at generere helt uforudsigelige eller blot helt tilfældige tal. Sådanne generatorer kaldes random number generators (RNG - engelsk random number generator, RNG ). Da sådanne generatorer oftest bruges til at generere unikke symmetriske og asymmetriske nøgler til kryptering, er de oftest bygget af en kombination af en kryptografisk stærk PRNG og en ekstern entropikilde (og denne kombination forstås nu almindeligvis som RNG).
Næsten alle større mikrochipproducenter leverer hardware-RNG'er med forskellige kilder til entropi ved at bruge forskellige metoder til at rense dem for uundgåelig forudsigelighed. Men i øjeblikket svarer hastigheden til at indsamle tilfældige tal af alle eksisterende mikrochips (flere tusinde bits i sekundet) ikke hastigheden af moderne processorer.
I moderne forskning bliver der gjort forsøg på at bruge måling af objekters fysiske egenskaber (for eksempel temperatur ) eller endda kvanteudsving i vakuum som en entropikilde for RNG. [34]
I personlige computere bruger software-RNG-forfattere meget hurtigere kilder til entropi, såsom lydkortstøj eller en processor-urtæller . Entropiindsamling var det mest sårbare punkt i RNG. Dette problem er stadig ikke helt løst i mange enheder (såsom smart cards ), der forbliver sårbare på denne måde. [35] Mange RNG'er bruger traditionelle afprøvede, omend langsomme, metoder til entropiindsamling, såsom måling af brugerrespons ( musebevægelser osv.), som i PGP og Yarrow [36] eller interaktioner mellem tråde , såsom , i Java SecureRandom.
Hvis den aktuelle tid bruges som kilde til entropi, så for at opnå et heltal fra 0 til N , er det nok at beregne resten af at dividere den aktuelle tid i millisekunder med tallet N +1. Ulempen ved denne RNG er, at den producerer det samme tal i et millisekund.
Entropi kilde | PRNG | Fordele | Fejl | |
---|---|---|---|---|
/dev/random på UNIX / Linux | Processorens urtæller, dog kun indsamlet under hardwareafbrydelser | LFSR , med output hashing via SHA-1 | Tilgængelig på alle Unixes, en pålidelig kilde til entropi | Det "varmes op" i meget lang tid, kan "sætte sig fast" i lang tid eller fungerer som en PRNG ( / dev / urandom ) |
Yarrow af Bruce Schneier [36] | Traditionelle metoder | AES -256 og SHA-1 lille intern tilstand | Fleksibelt krypto-resistent design | Langsom |
Microsoft CryptoAPI | Aktuel tid, harddiskstørrelse, ledig hukommelse, procesnummer og NETBIOS-navn på computeren | MD5 -hash af den interne tilstand, 128 bit i størrelse | Indbygget i Windows, sætter sig ikke fast | Afhænger stærkt af den anvendte kryptografiske udbyder (CSP). |
Java SecureRandom | Kommunikation mellem tråde | SHA-1 - intern tilstand hash (1024 bit) | Stor intern tilstand | Langsom entropiindsamling |
RdRand af intel [37] | Støjstrømme | PFS-konstruktion baseret på "tilfældig" bitlæsning af værdier fra strømme [37] | Meget hurtig, sætter sig ikke fast | Den oprindelige bebyggelse, ejendommene gives kun efter godkendelse fra udviklerne. |
Et af kriterierne for, at PRNG er kryptografisk stærk, er manglende evne til at skelne outputværdierne af PRNG fra en uafhængig tilfældig sekvens, der er ensartet fordelt over intervallet. Lad der være en familie af PRNG , hvor kardinalitet af sættet er lig med . Som nævnt ovenfor, er et endeligt sæt af tilstande, er en sandsynlighedsfordeling i tilstandsrummet, der bruges til at vælge den oprindelige tilstand (engelsk frø), er en overgangsfunktion, er rummet af outputværdier, . Normalt er generatorens tilstand givet af den rekursive formel for . Generator output værdi ; er en sekvens af pseudo-tilfældige tal. Antag, at overgangs- og udgangsfunktionerne kan beregnes i polynomisk tid, potenser af . Lad være en klasse af statistiske test , der forsøger i polynomiel tid at skelne outputværdierne af PRNG fra en uafhængig tilfældig sekvens ensartet fordelt over intervallet . En familie af PRNG'er kaldes god i form af polynomisk tid, hvis der er en sådan, at ingen af testene for alle kan skelne PRNG'ens outputværdier fra en uafhængig tilfældig sekvens ensartet fordelt over intervallet med sandsynlighed . [3]
Kryptografiske applikationer bruger deterministiske algoritmer til at generere tilfældige tal og genererer derfor en række tal, som teoretisk set ikke kan være statistisk tilfældige. På samme tid, hvis du vælger en god algoritme, vil den resulterende numeriske sekvens - pseudo-tilfældige tal - bestå de fleste test for tilfældighed. Et af kendetegnene ved en sådan sekvens er en lang gentagelsesperiode. [3]
Eksempler på velkendte kryptografisk stærke PRNG'er er RC4 [31] , ISAAC [38] , SEAL [39] , SNOW [40] , en meget langsom teoretisk Blum-Blum-Shub algoritme [31] samt tællere med kryptografisk hash funktioner eller kryptografisk sikre blokcifre i stedet for outputfunktionen [31] .
Også kryptografisk stærke chiffer omfatter generatorer med multiple skifteregistre , generatorer med ikke-lineære transformationer og majoritetskrypteringsgeneratorer A5/x . [31]
Generatoren af tilfældige tal krypteres ved hjælp af forskellige hemmelige nøgler opnået på hvert trin. En tæller med en lang periode bruges som input til krypteringsenheden. Ved brug af en 56-bit DES -nøgle kan en tæller med et punktum bruges .
Den pseudo-tilfældige sekvens opnået af dette skema har en fuld periode: hver outputværdi , , ... er baseret på en anden tællerværdi, derfor . Da nøglen er hemmelig, afhænger enhver hemmelig nøgle ikke af kendskabet til en eller flere tidligere hemmelige nøgler. For at øge den kryptografiske styrke af algoritmen er det nødvendigt ved hvert trin at kryptere et tilfældigt tal med en RNG - . [41]
PRNG fra ANSI X9.17-standarden bruges i mange finansielle sikkerheds- og PGP -applikationer . I hjertet af denne PRNG er triple DES . ANSI X9.17-generatoren består af følgende dele:
De tilfældige inputværdier er og . er outputværdien. Beregning fra uden viden er ikke mulig i en rimelig tid, og dermed den næste pseudo-tilfældige værdi , da tre yderligere krypteringsoperationer udføres for at opnå. [42]
Bortset fra de forældede, velkendte LFSR-generatorer , der blev meget brugt som hardware-PRNG'er i det 20. århundrede, er meget lidt kendt om moderne hardware-PRNG'er, da de fleste af dem er udviklet til militære formål eller er patenteret og hemmeligholdt . Hardwarebaserede RLOS -generatorer Toyocrypt og LILI-128 blev hacket ved hjælp af algebraiske angreb [43] [44] .
På nuværende tidspunkt er det kendt om brugen af hardware PRNG'er implementeret på basis af laveffektstøj i elektriske kredsløb. [45]
Tilfældig talgenerator til lotterier er et hardware-softwarekompleks, der bruges i lotterier, hvor det er nødvendigt at gætte en kombination af et bestemt antal tal. Ethvert af de mulige tal har samme sandsynlighed for at forekomme.
Forsøg på at skabe en tilfældig talgenerator går tilbage til 3500 f.Kr. e. og er forbundet med det gamle egyptiske brætspil Senet . I Senet spiller to spillere på to sider. Træk bestemmes ved hjælp af 4 flade pinde, som kan betragtes som en tilfældig talgenerator på den tid. Kast alle fire pinde på én gang. Scoringen er som følger: 1 stok faldt med den hvide side op - 1 point og et ekstra kast; 2 - 2 point; 3 - 3 point, 4 - 4 og et ekstra kast. En af siderne på pinden er sort, og hvis alle fire pinde falder med den sorte side opad, er dette det maksimale resultat - 5 point og et ekstra kast.
Den velkendte tilfældige talgenerator ERNIE er blevet brugt i mange år til at bestemme vindertallene i det britiske lotteri.
De vigtigste krav til software og udstyr, der bruges til at gennemføre lotterier i Den Russiske Føderation, er fastsat af føderal lov nr. 138-FZ af 11. november 2003 "Om lotterier":
I russiske statslotterier (Gosloto 5 ud af 36, Gosloto 6 ud af 36, Gosloto 6 ud af 45, Gosloto 7 ud af 49, Gosloto 4 ud af 20, "Sportloto" 6 ud af 49 "") [47] selv- læsning af lotterietromler bruges til at afgøre vinderne . Lodtrækningerne sendes live. [48]
I russiske statslotterier ("Rapido", "Keno-Sportloto", "Top-3", "12/24", "Alt for hundrede"), bruges en tilfældig talgenerator til at bestemme vinderne - en hardware og software system certificeret af ANO "MIC" og opfylder anbefalingerne fra FSUE VNIIMS . Enheden genererer en kontinuerlig strøm af tilfældig støj, som konverteres til tal. På et givet tidspunkt bliver aktuelle værdier snuppet fra strømmen, som er den vindende lotterikombination. [49]
I 2015 blev den tidligere sikkerhedsdirektør for US Multi-State Lottery Association , efter at have vundet 16,5 millioner dollars, som havde adgang til software brugt i lotteritrækninger, sigtet for at bruge specielle algoritmer til at bestemme den vindende lotterikombination i flere dage om året. [halvtreds]