Generator af pseudo-tilfældige tal

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. januar 2022; checks kræver 6 redigeringer .

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 tilfældige tal

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]

Kvalitative krav til PRNG

Tidlige tilgange til dannelsen af ​​PRSP'er

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.

Deterministiske PRNG'er

Algoritme

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 .

Liste over pseudo-tilfældige tal generatorer

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.

Engangsnotesblok

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.

Ulemper ved PRNG

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.

PRNG med entropikilde eller RNG

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.

Et eksempel på en simpel RNG med en entropikilde

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.

Eksempler på RNG- og entropikilder

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.

PRNG i kryptografi

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]

Eksempler på krypto-resistente PRNG'er

Round-robin kryptering

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 .

  1. På tidspunktet for initialisering genereres en hemmelig nøgle og en konstant . skal være tilfældig og kun bruges til denne generator.
  2. På hvert trin sker følgende:

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]

  •  er nøglen, der bruges i hvert trin.
  •  - nøglekrypteringsfunktion .
  •  - tilfældigt tal med RNG.
ANSI X9.17

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:

  1. På tidspunktet for initialiseringen genereres en hemmelig nøgle . Det skal være tilfældigt og bruges kun til denne generator.
  2. På hvert trin sker følgende:
  •  — værdien af ​​dato og klokkeslæt ved begyndelsen af ​​generationens generation.
  •  er startværdien for -th generations stage.
  •  er et pseudo-tilfældigt tal, der er oprettet på generationens trin.
  •  er nøglen, der bruges i hvert trin.
  •  - nøglekrypteringsfunktion .

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]

Hardware PRNG'er

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]

Anvendelse af PRNG i lotterier

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":

  • De tekniske karakteristika ved lotteriudstyret skal sikre tilfældigheden af ​​fordelingen af ​​gevinster ved udtrækning af præmiepuljen for lodtrækningslotterier.
  • Procedurer, der implementerer algoritmer, der gør det muligt at forudbestemme resultatet af lodtrækningen om præmiefonden før starten af ​​en sådan lodtrækning, bør ikke anvendes.
  • Lotteriudstyr, der anvendes ved lodtrækningen, skal sikre beskyttelse af oplysninger mod tab, tyveri, forvanskning, uautoriserede handlinger til at ødelægge dem, ændring, kopiering og andre lignende handlinger og uautoriseret adgang via datatransmissionsnettet. [46]

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]

Se også

