Získavanie a konverzia náhodných čísel.

Existujú dva hlavné spôsoby, ako získať náhodné čísla:

1) Náhodné čísla generuje špeciálna elektronická príloha (senzor náhodných čísel) nainštalovaná v počítači. Implementácia tejto metódy nevyžaduje takmer žiadne ďalšie operácie okrem prístupu k senzoru náhodných čísel.

2) Algoritmická metóda - založená na generovaní náhodných čísel v samotnom stroji pomocou špeciálneho programu. Nevýhodou tohto spôsobu je dodatočná spotreba počítačového času, keďže v tomto prípade stroj sám vykonáva operácie elektronického set-top boxu.

Program na generovanie náhodných čísel pomocou daného distribučného zákona môže byť ťažkopádny. Náhodné čísla s daným zákonom rozdelenia sa preto zvyčajne získavajú nie priamo, ale transformáciou náhodných čísel, ktoré majú nejaké štandardné rozdelenie. Toto štandardné rozdelenie je často rovnomerné (ľahko dostupné a ľahko premeniteľné na iné zákony).

Najvýhodnejšie je získať náhodné čísla s jednotným zákonom pomocou elektronického set-top boxu, ktorý oslobodí počítač od dodatočné náklady strojový čas. Získanie čisto rovnomernej distribúcie na počítači je nemožné kvôli obmedzenej povahe bitovej mriežky. Preto sa namiesto súvislej množiny čísel na intervale (0, 1) používa diskrétna množina čísel 2nčísla, kde n– bitová hĺbka strojového slova.

Zákon rozdelenia takejto populácie je tzv kvázi uniforma . Pri n³20 sa rozdiely medzi jednotnými a kvázi-jednotnými zákonmi stávajú bezvýznamnými.

Na získanie kvázi-jednotných náhodných čísel sa používajú 2 metódy:

1) generovanie náhodných čísel pomocou elektronického set-top boxu modelovaním niektorých náhodných procesov;

2) získanie pseudonáhodných čísel pomocou špeciálnych algoritmov.

Na získanie n-ciferné binárne náhodné číslo, prvá metóda simuluje postupnosť nezávislých náhodných premenných z i, pričom má hodnotu 0 alebo 1. Výsledná postupnosť je 0 a 1, ak ju považujeme za zlomkové číslo, a predstavuje náhodnú premennú kvázi rovnomerného rozdelenia na intervale (0, 1). Hardvérové ​​metódy na získanie týchto čísel sa líšia iba spôsobom, akým získavajú implementáciu z i.

Jedna z metód je založená na počítaní počtu rádioaktívnych častíc za určité časové obdobie Dt, ak je počet častíc väčší Dt aj vtedy z i=1 , a ak nepárne, potom z i=0 .

Iná metóda využíva šumový efekt vákuovej trubice. Zaznamenávaním hodnoty šumového napätia v určitých časových bodoch t i, získame hodnoty nezávislých náhodných premenných U(t i), t.j. napätie (Volty).

Rozsah z i určuje zákon:

Kde a– určitá hodnota prahového napätia.

Rozsah a zvyčajne sa vyberá z podmienok:

Chyba hardvérová metóda spočíva v tom, že neumožňuje použitie metódy dvojitého spustenia na riadenie činnosti algoritmu na riešenie akéhokoľvek problému, pretože opakovaným spustením sa nezískajú rovnaké náhodné čísla.

Pseudonáhodné volacie čísla vygenerované na počítači pomocou špeciálne programy rekurentná metóda: každé náhodné číslo sa získa z predchádzajúceho pomocou špeciálnych transformácií.

Najjednoduchšia z týchto transformácií je nasledujúca. Nech sú nejaké n– bitové binárne číslo z intervalu nО (0, 1). Urovnajme to a dostaneme 2n ciferné číslo. Vyzdvihnime priemery n výboje. Získané týmto spôsobom n– číselné číslo bude novou hodnotou náhodného čísla. Opäť to štvorčekujeme atď. Táto postupnosť je pseudonáhodná, pretože z teoretického hľadiska nie je náhodný.

Nevýhodou rekurentných algoritmov je, že postupnosti náhodných čísel môžu degenerovať (napríklad dostaneme len nulovú postupnosť alebo postupnosť jednotiek, prípadne sa môže objaviť periodicita).

Deterministické PRNG

Žiadny deterministický algoritmus nemôže generovať úplne náhodné čísla, môže len aproximovať niektoré vlastnosti náhodných čísel. Ako povedal John von Neumann: každý, kto má slabosť pre aritmetické metódy získavania náhodných čísel, je bez akýchkoľvek pochybností hriešny».

