Pseudo-slumptalsgenerator

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 januari 2022; kontroller kräver 6 redigeringar .

Pseudo-slumptalsgenerator ( PRNG , engelska pseudorandom number generator , PRNG ) är en algoritm som genererar en sekvens av tal , vars element är nästan oberoende av varandra och lyder en given fördelning (vanligtvis diskret uniform ).

Modern datavetenskap använder sig i stor utsträckning av pseudo-slumptal i en mängd olika tillämpningar, från Monte Carlo och simulering till kryptografi . Samtidigt beror kvaliteten på de erhållna resultaten direkt på kvaliteten på de använda PRNG:erna. Denna omständighet betonas av den välkända aforismen av ORNL -matematikern Robert Caviu: " Slumptalsgenerering är för viktigt för att lämnas åt slumpen ."

Källor till slumpmässiga siffror

Källor till verkliga slumptal är extremt svåra att hitta. Fysiska brus [1] såsom detektorer för joniserande strålningshändelse , skottljud i ett motstånd eller kosmisk strålning [2] kan vara sådana källor. Sådana enheter används dock sällan i nätverkssäkerhetsapplikationer. Brutala attacker på sådana enheter orsakar också svårigheter.

Fysiska källor till slumptal har ett antal nackdelar:

Tid och arbetskostnader under installation och konfiguration jämfört med programvara PRNG;
hög kostnad;
Generering av slumptal är långsammare än med mjukvaruimplementering av PRNG;
Omöjligheten att reproducera en tidigare genererad sekvens av slumptal. [3]

Samtidigt kan slumptal erhållna från en fysisk källa användas som ett genererande element (engelsk utsäde) för mjukvaru-PRNG. Sådana kombinerade generatorer används i kryptografi, lotterier, spelautomater. [3]

Kvalitativa krav för PRNG

En tillräckligt lång period för att säkerställa att sekvensen inte går i loop inom det problem som ska lösas. Periodens längd måste vara matematiskt bevisad;
Effektivitet - algoritmens hastighet och låga minneskostnader;
Reproducerbarhet - förmågan att återproducera en tidigare genererad sekvens av tal hur många gånger som helst;
Portabilitet - samma funktion på olika hårdvara och operativsystem;
Hastigheten för att erhålla ett element i en sekvens av tal, när ett element specificeras, för vilket värde som helst; detta gör att sekvensen kan delas upp i flera strömmar (sekvenser av nummer). [3] ${\displaystyle X_{n+i))$ $X_{{n}}$ $i$

Tidiga tillvägagångssätt för bildandet av PRSPs

John von Neumann ansåg att det var oacceptabelt att använda fysiska slumptalsgeneratorer inom datorteknik, eftersom om det skulle bli nödvändigt att kontrollera beräkningar skulle upprepade tidigare åtgärder kräva reproduktion av ett slumptal, medan generering av ett nytt slumptal är oacceptabelt. Preliminär registrering och lagring av genererade slumptal skulle innebära möjligheten att läsa dem. Dataavläsningsmekanismen var en av de svagaste länkarna i 1940-talets datorer. John von Neumann gav följande medelkvadratmetod [4] för att erhålla tiosiffriga pseudoslumptal:

Ett tiosiffrigt tal kvadreras, sedan tas ett tiosiffrigt tal från mitten av kvadraten på talet, som kvadreras igen, och så vidare.

Till exempel, för 4-siffriga nummer, från och med 1234, får vi , där vi tar de mittersta 4 siffrorna (lägg till en nolla i början, om det behövs). Sedan kvadrerar vi det resulterande talet , och så vidare. Nackdelen med denna metod är den begränsade uppsättningen av PSCH på grund av det faktum att sekvensen loopar - . $1234^{2}=1522756$ $01{\overline {5227}}56$ $5227^{2}=27{\overline {3215}}29$ $5000^{2}=25{\overline {0000}}00.0^{2}=0,\dots$

År 1951 föreslog D. G. Lemer en linjär kongruent metod , [5] vars kärna är att specificera en sekvens av heltal med en rekursiv formel där är heltal och uppfyller följande villkor: . Nackdelen med denna metod är beroendet av , eftersom , samt det faktum att PFC loopar. $X_{n+1}=(aX_{n}+c)~{\bmod {~}}m,$ $a,\ m,\ c$ $0<m,\ \ 0<a<m,\ \ 0<c<m,\ \ X_{0}<m$ $X_{n},\ n>0$ $X_{{0}}$ $X_{n}=\left(a^{n}X_{0}+{\frac {c(a^{n}-1)}{(a-1)))\right)~{\ bmod {~}}m$

Deterministiska PRNGs

Algoritm