Noter

  1. N.G. Bardis, A.P. Markovskyi, N. Doukas, N.V. Karadimas. True Random Number Generation Baseret på Environmental Noise Measurements for Military Applications  // Proceedings of the 8th WSEAS International Conference on SIGNAL PROCESSING, ROBOTICS and AUTOMATION. - 2009. - S. 68-73 . - ISBN 978-960-474-054-3 . — ISSN 1790-5117 . Arkiveret fra originalen den 30. august 2017.
  2. Random.org . Dato for adgang: 19. november 2017. Arkiveret fra originalen 24. februar 2011.
  3. ↑ 1 2 3 4 5 6 L'Ecuyer, Pierre. Random Number Generation  // Springer Handbooks of Computational Statistics: Kapitel. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 . Arkiveret fra originalen den 1. december 2017.
  4. Von Neumann, John. Forskellige teknikker brugt i forbindelse med tilfældige cifre  // National Bureau of Standards Applied Mathematics Series. - 1951. - Nr. 12 . - S. 36-38 . Arkiveret fra originalen den 6. november 2020.
  5. Lehmer, D. H. Mathematical Methods in Large-Scale Computing Units  // Ann, Comput Lab. Harvard Univ. - 1951. - Vol. 26. - S. 141-146 .  (utilgængeligt link)
  6. Intel Digital Random Number Generator (DRNG): Software Implementation Guide, Revision 1.1 (PDF). Intel Corporation (7. august 2012). Hentet 25. november 2012. Arkiveret fra originalen 18. maj 2013.
  7. National Bureau of Standards. Årsrapport 1951 National Bureau of Standards .
  8. JH Curtiss. Et symposium med digitalt regnemaskineri i stor skala  // Matematiske tabeller og andre hjælpemidler til beregning. - 1947-04. - T. 2 , nej. 18 . - S. 229 . - doi : 10.2307/2002294 . Arkiveret 11. maj 2022.
  9. JW Wrench. Table errata: The art of computer programmering, Vol. 2: Seminumeriske algoritmer (Addison-Wesley, Reading, Mass., 1969) af Donald E. Knuth  //  Mathematics of Computation. - 1970. - Bd. 24 , udg. 110 . — S. 504 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1970-0400642-2 .
  10. Robert C. Tausworth. Tilfældige tal genereret af lineær gentagelse modulo to  //  Mathematics of Computation. - 1965. - Bd. 19 , iss. 90 . — S. 201–209 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1965-0184406-1 .
  11. B.A. Wichmann, ID Hill. Algoritme AS 183: En effektiv og bærbar Pseudo-Random Number Generator  // Journal of the Royal Statistical Society. Serie C (Anvendt statistik). - 1982. - T. 31 , no. 2 . — S. 188–190 . — ISSN 0035-9254 . - doi : 10.2307/2347988 . Arkiveret 11. maj 2022.
  12. Stephen Wolfram. Statistisk mekanik af cellulære automater  // Anmeldelser af moderne fysik. — 1983-07-01. - T. 55 , no. 3 . — S. 601–644 . - doi : 10.1103/RevModPhys.55.601 .
  13. L. Blum, M. Blum, M. Shub. En simpel uforudsigelig pseudo-tilfældig talgenerator  // SIAM Journal on Computing. - 1986-05-01. - T. 15 , nej. 2 . — S. 364–383 . — ISSN 0097-5397 . - doi : 10.1137/0215025 . Arkiveret fra originalen den 27. april 2022.
  14. SK Park, KW Miller. Tilfældige talgeneratorer: gode er svære at finde  // Kommunikation af ACM. — 1988-10-01. - T. 31 , nej. 10 . - S. 1192-1201 . — ISSN 0001-0782 . - doi : 10.1145/63039.63042 .
  15. RS Wikramaratna. ACORN—En ny metode til at generere sekvenser af ensartet fordelte pseudo-tilfældige tal  // Journal of Computational Physics. — 1989-07. - T. 83 , nr. 1 . — S. 16–31 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(89)90221-0 .
  16. G. K. Savvidy, N. G. Ter-Arutyunyan-Savvidy. Om Monte Carlo simulering af fysiske systemer  (engelsk)  // Journal of Computational Physics. - 1991-12-01. — Bd. 97 , udg. 2 . — S. 566–572 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(91)90015-D . Arkiveret 11. maj 2022.
  17. 1 2 George Marsaglia, Arif Zaman. En ny klasse af tilfældige talgeneratorer  // The Annals of Applied Probability. - 1991-08. - T. 1 , nej. 3 . — S. 462–480 . — ISSN 2168-8737 1050-5164, 2168-8737 . - doi : 10.1214/aoap/1177005878 . Arkiveret fra originalen den 19. april 2022.
  18. ISAAC, en hurtig kryptografisk tilfældig talgenerator . www.burtleburtle.net . Hentet: 17. maj 2022.
  19. Makoto Matsumoto, Takuji Nishimura. Mersenne twister: en 623-dimensionelt ligefordelt ensartet pseudo-tilfældig talgenerator  // ACM Transactions on Modeling and Computer Simulation. — 1998-01-01. - T. 8 , nej. 1 . — S. 3–30 . — ISSN 1049-3301 . doi : 10.1145 / 272991.272995 .
  20. George Marsaglia. Xorshift RNGs  //  Journal of Statistical Software. - 2003-07-04. — Bd. 8 . — S. 1–6 . — ISSN 1548-7660 . - doi : 10.18637/jss.v008.i14 .
  21. Bogkilder - Wikipedia . en.wikipedia.org . Hentet 17. maj 2022. Arkiveret fra originalen 24. april 2022.
  22. François Panneton, Pierre L'Ecuyer, Makoto Matsumoto. Forbedrede langtidsgeneratorer baseret på lineære gentagelser modulo 2  // ACM-transaktioner på matematisk software. - 01-03-2006. - T. 32 , no. 1 . — S. 1–16 . — ISSN 0098-3500 . - doi : 10.1145/1132973.1132974 .
  23. 1 2 3 John K. Salmon, Mark A. Moraes, Ron O. Dror, David E. Shaw. Parallelle tilfældige tal: så let som 1, 2, 3  // Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis. — New York, NY, USA: Association for Computing Machinery, 2011-11-12. — S. 1–12 . - ISBN 978-1-4503-0771-0 . - doi : 10.1145/2063384.2063405 .
  24. BG Sileshi, C. Ferrer, J. Oliver. Accelererer hardware Gaussisk tilfældig talgenerering ved hjælp af Ziggurat og CORDIC algoritmer  // 2014 IEEE SENSORS. — 2014-11. — S. 2122–2125 . - doi : 10.1109/ICSENS.2014.6985457 . Arkiveret fra originalen den 17. maj 2022.
  25. Random Bit Generator  // SpringerReference. — Berlin/Heidelberg: Springer-Verlag.
  26. Bernard Widynski. Middle-Square Weyl Sequence RNG  // arXiv:1704.00358 [cs]. — 2022-03-20. Arkiveret fra originalen den 17. maj 2022.
  27. David Blackman, Sebastiano Vigna. Krypterede lineære  pseudorandomtalgeneratorer // arXiv:1805.01407[cs]. — 28-03-2022. Arkiveret 11. maj 2022.
  28. Shin Harase, Takamitsu Kimoto. Implementering af 64-bit maksimalt ligefordelte F2-lineære generatorer med Mersenne Prime Period  // ACM-transaktioner på matematisk software. — 2018-01-03. - T. 44 , no. 3 . — S. 30:1–30:11 . — ISSN 0098-3500 . - doi : 10.1145/3159444 .
  29. Bernard Widynski. Squares: A Fast Counter-Based RNG  // arXiv:2004.06278 [cs]. — 2022-03-13. Arkiveret 11. maj 2022.
  30. Daniel Henrique Pereira. Itamaracá: En ny enkel måde at generere pseudo-tilfældige tal  (engelsk) . — 25-01-2022. - doi : 10.33774/coe-2022-zsw6t . Arkiveret fra originalen den 27. april 2022.
  31. ↑ 1 2 3 4 5 Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Informationssikkerhed. Studievejledning . - S. 100-113. Arkiveret 24. november 2020 på Wayback Machine
  32. Donald Knuth . Kapitel 3.3. Spektralt kriterium // Kunsten at programmere. Dekret. op. - S. 129-130.
  33. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeriske opskrifter i C: The Art of Scientific Computing. — 2. udg. - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .
  34. Tilfældige tal opnået fra kvantevakuumet . Hentet 18. april 2012. Arkiveret fra originalen 19. april 2012.
  35. Jovan DJ. Goli c. Cryptanalytic Attacks on MIFARE Classic Protocol  // Emner i kryptologi - CT-RSA 2013. - Springer, Berlin, Heidelberg, 2013. - Nr. 7779 . - S. 239-259 . - doi : 10.1007/978-3-642-36095-4_16 .
  36. 12 Røllike . _ Hentet 10. september 2004. Arkiveret fra originalen 8. november 2012.
  37. ↑ 1 2 Intel DRNG Software Implementation Guide . Intel . Hentet 8. december 2017. Arkiveret fra originalen 21. april 2016.
  38. J.-P. Aumasson. På pseudo-tilfældig generator ISAAC  // Cryptology ePrint Archive. - 2006. Arkiveret 8. september 2016.
  39. H. Chen, K. Laine, R. Player. [ https://eprint.iacr.org/2017/224.pdf Simple Encrypted Arithmetic Library - SEAL v2.1] // Cryptology ePrint Archive. - 2017. Arkiveret den 10. juli 2017.
  40. A. Kircanski og A. M. Youssef. [ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.301.2615&rep=rep1&type=pdf On the Sliding Property of SNOW 3G and SNOW 2.0] // Information Security, IET. - 2010. - Nr. 5(4) . - S. 199-206 . Arkiveret fra originalen den 16. december 2017.
  41. Laponina O. R. Symmetriske krypteringsalgoritmer . KEND INTUIT . Hentet 8. december 2017. Arkiveret fra originalen 9. december 2017.
  42. Kelsey J., Schneier B., Wagner D., Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators  // Hurtig softwarekryptering. FSE 1998. Forelæsningsnotater i datalogi. - Springer, Berlin, Heidelberg, 1998. - Vol. 1372. - doi : 10.1007/3-540-69710-1_12 . Arkiveret fra originalen den 7. december 2017.
  43. N. T. Courtois. Højere ordens korrelationsangreb, XL-algoritme og krypteringsanalyse af Toyocrypt  // Cryptology ePrint Archive. - 2002. Arkiveret 29. marts 2017.
  44. Ed Dawson, Andrew Clark, J Golic, W Millan, L Penna. LILI-128 Keystream Generator . — 2000-12-13. Arkiveret fra originalen den 16. december 2017.
  45. C. S. Petrie, J. A. Connelly. En støjbaseret IC tilfældig talgenerator til applikationer i kryptografi  // IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. - Maj 2000. - Vol. 47, nr. 5 . — S. 615–621 . — ISSN 1057-7122 . doi : 10.1109 / 81.847868 .
  46. Artikel 12.1. Krav til lotteriudstyr og lotteriterminaler . Hentet 6. december 2017. Arkiveret fra originalen 6. december 2017.
  47. Svar på spørgsmål om Stoloto . Hundred Lotto . Hentet 6. december 2017. Arkiveret fra originalen 6. december 2017.
  48. Udsendelser af statslotteritrækninger . Hundred Lotto . Hentet 6. december 2017. Arkiveret fra originalen 6. december 2017.
  49. Generator af tilfældige tal . Hundred Lotto . Hentet 6. december 2017. Arkiveret fra originalen 6. december 2017.
  50. Mand hackede tilfældigt tal-generator for at rigge lotterier, siger efterforskere , The Guardian . Arkiveret fra originalen den 23. december 2017. Hentet 6. december 2017.

Litteratur

  • Donald E. Knuth . Kapitel 3. Tilfældige tal // Kunsten at programmere computer. - 3. udg. - M. : Williams , 2000. - V. 2. Opnåede algoritmer. — 832 s. - 7000 eksemplarer.  - ISBN 5-8459-0081-6 (russisk) ISBN 0-201-89684-2 (engelsk).
  • Kelton W., Lowe A. Simuleringsmodellering. CS klassiker. - 3. udg. - Sankt Petersborg. : Peter, 2004. - S. 465, 466. - 487 s. — ISBN 0070592926 . — ISBN 5-94723-981-7 .
  • L'Ecuyer, Pierre. Random Number Generation  // Springer Handbooks of Computational Statistics: Kapitel. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 .

Links