Akýkoľvek PRNG s obmedzenými zdrojmi skôr či neskôr prechádza do cyklov – začína opakovať rovnakú postupnosť čísel. Dĺžka cyklov PRNG závisí od samotného generátora a je v priemere asi 2 n/2, kde n je veľkosť vnútorného stavu v bitoch, hoci lineárne kongruentné a LFSR generátory majú maximálne cykly rádovo 2 n. Ak PRNG môže konvergovať k cyklom, ktoré sú príliš krátke, PRNG sa stane predvídateľným a nepoužiteľným.

Väčšina jednoduchých aritmetických generátorov, aj keď je veľmi rýchla, trpí mnohými vážnymi nevýhodami:

• Obdobie/obdobia sú príliš krátke.
• Po sebe idúce hodnoty nie sú nezávislé.
• Niektoré bity sú „menej náhodné“ ako iné.
• Nerovnomerné jednorozmerné rozloženie.
• Reverzibilita.

Najmä algoritmus sálového počítača sa ukázal ako veľmi zlý, čo vyvolalo pochybnosti o platnosti výsledkov mnohých štúdií, ktoré tento algoritmus používali.

PRNG so zdrojom entropie alebo RNG

Rovnako ako je potrebné generovať ľahko opakovateľné sekvencie náhodných čísel, je potrebné generovať aj úplne nepredvídateľné alebo jednoducho úplne náhodné čísla. Takéto generátory sa nazývajú generátory náhodných čísel(RNG - angličtina) generátor náhodných čísel, RNG). Keďže takéto generátory sa najčastejšie používajú na generovanie jedinečných symetrických a asymetrických kľúčov na šifrovanie, sú najčastejšie zostavené z kombinácie kryptograficky silného PRNG a externého zdroja entropie (a práve táto kombinácia sa dnes bežne chápe ako RNG).

Takmer všetci hlavní výrobcovia čipov dodávajú hardvérové ​​RNG rôznych zdrojov pomocou entropie rôzne metódy očistiť ich od nevyhnutnej predvídateľnosti. Avšak, na tento moment rýchlosť, akou všetky existujúce mikročipy zbierajú náhodné čísla (niekoľko tisíc bitov za sekundu), nezodpovedá rýchlosti moderných procesorov.

V osobných počítačoch používajú autori softvérových RNG oveľa rýchlejšie zdroje entropie, ako je hluk zvuková karta alebo počítadlo cyklov procesora. Predtým, ako bolo možné čítať hodnoty počítadla hodín, bolo zhromažďovanie entropie najzraniteľnejším bodom RNG. Tento problém stále nie je úplne vyriešený v mnohých zariadeniach (napr. smart karty), ktoré tak zostávajú zraniteľné. Mnoho RNG stále používa tradičné (zastarané) metódy zhromažďovania entropie, ako je meranie reakcií používateľov (pohyb myši atď.), ako napríklad interakcia medzi vláknami, ako v prípade Java secure random.

Príklady zdrojov RNG a entropie

Niekoľko príkladov RNG s ich zdrojmi entropie a generátormi:

	Zdroj entropie	PRNG	Výhody	Nedostatky
/dev/random v systéme Linux	Počítadlo hodín CPU sa však zhromažďuje iba počas hardvérových prerušení	LFSR, s výstupom hash cez	Veľmi dlho sa „zohrieva“, môže sa „zaseknúť“ na dlhú dobu alebo funguje ako PRNG ( /dev/urandom)
Yarrow od Brucea Schneiera	Tradičné (zastarané) metódy	AES-256 a	Flexibilný dizajn odolný voči kryptomenám	Trvá dlho, kým sa „zahreje“, veľmi malý vnútorný stav, príliš závisí od kryptografickej sily zvolených algoritmov, pomalý, použiteľný výlučne na generovanie kľúčov
Generátor od Leonida Yurieva	Hluk zvukovej karty	?	S najväčšou pravdepodobnosťou dobrý a rýchly zdroj entropie	Žiadny nezávislý, známy krypto-silný PRNG, dostupný výhradne ako Windows
Microsoft		Zabudované do systému Windows, nezasekáva sa	Malý vnútorný stav, ľahko predvídateľný
	Komunikácia medzi vláknami		V Jave zatiaľ nie je na výber, je tam veľký vnútorný stav	Pomalý zber entropie
Chaos od Ruptora	Počítadlo hodín procesora, zbierané nepretržite	Hašovanie 4096-bitového vnútorného stavu založené na nelineárnom variante generátora Marsaglia	Kým sa najrýchlejší zo všetkých, veľký vnútorný stav, „zasekne“
RRAND od spoločnosti Ruptor	Počítadlo hodín procesora	Šifrovanie vnútorného stavu pomocou prúdovej šifry	Veľmi rýchly, vnútorný stav ľubovoľnej veľkosti na výber, žiadne „zaseknutie“

