Generátor pseudonáhodných čísel

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 10. ledna 2022; kontroly vyžadují 6 úprav .

Generátor pseudonáhodných čísel ( PRNG , anglicky pseudorandom number generator , PRNG ) je algoritmus , který generuje posloupnost čísel , jejichž prvky jsou na sobě téměř nezávislé a řídí se daným rozdělením (obvykle diskrétní uniforma ).

Moderní informatika široce využívá pseudonáhodná čísla v různých aplikacích, od Monte Carla a simulace až po kryptografii . Kvalita získaných výsledků přitom přímo závisí na kvalitě použitých PRNG. Tuto okolnost zdůrazňuje známý aforismus matematika ORNL Roberta Caviu: " Generování náhodných čísel je příliš důležité na to, aby bylo ponecháno náhodě ."

Zdroje náhodných čísel

Zdroje skutečných náhodných čísel se hledají extrémně obtížně. Takovými zdroji mohou být fyzikální šumy [1] , jako jsou detektory událostí ionizujícího záření , šum výstřelu v rezistoru nebo kosmické záření [2] . Taková zařízení se však v aplikacích pro zabezpečení sítí používají jen zřídka. Potíže způsobují i brutální útoky na taková zařízení.

Fyzické zdroje náhodných čísel mají řadu nevýhod:

Časové a mzdové náklady během instalace a konfigurace ve srovnání se softwarem PRNG;
vysoká cena;
Generování náhodných čísel je pomalejší než u softwarové implementace PRNG;
Nemožnost reprodukovat dříve vygenerovanou sekvenci náhodných čísel. [3]

Náhodná čísla získaná z fyzického zdroje lze zároveň použít jako generující prvek (anglicky seed) pro softwarové PRNG. Takové kombinované generátory se používají v kryptografii, loteriích, hracích automatech. [3]

Kvalitativní požadavky na PRNG

Dostatečně dlouhé období , aby se zajistilo, že se sekvence nezacyklí v rámci řešeného problému. Délka období musí být matematicky prokázána;
Efektivita - rychlost algoritmu a nízké náklady na paměť;
Reprodukovatelnost - schopnost opakovaně reprodukovat dříve vygenerovanou sekvenci čísel libovolný počet opakování;
Přenositelnost – stejné fungování na různém hardwaru a operačních systémech;
Rychlost získání prvku posloupnosti čísel při zadávání prvku pro libovolnou hodnotu; to umožňuje rozdělit sekvenci do více proudů (sekvencí čísel). [3] ${\displaystyle X_{n+i))$ $X_{{n}}$ $i$

Rané přístupy k vytváření PRSP

John von Neumann považoval za nepřijatelné používat fyzické generátory náhodných čísel ve výpočetní technice, protože pokud by bylo nutné výpočty kontrolovat, opakování předchozích akcí by vyžadovalo reprodukci náhodného čísla, zatímco generování nového náhodného čísla je nepřijatelné. Předběžný záznam a ukládání generovaných náhodných čísel by znamenalo možnost jejich čtení. Mechanismus čtení dat byl jedním z nejslabších článků počítačů 40. let. John von Neumann dal následující metodu středních čtverců [4] pro získání desetimístných pseudonáhodných čísel:

Desetimístné číslo se odmocní, pak se ze středu odmocniny čísla vezme desetimístné číslo, které se znovu odmocní a tak dále.

Například pro 4místná čísla počínaje 1234 dostaneme , kde vezmeme prostřední 4 číslice (v případě potřeby přidáme na začátek nulu). Poté výsledné číslo odmocníme a tak dále. Nevýhodou této metody je omezená množina PSCH kvůli skutečnosti, že sekvence zacyklí - . $1234^{2}=1522756$ $01{\overline {5227}}56$ $5227^{2}=27{\overline {3215}}29$ $5000^{2}=25{\overline {0000}}00,0^{2}=0,\tečky$

V roce 1951 D. G. Lemer navrhl lineární kongruentní metodu , [5] jejíž podstatou je specifikovat posloupnost celých čísel pomocí rekurzivního vzorce kde jsou celá čísla a splňují následující podmínky: . Nevýhodou této metody je závislost na , od , stejně jako skutečnost, že PFC smyčky. $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$

Deterministické PRNG

Algoritmus