De flesta av de deterministiska PRNG :erna motsvarar den :1994]1 [struktur som föreslogs av P. Lecuer . Vanligtvis och tillståndet för generatorn ges av den rekursiva formeln för . Generatorns utgångsvärde ; är en sekvens av pseudoslumptal. Eftersom det är ändligt måste det finnas några ändliga och sådana som . Detta innebär att villkoren och kommer att vara uppfyllda för alla , eftersom funktionerna och är deterministiska. Således visar det sig att sekvensen är periodisk. PRNG- perioden kallas den minsta positiva . [3] $({\mathcal {S)),\mu ,f,{\mathcal {U)),g)$ $\mathcal{S}$ $\mu$ $\mathcal{S}$ ${\displaystyle {\mathcal {s_{0))))$ $f:{\mathcal {S}}\rightarrow {\mathcal {S}}$ ${\mathcal {U}}$ $g:{\mathcal {S}}\rightarrow {\mathcal {U}}$ ${\mathcal {U}}=(0,1)$ $s_{i}=f\ (s_{i-1})$ $i\geq 1$ $u_{i}=g\ (s_{i})\in {\mathcal {U}}$ $u_{0},\ u_{1},\ u_{2}\ ...$ ${\mathcal {U}}$ $l\geq 0$ $j>0$ ${\displaystyle s_{l+j}=s_{l))$ $i\geq l$ $s_{i+j}=s_{i}$ ${\displaystyle u_{i+j}=u_{i))$ $f$ $g$ $j$

De vanligaste är den linjära kongruentialmetoden , Fibonaccimetoden med fördröjningar , skiftregistret med linjär återkoppling , skiftregistret med generaliserad återkoppling .

Av moderna PRNG:er har " Mersenne-virveln " som föreslogs 1997 av Matsumoto och Nishimura också blivit utbredd . Dess fördelar är en kolossal period (2 19937 −1), en enhetlig fördelning i 623 dimensioner (den linjära kongruentialmetoden ger en mer eller mindre enhetlig fördelning i max 5 dimensioner), snabb generering av slumptal (2-3 gånger snabbare än standard PRNG med linjär kongruent metod). Det finns dock algoritmer som känner igen sekvensen som genereras av Mersenne-virveln som icke-slumpmässig.

En pseudo-slumptalsgenerator ingår i många moderna processorer , till exempel ingår RdRand i IA-32-instruktionsuppsättningen. [6]

En variant av PRNG är GPSB (PRBG) - generatorer av pseudo-slumpmässiga bitar, såväl som olika strömchiffer .

Lista över pseudo-slumptalsgeneratorer

Följande är en lista över generatorer som historiskt sett har stått ut inom området för generering av pseudo-slumptal, antingen på grund av sin historiska betydelse eller för att de var en innovativ modell för sina epoker. Dessutom, trots att detta är en PRNG, kan några av dem vara tillämpliga inom kryptografi.

Algoritm	Författarna		Länkar	Beskrivning
mitten av kvadraten	John von Neumman	1946	[7]	PRNG, som anses vara låg kvalitet men av stor historisk betydelse som en av de första algoritmerna.
Lehmer Generator / Linjär kongruentiell metod	D.H. Lehmer	1951	[åtta]	Det är också känt som metoden för multiplikativ linjär kongruens och har varit mycket inflytelserik inom detta forskningsområde. Den är också känd som den linjära kongruentiella metoden, vars grund har förbättrats med tiden.
Lag Fibonacci Generator	GJ Mitchell; D.P. Moore	1958	[9]	En mycket inflytelserik algoritm i studiet av processer för generering av slumptal, som inspirerar andra senare stora författare som G. Marsaglia, skapare av ett kvalitetstest för slumptal som heter "Diehard", till exempel.
Linjärt återkopplingsregister (LFSR) / Tausworthe-oscillator	R.C. Tausworth	1965	[tio]	En generator vars design påverkade många andra efterföljande PRNG:er. Därför är det mycket historiskt viktigt. Även känd som Tausworthe-generatorn.
Wichmann & Hill Generator	B.A. Wichmann; D.I. Hill	1982	[elva]	En kombination av tre små LCG:er lämpliga för 16-bitars processorer. Används flitigt i många program, till exempel, användes den i Excel 2003 och några senare versioner för RAND-funktionen i Excel och var standardgeneratorn i Python fram till version 2.2.
Regel 30	Wolfram, Stephen	1983	[12]	Generator baserad på cellulära automater.
Blum-Blum-Shub Generator	Bloom, Manuel ; L. Blum; M. Shub	1986	[13]	Det anses vara en av de säkraste generatorerna ur en kryptografisk synvinkel, främst på grund av inkorporeringen av forskning och begrepp hämtade från talteorin i dess formel. För denna Blum-algoritm tilldelades Manuel 1995 års Alan Turing-pris.
park-miller generator	SK Park; KW Miller	1988	[fjorton]	En konkret implementering av Lehmer-generatorn, mycket använd eftersom den ingår i C++ som minstd_rand0-funktionen sedan C++11.
EKOLLON	RS Wikramaratna	1989	[femton]	Dess namn kommer från den engelska förkortningen ACORN, som står för ″Additive Congruent Random Number″.
MIXMAX	GK Savvidy; NG Ter-Arutyunyan-Savvidy	1991	[16]	Detta är en generator som tillhör klassen av matriskongruenta linjära generatorer, en generalisering av metoden för linjära kongruenser. Logiken i MIXMAX-familjen av generatorer är baserad på resultaten av ergodisk teori och klassisk mekanik.
Add-with-carry	G. Marsaglia	1991	[17]	Modifiering av Fibonacci-generatorer med fördröjning.
Subtrahera-med-låna	G. Marsaglia; A. Zaman	1991	[17]	Algoritm härledd från Fibonacci-generatorer med fördröjning.
ISAAC	RJ Jenkins Jr.	1993	[arton]	Cryptographically Secure Cryptographic Data Generator (CSPRNG) utvecklad av Robert J. Jenkins.
Mersenne Twister, MT	M. Matsumoto; T. Nishimura	1996	[19]	Detta är förmodligen den mest kända generatorn på den här listan, främst för att det är en algoritm implementerad i RAND-funktionen för programmeringsspråken Python och R, förutom dess starka närvaro i elektroniska spel som Pro Evolution Soccer (PES).
Xorshift	G. Marsaglia	2003	[tjugo]	Detta är en mycket snabb undertyp av LFSR-generatorer. Marsaglia föreslog också en xorwow-generator som en förbättring, där utsignalen från xorshift-generatorn summeras med en Weyl-sekvens. xorwow-generatorn är standardgeneratorn i nVidia CUDA API CURAND-biblioteket för GPU:er.
Fortuna algoritm	Schneier, Bruce ; Niels Ferguson	2003	[21]	Algoritmen anses vara kryptografiskt säker. CSPRNG, välkänd för att vara inbäddad i Apples system och produkter.
Väl jämnt fördelad långperiodisk linjär (WELL)	F. Panneton; P. L'Ecuyer; M. Matsumoto	2006	[22]	En algoritm känd som ett tillägg till Mersenne Twister (MT), som medvetet försöker dölja sina svagheter.
Advanced Randomization System (ARS)	J. Salmon; M. Moraes; R. Dror; D. Shaw	2011	[23]	En förenklad version av AES-blockchifferet som ger mycket hög prestanda på ett system som stöder AES-NI.
Threefry	J. Salmon, M. Moraes, R. Dror och D. Shaw	2011	[23]	En förenklad version av Threefish-blockchifferet lämplig för GPU-implementering.
Philox (Philox)	J. Salmon, M. Moraes, R. Dror och D. Shaw	2011	[23]	Förenkling och modifiering av blockchifferet Threefish med tillägg av S-box.
Permuterad kongruentialgenerator (PCG)	M.E. O'Neill	2014	[24]	Modell erhållen med den linjära kongruentialmetoden.
Random Cycle Bit Generator (RCB)	R. Cookman	2016	[25]	RCB:n beskrivs som en bitmönstergenerator utformad för att övervinna några av bristerna hos Mersenne Twist (MT) och begränsningen av kort period/bitlängd hos shift/modulo-generatorer.
Middle Square Weyl Sequence RNG	B. Widynski	2017	[26]	En variant på John von Neumanns ursprungliga medelkvadratmetod.
Xoroshiro128+	D. Blackman; S. Vigna	2018	[27]	Modifiering av G. Marsaglias Xorshift-generator, en av de snabbaste generatorerna på moderna 64-bitars processorer. Relaterade generatorer är xoroshiro128, xoshiro256+ och xoshiro256*.
64-bitars MELG (MELG-64)	S. Harase; T. Kimoto	2018	[28]	Implementering av 64-bitars linjära F2-generatorer med primär Mersenne-period.
Rutor RNG	B. Widynski	2020	[29]	En motbaserad version av Middle Square Weyl Sequence RNG. Liknande design som Philox, men mycket snabbare.
Itamaraca (Ita)	D.H. Pereira	2021	[trettio]	Känd som den första PRNG-algoritmen baserad på absolutvärdesfunktionen. Itamaracá är också en enkel och snabb modell som genererar aperiodiska sekvenser av slumptal.

Anteckningsblock för engångsbruk

En alternativ lösning är att skapa en uppsättning av ett stort antal slumpmässiga tal och publicera den i någon sorts ordbok , kallad " engångsblock ". Men även sådana uppsättningar ger en mycket begränsad källa till nummer jämfört med antalet som krävs av nätverkssäkerhetsapplikationer. Även om dessa uppsättningar ger statistisk slumpmässighet, är de inte tillräckligt säkra eftersom en angripare kan få en kopia av ordboken.

Nackdelar med PRNG

Ingen deterministisk algoritm kan generera helt slumpmässiga tal, den kan bara approximera vissa av deras egenskaper. Som John von Neumann sa , " Vem som helst som har en svaghet för de aritmetiska metoderna för att erhålla slumpmässiga tal är utan tvekan en syndare ."

Alla PRNG med begränsade resurser fastnar förr eller senare - den börjar upprepa samma nummersekvens. Längden på PRNG-cykler beror på själva generatorn och är ungefär , där är storleken på det interna tillståndet i bitar, även om linjära kongruenta och LFSR- generatorer har maximala ordningscykler [31] . Om den genererade PRNG-sekvensen konvergerar till för korta cykler, blir sådan PRNG förutsägbar och olämplig för praktiska tillämpningar. $2^{\frac {n}{2}}$ $n$ $2^{n}$

De flesta enkla aritmetiska generatorer, även om de är snabba, lider av många allvarliga brister:

För kort period/perioder.
Konsekutiva värden är inte oberoende.
Vissa bitar är "mindre slumpmässiga" än andra.
Ojämn endimensionell fördelning.
Reversibilitet.

Speciellt RANDU- algoritmen , som har använts på stordatorer i decennier , visade sig vara mycket dålig [32] [33] , vilket väckte tvivel om tillförlitligheten av resultaten från många studier som använder denna algoritm.

PRNG med entropikälla eller RNG

Tillsammans med behovet av att generera lätt reproducerbara sekvenser av slumptal, finns det också ett behov av att generera helt oförutsägbara eller helt enkelt helt slumpmässiga tal. Sådana generatorer kallas slumptalsgeneratorer (RNG - engelska slumptalsgenerator, RNG ). Eftersom sådana generatorer oftast används för att generera unika symmetriska och asymmetriska nycklar för kryptering, är de oftast byggda av en kombination av en kryptografiskt stark PRNG och en extern entropikälla (och denna kombination är nu allmänt uppfattad som RNG).

Nästan alla stora mikrochipstillverkare levererar hårdvaru-RNG:er med olika källor till entropi, genom att använda olika metoder för att rensa dem från oundviklig förutsägbarhet. Men för tillfället matchar inte hastigheten för att samla in slumptal av alla befintliga mikrochips (flera tusen bitar per sekund) hastigheten hos moderna processorer.

I modern forskning görs försök att använda mätningen av de fysiska egenskaperna hos föremål (till exempel temperatur ) eller till och med kvantfluktuationer av vakuum som en entropikälla för RNG. [34]

I persondatorer använder RNG-programförfattare mycket snabbare källor till entropi, som ljudkortsbrus eller en processorklockräknare . Entropisamlingen var den mest sårbara punkten i RNG. Det här problemet är fortfarande inte helt löst i många enheter (som smarta kort ) som förblir sårbara på detta sätt. [35] Många RNG:er använder traditionella beprövade, om än långsamma, metoder för insamling av entropi, som att mäta användarens respons ( musrörelser , etc.), som i PGP och Yarrow [36] , eller interaktioner mellan trådar , som , i Java SecureRandom.

Ett exempel på en enkel RNG med en entropikälla

Om den aktuella tiden används som entropikälla, räcker det för att få ett heltal från 0 till N , att beräkna resten av att dividera den aktuella tiden i millisekunder med talet N +1. Nackdelen med denna RNG är att den producerar samma nummer under en millisekund.

Exempel på RNG- och entropikällor

	Entropikälla	PRNG	Fördelar	Brister
/dev/random på UNIX / Linux	Processorklockräknare, samlas dock bara in under hårdvaruavbrott	LFSR , med output-hashning via SHA-1	Tillgänglig på alla Unix, en pålitlig källa till entropi	Det "värms upp" under mycket lång tid, kan "fastna" under lång tid, eller fungerar som en PRNG ( / dev / urandom )
Yarrow av Bruce Schneier [36]	Traditionella metoder	AES -256 och SHA-1 litet internt tillstånd	Flexibel kryptobeständig design	Långsam
Microsoft CryptoAPI	Aktuell tid, hårddiskstorlek, ledigt minne, processnummer och NETBIOS-namn på datorn	MD5- hash för det interna tillståndet, 128 bitar i storlek	Inbyggd i Windows, fastnar inte	Beror starkt på vilken kryptografisk leverantör (CSP) som används.
Java SecureRandom	Kommunikation mellan trådar	SHA-1 - intern tillståndshash (1024 bitar)	Stort internt tillstånd	Långsam entropisamling
RdRand av intel [37]	Bullerströmmar	PFS-konstruktion baserad på "slumpmässig" bitavläsning av värden från strömmar [37]	Mycket snabb, fastnar inte	Den ursprungliga utvecklingen, fastigheterna ges endast efter godkännande av exploatörerna.

PRNG i kryptografi

Ett av kriterierna för att PRNG är kryptografiskt stark är oförmågan att skilja utdatavärdena för PRNG från en oberoende slumpmässig sekvens jämnt fördelad över intervallet. Låt det finnas en familj av PRNG , där kardinaliteten av uppsättningen är lika med . Som nämnts ovan, är en ändlig uppsättning tillstånd, är en sannolikhetsfördelning i tillståndet utrymme som används för att välja det initiala tillståndet (engelsk frö), är en övergångsfunktion, är utrymmet för utdatavärden, . Vanligtvis och tillståndet för generatorn ges av den rekursiva formeln för . Generatorns utgångsvärde ; är en sekvens av pseudoslumptal. Antag att övergångs- och utgångsfunktionerna kan beräknas i polynomtid, potenser av . Låt vara en klass av statistiska tester som försöker i polynomtid att skilja utdatavärdena för PRNG från en oberoende slumpmässig sekvens likformigt fördelad över intervallet . En familj av PRNG:er kallas bra i termer av polynomtid om det finns en sådan att ingen av testerna för alla kan särskilja utdatavärdena för PRNG från en oberoende slumpmässig sekvens likformigt fördelad över intervallet med sannolikhet . [3] ${\mathcal {U}}=(0,1)$ ${\xi _{k}=({\mathcal {S_{k))},\mu _{k},f_{k},{\mathcal {U_{k))},g_{k} ),k=1,2,...}$ ${\displaystyle {\mathcal {S_{k))))$ $2^k$ $\mathcal{S}$ $\mu$ $\mathcal{S}$ ${\displaystyle {\mathcal {s_{0))))$ $f:{\mathcal {S}}\rightarrow {\mathcal {S}}$ ${\mathcal {U}}$ $g:{\mathcal {S}}\rightarrow {\mathcal {U}}$ ${\mathcal {U}}=(0,1)$ $s_{i}=f\ (s_{i-1})$ $i\geq 1$ $u_{i}=g\ (s_{i})\in {\mathcal {U}}$ $u_{0},\ u_{1},\ u_{2}\ ...$ $f$ $g$ $k$ $\mathcal{T}$ $k$ ${\mathcal {U}}=(0,1)$ ${\displaystyle \xi _{k))$ $\epsilon > 0$ $k$ $\mathcal{T}$ ${\mathcal {U}}=(0,1)$ ${\displaystyle 1/2+e^{-k\epsilon ))$

Kryptografiska applikationer använder deterministiska algoritmer för att generera slumpmässiga tal, och genererar därför en sekvens av tal som teoretiskt sett inte kan vara statistiskt slumpmässiga. Samtidigt, om du väljer en bra algoritm, kommer den resulterande numeriska sekvensen - pseudoslumptal - att klara de flesta tester för slumpmässighet. En av egenskaperna hos en sådan sekvens är en lång upprepningsperiod. [3]

Exempel på välkända kryptografiskt starka PRNG:er är RC4 [31] , ISAAC [38] , SEAL [39] , SNOW [40] , en mycket långsam teoretisk Blum-Blum-Shub-algoritm [31] , samt räknare med kryptografisk hash funktioner eller kryptografiskt säkra blockchiffer istället för utdatafunktionen [31] .

Kryptografiskt starka chiffer inkluderar också generatorer med flera skiftregister , generatorer med icke-linjära transformationer och majoritetskrypteringsgeneratorer A5/x . [31]

Exempel på kryptoresistenta PRNGs

Round-robin-kryptering

Slumptalsgeneratorn krypteras med hjälp av olika hemliga nycklar som erhålls i varje steg. En räknare med lång period används som indata till krypteringsenheten. När du använder en 56-bitars DES -nyckel kan en räknare med punkt användas . $X_{i}$ $N$ $2^{56}$

Vid tidpunkten för initieringen genereras en hemlig nyckel och en konstant . måste vara slumpmässigt och endast användas för denna generator. $K$ $C$ $K$
I varje steg händer följande:

X_{i}=E_{K}(C)

C=C+1

Den pseudo-slumpmässiga sekvensen som erhålls av detta schema har en hel period: varje utdatavärde , , … baseras på ett annat räknarvärde, därför . Eftersom nyckeln är hemlig, beror inte någon hemlig nyckel på kunskapen om en eller flera tidigare hemliga nycklar. För att öka algoritmens kryptografiska styrka är det nödvändigt att vid varje steg kryptera ett slumptal med en RNG - . [41] $X_{{0}}$ $X_{1}$ $X_{N-1}$ ${\displaystyle X_{0}\neq X_{1}\neq ...\neq X_{N-1))$ $K$ $X_{i}$ $R_{i}$ $X_{i}=E_{K}(R_{i})$

$K$ är nyckeln som används i varje steg.
$E_{K}$ - nyckelkrypteringsfunktion . $K$
$R_{i}$ - slumptal med RNG.

ANSI X9.17

PRNG från ANSI X9.17-standarden används i många applikationer för ekonomisk säkerhet och PGP . Kärnan i denna PRNG är trippel DES . ANSI X9.17-generatorn består av följande delar:

Vid tidpunkten för initieringen genereras en hemlig nyckel . Det måste vara slumpmässigt och används endast för denna generator. $K$
I varje steg händer följande:

T_{i}=E_{K}(D_{i})

R_{i}=E_{K}(T_{i}\oplus V_{i})

V_{i+1}=E_{K}(T_{i}\oplus R_{i})

${\displaystyle D_{i))$ — Värdet av datum och tid i början av generationens generation. $i$
$V_{i}$ är det initiala värdet för -th generationens steg. $i$
$R_{i}$ är ett pseudo-slumpmässigt tal som skapas i generationens generation. $i$
$K$ är nyckeln som används i varje steg.
$E_{K}$ - nyckelkrypteringsfunktion . $K$

De inmatade slumpmässiga värdena är och . är utgångsvärdet. Beräkning från utan kunskap är inte möjlig inom rimlig tid, och därmed nästa pseudo-slumpmässiga värde , eftersom tre ytterligare krypteringsoperationer utförs för att erhålla. [42] ${\displaystyle D_{i))$ $V_{i}$ $R_{i}$ $V_{i+1}$ $R_{i}$ $K$ $R_{i+1}$ $V_{i+1}$

Hårdvara PRNGs

Bortsett från de föråldrade, välkända LFSR-generatorerna som användes allmänt som hårdvaru-PRNGs på 1900-talet, är mycket lite känt om modern hårdvaru-PRNG, eftersom de flesta av dem är utvecklade för militära ändamål eller är patenterade och hålls hemliga . Hårdvarubaserade RLOS- generatorer Toyocrypt och LILI-128 hackades med hjälp av algebraiska attacker [43] [44] .

För närvarande är det känt om användningen av hårdvaru-PRNG:er implementerade på basis av lågeffektbrus i elektriska kretsar. [45]

Tillämpning av PRNG i lotterier

Slumptalsgenerator för lotterier är ett hårdvaru-mjukvarukomplex som används i lotterier där det är nödvändigt att gissa en kombination av ett visst antal nummer. Alla möjliga tal har samma sannolikhet att inträffa.

Försök att skapa en slumptalsgenerator går tillbaka till 3500 f.Kr. e. och är förknippade med det forntida egyptiska brädspelet Senet . I Senet spelar två spelare på två sidor. Drag bestäms med hjälp av fyra platta pinnar, som kan betraktas som en slumptalsgenerator på den tiden. Kasta alla fyra pinnarna på en gång. Poängsättningen är som följer: 1 pinne föll med den vita sidan upp - 1 poäng och ytterligare ett kast; 2 - 2 poäng; 3 - 3 poäng, 4 - 4 och ett extra kast. En av pinnens sidor är svart och om alla fyra pinnarna faller med den svarta sidan uppåt är detta maxresultat - 5 poäng och ytterligare ett kast.

Den välkända slumptalsgeneratorn ERNIE har använts i många år för att fastställa det brittiska lotteriets vinnande nummer.

Huvudkraven för programvara och utrustning som används för att genomföra lotterier i Ryska federationen fastställs av federal lag nr 138-FZ av den 11 november 2003 "Om lotterier":

De tekniska egenskaperna hos lotteriutrustningen måste säkerställa slumpmässigheten i fördelningen av vinster vid dragning av vinstfonden för draglotterier.
Procedurer som implementerar algoritmer som gör det möjligt att förutbestämma resultatet av dragningen av prisfonden innan en sådan dragning påbörjas bör inte användas.
Lotteriutrustning som används vid lotteriet ska säkerställa skyddet av information från förlust, stöld, förvanskning, obehöriga åtgärder för att förstöra den, ändring, kopiering och andra liknande handlingar och obehörig åtkomst via dataöverföringsnätet. [46]

I ryska statliga lotterier (Gosloto 5 av 36, Gosloto 6 av 36, Gosloto 6 av 45, Gosloto 7 av 49, Gosloto 4 av 20, "Sportloto" 6 av 49 "") [47] själv- laddning av lotteritrummor används för att avgöra vinnarna . Dragningarna sänds live. [48]

I ryska statliga lotterier ("Rapido", "Keno-Sportloto", "Top-3", "12/24", "Allt för hundra"), används en slumptalsgenerator för att avgöra vinnarna - en hårdvara och mjukvara system certifierat av ANO "MIC" och uppfyller rekommendationerna från FSUE VNIIMS . Enheten genererar en kontinuerlig ström av slumpmässigt brus, som omvandlas till siffror. Vid en given tidpunkt rycks nuvarande värden från strömmen, som är den vinnande lotterikombinationen. [49]

År 2015 anklagades den tidigare säkerhetsdirektören för US Multi-State Lottery Association , efter att ha vunnit 16,5 miljoner dollar, som hade tillgång till programvara som användes i lotteridragningar, för att ha använt speciella algoritmer för att fastställa den vinnande lotterikombinationen flera dagar om året. [femtio]

Se även

Anteckningar

↑ N.G. Bardis, A.P. Markovskyi, N. Doukas, N.V. Karadimas. True Random Number Generation Baserat på miljöbullermätningar för militära tillämpningar // 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 . Arkiverad från originalet den 30 augusti 2017.
↑ Random.org . Tillträdesdatum: 19 november 2017. Arkiverad från originalet 24 februari 2011. (obestämd)
↑ 1 2 3 4 5 6 L'Ecuyer, Pierre. Generering av slumptal // Springer Handbooks of Computational Statistics: Kapitel. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 . Arkiverad från originalet den 1 december 2017.
↑ Von Neumann, John. Olika tekniker som används i samband med slumpmässiga siffror // National Bureau of Standards Applied Mathematics Series. - 1951. - Nr 12 . - S. 36-38 . Arkiverad från originalet den 6 november 2020.
↑ Lehmer, D. H. Matematiska metoder i storskaliga beräkningsenheter // Ann, Comput Lab. Harvard Univ. - 1951. - Vol. 26. - S. 141-146 . (inte tillgänglig länk)
↑ Intel Digital Random Number Generator (DRNG): Programvaruimplementeringsguide, version 1.1 (PDF). Intel Corporation (7 augusti 2012). Hämtad 25 november 2012. Arkiverad från originalet 18 maj 2013. (obestämd)
↑ National Bureau of Standards. Årsrapport 1951 National Bureau of Standards .
↑ JH Curtiss. Ett symposium av storskaliga digitala beräkningsmaskiner // Matematiska tabeller och andra hjälpmedel för beräkning. - 1947-04. - T. 2 , nej. 18 . - S. 229 . - doi : 10.2307/2002294 . Arkiverad 11 maj 2022.
↑ JW Wrench. Table errata: The art of computer programmering, Vol. 2: Seminumeriska algoritmer (Addison-Wesley, Reading, Mass., 1969) av Donald E. Knuth // Mathematics of Computation. - 1970. - Vol. 24 , iss. 110 . — S. 504 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1970-0400642-2 .
↑ Robert C. Tausworth. Slumptal genererade av linjär upprepning modulo två // Mathematics of Computation. - 1965. - Vol. 19 , iss. 90 . — S. 201–209 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1965-0184406-1 .
↑ B.A. Wichmann, ID Hill. Algoritm AS 183: En effektiv och bärbar Pseudo-Random Number Generator // Journal of the Royal Statistical Society. Serie C (tillämpad statistik). - 1982. - T. 31 , nr. 2 . — S. 188–190 . — ISSN 0035-9254 . - doi : 10.2307/2347988 . Arkiverad 11 maj 2022.
↑ Stephen Wolfram. Statistisk mekanik för cellulära automater // Recensioner av modern fysik. — 1983-07-01. - T. 55 , nej. 3 . — S. 601–644 . - doi : 10.1103/RevModPhys.55.601 .
↑ L. Blum, M. Blum, M. Shub. En enkel oförutsägbar pseudo-slumptalsgenerator // SIAM Journal on Computing. - 1986-05-01. - T. 15 , nej. 2 . — S. 364–383 . — ISSN 0097-5397 . - doi : 10.1137/0215025 . Arkiverad från originalet den 27 april 2022.
↑ SK Park, KW Miller. Slumptalsgeneratorer: bra är svåra att hitta // Kommunikation av ACM. — 1988-10-01. - T. 31 , nej. 10 . - S. 1192-1201 . — ISSN 0001-0782 . - doi : 10.1145/63039.63042 .
↑ RS Wikramaratna. ACORN—En ny metod för att generera sekvenser av enhetligt fördelade pseudo-slumptal // Journal of Computational Physics. — 1989-07. - T. 83 , nej. 1 . — S. 16–31 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(89)90221-0 .
↑ G. K. Savvidy, N. G. Ter-Arutyunyan-Savvidy. Om Monte Carlos simulering av fysiska system (engelska) // Journal of Computational Physics. - 1991-12-01. — Vol. 97 , iss. 2 . — S. 566–572 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(91)90015-D . Arkiverad 11 maj 2022.
↑ 1 2 George Marsaglia, Arif Zaman. En ny klass av slumptalsgeneratorer // 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 . Arkiverad från originalet den 19 april 2022.
↑ ISAAC, en snabb kryptografisk slumptalsgenerator . www.burtleburtle.net . Hämtad: 17 maj 2022. (obestämd)
↑ Makoto Matsumoto, Takuji Nishimura. Mersenne twister: en 623-dimensionellt ekvifördelad enhetlig pseudo-slumptalsgenerator // 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 .
↑ George Marsaglia. Xorshift RNGs // Journal of Statistical Software. - 2003-07-04. — Vol. 8 . — S. 1–6 . — ISSN 1548-7660 . - doi : 10.18637/jss.v008.i14 .
↑ Bokkällor - Wikipedia . en.wikipedia.org . Hämtad 17 maj 2022. Arkiverad från originalet 24 april 2022. (ryska)
↑ François Panneton, Pierre L'Ecuyer, Makoto Matsumoto. Förbättrade långtidsgeneratorer baserade på linjära upprepningar modulo 2 // ACM-transaktioner på matematisk programvara. — 2006-03-01. - T. 32 , nej. 1 . — S. 1–16 . — ISSN 0098-3500 . - doi : 10.1145/1132973.1132974 .
↑ 1 2 3 John K. Salmon, Mark A. Moraes, Ron O. Dror, David E. Shaw. Parallella slumptal: så enkelt 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 .
↑ BG Sileshi, C. Ferrer, J. Oliver. Accelererar hårdvara Gaussisk slumptalsgenerering med Ziggurat och CORDIC algoritmer // 2014 IEEE SENSORS. — 2014-11. — S. 2122–2125 . - doi : 10.1109/ICSENS.2014.6985457 . Arkiverad från originalet den 17 maj 2022.
↑ Random Bit Generator // SpringerReference. — Berlin/Heidelberg: Springer-Verlag.
↑ Bernard Widynski. Middle-Square Weyl Sequence RNG // arXiv:1704.00358 [cs]. — 2022-03-20. Arkiverad från originalet den 17 maj 2022.
↑ David Blackman, Sebastiano Vigna. Förvrängda linjära pseudoslumptalsgeneratorer // arXiv:1805.01407[cs]. — 2022-03-28. Arkiverad 11 maj 2022.
↑ Shin Harase, Takamitsu Kimoto. Implementering av 64-bitars maximalt likafördelade F2-linjära generatorer med Mersenne Prime Period // ACM-transaktioner på matematisk programvara. — 2018-01-03. - T. 44 , nej. 3 . — S. 30:1–30:11 . — ISSN 0098-3500 . - doi : 10.1145/3159444 .
↑ Bernard Widynski. Squares: A Fast Counter-Based RNG // arXiv:2004.06278 [cs]. — 2022-03-13. Arkiverad 11 maj 2022.
↑ Daniel Henrique Pereira. Itamaracá: Ett nytt enkelt sätt att generera pseudo-slumptal (engelska) . — 2022-01-25. - doi : 10.33774/coe-2022-zsw6t . Arkiverad från originalet den 27 april 2022.
↑ 1 2 3 4 5 Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Informationssäkerhet. Studiehandledning . - S. 100-113. Arkiverad 24 november 2020 på Wayback Machine
↑ Donald Knuth . Kapitel 3.3. Spektralkriterium // Konsten att programmera. Dekret. op. - S. 129-130.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeriska recept i C: The Art of Scientific Computing. — 2:a uppl. - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .
↑ Slumptal erhållna från kvantvakuumet . Hämtad 18 april 2012. Arkiverad från originalet 19 april 2012. (obestämd)
↑ Jovan DJ. Goli c. Cryptanalytic Attacks on MIFARE Classic Protocol // Ämnen inom kryptologi - CT-RSA 2013. - Springer, Berlin, Heidelberg, 2013. - Nr 7779 . - S. 239-259 . - doi : 10.1007/978-3-642-36095-4_16 .
↑ 12 Yarrow . _ Hämtad 10 september 2004. Arkiverad från originalet 8 november 2012. (obestämd)
↑ 1 2 Intel DRNG Software Implementation Guide . Intel . Hämtad 8 december 2017. Arkiverad från originalet 21 april 2016. (obestämd)
↑ J.-P. Aumasson. På pseudo-slumpgeneratorn ISAAC // Cryptology ePrint Archive. - 2006. Arkiverad den 8 september 2016.
↑ H. Chen, K. Laine, R. Player. [ https://eprint.iacr.org/2017/224.pdf Simple Encrypted Arithmetic Library - SEAL v2.1] // Cryptology ePrint Archive. - 2017. Arkiverad den 10 juli 2017.
↑ A. Kircanski och 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 . Arkiverad från originalet den 16 december 2017.
↑ Laponina O. R. Symmetriska krypteringsalgoritmer . KÄNNA INTUIT . Hämtad 8 december 2017. Arkiverad från originalet 9 december 2017. (obestämd)
↑ Kelsey J., Schneier B., Wagner D., Hall C. Cryptanalytic Attacks on Pseudorandom Number Generators // Fast Software Encryption. FSE 1998. Föreläsningsanteckningar i datavetenskap. - Springer, Berlin, Heidelberg, 1998. - Vol. 1372. - doi : 10.1007/3-540-69710-1_12 . Arkiverad från originalet den 7 december 2017.
↑ N. T. Courtois. Högre ordnings korrelationsattacker, XL-algoritm och kryptoanalys av Toyocrypt // Cryptology ePrint Archive. - 2002. Arkiverad den 29 mars 2017.
↑ Ed Dawson, Andrew Clark, J Golic, W Millan, L Penna. LILI-128 Keystream Generator . — 2000-12-13. Arkiverad från originalet den 16 december 2017.
↑ C. S. Petrie, J. A. Connelly. En brusbaserad IC-slumptalsgenerator för applikationer inom 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 .
↑ Artikel 12.1. Krav på lotteriutrustning och lotteriterminaler . Hämtad 6 december 2017. Arkiverad från originalet 6 december 2017. (obestämd)
↑ Svar på frågor om Stoloto . Hundralotto . Hämtad 6 december 2017. Arkiverad från originalet 6 december 2017. (obestämd)
↑ Sändningar av statliga lotteridragningar . Hundralotto . Hämtad 6 december 2017. Arkiverad från originalet 6 december 2017. (obestämd)
↑ Slumptalsgenerator . Hundralotto . Hämtad 6 december 2017. Arkiverad från originalet 6 december 2017. (obestämd)
↑ Man hackade slumptalsgenerator för att rigga lotterier, säger utredare , The Guardian . Arkiverad från originalet den 23 december 2017. Hämtad 6 december 2017.

Litteratur

Donald E. Knuth . Kapitel 3. Slumptal // Konsten att programmera datorer. - 3:e uppl. - M. : Williams , 2000. - V. 2. Erhållna algoritmer. — 832 sid. - 7000 exemplar. - ISBN 5-8459-0081-6 (ryska) ISBN 0-201-89684-2 (engelska).
Kelton W., Lowe A. Simuleringsmodellering. CS klassiker. - 3:e upplagan - St Petersburg. : Peter, 2004. - S. 465, 466. - 487 sid. — ISBN 0070592926 . — ISBN 5-94723-981-7 .
L'Ecuyer, Pierre. Generering av slumptal // Springer Handbooks of Computational Statistics: Kapitel. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 .

Länkar

V. A. Uspensky. Slumpmässighetens fyra algoritmiska ansikten . - MTSNMO , 2006. - 48 sid. — ISBN 978-5-94057-485-9 .
Yuri Lifshits. Föreläsning 9: Pseudoslumpgeneratorer // Moderna problem med kryptografi . - Föreläsningskurs.
L. Barash. AKS-algoritmen för att kontrollera siffror för enkelhet och söka efter konstanter för pseudo-slumptalsgeneratorer // Security of Information Technologies. - 2005. - Nr 2 . - S. 27-38 . Arkiverad från originalet den 18 oktober 2014.
Zhelnikov V. Pseudo-slumpmässiga talsekvenser // Kryptografi från papyrus till dator . - M. : ABF, 1996. - 335 sid. - ISBN 5-87484-054-0 .
Kryptografiska slumptal
Teori och praktik för generering av slumptal
Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analys av Linux Random Number Generator
En statistisk testsvit för slumpmässiga och pseudoslumpmässiga nummergeneratorer för kryptografiska applikationer NIST SP 800-22