PRNG v kryptografii

Typom PRNG sú PRBG – generátory pseudonáhodných bitov, ako aj rôzne prúdové šifry. PRNG, podobne ako prúdové šifry, pozostávajú z vnútorného stavu (väčšinou s veľkosťou od 16 bitov do niekoľkých megabajtov), ​​funkcie na inicializáciu vnútorného stavu pomocou kľúča resp. semeno(Angličtina) semeno), funkcie aktualizácie vnútorného stavu a výstupné funkcie. PRNG sa delia na jednoduché aritmetické, zlomené kryptografické a kryptografické silné. Ich všeobecným účelom je generovať postupnosti čísel, ktoré nemožno odlíšiť od náhodných výpočtovými metódami.

Hoci mnohé silné PRNG alebo prúdové šifry ponúkajú oveľa viac „náhodných“ čísel, takéto generátory sú oveľa pomalšie ako konvenčné aritmetické generátory a nemusia byť vhodné pre akýkoľvek druh výskumu, ktorý vyžaduje, aby bol procesor voľný na užitočnejšie výpočty.

Na vojenské účely a terénne podmienky Nepoužívajú sa iba tajné synchrónne kryptografické silné PRNG (streamové šifry). Príklady dobre známych krypto-silných PRNG sú ISAAC, SEAL, Snow, veľmi pomalý teoretický algoritmus Bloom, Bloom a Shub, ako aj počítadlá s kryptografickými hašovacími funkciami alebo silnými blokovými šiframi namiesto výstupnej funkcie.

Hardvér PRNG