Většina deterministických PRNG odpovídá struktuře navržené P. Lecuerem 1994:v roce]1 [ . Obvykle a stav generátoru je dán rekurzivním vzorcem pro . výstupní hodnota generátoru ; je posloupnost pseudonáhodných čísel. Protože je konečný, musí existovat nějaké konečné a takové, že . To znamená, že podmínky a budou splněny pro všechny , protože funkce a jsou deterministické. Ukazuje se tedy, že sekvence je periodická. Období PRNG se nazývá minimální kladné . [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}$ $u_{i+j}=u_{i}$ $f$ $G$ $j$

Nejběžnější jsou lineární kongruenciální metoda , Fibonacciho metoda se zpožděními , posuvný registr s lineární zpětnou vazbou , posuvný registr se zobecněnou zpětnou vazbou .

Z moderních PRNG se také rozšířil „Mersennův vír “ navržený v roce 1997 Matsumotem a Nishimurou . Jeho předností je kolosální perioda (2 19937 −1), rovnoměrné rozdělení v 623 dimenzích (lineární kongruenciální metoda dává víceméně rovnoměrné rozdělení maximálně v 5 dimenzích), rychlé generování náhodných čísel (2-3x rychlejší než standardní PRNG pomocí metody lineární kongruence). Existují však algoritmy, které rozpoznají sekvenci generovanou Mersennovým vírem jako nenáhodnou.

Generátor pseudonáhodných čísel je součástí mnoha moderních procesorů , například RdRand je součástí instrukční sady IA-32. [6]

Variantou PRNG jsou GPSB (PRBG) - generátory pseudonáhodných bitů a také různé proudové šifry .

Seznam generátorů pseudonáhodných čísel

Následuje seznam generátorů, které historicky vynikly na poli generování pseudonáhodných čísel, ať už kvůli svému historickému významu, nebo protože byly inovativním modelem pro své doby. Navíc, přestože se jedná o PRNG, některé z nich mohou být použitelné v oblasti kryptografie.

Algoritmus	Autoři		Odkazy	Popis
střední náměstí	John von Neumman	1946	[7]	PRNG, který je považován za nekvalitní, ale má velký historický význam jako jeden z prvních algoritmů.
Lehmerův generátor / Lineární kongruenciální metoda	D. H. Lehmer	1951	[osm]	Je také známá jako metoda multiplikativních lineárních kongruencí a byla velmi vlivná v této oblasti výzkumu. Je také známá jako lineární kongruenciální metoda, jejíž základ se postupem času zdokonaloval.
Lag Fibonacciho generátor	GJ Mitchell; D. P. Moore	1958	[9]	Velmi vlivný algoritmus ve studiu procesů generování náhodných čísel, který inspiroval další pozdější velké autory jako G. Marsaglia, tvůrce testu kvality náhodných čísel nazvaného „Diehard“.
Posuvný registr s lineární zpětnou vazbou (LFSR) / Tausworthův oscilátor	R. C. Tausworth	1965	[deset]	Generátor, jehož design ovlivnil mnoho dalších následných PRNG. Proto je velmi historicky důležitý. Také známý jako Tausworthův generátor.
Generátor Wichmann & Hill	B.A. Wichmann; D.I. Hill	1982	[jedenáct]	Kombinace tří malých LCG vhodných pro 16bitové procesory. Široce používán v mnoha programech, například byl používán v Excelu 2003 a některých pozdějších verzích pro funkci NÁHČÍSLO v Excelu a byl výchozím generátorem v Pythonu až do verze 2.2.
Pravidlo 30	Wolfram, Stephen	1983	[12]	Generátor založený na celulárních automatech.
Blum-Blum-Shub generátor	Bloom, Manuel ; L. Blum; M. Shub	1986	[13]	Je považován za jeden z nejbezpečnějších generátorů z kryptografického hlediska, především díky začlenění výzkumu a konceptů převzatých z teorie čísel do jeho vzorce. Za tento Blumův algoritmus byl Manuel oceněn v roce 1995 cenou Alana Turinga.
generátor park-miller	SK Park; KW Miller	1988	[čtrnáct]	Konkrétní implementace generátoru Lehmer, široce používaný, protože je součástí C++ jako funkce minstd_rand0 od C++11.
ŽALUD	RS Wikramaratna	1989	[patnáct]	Jeho název pochází z anglické zkratky ACORN, což znamená ″Additive Congruent Random Number″.
MIXMAX	GK Savvidy; NG Ter-Arutyunyan-Savvidy	1991	[16]	Jedná se o generátor patřící do třídy maticových kongruentních lineárních generátorů, zobecnění metody lineárních kongruencí. Logika generátorů rodiny MIXMAX je založena na výsledcích ergodické teorie a klasické mechaniky.
Add-with-carry	G. Marsaglia	1991	[17]	Úprava Fibonacciho generátorů se zpožděním.
Odečíst-s-půjčit	G. Marsaglia; A. Zaman	1991	[17]	Algoritmus odvozený z Fibonacciho generátorů se zpožděním.
ISAAC	RJ Jenkins Jr.	1993	[osmnáct]	Cryptographically Secure Cryptographic Data Generator (CSPRNG) vyvinutý Robertem J. Jenkinsem.
Mersenne Twister, MT	M. Matsumoto; T. Nishimura	1996	[19]	Toto je pravděpodobně nejznámější generátor na tomto seznamu, hlavně proto, že se jedná o algoritmus implementovaný ve funkci RAND programovacích jazyků Python a R, kromě jeho silného zastoupení v elektronických hrách, jako je Pro Evolution Soccer (PES).
Xorshift	G. Marsaglia	2003	[dvacet]	Jedná se o velmi rychlý podtyp generátorů LFSR. Marsaglia také navrhl jako vylepšení generátor xorwow, ve kterém je výstup generátoru xorshift sečten s Weylovou sekvencí. Generátor xorwow je výchozím generátorem v knihovně nVidia CUDA API CURAND pro GPU.
Algoritmus Fortuna	Schneier, Bruce ; Nils Ferguson	2003	[21]	Algoritmus je považován za kryptograficky bezpečný. CSPRNG, dobře známý tím, že je zabudován do systémů a produktů Apple.
Dobře ekvidistribuovaná dlouhodobá lineární (WELL)	F. Panneton; P. L'Ecuyer; M. Matsumoto	2006	[22]	Algoritmus známý jako doplněk k Mersenne Twister (MT), který se záměrně snaží skrýt své slabiny.
Advanced Randomization System (ARS)	J. Salmon; M. Moraes; R. Dror; D. Shaw	2011	[23]	Zjednodušená verze blokové šifry AES, která poskytuje velmi vysoký výkon na systému s podporou AES-NI.
Threefry	J. Salmon, M. Moraes, R. Dror a D. Shaw	2011	[23]	Zjednodušená verze blokové šifry Threefish vhodná pro implementaci GPU.
Philox (Philox)	J. Salmon, M. Moraes, R. Dror a D. Shaw	2011	[23]	Zjednodušení a úprava blokové šifry Threefish s přidáním S-boxu.
Permutovaný kongruenciální generátor (PCG)	M.E. O'Neill	2014	[24]	Model získaný pomocí lineární kongruenciální metody.
Generátor bitů náhodných cyklů (RCB)	R. Cookman	2016	[25]	RCB je popsán jako generátor bitových vzorů navržený k překonání některých nedostatků Mersenne Twist (MT) a omezení krátké periody/bitové délky u generátorů posunu/modulu.
Middle Square Weyl Sequence RNG	B. Widynski	2017	[26]	Variace na původní metodu středních čtverců Johna von Neumanna.
Xoroshiro128+	D. Blackman; S. Vigna	2018	[27]	Úprava generátoru Xorshift G. Marsaglia, jednoho z nejrychlejších generátorů na moderních 64bitových procesorech. Související generátory jsou xoroshiro128, xoshiro256+ a xoshiro256*.
64bitový MELG (MELG-64)	S. Harase; T. Kimoto	2018	[28]	Implementace 64bitových lineárních F2 generátorů s primární periodou Mersenne.
Čtverce RNG	B. Widynski	2020	[29]	Verze Middle Square Weyl Sequence RNG založená na pultech. Designově podobný Philoxu, ale mnohem rychlejší.
itamaraca (Ita)	D.H. Pereira	2021	[třicet]	Známý jako první algoritmus PRNG založený na funkci absolutní hodnoty. Itamaracá je také jednoduchý a rychlý model, který generuje aperiodické sekvence náhodných čísel.

Poznámkový blok na jedno použití

Alternativním řešením je vytvořit sadu velkého počtu náhodných čísel a publikovat ji v nějakém slovníku , který se nazývá " jednorázový blok ". I takové sady však poskytují velmi omezený zdroj čísel ve srovnání s počtem požadovaným aplikacemi pro zabezpečení sítě. I když tyto sady poskytují statistickou náhodnost, nejsou dostatečně bezpečné, protože útočník by mohl získat kopii slovníku.

Nevýhody PRNG

Žádný deterministický algoritmus nemůže generovat zcela náhodná čísla, může pouze aproximovat některé jejich vlastnosti. Jak řekl John von Neumann : " Každý, kdo má slabost pro aritmetické metody získávání náhodných čísel, je bezpochyby hříšník ."

Jakékoli PRNG s omezenými zdroji se dříve nebo později zasekne – začne opakovat stejnou sekvenci čísel. Délka PRNG cyklů závisí na samotném generátoru a je asi , kde je velikost vnitřního stavu v bitech, ačkoli lineární kongruentní a LFSR generátory mají maximální cykly řádu [31] . Pokud vygenerovaná sekvence PRNG konverguje k příliš krátkým cyklům, pak se takový PRNG stává předvídatelným a nevhodným pro praktické aplikace. $2^{\frac {n}{2}}$ $n$ $2^{n}$

Většina jednoduchých aritmetických generátorů, i když je rychlá, trpí mnoha vážnými nedostatky:

Příliš krátké období/období.
Po sobě jdoucí hodnoty nejsou nezávislé.
Některé bity jsou „méně náhodné“ než jiné.
Nerovnoměrné jednorozměrné rozdělení.
Reverzibilita.

Zejména algoritmus RANDU , který se používá na sálových počítačích po desetiletí , se ukázal jako velmi špatný [32] [33] , což vyvolává pochybnosti o spolehlivosti výsledků mnoha studií používajících tento algoritmus.

PRNG se zdrojem entropie nebo RNG

Spolu s potřebou generovat snadno reprodukovatelné sekvence náhodných čísel existuje také potřeba generovat zcela nepředvídatelná nebo jednoduše zcela náhodná čísla. Takové generátory se nazývají generátory náhodných čísel (RNG - anglicky random number generator, RNG ). Protože se takové generátory nejčastěji používají ke generování jedinečných symetrických a asymetrických klíčů pro šifrování, jsou nejčastěji sestaveny z kombinace kryptograficky silného PRNG a externího zdroje entropie (a tato kombinace je nyní běžně chápána jako RNG).

Téměř všichni hlavní výrobci mikročipů dodávají hardwarové RNG s různými zdroji entropie a používají různé metody, aby je očistili od nevyhnutelné předvídatelnosti. V současné době však rychlost sběru náhodných čísel všemi existujícími mikročipy (několik tisíc bitů za sekundu) neodpovídá rychlosti moderních procesorů.

V moderním výzkumu se objevují pokusy využít měření fyzikálních vlastností objektů (například teploty ) nebo dokonce kvantových fluktuací vakua jako zdroje entropie pro RNG. [34]

V osobních počítačích používají autoři softwaru RNG mnohem rychlejší zdroje entropie, jako je šum zvukové karty nebo počítadlo hodin procesoru . Sběr entropie byl nejzranitelnějším bodem RNG. Tento problém stále není plně vyřešen v mnoha zařízeních (jako jsou čipové karty ), která zůstávají tímto způsobem zranitelná. [35] Mnoho RNG používá tradiční osvědčené, i když pomalé, metody sběru entropie, jako je měření odezvy uživatele ( pohyb myši atd.), jako v PGP a Yarrow [36] , nebo interakce mezi vlákny , jako je , v Java SecureRandom.

Příklad jednoduchého RNG se zdrojem entropie

Pokud je jako zdroj entropie použit aktuální čas, pak pro získání celého čísla od 0 do N stačí vypočítat zbytek dělení aktuálního času v milisekundách číslem N +1. Nevýhodou tohoto RNG je, že produkuje stejné číslo po dobu jedné milisekundy.

Příklady zdrojů RNG a entropie

	Zdroj entropie	PRNG	Výhody	Nedostatky
/dev/random na UNIX / Linux	Čítač hodin procesoru se však shromažďuje pouze během hardwarových přerušení	LFSR s výstupním hashováním přes SHA-1	Dostupné na všech Unixech, spolehlivý zdroj entropie	Velmi dlouho se „zahřívá“, může se „zaseknout“ na dlouhou dobu nebo funguje jako PRNG ( / dev / urandom )
Řebříček od Bruce Schneiera [36]	Tradiční metody	Malý vnitřní stav AES -256 a SHA-1	Flexibilní design odolný vůči kryptoměnám	Pomalý
Microsoft CryptoAPI	Aktuální čas, velikost pevného disku, volná paměť, číslo procesu a název NETBIOS počítače	MD5 hash vnitřního stavu, velikost 128 bitů	Vestavěný ve Windows, nezasekává se	Silně závisí na použitém poskytovateli kryptografie (CSP).
Java SecureRandom	Komunikace mezi vlákny	SHA-1 – interní stavová hash (1024 bitů)	Skvělý vnitřní stav	Sběr pomalé entropie
RdRand od intel [37]	Hlukové proudy	Konstrukce PFS založená na „náhodném“ bitovém čtení hodnot z proudů [37]	Velmi rychlé, nezasekává se	Původní zástavba, vlastnosti jsou dány pouze dle souhlasu developerů.

PRNG v kryptografii

Jedním z kritérií, že PRNG je kryptograficky silný, je neschopnost rozlišit výstupní hodnoty PRNG od nezávislé náhodné sekvence rovnoměrně rozložené v intervalu. Nechť existuje rodina PRNG , kde mohutnost množiny je rovna . Jak bylo uvedeno výše, je konečná množina stavů, je rozdělení pravděpodobnosti ve stavovém prostoru používané k výběru počátečního stavu (anglicky seed), je přechodová funkce, je prostor výstupních hodnot, . Obvykle a stav generátoru je dán rekurzivním vzorcem pro . výstupní hodnota generátoru ; je posloupnost pseudonáhodných čísel. Předpokládejme, že přechodové a výstupní funkce lze vypočítat v polynomiálním čase, mocniny . Nechť je třída statistických testů , které se v polynomiálním čase snaží odlišit výstupní hodnoty PRNG od nezávislé náhodné sekvence rovnoměrně rozložené v intervalu . Rodina PRNG se nazývá dobrá z hlediska polynomiálního času , pokud existuje taková, že žádný z testů nemůže rozlišit výstupní hodnoty PRNG od nezávislé náhodné sekvence rovnoměrně rozložené v intervalu s pravděpodobností . [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)$ $1/2+e^{-k\epsilon }$

Kryptografické aplikace používají ke generování náhodných čísel deterministické algoritmy, a proto generují posloupnost čísel, která teoreticky nemohou být statisticky náhodná. Zároveň, pokud zvolíte dobrý algoritmus, výsledná číselná posloupnost – pseudonáhodná čísla – projde většinou testů na náhodnost. Jednou z charakteristik takové sekvence je dlouhá doba opakování. [3]

Příklady dobře známých kryptograficky silných PRNG jsou RC4 [31] , ISAAC [38] , SEAL [39] , SNOW [40] , velmi pomalý teoretický Blum-Blum-Shub algoritmus [31] a také čítače s kryptografickým hashem funkce nebo kryptograficky zabezpečené blokové šifry místo výstupní funkce [31] .

Mezi kryptograficky silné šifry také patří generátory s více posuvnými registry , generátory s nelineární transformací a generátory většinového šifrování A5/x . [31]

Příklady PRNG odolných vůči kryptoměnám

Round-robin šifrování

Generátor náhodných čísel je zašifrován pomocí různých tajných klíčů získaných v každé fázi. Čítač s dlouhou periodou se používá jako vstup do šifrovacího zařízení. Při použití 56bitového klíče DES lze použít čítač s tečkou . $X_{i}$ $N$ $2^{56}$

Při inicializaci se vygeneruje tajný klíč a konstanta . musí být náhodné a použít pouze pro tento generátor. $K$ $C$ $K$
V každé fázi se děje následující:

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

C=C+1

Pseudonáhodná sekvence získaná tímto schématem má celou periodu: každá výstupní hodnota , , … je založena na jiné hodnotě čítače, proto . Protože klíč je tajný, žádný tajný klíč nezávisí na znalosti jednoho nebo více předchozích tajných klíčů. Pro zvýšení šifrovací síly algoritmu je nutné v každém kroku zašifrovat náhodné číslo pomocí 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$ je klíč používaný v každé fázi.
$E_{K}$ - funkce šifrování klíče . $K$
$R_{i}$ - náhodné číslo s RNG.

ANSI X9.17

PRNG ze standardu ANSI X9.17 se používá v mnoha aplikacích finančního zabezpečení a PGP . Srdcem tohoto PRNG je trojité DES . Generátor ANSI X9.17 se skládá z následujících částí:

V okamžiku inicializace je vygenerován tajný klíč . Musí být náhodný a používá se pouze pro tento generátor. $K$
V každé fázi se děje následující:

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))$ — hodnota data a času na začátku tý fáze generování. $i$
$V_{i}$ je počáteční hodnota pro -tou fázi generování. $i$
$R_{i}$ je pseudonáhodné číslo vytvořené v té fázi generování. $i$
$K$ je klíč používaný v každé fázi.
$E_{K}$ - funkce šifrování klíče . $K$

Vstupní náhodné hodnoty jsou a . je výstupní hodnota. Výpočet bez znalosti není možný v rozumném čase, a tedy další pseudonáhodná hodnota , protože k získání jsou provedeny tři další šifrovací operace. [42] ${\displaystyle D_{i))$ $V_{i}$ $R_{i}$ $V_{i+1}$ $R_{i}$ $K$ $R_{i+1}$ $V_{i+1}$

Hardwarové PRNG

Kromě zastaralých, dobře známých generátorů LFSR, které byly široce používány jako hardwarové PRNG ve 20. století, je o moderních hardwarových PRNG známo jen velmi málo, protože většina z nich je vyvinuta pro vojenské účely nebo je patentována a udržována v tajnosti . Hardwarové generátory RLOS Toyocrypt a LILI-128 byly hacknuty pomocí algebraických útoků [43] [44] .

V současné době je známo použití hardwarových PRNG implementovaných na bázi nízkovýkonového šumu v elektrických obvodech. [45]

Aplikace PRNG v loteriích

Generátor náhodných čísel pro loterie je hardwarově-softwarový komplex používaný v loteriích, ve kterých je nutné uhodnout kombinaci určitého počtu čísel. Každé z možných čísel má stejnou pravděpodobnost výskytu.

Pokusy o vytvoření generátoru náhodných čísel se datují do roku 3500 před naším letopočtem. E. a jsou spojeny se staroegyptskou stolní hrou Senet . V Senetu hrají dva hráči na dvě strany. Tahy se určují pomocí 4 plochých tyčinek, které lze považovat za generátor náhodných čísel té doby. Hoďte všechny čtyři klacky najednou. Bodování je následující: 1 hůl spadla bílou stranou nahoru – 1 bod a další hod; 2 - 2 body; 3 - 3 body, 4 - 4 a hod navíc. Jedna ze stran hole je černá a pokud všechny čtyři hole spadnou černou stranou nahoru, je to maximální výsledek - 5 bodů a dodatečný hod.