Odhliadnuc od dedičstva, známych generátorov LFSR, ktoré boli v 20. storočí široko používané ako hardvérové ​​PRNG, je, žiaľ, veľmi málo známe o moderných hardvérových PRNG (streamových šifrách), keďže väčšina z nich bola vyvinutá na vojenské účely a sú držané v tajnosti. . Takmer všetky existujúce komerčné hardvérové ​​PRNG sú patentované a tiež udržiavané v tajnosti. Hardvérové ​​PRNG sú obmedzené prísnymi požiadavkami na spotrebnú pamäť (najčastejšie je používanie pamäte zakázané), rýchlosť (1-2 hodinové cykly) a plochu (niekoľko stoviek FPGA – resp.

Kvôli nedostatku dobrých hardvérových PRNG sú výrobcovia nútení používať oveľa pomalšie, ale dobre známe blokové šifry, ktoré sú k dispozícii (Computer Review No. 29 (2003)).

Yuri Lifshits. Kurz „Moderné problémy kryptografie“ 9. prednáška: Pseudonáhodné generátory

L. Baraš. Algoritmus AKS na kontrolu primality čísel a hľadanie konštánt generátora pseudonáhodných čísel

Vladimír Želnikov. Pseudonáhodné sekvencie čísel // Kryptografia z papyrusu do počítača M.: ABF, 1996.

random.org (anglicky) - online služba na generovanie náhodných čísel

Kryptografické náhodné čísla

Teória a prax generovania náhodných čísel

Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analýza linuxového generátora náhodných čísel

Sada štatistických testov pre generátory náhodných a pseudonáhodných čísel pre kryptografické aplikácie NIST SP 800-22

19.09.2017, ut, 13:18, moskovského času , Text: Valéria Šmyrová

Spoločnosť Security Code, vývojár kryptografického komplexu Continent, získala patent na biologický snímač náhodných čísel. Toto je presne biologický senzor, pretože náhodnosť je založená na reakcii používateľa na zobrazený obrázok. Spoločnosť ubezpečuje, že takéto technológie neboli doteraz vo svete patentované.

Získanie patentu

Spoločnosť Security Code získala patent na technológiu biologických snímačov náhodných čísel. Podľa vývojárov sa pri vytváraní technológie použil „nový prístup k riešeniu problému generovania náhodných čísel pomocou počítača a osoby“. Vývoj sa už používa v mnohých produktoch, vrátane Continent-AP, Secret Net Studio, Continent TLS a Jinn, ako aj v kryptografickej knižnici SCrypt.

Ako pre CNews vysvetlili zástupcovia spoločnosti, na senzore sa pracuje už tri roky. Pozostáva z vedeckej časti, realizačnej časti a experimentálnej časti. Za vedeckú časť firmy sú zodpovední traja ľudia, na vývoji sa podieľal celý tím programátorov, testovanie a experimenty robil celý tím, čo je niekoľko stoviek ľudí.

Technologické schopnosti

Nový senzor dokáže generovať náhodné sekvencie na osobných zariadeniach – nie sú potrebné žiadne ďalšie zariadenia ani hardvérové ​​doplnky. Dá sa použiť pri šifrovaní dát a v akejkoľvek oblasti, kde sú potrebné náhodné binárne sekvencie. Podľa vývojárov pomáha oveľa rýchlejšie vytvárať šifrovacie kľúče na mobilných zariadeniach. Túto vlastnosť možno použiť na šifrovanie údajov alebo generovanie elektronického podpisu.

Ako bolo vysvetlené Alisa Koreneva, systémový analytik „bezpečnostného kódu“, snímač spoločnosti generuje náhodné sekvencie založené na rýchlosti a presnosti reakcie ruky používateľa na zmeny v obraze na obrazovke počítača alebo tabletu. Na zadávanie sa používa myš alebo dotyková obrazovka. Vyzerá to takto: kruhy sa chaoticky pohybujú po obrazovke, niektoré ich parametre sa časom menia. V niektorých momentoch používateľ reaguje na zmeny v obraze. Berúc do úvahy zvláštnosti jeho motorických schopností, odráža sa to v náhodnom množstve bitov.

Môžete generovať sekvencie náhodných čísel na základe spontánnych ľudských reakcií

Mimo kryptografie možno senzor použiť na generovanie náhodných čísel počítačové hry alebo vybrať víťazov súťaže.

Vedecká novinka

Ako spoločnosť vysvetlila pre CNews, mnohí známymi metódami Konštrukcia snímačov náhodných čísel je založená buď na fyzikálnych zákonoch a javoch, alebo na deterministických algoritmoch. Sekvencie je možné generovať pomocou počítača – v tomto prípade sa za základ náhodnosti berie nestabilita niektorých častí počítača a neistota hardvérového rušenia.

Novinka technológie bezpečnostného kódu spočíva v tom, že zdrojom náhodnosti je reakcia človeka na meniaci sa obraz, ktorý sa zobrazuje na displeji zariadenia. Preto názov vynálezu obsahuje slovo „biologický“. Spoločnosť uvádza, že ani ona, ani Rospatent nenašli patentované analógy technológie v Rusku ani vo svete. Vo všeobecnosti sú však takéto techniky známe: napríklad sekvenciu možno generovať na základe akcií používateľa, ako sú kliknutia alebo pohyby myši alebo stlačenia klávesov na klávesnici.

Podľa Koreneva vývojový tím analyzoval rôzne cesty generovanie náhodných sekvencií. Ako sa ukázalo, v mnohých prípadoch neexistujú žiadne rozumné odhady výkonu generovania alebo štatistických vlastností generovaných sekvencií alebo oboch. Je to spôsobené ťažkosťami s odôvodnením už vynájdenej technológie. Bezpečnostný kódex tvrdí, že jeho výskum priniesol rozumné odhady miery generovania, dokázal zdôvodniť dobré pravdepodobnostné charakteristiky a štatistické vlastnosti a odhadol entropiu, ktorú prispeli ľudské činy.

Produkty využívajúce technológiu

„Kontinent“ je hardvér softvérový balík, určený na šifrovanie dát. Používa sa v ruskom verejnom sektore, napríklad v štátnej pokladnici. Pozostáva z firewallu a nástrojov na vytvorenie VPN. Bol vytvorený spoločnosťou NIP Informzashita a teraz je vyvíjaný spoločnosťou Security Code LLC.

Konkrétne prístupový server „Continent“ a informačný kryptografický ochranný systém „Continent-AP“ sú modulom pre bezpečný vzdialený prístup pomocou algoritmov GOST a „Continent TLS VPN“ je systém na poskytovanie bezpečného vzdialeného prístupu k webovým aplikáciám aj pomocou GOST. šifrovacie algoritmy.

Secret Net Studio je komplexné riešenie na ochranu pracovných staníc a serverov na úrovni dát, aplikácií, siete, operačného systému a periférnych zariadení, ktorá tiež vyvíja „Bezpečnostný kódex“. Jinn-Client je určený na ochranu kryptografických informácií na vytváranie elektronického podpisu a dôveryhodnú vizualizáciu dokumentov a Jinn-Server je softvérový a hardvérový komplex na budovanie právne významných systémov správy elektronických dokumentov.

Kryptografická knižnica SCrypt, ktorú tiež používa nový snímač, bol vyvinutý „Bezpečnostným kódom“ pre pohodlnejšie použitie kryptografických algoritmov v rôznych produktoch. Toto je jediný programový kód, ktorý bol skontrolovaný na chyby. Knižnica podporuje kryptografické hašovanie, elektronický podpis a šifrovacie algoritmy.

Čo robí „Bezpečnostný kód“?

"Bezpečnostný kód" je ruská spoločnosť, ktorá vyvíja softvér a hardvér. Bola založená v roku 2008. Náplňou produktu je ochrana informačných systémov a ich uvedenie do súladu s medzinárodnými a priemyselnými štandardmi vrátane ochrany dôverných informácií vrátane štátneho tajomstva. „Bezpečnostný kódex“ má deväť licencií od Federálnej služby pre technickú a exportnú kontrolu (FSTEK) Ruska, Federálnej bezpečnostnej služby (FSB) Ruska a Ministerstva obrany.

Zamestnancov spoločnosti tvorí asi 300 špecialistov, produkty predáva 900 autorizovaných partnerov vo všetkých regiónoch Ruska a krajín SNŠ. Klientská základňa Bezpečnostného kódexu zahŕňa približne 32 tisíc vládnych a komerčných organizácií.

Existujú tri zásadne odlišné spôsoby získavania čísel, ktoré sa používajú ako náhodné: fyzické, tabuľkové a algoritmické.

Predpokladá sa, že prvý pokus o vytvorenie fyzického generátora náhodných čísel pochádza z roku 3500 pred Kristom. a je spojená s stolná hra senet, staroegyptská spoločenská zábava. Podľa moderných rekonštrukcií pravidiel hry sa na určenie počtu bodov každého hráča a poradia ťahov v tejto hre používali štyri ploché palice, z ktorých jedna strana bola biela a druhá strana čierna. Paličky sa hádzali súčasne a podľa vypadnutej kombinácie farieb sa určovali ďalšie možnosti pre hráčov. Na začiatku 20. stor. sekvencie náhodných čísel boli simulované ručne – pomocou hodov mincou resp kocky, odvíjajúci sa hracie karty, ruleta, vyberanie loptičiek z urny a pod. Moderné fyzikálne (hardvérové) snímače sú špeciálne zariadenia, ktoré generujú náhodné čísla na základe prevodu náhodného šumu prirodzeného alebo umelého pôvodu (tepelný šum, efekt výstrelu na vákuové trubice, rádioaktívny rozpad atď.). Napríklad auto ERNIE 4 (zariadenie na elektronický indikátor náhodného čísla),

• 1 Niekedy, aj keď zriedkavo, sa za štandardné považuje rozdelenie uvedené v tabuľke 0 1 ... 8 9
• 0,1 0,1 ... 0,1 0,1/, ktorý určuje výherné čísla v mesačnej britskej lotérii, využíva ako zdroj náhodných veličín tepelný šum tranzistorov. U fyzikálna metóda Získanie postupnosti náhodných čísel má vlastnosti, ktoré sú nevýhodou simulačného modelu. Medzi ne patrí predovšetkým potreba špeciálnych opatrení na zabezpečenie stability zdroja signálu prevedeného na náhodné čísla a nemožnosť reprodukovať výslednú postupnosť náhodných čísel.

Tabuľky s náhodnými číslami sú odstránené spomínané nedostatky. Vysvetlime si, čo znamená tabuľka náhodných čísel. Predpokladajme, že sme implementovali N nezávislých experimentov, v dôsledku ktorých získali náhodné čísla a, a 2, osdg. Zapísaním týchto čísel (v poradí vzhľadu a vo forme obdĺžnikovej tabuľky) získate to, čo sa nazýva tabuľka náhodných čísel. Používa sa nasledovne. Počas výpočtov môžeme potrebovať náhodnú číslicu alebo náhodné číslo. Ak sa vyžaduje náhodné číslo, potom môžeme vziať ľubovoľné číslo z tejto tabuľky. To isté platí pre prípad celočíselného náhodného čísla – pre každú číslicu si môžete zvoliť ľubovoľnú číslicu. Ak potrebujeme náhodné číslo 0 k nasledujúcich číslic сс, a 2 , ос/ a predpokladáme, že 8 = (Hoco^.-.o^. V tomto prípade v prípade „ideálnej“ tabuľky náhodných číslic , môžeme z neho vyberať číslice náhodne, možno za sebou, môžete použiť ľubovoľný algoritmus výberu, ktorý nezávisí od hodnôt čísel v tabuľke, začať od ľubovoľného miesta v tabuľke, čítať v ľubovoľnom smere.

Prvé tabuľky náhodných čísel boli získané pomocou rulety. Takéto tabuľky vyšli niekoľkokrát v knižnej podobe. Jedna z najznámejších tabuliek, publikovaná v roku 1927, obsahovala viac ako 40 000 náhodných čísel „náhodne prevzatých zo správ zo sčítania ľudu“.

Historický odkaz

Leonard Tippett (Leonard Henry Caleb Tippett, 1902-1985) - anglický štatistik, študent K. Pearsona a R. Fishera. V rokoch 1965-1966 - Prezident Kráľovskej štatistickej spoločnosti. S jeho menom sú spojené niektoré dôležité výsledky v teórii extrémnych hodnôt, napríklad Fisher-Tippettovo rozdelenie a Fisher-Tippett-Gnedenkova veta.

Neskôr boli navrhnuté špeciálne zariadenia (stroje), ktoré mechanicky generovali náhodné čísla. Prvý takýto stroj použili v roku 1939 M. J. Kendall a B. Babington-Smith na vytvorenie tabuliek obsahujúcich 100 tisíc náhodných číslic. V roku 1955 spol RAND Corporation zverejnil známe tabuľky obsahujúce milión náhodných číslic získaných iným strojom tohto typu. Praktické využitie tabuľky náhodných čísel sa v súčasnosti obmedzujú spravidla na problémy, pri ktorých sa používajú metódy náhodného výberu

vzorky, napríklad v sociologických štúdiách alebo pri vykonávaní štatistickej akceptačnej kontroly kvality kusových výrobkov na rôzne účely.

Toto je zaujímavé

V Rusku platí GOST 18321-73 (ST SEV 1934-79), ktorým sa ustanovujú pravidlá výberu jednotiek produktov na odber vzoriek pri vykonávaní štatistickej kontroly kvality, štatistických metód analýzy a regulácie. technologických procesov pre všetky druhy kusových výrobkov pre priemyselné a technické účely a spotrebný tovar. Uvádza sa v ňom najmä, že pri výbere jednotiek výrobkov do vzorky sa „používajú tabuľky náhodných čísel podľa ST SEV 546-77“.

aplikovať opakovane; všetky čísla sa dajú ľahko reprodukovať; a ponuka čísel v takomto poradí je obmedzená. Avšak postupnosť pseudonáhodných čísel má zjavná výhoda pred tabuľkou: existovať jednoduché vzorce na výpočet pseudonáhodného čísla, pričom na získanie každého čísla sa minie iba 3-5 príkazov a výpočtový program zaberá len niekoľko buniek v jednotke.

Existuje mnoho algoritmov na získanie sekvencií pseudonáhodných čísel, implementácie takýchto algoritmov, nazývaných senzory (generátory) pseudonáhodných čísel, sú podrobne opísané v odbornej literatúre. Uveďme niekoľko najznámejších algoritmov.

• Tippett L. Náhodné vzorkovacie čísla. Londýn: Cambridge University Press, 1927.
• Pozri: Knuth D. E. The Art of Programming. 3. vyd. M.: Williams, 2000. T. 2. Ch. 3.Náhodné čísla.

Navrhuje sa prístup na skonštruovanie biologického snímača náhodných čísel navrhnutého na generovanie náhodných sekvencií na počítači alebo tablete rýchlosťou niekoľko stoviek bitov za minútu. Tento prístup je založený na výpočte množstva veličín spojených s náhodnou reakciou používateľa na pseudonáhodný proces zobrazený na obrazovke počítača. Pseudonáhodný proces je implementovaný ako vzhľad a krivočiary pohyb kruhov na obrazovke v určitej špecifikovanej oblasti.

Úvod

Význam problémov spojených s generovaním náhodných sekvencií (RS) pre kryptografické aplikácie je spôsobený ich použitím v kryptografických systémoch na generovanie kľúčových a pomocných informácií. Samotný pojem náhodnosti má filozofické korene, čo naznačuje jeho zložitosť. V matematike existujú rôzne prístupy k definovaniu pojmu „náhoda“ a ich prehľad je uvedený napríklad v našom článku „Nie sú nehody náhodné?“ . Informácie o známych prístupoch k definovaniu pojmu „náhodnosti“ sú systematizované v tabuľke 1.

Tabuľka 1. Prístupy k určovaniu náhodnosti

Názov prístupu	Autori	Podstata prístupu
Frekvencia	von Mises, kostol, Kolmogorov, Loveland	V spoločnom podniku by sa mala dodržiavať stabilita frekvencie výskytu prvkov. Napríklad znaky 0 a 1 sa musia vyskytovať nezávisle as rovnakými pravdepodobnosťami nielen v binárnom SP, ale aj v ktorejkoľvek z jeho podsekvencií, vybraných náhodne a bez ohľadu na počiatočné podmienky generovania.
Komplexné	Kolmogorov, Čaitin	Akýkoľvek opis implementácie spoločného podniku nemôže byť podstatne kratší ako samotná implementácia. To znamená, že SP musí mať zložitú štruktúru a entropia jeho počiatočných prvkov musí byť vysoká. Sekvencia je náhodná, ak je jej algoritmická zložitosť blízka dĺžke sekvencie.
Kvantitatívne	Martin-Lof	Štiepenie pravdepodobnostný priestor sekvencie na nenáhodné a náhodné, teda na sekvencie, ktoré „zlyhajú“ a „prejdú“ súborom špecifických testov určených na identifikáciu vzorov.
Kryptografický	Moderný prístup	Sekvencia sa považuje za náhodnú, ak výpočtová zložitosť vyhľadávania vzorov nie je menšia ako daná hodnota.

Pri štúdiu problematiky syntézy biologického snímača náhodného čísla (ďalej len BioRSN) je vhodné brať do úvahy ďalšia podmienka: sekvencia sa považuje za náhodnú, ak je dokázaná náhodnosť fyzického zdroja, najmä ak je zdroj lokálne stacionárny a vytvára sekvenciu s danými charakteristikami. Tento prístup k definícii náhodnosti je relevantný pri konštrukcii BioDSCh, možno ho podmienečne nazvať „fyzický“. Splnenie podmienok určuje vhodnosť sekvencie na použitie v kryptografických aplikáciách.
Známy rôznymi spôsobmi generovanie náhodných čísel na počítači, zahŕňajúce použitie zmysluplných a nevedomých akcií používateľa ako zdroja náhodnosti. Medzi takéto akcie patrí napríklad stláčanie kláves na klávesnici, pohyb alebo klikanie myšou atď. Mierou náhodnosti vygenerovanej sekvencie je entropia. Nevýhodou mnohých známych metód je obtiažnosť odhadu množstva získanej entropie. Prístupy súvisiace s meraním charakteristík nevedomých ľudských pohybov umožňujú získať relatívne malý zlomok náhodných bitov za jednotku času, čo ukladá určité obmedzenia na použitie generovaných sekvencií v kryptografických aplikáciách.

Pseudonáhodný proces a používateľská úloha

Uvažujme o generovaní SP pomocou zmysluplných reakcií používateľov na nejaký dosť zložitý pseudonáhodný proces. Konkrétne: v náhodných časových okamihoch sa merajú hodnoty určitého súboru časovo premenných veličín. Náhodné hodnoty procesných veličín sú potom reprezentované ako náhodná sekvencia bitov. Vlastnosti kryptografickej aplikácie a operačného prostredia určili množstvo požiadaviek na BioDSCh:

1. Vygenerované sekvencie by mali byť v štatistických charakteristikách blízke ideálnym náhodným sekvenciám, najmä polaritou ( relatívna frekvencia"1") binárnej postupnosti by mala byť blízko 1/2.
2. Počas implementácie procesu bežným používateľom musí byť rýchlosť generovania aspoň 10 bitov/s.
3. Trvanie generovania priemerným používateľom 320 bitov (ktoré zodpovedajú v algoritme GOST 28147-89 súčtu dĺžky kľúča (256 bitov) a dĺžky synchronizačnej správy (64 bitov)) by nemalo presiahnuť 30 sekúnd.
4. Jednoduché používanie používateľom s programom BioDSCh.

Opíšme princíp konštrukcie uvažovanej triedy BioDSCh. Nazvime pracovnú oblasť obdĺžnik umiestnený v strede obrazovky osobného alebo tabletového počítača a zaberá väčšinu obrazovky, aby používateľovi poskytol pohodlnú vizuálnu analýzu procesu. V strede pracovnej oblasti sa postupne generuje N kruhov s priemerom d v časových intervaloch zlomku sekundy, odkiaľ začínajú priamočiary pohyb v rôznych smeroch. Smer pohybu i-teho kruhu, generovaného v momente i-teho kliknutia používateľa (v prípade tabletu stlačenie prsta), je určený smerom „vektora odchodu kruhu“, neviditeľný pre užívateľa, v rovnakom momente, ktorý sa rovnomerne otáča danou rýchlosťou okolo stredu pracovnej plochy, i=1,…,N.
Kruhy sa pohybujú ako projekcie loptičiek na biliardovom stole, keď na seba narážajú, odrážajú sa od seba a od hraníc pracovného priestoru, často menia smer pohybu a simulujú celkovo chaotický proces pohybu kruhov po diele. oblasť (obr. 1).

Obrázok 1. Trajektórie pohybu stredov kruhov vo vnútri pracovnej oblasti

Úlohou užívateľa je vygenerovať M náhodných bitov. Keď sa v pracovnej oblasti objaví posledný kruh, používateľ musí rýchlo odstrániť všetkých N pohyblivých kruhov kliknutím v náhodnom poradí na oblasť každého kruhu myšou (v prípade tabletu prstom). Relácia na generovanie určitého počtu bitov SP končí po vymazaní všetkých kruhov. Ak počet bitov vygenerovaných v jednej relácii nestačí, potom sa relácia opakuje toľkokrát, koľkokrát je potrebné na vygenerovanie M bitov.

Spracujte namerané veličiny

Generovanie SP sa vykonáva meraním množstva charakteristík opísaného pseudonáhodného procesu v náhodných časoch určených reakciou používateľa. Čím vyššia je rýchlosť generovania bitov, tým viac nezávislých charakteristík sa meria. Nezávislosť meraných charakteristík znamená nepredvídateľnosť hodnoty každej charakteristiky podľa známe hodnoty iné vlastnosti.
Všimnite si, že každý kruh pohybujúci sa na obrazovke je očíslovaný, rozdelený na 2 k rovnakých sektorov neviditeľných pre používateľa, očíslovaných od 0 do 2 k -1, kde k je prirodzené číslo a otáča sa okolo svojho geometrického stredu danou uhlovou rýchlosťou. Používateľ nevidí číslovanie kruhov a sektorov kruhu.
V momente vstupu do kruhu (úspešné kliknutie alebo stlačenie prsta) sa meria množstvo charakteristík procesu, takzvané zdroje entropie. Nech a i označuje bod dopadu i-tý kruh, i=1,2,... Potom je vhodné medzi merané veličiny zaradiť:

• X a Y súradnice bodu ai;
• vzdialenosť R od stredu kružnice k bodu a i;
• číslo sektora vo vnútri i-teho kruhu obsahujúceho bod a i ;
• číslo kruhu atď.

Namerané hodnoty sú konvertované do binárnej reprezentácie, ktorej prvky sú potom filtrované, keď sú zahrnuté vo výslednej bitovej sekvencii.

Experimentálne výsledky

Na určenie parametrov pre prioritnú implementáciu BioDSCh bolo vykonaných približne 104 sedení rôznymi interpretmi. Vykonané experimenty umožnili určiť oblasti vhodné hodnoty pre parametre modelu BioDSCh: rozmery pracovnej plochy, počet a priemer kruhov, rýchlosť pohybu kruhov, rýchlosť rotácie „vektora odchodu kruhov“, počet sektorov, na ktoré sú kruhy rozdelené, uhlová rýchlosť rotácia kruhov atď.
Pri analýze výsledkov operácie BioDSCh sa vychádzalo z nasledujúcich predpokladov:

• zaznamenané udalosti sú nezávislé v čase, to znamená, že reakciu používateľa na proces pozorovaný na obrazovke je ťažké s vysokou presnosťou replikovať inému používateľovi aj samotnému používateľovi;
• zdroje entropie sú nezávislé, to znamená, že nie je možné predpovedať hodnoty žiadnej charakteristiky zo známych hodnôt iných charakteristík;
• kvalita výstupnej postupnosti by sa mala posudzovať s prihliadnutím na známe prístupy k určovaniu náhodnosti (tabuľka 1), ako aj na „fyzický“ prístup.

Hodnotenie intervalov spoľahlivosti pre hodnoty vypočítaných procesných veličín zodpovedá hladine významnosti 0,05. Na rozpoznanie rovnomernosti rozloženia znakov výslednej vzorky (po redukcii na binárnu formu) bol použitý chí-kvadrát test zhody s rovnomerným rozdelením.
V súlade s dĺžkou generovaných binárnych sekvencií sa stanovilo prijateľné obmedzenie ich polarity p: |p-1/2|?b, kde b?10-2.
Počet bitov získaných z hodnôt nameraných procesných veličín (zdrojov entropie) bol určený empiricky na základe analýzy informačnej entropie hodnôt uvažovaných charakteristík. Empiricky sa zistilo, že „odstránenie“ akéhokoľvek kruhu vám umožní získať približne 30 bitov náhodnej sekvencie. Preto s použitými parametrami rozloženia BioDSCh postačujú 1-2 relácie prevádzky BioDSCh na vygenerovanie kľúča a inicializačného vektora algoritmu GOST 28147-89.
Pokyny na zlepšenie charakteristík biologických generátorov by mali byť spojené tak s optimalizáciou parametrov tohto usporiadania, ako aj so štúdiom ďalších rozložení BioDSCh.