Známý generátor náhodných čísel ERNIE se již řadu let používá k určování výherních čísel britské loterie.

Hlavní požadavky na software a vybavení používané k provádění loterií v Ruské federaci jsou stanoveny federálním zákonem č. 138-FZ ze dne 11. listopadu 2003 „o loteriích“:

Technické vlastnosti loterijního zařízení musí zajistit nahodilost rozdělení výher při losování cenového fondu losovacích loterií.
Neměly by se používat postupy, které implementují algoritmy, které by umožnily předem určit výsledek losování cenového fondu před začátkem takového losování.
Loterijní zařízení používané při losování musí zajistit ochranu informací před ztrátou, odcizením, zkreslením, neoprávněným jednáním směřujícím k jejich zničení, pozměňováním, kopírováním a jiným podobným jednáním a neoprávněným přístupem prostřednictvím sítě přenosu dat. [46]

V ruských státních loteriích (Gosloto 5 z 36, Gosloto 6 ze 36, Gosloto 6 ze 45, Gosloto 7 ze 49, Gosloto 4 z 20, "Sportloto" 6 ze 49 "") [47] sebe- nakládací loterijní bubny se používají k určení vítězů . Losování je vysíláno živě. [48]

V ruských státních loteriích ("Rapido", "Keno-Sportloto", "Top-3", "12/24", "Vše za sto") se k určení výherců používá generátor náhodných čísel - hardware a software systém certifikovaný ANO "MIC" a splňující doporučení FSUE VNIIMS . Zařízení generuje nepřetržitý proud náhodného šumu, který se převádí na čísla. V daném okamžiku jsou ze streamu staženy aktuální hodnoty, které jsou výherní loterijní kombinací. [49]

V roce 2015 byl bývalý bezpečnostní ředitel US Multi-State Lottery Association poté, co vyhrál 16,5 milionu dolarů, který měl přístup k softwaru používanému při losování loterií, obviněn z používání speciálních algoritmů k určení vítězné loterijní kombinace na několik dní v roce. [padesáti]

Viz také

Poznámky

↑ N.G. Bardis, A. P. Markovskyi, N. Doukas, N. V. Karadimas. Generování skutečných náhodných čísel na základě měření environmentálního hluku pro vojenské aplikace // Sborník příspěvků z 8. mezinárodní konference WSEAS o ZPRACOVÁNÍ SIGNÁLU, ROBOTICE a AUTOMATIZACE. - 2009. - S. 68-73 . - ISBN 978-960-474-054-3 . — ISSN 1790-5117 . Archivováno z originálu 30. srpna 2017.
↑ Random.org . Datum přístupu: 19. listopadu 2017. Archivováno z originálu 24. února 2011. (neurčitý)
↑ 1 2 3 4 5 6 L'Ecuyer, Pierre. Generování náhodných čísel // Springer Handbooks of Computational Statistics : Kapitola. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 . Archivováno z originálu 1. prosince 2017.
↑ Von Neumann, John. Různé techniky používané ve spojení s náhodnými číslicemi // National Bureau of Standards Applied Mathematics Series. - 1951. - č. 12 . - S. 36-38 . Archivováno z originálu 6. listopadu 2020.
↑ Lehmer, D. H. Mathematical Methods in Large-Scale Computing Units // Ann, Computing Lab. Harvardská univerzita - 1951. - Sv. 26. - S. 141-146 . (nedostupný odkaz)
↑ Intel Digital Random Number Generator (DRNG): Software Implementation Guide, Revize 1.1 (PDF). Intel Corporation (7. srpna 2012). Získáno 25. listopadu 2012. Archivováno z originálu 18. května 2013. (neurčitý)
↑ Národní úřad pro standardy. Výroční zpráva 1951 National Bureau of Standards .
↑ JH Curtiss. Symposium velkých digitálních počítacích strojů // Matematické tabulky a další pomůcky pro výpočty. - 1947-04. - T. 2 , ne. 18 . - S. 229 . - doi : 10.2307/2002294 . Archivováno 11. května 2022.
↑ JW klíč. Table errata: The art of computer programming, sv. 2: Seminumerické algoritmy (Addison-Wesley, Reading, Mass., 1969) od Donalda E. Knutha // Mathematics of Computation. - 1970. - Sv. 24 , iss. 110 . — S. 504 . — ISSN 1088-6842 0025-5718, 1088-6842 . - doi : 10.1090/S0025-5718-1970-0400642-2 .
↑ Robert C. Tausworth. Náhodná čísla generovaná lineárním opakováním modulo dva // Matematika počítání. - 1965. - Sv. 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. Algoritmus AS 183: Efektivní a přenosný generátor pseudonáhodných čísel // Journal of the Royal Statistical Society. Řada C (Aplikovaná statistika). - 1982. - T. 31 , no. 2 . — S. 188–190 . — ISSN 0035-9254 . - doi : 10.2307/2347988 . Archivováno 11. května 2022.
↑ Stephen Wolfram. Statistická mechanika celulárních automatů // Recenze moderní fyziky. — 1983-07-01. - T. 55 , č.p. 3 . — S. 601–644 . - doi : 10.1103/RevModPhys.55.601 .
↑ L. Blum, M. Blum, M. Shub. Jednoduchý nepředvídatelný generátor pseudonáhodných čísel // SIAM Journal on Computing. - 1986-05-01. - T. 15 , č.p. 2 . — S. 364–383 . — ISSN 0097-5397 . - doi : 10.1137/0215025 . Archivováno z originálu 27. dubna 2022.
↑ SK Park, KW Miller. Generátory náhodných čísel: ty dobré se těžko hledají // Komunikace ACM. — 10.10.1988. - T. 31 , č.p. 10 . - S. 1192-1201 . — ISSN 0001-0782 . - doi : 10.1145/63039.63042 .
↑ RS Wikramaratna. ACORN—Nová metoda pro generování sekvencí rovnoměrně distribuovaných pseudonáhodných čísel // Journal of Computational Physics. — 1989-07. - T. 83 , č.p. 1 . — S. 16–31 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(89)90221-0 .
↑ G. K. Savvidy, N. G. Ter-Arutyunyan-Savvidy. O simulaci fyzikálních systémů v Monte Carlu (anglicky) // Journal of Computational Physics. - 12.12.1991. — Sv. 97 , iss. 2 . — S. 566–572 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(91)90015-D . Archivováno 11. května 2022.
↑ 1 2 George Marsaglia, Arif Zaman. Nová třída generátorů náhodných čísel // The Annals of Applied Probability. — 1991-08. - T. 1 , ne. 3 . — S. 462–480 . — ISSN 2168-8737 1050-5164, 2168-8737 . - doi : 10.1214/aoap/1177005878 . Archivováno z originálu 19. dubna 2022.
↑ ISAAC, rychlý kryptografický generátor náhodných čísel . www.burtleburtle.net . Staženo: 17. května 2022. (neurčitý)
↑ Makoto Matsumoto, Takuji Nishimura. Mersenne twister: 623-dimenzionálně rovnoměrně distribuovaný generátor pseudonáhodných čísel // ACM Transactions on Modeling and Computer Simulation. — 1998-01-01. - T. 8 , ne. 1 . — S. 3–30 . — ISSN 1049-3301 . doi : 10.1145 / 272991.272995 .
↑ George Marsaglia. Xorshift RNGs // Journal of Statistical Software. - 04.07.2003. — Sv. 8 . — S. 1–6 . — ISSN 1548-7660 . - doi : 10.18637/jss.v008.i14 .
↑ Knižní zdroje - Wikipedie . en.wikipedia.org . Získáno 17. května 2022. Archivováno z originálu dne 24. dubna 2022. (Ruština)
↑ François Panneton, Pierre L'Ecuyer, Makoto Matsumoto. Vylepšené generátory dlouhého období založené na lineárních opakováních modulo 2 // ACM Transactions on Mathematical Software. — 2006-03-01. - T. 32 , č.p. 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. Paralelní náhodná čísla: stejně snadné jako 1, 2, 3 // Sborník z mezinárodní konference 2011 pro vysoce výkonné výpočty, sítě, úložiště a analýzu. — 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. Zrychlení hardwarového generování gaussovských náhodných čísel pomocí algoritmů Ziggurat a CORDIC // 2014 IEEE SENSORS. — 2014-11. — S. 2122–2125 . - doi : 10.1109/ICSENS.2014.6985457 . Archivováno z originálu 17. května 2022.
↑ Generátor náhodných bitů // SpringerReference. — Berlín/Heidelberg: Springer-Verlag.
↑ Bernard Widynski. Middle-Square Weyl Sequence RNG // arXiv:1704.00358 [cs]. — 20. 3. 2022. Archivováno z originálu 17. května 2022.
↑ David Blackman, Sebastiano Vigna. Generátory kódovaných lineárních pseudonáhodných čísel // arXiv:1805.01407[cs]. — 28. 3. 2022. Archivováno 11. května 2022.
↑ Shin Harase, Takamitsu Kimoto. Implementace 64bitových maximálně ekvidistribuovaných F2-lineárních generátorů s Mersenne Prime Period // ACM transakce na matematickém softwaru. — 2018-01-03. - T. 44 , č.p. 3 . — S. 30:1–30:11 . — ISSN 0098-3500 . - doi : 10.1145/3159444 .
↑ Bernard Widynski. Čtverce: A Fast Counter-Based RNG // arXiv:2004.06278 [cs]. — 2022-03-13. Archivováno 11. května 2022.
↑ Daniel Henrique Pereira. Itamaracá: Nový jednoduchý způsob generování pseudonáhodných čísel (anglicky) . — 25. 1. 2022. - doi : 10.33774/coe-2022-zsw6t . Archivováno z originálu 27. dubna 2022.
↑ 1 2 3 4 5 Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Informační bezpečnost. Studijní příručka . - S. 100-113. Archivováno 24. listopadu 2020 na Wayback Machine
↑ Donald Knuth . Kapitola 3.3. Spektrální kritérium // Umění programování. Dekret. op. - S. 129-130.
↑ William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numerické recepty v C: The Art of Scientific Computing. — 2. vyd. - Cambridge University Press, 1992. - S. 277. - ISBN 0-521-43108-5 .
↑ Náhodná čísla získaná z kvantového vakua . Získáno 18. dubna 2012. Archivováno z originálu 19. dubna 2012. (neurčitý)
↑ Jovan DJ. Goli c. Cryptanalytic Attacks on MIFARE Classic Protocol // Topics in Cryptology - CT-RSA 2013. - Springer, Berlin, Heidelberg, 2013. - No. 7779 . - S. 239-259 . - doi : 10.1007/978-3-642-36095-4_16 .
↑ Řebříček 12. _ _ Získáno 10. září 2004. Archivováno z originálu 8. listopadu 2012. (neurčitý)
↑ 1 2 Příručka pro implementaci softwaru Intel DRNG . Intel . Získáno 8. prosince 2017. Archivováno z originálu dne 21. dubna 2016. (neurčitý)
↑ J.-P. Aumasson. Na pseudonáhodném generátoru ISAAC // Cryptology ePrint Archive. - 2006. Archivováno 8. září 2016.
↑ H. Chen, K. Laine, R. Player. [ https://eprint.iacr.org/2017/224.pdf Jednoduchá šifrovaná aritmetická knihovna – SEAL v2.1] // Archiv kryptologie ePrint. - 2017. Archivováno 10. července 2017.
↑ A. Kircanski a 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. - č. 5(4) . - S. 199-206 . Archivováno z originálu 16. prosince 2017.
↑ Laponina O. R. Symetrické šifrovací algoritmy . POZNAT INTUIT . Získáno 8. prosince 2017. Archivováno z originálu 9. prosince 2017. (neurčitý)
↑ Kelsey J., Schneier B., Wagner D., hala C. Kryptanalytické útoky na generátory pseudonáhodných čísel // Rychlé softwarové šifrování. FSE 1998. Poznámky k přednáškám z informatiky. - Springer, Berlín, Heidelberg, 1998. - Sv. 1372. - doi : 10.1007/3-540-69710-1_12 . Archivováno z originálu 7. prosince 2017.
↑ N. T. Courtois. Korelační útoky vyššího řádu, XL algoritmus a kryptoanalýza Toyocryptu // Archiv kryptologie ePrint. - 2002. Archivováno 29. března 2017.
↑ Ed Dawson, Andrew Clark, J Golic, W Millan, L Penna. Generátor Keystream LILI-128 . — 2000-12-13. Archivováno z originálu 16. prosince 2017.
↑ C. S. Petrie, J. A. Connelly. Generátor náhodných čísel integrovaných obvodů založený na šumu pro aplikace v kryptografii // IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications. - Květen 2000. - Sv. 47, č. 5 . — S. 615–621 . — ISSN 1057-7122 . doi : 10.1109 / 81.847868 .
↑ Článek 12.1. Požadavky na loterijní zařízení a loterijní terminály . Získáno 6. prosince 2017. Archivováno z originálu 6. prosince 2017. (neurčitý)
↑ Odpovědi na otázky o Stoloto . Sto lotto . Získáno 6. prosince 2017. Archivováno z originálu 6. prosince 2017. (neurčitý)
↑ Přenosy losování státní loterie . Sto lotto . Získáno 6. prosince 2017. Archivováno z originálu 6. prosince 2017. (neurčitý)
↑ Generátor náhodných čísel . Sto lotto . Získáno 6. prosince 2017. Archivováno z originálu 6. prosince 2017. (neurčitý)
↑ Muž hacknul generátor náhodných čísel, aby zmanipuloval loterie, říkají vyšetřovatelé , The Guardian . Archivováno z originálu 23. prosince 2017. Staženo 6. prosince 2017.

Literatura

Donald E. Knuth . Kapitola 3. Náhodná čísla // Umění počítačového programování. - 3. vyd. - M .: Williams , 2000. - V. 2. Získané algoritmy. — 832 s. - 7000 výtisků. - ISBN 5-8459-0081-6 (ruština) ISBN 0-201-89684-2 (anglicky).
Kelton W., Lowe A. Simulační modelování. CS klasika. - 3. vyd. - Petrohrad. : Peter, 2004. - S. 465, 466. - 487 s. — ISBN 0070592926 . — ISBN 5-94723-981-7 .
L'Ecuyer, Pierre. Generování náhodných čísel // Springer Handbooks of Computational Statistics : Kapitola. - 2007. - S. 93-137 . - doi : 10.1002/9780470172445.ch4 .

Odkazy

V. A. Uspenský. Čtyři algoritmické tváře náhodnosti . - MTSNMO , 2006. - 48 s. — ISBN 978-5-94057-485-9 .
Yuri Lifshits. Přednáška 9: Pseudonáhodné generátory // Moderní problémy kryptografie . - Přednáškový kurz.
L. Barash. Algoritmus AKS pro jednoduchost kontroly čísel a hledání konstant generátorů pseudonáhodných čísel // Bezpečnost informačních technologií. - 2005. - č. 2 . - S. 27-38 . Archivováno z originálu 18. října 2014.
Zhelnikov V. Pseudonáhodné posloupnosti čísel // Kryptografie od papyru k počítači . - M. : ABF, 1996. - 335 s. - ISBN 5-87484-054-0 .
Kryptografická náhodná čísla
Teorie a praxe generování náhodných čísel
Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analýza linuxového generátoru náhodných čísel
Sada statistických testů pro generátory náhodných a pseudonáhodných čísel pro kryptografické aplikace NIST SP 800-22