Generátor pseudonáhodné sekvence.

Služby

První široce používanou technologií pro generování náhodného čísla byl algoritmus navržený Lechmerem, který je známý jako lineární kongruentní metoda. Tento algoritmus je parametrizován čtyřmi čísly takto: Následné náhodná čísla

(X n) se získá pomocí následující iterační rovnosti:

X n + 1 = (a X n + c) mod m< m.

Jsou-li m, a a c celá čísla, vytvoří se posloupnost celých čísel v rozsahu 0 X n

Výběr hodnot pro a, c a m je rozhodující pro vývoj dobrého generátoru náhodných čísel. Je zřejmé, že m musí být velmi velké, aby bylo možné generovat mnoho náhodných čísel. Předpokládá se, že m by se mělo přibližně rovnat maximálnímu kladnému celému číslu pro tohoto počítače

. Takže obvykle m je blízko nebo rovno 2 31 .

Při výběru generátoru náhodných čísel se používají tři kritéria:

1. Funkce musí vytvořit kompletní období, tzn. všechna čísla mezi 0 a m před vygenerovanými čísly se začnou opakovat.

2. Vygenerovaná sekvence se musí objevit náhodně. Sekvence není náhodná, protože je generována deterministicky, ale různé statistické testy, které lze použít, by měly ukázat, že sekvence je náhodná.

3. Funkce musí být efektivně implementována na 32bitových procesorech. Hodnoty a, c a m musí být zvoleny tak, aby byla splněna tato tři kritéria. V souladu s prvním kritériem lze ukázat, že pokud m je jednoduché a c = 0, pak když určitou hodnotu a období vytvořený funkcí

, bude se rovnat m-1. Pro 32bitovou aritmetiku je odpovídající prvočíslo m = 2 31 - 1. Funkce pro generování pseudonáhodných čísel je tedy:

X n +1 = (a X n) mod (2 31 - 1) Pouze malý počet

Síla lineárního kongruentního algoritmu spočívá v tom, že pokud jsou faktor a modul (báze) vhodně zvoleny, pak výsledná posloupnost čísel bude statisticky nerozeznatelná od posloupnosti, která je náhodná z množiny 1, 2, ..., m- 1. Ale v posloupnosti získané pomocí algoritmu nemůže být žádná náhodnost, bez ohledu na volbu počáteční hodnoty X 0 . Pokud je vybrána hodnota, zbývající čísla v sekvenci budou předem určena. To je vždy bráno v úvahu při kryptoanalýze.

Pokud protivník ví, že se používá lineární kongruentní algoritmus, a jsou-li známy jeho parametry (a = 7 5, c = 0, m = 2 31 - 1), pak pokud je odhaleno jedno číslo, stane se celá posloupnost čísel známý. I když protivník ví pouze to, že se používá lineární kongruentní algoritmus, znalost malé části posloupnosti stačí k určení parametrů algoritmu a všech následujících čísel. Předpokládejme, že nepřítel může určit hodnoty X 0, X 1, X 2, X 3. Pak:

X 1 = (a X 0 + c) mod mX 2 = (a X 1 + c) mod mX 3 = (a X 2 + c) mod m

Tyto rovnosti nám umožňují najít a, c a m.

Tedy, ačkoliv algoritmus je dobrý generátor pseudonáhodné posloupnosti čísel, je žádoucí, aby skutečná použitá posloupnost byla nepředvídatelná, protože v tomto případě znalost části posloupnosti neumožní určit její budoucí prvky. Tohoto cíle lze dosáhnout několika způsoby. Například pomocí interního systémové hodiny pro úpravu toku náhodných čísel. Jedním ze způsobů použití hodin je restartovat sekvenci po N číslech s použitím aktuální hodnoty hodin modulo m jako nové počáteční hodnoty. Dalším způsobem je jednoduchý doplněk aktuální časové hodnoty ke každému náhodnému číslu modulo m.

(Angličtina) ruština: « Generování náhodných čísel je příliš důležité na to, aby bylo ponecháno náhodě».

Encyklopedický YouTube

1 / 5

✪ Generátory náhodných a pseudonáhodných čísel

✪ Generátor pseudonáhodných čísel | Kryptografie | Programování (část 8)

✪ C++ lekce od nuly / Lekce #5 - Generátor čísel + řetězce v C++

✪ rand. srand a nastavte rozsah. srand čas null. Generátor náhodných čísel. randomizovat. Lekce #29.

✪ Náhodná čísla, lineární kongruenciální metoda - LNG (Linear Congruential Generator)

titulky

Když pozorujeme fyzický svět, všude nalézáme náhodné variace. Můžeme vytvořit skutečné, měření náhodných změn nazývaných šum. Měřením tohoto šumu (vzorkováním) lze získat čísla. Například pokud měříte elektrický proud statické z TV po nějakou dobu, získáte perfektní náhodnou sekvenci. Tuto náhodnou sekvenci si můžete vizualizovat nakreslením cesty, jejíž směr se mění s každým číslem. Tomu se říká náhodná procházka. Je třeba poznamenat, že v každém bodě sekvence neexistuje žádný vzor jakékoli stupnice – další krok je vždy nepředvídatelný. To říkají náhodné procesy nedeterministické, neboť jejich vývoj nelze předem předvídat. Stroje jsou naproti tomu deterministické. v milisekundách. Jejich operace jsou předvídatelné a opakovatelné. V roce 1946 byl John von Neumann pozván, aby provedl výpočty pro armádu. Byl zvláště aktivní v konstrukci vodíkové bomby. najít ten, který bude pasovat a otevřít zámek.

Bude to ale trvat několik dní.

Předpokládáme tedy, že po dobu 8 hodin je prakticky chráněn. Při použití generátorů pseudonáhodných čísel se bezpečnost zvyšuje s rostoucí délkou zrna. Nejvýkonnější počítač vyzkouší všechna možná zrna po mnoho let, takže místo dokonalého zabezpečení můžeme bezpečně předpokládat praktické zabezpečení. S rostoucí rychlostí výpočtu by se měla úměrně zvětšovat i délka zrna. Pseudonáhodnost osvobozuje Alici a Boba od nutnosti vyměňovat si předem kompletní náhodnou sekvenci offsetů.

Místo toho si vyměňují relativně malá náhodná zrna a roztahují je do stejných náhodných sekvencí, které jsou vyžadovány. Ale co se stane, když se nikdy nesetkají, aby si toto náhodné zrno vyměnili. Zdroje náhodných čísel

Zdroje skutečných náhodných čísel je extrémně obtížné najít. Takovými zdroji mohou být fyzikální šum, jako jsou detektory událostí ionizujícího záření, šum výstřelu v rezistoru nebo kosmické záření. Taková zařízení se však používají v aplikacích

zabezpečení sítě zřídka. Objevují se také potíže brutální útoky pro podobná zařízení.

Kryptografické aplikace používají ke generování náhodných čísel speciální algoritmy. Tyto algoritmy jsou předem určené, a proto generují posloupnost čísel, která teoreticky nemohou být statisticky náhodná. Zároveň, pokud zvolíte dobrý algoritmus, výsledná číselná posloupnost je

Mezi moderními 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 (metoda lineární kongruence 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.

PRNG se zdrojem entropie nebo RNG

Stejně jako je potřeba generovat snadno opakovatelné sekvence náhodných čísel, je potřeba generovat i zcela nepředvídatelná nebo prostě úplně náhodná čísla. Takové generátory se nazývají generátory náhodných čísel(RNG - anglický generátor náhodných čísel, RNG). Protože se tyto 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 kryptografického PRNG a externí zdroj entropie (a právě tato kombinace je dnes běžně chápána jako RNG).

Skoro všechno velkých výrobců mikročipy jsou dodávány hardwarovými RNG s různými zdroji entropie, které používají různé metody, aby je očistily od nevyhnutelné předvídatelnosti. Nicméně, na momentálně rychlost shromažďování náhodných čísel všemi existujícími mikročipy (několik tisíc bitů za sekundu) neodpovídá rychlosti moderní procesory.

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

V osobní počítače autoři softwarových RNG využívají mnohem rychlejší zdroje entropie, jako je hluk zvuková karta nebo čítač cyklů procesoru. Shromažďování entropie bylo nejzranitelnějším bodem RNG. Tento problém stále není plně vyřešen u mnoha zařízení (např. čipových karet), která tak zůstávají zranitelná. Mnoho RNG používá tradiční, i když pomalé, metody shromažďování entropie, jako je měření odezvy uživatele (pohyb myši atd.), jako v PGP a Yarrow, nebo interakce mezi vlákny, jako v Java SecureRandom.

Příklad jednoduchého RNG se zdrojem entropie

Pokud jako zdroj entropie použijeme aktuální čas, pak k 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 během jedné milisekundy.

Příklady zdrojů RNG a entropie

		PRNG	Výhody	Nedostatky
/dev/random na UNIX/Linux	Čítač hodin CPU se však shromažďuje pouze během hardwarových přerušení	LFSR, s výstupem hash přes SHA-1	Dostupné ve 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	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, velikost volnou paměť, číslo procesu a název počítače NETBIOS	MD5 hash vnitřního stavu o velikosti 128 bitů	Vestavěný ve Windows, nezasekává se	Velmi záleží na použitém poskytovateli kryptoměn (CSP).
Java SecureRandom	Komunikace mezi vlákny	SHA-1 hash vnitřního stavu (1024 bitů)	Skvělý vnitřní stav	Sběr pomalé entropie
Chaos od Ruptora	Počítadlo hodin procesoru, shromažďováno nepřetržitě	Hašování 4096bitového vnitřního stavu na základě nelineární varianty generátoru Marsaglia	Dokud se nejrychlejší ze všech, velký vnitřní stav, „nezasekne“	Původní vývoj, vlastnosti jsou uvedeny pouze dle sdělení autora
RRAND od společnosti Ruptor	Čítač hodin procesoru	Šifrování vnitřního stavu pomocí streamové šifry EnRUPT v režimu ověřeného šifrování (aeRUPT)	Velmi rychlé, vnitřní stav libovolné velikosti na výběr, žádné „zasekávání“	Původní vývoj, vlastnosti jsou uvedeny pouze dle sdělení autora. Šifra EnRUPT není kryptozabezpečená.
RdRand od intel	Aktuální hluk	Konstrukce frekvenčního generátoru založeného na „náhodném“ bitovém čtení hodnot z proudů	Velmi rychlé, nezasekává se	Původní vývoj, vlastnosti jsou uvedeny pouze dle tvrzení článku z habrahabr - prosím o upřesnění.
Stratosphera PRNG od ORION	Počítadlo hodin procesoru, shromažďováno nepřetržitě (sůl se také používá ve formě náhodně vybraného celého čísla)	Konstrukce PNG na základě algoritmu od Intelu s opakovaně použitelnou inicializací a posunem	Dostatečně rychlý, nezasekává se, projde všemi testy DIEHARD	Původní vývoj, vlastnosti jsou uvedeny pouze na základě informací na webu oriondevteam.com - (upřesnění ze dne 23.10.2013).

PRNG v kryptografii

Typ PRNG jsou PRBG - generátory pseudonáhodných bitů a také různé proudové šifry. PRNG, stejně jako proudové šifry, se skládají z vnitřního stavu (obvykle o velikosti od 16 bitů do několika megabajtů), funkce pro inicializaci vnitřního stavu pomocí klíče nebo obilí(anglicky seed), funkce pro aktualizaci vnitřního stavu a výstupní funkce. PRNG se dělí na jednoduché aritmetické, rozbité kryptografické a kryptografické silné. Jejich obecným účelem je generovat posloupnosti čísel, které nelze pomocí výpočetních metod odlišit od náhodných.

Ačkoli mnoho silných PRNG nebo proudových šifer nabízí mnohem více „náhodných“ čísel, takové generátory jsou mnohem pomalejší než konvenční aritmetické generátory a nemusí být vhodné pro jakýkoli druh výzkumu, který vyžaduje, aby byl procesor volný pro užitečnější výpočty.

Pro vojenské účely a polních podmínkách Používají se pouze tajné synchronní kryptografické silné PRNG (streamové šifry). Příklady dobře známých krypto-odolných PRNG jsou RC4, ISAAC, SEAL, Snow, velmi pomalý teoretický algoritmus Blum - Blum - Shuba, stejně jako čítače s kryptografické hašovací funkce nebo silné blokové šifry místo výstupní funkce.

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

Round-robin šifrování

V v tomto případě metoda se používá ke generování klíče relace z hlavního klíče. Čítač s periodou N se používá jako vstup do šifrovacího zařízení. Pokud je například použit 56bitový klíč DES, lze použít čítač s periodou 256. Po každém vytvořeném klíči se hodnota čítače zvýší o 1. Pseudonáhodná sekvence získaná pomocí tohoto schématu má tedy hodnotu. celé období: každý výstupní hodnota X0, X1,…XN-1 na základě různé významyčítač, takže X0 ≠ X1 ≠ XN-1. Protože hlavní klíč je tajný, je snadné prokázat, že žádný tajný klíč nezávisí na znalosti jednoho nebo více předchozích tajné klíče.

ANSI X9.17

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

1. Vstup: Generátor je řízen dvěma pseudonáhodnými vstupy. Jedním z nich je 64bitová reprezentace aktuální termíny a čas, které se mění při každém vytvoření čísla. Druhým je 64bitová nezpracovaná hodnota. Inicializuje se s nějakou libovolnou hodnotou a mění se během generování posloupnosti pseudonáhodných čísel.
2. Klíče: Generátor používá tři trojité DES moduly. Všechny tři používají stejný 56bitový pár klíčů, který je uchováván v tajnosti a používá se pouze při generování pseudonáhodného čísla.
3. Výstup: Výstup se skládá z 64bitového pseudonáhodného čísla a 64bitové hodnoty, která bude použita jako zdroj při vytváření dalšího čísla.

• DTi - hodnota data a času na začátku i-té fáze generování.
• Vi je počáteční hodnota pro i-tou generační fázi.
• Ri je pseudonáhodné číslo vytvořené v i-té fázi generování.
• K1, K2 - klíče používané v každé fázi.

1 Ri = EDEK1,K2 [ EDEK1,K2 [ DTi] Vi ] 2 Vi+1 = EDEK1,K2 [ EDEK1,K2 [ DTi] Ri]

Schéma zahrnuje použití 112bitového klíče a tří EDE šifrování. Jako vstup jsou zadány dvě pseudonáhodné hodnoty: hodnota data a času a počáteční hodnota aktuální iterace, výstup je počáteční hodnota pro další iteraci a další pseudonáhodná hodnota; I když je pseudonáhodné číslo Ri kompromitováno, není možné vypočítat Vi+1 z Ri v rozumném čase, a tedy další pseudonáhodnou hodnotu Ri+1, protože pro získání Vi+ jsou provedeny tři další EDE operace. 1.

Hardware PRNG

Kromě dědictví, známých generátorů LFSR, které byly široce používány jako hardwarové PRNG ve 20. století, je bohužel o moderních hardwarových PRNG (streamových šifrách) známo jen velmi málo, protože většina z nich byla vyvinuta pro vojenské účely a jsou uchovávány v tajnosti. . Téměř všechny existující komerční hardwarové PRNG jsou patentovány nebo drženy v tajnosti. Hardwarové PRNG jsou omezeny přísnými požadavky na spotřební paměť (nejčastěji je zakázáno použití paměti), výkon (1-2 hodinové cykly) a plochu (několik set buněk FPGA nebo ASIC). Kvůli tak přísným požadavkům na hardwarové PRNG je velmi obtížné vytvořit krypto-proof generátor, a proto byly dosud všechny známé hardwarové PRNG rozbity. Příklady takových generátorů jsou Toyocrypt a LILI-128, což jsou oba generátory LFSR a oba byly prolomeny pomocí algebraických útoků.

Kvůli nedostatku dobrých hardwarových PRNG jsou výrobci nuceni používat mnohem pomalejší, ale dobře známé existující. blokové šifry(DES, AES) a hashovací funkce (SHA-1) v režimech streamování.

Generátory pseudonáhodné sekvence

V praxi je jedním z nejdůležitějších následující úkol. Na základě výše uvedených a dalších vlastností RRSP je nutné určit, zda konkrétní sekvence je implementací RRSP. V následujícím budeme kvůli stručnosti jednoduše nazývat implementaci RRSP náhodnou posloupností.

Konstruktivní přístup k definování náhodné posloupnosti navrhli Blum, Goldwasser, Micalli a Yao. Jejich definice považuje posloupnost za náhodnou, pokud neexistuje polynomiální (pravděpodobnostní) algoritmus, který ji dokáže odlišit od čisté náhodnosti. Tato sekvence se nazývá polynomiálně nerozeznatelné od náhodného nebo pseudonáhodný.

Tento přístup umožňuje ke generování používat pseudonáhodné sekvence (PSR). deterministický implementované algoritmy konečných automatů. Ačkoli z matematického hlediska nejsou takové posloupnosti náhodné, protože jsou zcela určeny počátečním plněním, jejich praktické využití neposkytuje kryptoanalytikovi žádné výhody kvůli jeho „nerozlišitelnosti“ od náhodných. Protože se tento přístup zdá konstruktivnější, budeme se mu věnovat podrobněji.

Náhodné sekvence ve smyslu posledně uvedené definice se také nazývá „náhodný pro všechny“ praktické aplikace" Generátory takových sekvencí se nazývají kryptograficky bezpečné ( kryptograficky silné) nebo kryptograficky bezpečné ( kryptograficky bezpečné). Pseudonáhodnost v tomto případě není pouze vlastností sekvence (či generátoru), ale také vlastností pozorovatele, respektive jeho výpočetních schopností.

Pro PSP byla prokázána dvě důležitá tvrzení:

1. Posloupnost je pseudonáhodná právě tehdy, když je nepředvídatelné, tj. vydrží testování s dalším bitem. To znamená, že i když je známa část sekvence libovolné délky, pak pokud počáteční naplnění generátoru a parametry generovacího algoritmu nejsou známy, není možné navrhnout algoritmus, který by byl výrazně lepší než jednoduché hádání nebo přehazování. mincí k získání dalšího bitu.

2. Kryptograficky silné generátory existují tehdy a jen tehdy, když existují funkce, které jsou snadno vypočítatelné, ale výpočetně obtížně invertovatelné (jednosměrné funkce - jednosměrné funkce). V tomto případě může být každému generátoru PSP přiřazena korespondence jedna ku jedné s určitou jednosměrnou funkcí, která závisí na určitých parametrech.

Nejjednodušší snímač pseudonáhodných čísel je lineární kongruentní generátor(LKG), který je popsán opakující se rovnicí tvaru X n =(aX n-1 +b) mod N, Kde X 0 – náhodná počáteční hodnota, A- násobitel, b- přírůstek, N– modul.

Perioda výstupní sekvence takového generátoru nepřekročí N, maximální hodnota dosaženo správnou volbou parametrů a,b,N, totiž kdy

· čísla N A b coprime: GCD(N,b)=1);

· a-1 násobek libovolného prvočísla p, dělení N;

· a-1 násobek 4 , Pokud N násobek 4 .

Níže je uveden seznam konstant pro LKG, které poskytují maximální období sekvencí a, což je stejně důležité, odpovídající sekvence projdou statistickými testy.

Pro implementaci LCG na osobních počítačích se modul často používá s ohledem na jejich bitovou mřížku N=231-1»2,14×109. V tomto případě je pro konstantu dosaženo nejkvalitnějších statistických vlastností PSP a=397204094.

Ve srovnání s jinými typy generátorů PSP tento typ poskytuje vysoký výkon kvůli malému počtu operací k vytvoření jednoho pseudonáhodného bitu.

Nevýhodou LCG z hlediska jejich použití pro vytváření proudových šifer je předvídatelnost výstupních sekvencí. Byly navrženy účinné útoky na LKG Joan Boyar, vlastní metody útoků na kvadratické - Xn = (aXn-12 +bXn-1 +c)modNa krychlový - X n = (aX n -1 3 +bX n -1 2 +cX n -1 +d)modN generátory.

Další badatelé shrnuli výsledky práce Bojar pro případ obecného generátoru polynomiálních kongruentů. Záď A Bojar ukázal, jak rozlousknout LKG, i když není známa celá sekvence.

Wishmann A Kopec a později Pierre L'Ecuger studované kombinace LCG. Výsledky nejsou kryptograficky silnější, ale mají delší období a chovají se lépe podle určitých kritérií náhodnosti.

Posunovací registry s lineární zpětnou vazbou (Lineární zpětné posuvné registry - LFSR) zahrnují samotný posuvný registr a obvod pro výpočet funkce zpětná vazba (sekvence klepnutí) – viz obr. 12:

Bitový proud

n

∙∙∙

2

1

Rýže. 2. Lineární zpětnovazební posuvný registr ( LFSR)

V diagramu je obsah registru - sekvence bitů - posunut s příchodem hodinového impulsu ( hodinový puls) o jedno místo vpravo. Za výstup se považuje nejméně významný bit LFSR v tomto pracovním cyklu. Hodnota nejvýznamnější číslice je výsledkem sčítání o mod2(funkce XOR) bity zpětné vazby.

teoreticky n-bit LFSR může generovat pseudonáhodnou sekvenci s tečkou 2n-1 kousek, takový LFSR se nazývají registry maximální periody. K tomu musí posuvný registr navštívit všechny 2n-1 vnitřní stavy ( 2n-1, protože zaplnění posuvného registru nulou způsobí nekonečnou sekvenci nul).

Připomeňme, že polynom se nazývá neredukovatelný, pokud jej nelze vyjádřit jako součin jiných polynomů menšího stupně odlišných od 1 a samotného.

Primitivní polynom stupně n je neredukovatelný polynom, který se dělí, ale nedělí x d +1 pro kohokoli d: (2n-1│d)

Teorém(bez důkazu): Aby měl LFSR maximální periodu, je nutné a postačující, aby polynom vzniklý z prvků zpětné vazby ( sekvence klepnutí) plus jedna byl primitivní polynom modulo 2. (Ve skutečnosti je primitivní polynom generátorem v daném poli).

Seznam prakticky použitelných primitivních polynomů je uveden v.

Například primitivní polynom je x 32 x 7 x 5 x 3 x 2 x1. Záznam ( 32,7,5,3,2,1,0 ) znamená, že vezmete 32bitový posuvný registr a vygenerujete bit zpětné vazby přidáním přes mod2 7., 5., 3., 2. a 1. bit, dostaneme LFSR maximální délka (s 2 32 -1 státy).

Všimněte si, že pokud p(x) je tedy primitivní polynom x n × p (1/x)– také primitivní.

Například, pokud polynom (a,b,0) primitivní tedy (a,a-b,0)– primitivní. Pokud polynom (a,b,c,d,0) tak primitivní (a,a-d,a-c,a-b,0)- primitivní atd.

Primitivní trinomy jsou zvláště výhodné, protože Jsou přidány pouze 2 bity posuvného registru, ale jsou také náchylnější k útokům.

LFSR- vhodné pro technické provedení, ale mají nepříjemné vlastnosti. Po sobě jdoucí bity jsou lineárně závislé, což je činí nepoužitelnými pro šifrování. I když je obvod zpětné vazby neznámý, je dostačující 2n výstupní bity k jeho určení.

Velká náhodná čísla generovaná ze sekvenčních bitů LFSR, jsou vysoce korelované a někdy dokonce nejsou zcela náhodné. Nicméně, LFSR poměrně často používané jako prvky více složité algoritmy vytvoření sekvence šifrovacích klíčů.

Existuje také řada generátorů PSP (včetně generátorů Fibonacciho čísel), které z řady důvodů nebyly nalezeny široké uplatnění PROTI kryptografických systémů. Většina efektivní řešení byly získány na základě kompozitních generátorů.

Myšlenka konstrukce složeného generátoru je založena na skutečnosti, že kombinace dvou nebo více jednoduché generátory PSP, v případě správná volba sjednocující funkce (vč. mod 2, mod 2 32 -1 atd.), poskytuje generátor se zlepšenými vlastnostmi náhodnosti a v důsledku toho se zvýšenou šifrovací silou.

V případě vytvoření kryptograficky silného PSP generátoru je jednoduše vyřešena otázka vytváření proudových šifer. Výstup takového PSP je k nerozeznání (nebo spíše by měl být k nerozeznání) od RRSP. Dva generátory lze vždy spustit synchronně z jednoho počátečního stavového vektoru, který je mnohem kratší přenášená zpráva, který toto schéma odlišuje od Vernamovy šifry.

Existují 4 známé přístupy k navrhování vhodných generátorů:

1) systémově teoretický přístup;

2) komplexnost-teoretický přístup;

3) informačně-teoretický přístup;

4) randomizovaný přístup.

Tyto přístupy se liší ve svých předpokladech o schopnostech kryptoanalytika, definici kryptografického úspěchu a konceptu spolehlivosti.

V případě systémově teoretický přístup kryptograf vytvoří generátor toku klíčů, který má ověřitelné vlastnosti, včetně délky periody výstupní sekvence, statistického rozložení bitového toku, lineární složitosti transformace atd. S přihlédnutím ke známým technikám kryptoanalýzy kryptograf optimalizuje generátor proti těmto útokům.

Na základě tohoto přístupu Rüppel formuloval následující sadu kritérií pro proudové šifry:

1. Dlouhá perioda výstupní sekvence, žádné opakování;

2. Vysoká lineární složitost, jako charakteristika našeho generátoru prostřednictvím registru LFSR minimální délka, která může generovat stejný výstup;

3. Nerozlišitelnost od RRSP podle statistických kritérií;

4. Shuffle: jakýkoli bit toku klíčů musí být komplexní transformací všech nebo většiny bitů počátečního stavu (klíče);

5. Ztráta: redundance ve všech podstrukturách algoritmu generátoru musí být rozptýlena;

6. Kritéria pro nelinearitu transformací: v souladu s nějakou metrikou vzdálenost k lineární funkce by měla být dostatečně velká, kritérium pro lavinové šíření změn v případě změny jednoho bitu atd.

Praxe potvrzuje vhodnost použití stanovených kritérií nejen pro analýzu a hodnocení proudových šifer vytvořených v rámci systémově teoretického přístupu, ale i pro libovolné proudové a blokové šifry.

Hlavním problémem takových kryptosystémů je, že je pro ně obtížné prokázat jakákoli fakta o jejich kryptografické síle, protože u všech těchto kritérií nebyla prokázána jejich nezbytnost nebo dostatečnost. Proudová šifra může splnit všechny tyto principy a přesto být slabá, protože odolnost vůči dané sadě kryptoanalytických útoků nic nezaručuje.

Příkladem úspěšné konstrukce kompozitního generátoru z pohledu zvyšování lineární složitosti je Golemanova kaskáda (obr. 3).

Goleman stage obsahuje několik registrů LFSR a načasování každého dalšího LSFR ovládaný předchozím tak, aby se stav změnil LFSR-(k+1) v čase t dojde, pokud v předchozím kroku t-1 výstup LFSR-k se rovná 1 a LFSR-(k+1) jinak svůj stav nemění.

Pokud všechno LFSR– délky l, pak lineární složitost systému s n registry rovné l× (2 l-1)n-1.

X(t)

LFSR-2

LFSR-3

Takt

Rýže. 4. Střídavý start-stop generátor

Tento generátor má dlouhou periodu a vysokou lineární složitost.

Uplatňuje se komplexnost-teoretický přístup, kryptograf se snaží dokázat sílu generátoru pomocí teorie složitosti. Základem řešení v tomto přístupu jsou generátory založené na konceptu jednosměrná funkce.

Jednosměrná funkce F(x): D→R snadno vypočítatelný pro každého x О D, ale je velmi obtížné invertovat pro téměř všechny hodnoty R. V opačném případě, pokud V – výpočetní náročnost přijímání F(x) a V * je výpočetní složitost hledání f-1(x), pak platí nerovnost V * >>V. Je snadné vidět, že mocninná funkce v nějakém konečném poli může být kandidátem na jednosměrnou funkci F(x)=a x, Kde a,xОGF(q)– pole Galois od q prvky.

Je snadné vidět, že násobení, díky vlastnosti asociativnosti, může být provedeno za méně než číslo x-1 kroky. Například, a 9 =a×((a 2) 2) 2, což umožňuje vypočítat požadovaný stupeň místo osmi ve čtyřech krocích (nejprve a 2 = a × a, pak a 4 = a 2 a 2, a 8 = a 4 a 4 a konečně a 9 = a 8 a).

Inverzní operace je nalezení exponentu z hodnoty výkonová funkce(logaritmus) - v konečném poli zatím nelze řešit lépe než pomocí optimalizovaných metod výčtu možných variant. V případě velká velikost pole (pořadí 2 1024 ) je tento úkol moderní vývoj počítačové vybavení výpočetně neřešitelný.

Příkladem odpovídajícího generátoru je algoritmus RSA. Nechte parametr N=p×q, Kde p,q– prvočísla, počáteční hodnota generátoru x 0 N, e: GCD( e,(p-1)×(q-1))=1.

x i+1 =x e i mod N

Výsledek generátoru je nejmenší významný kousek x i+1. Trvanlivost tohoto generátoru je ekvivalentní trvanlivosti RSA. Li N dostatečně velký, generátor poskytuje praktickou odolnost.

Je navržen další příklad generátoru postaveného na komplexním přístupu Květ, Květ A Shub (BBS). V současné době je to jeden z nejjednodušších a efektivních algoritmů. Matematickou teorií tohoto generátoru jsou kvadratické modulo zbytky n.

Zvolme dvě velká prvočísla p A q, přičemž zbytek 3 při dělení 4. Produkt n pqŘíkejme tomu číslo Bloom. Pojďme si vybrat X: GCD( n,x)=1. Pojďme najít počáteční hodnotu generátoru: x 0 = x 2 mod n.

Teď i Té pseudonáhodné číslo je nejméně významný bit x i, Kde x i =x 2 i -2 mod n.

Všimněte si, že získat já- bit, není nutný žádný výpočet ( i-1) uvádí. Pokud víme p,q, pak to můžeme okamžitě vypočítat: b i Existuje nejmenší hodnotu bit:

Tato vlastnost vám umožňuje používat BBS- generátor pro práci se soubory s náhodným přístupem ( náhodný přístup).

Číslo n mohou být volně distribuovány, takže každý účastník sítě může samostatně vytvářet požadované bity. Navíc, pokud kryptoanalytik nemůže číslo faktorizovat n, nebude schopen předpovědět další bit, a to ani v pravděpodobnostním smyslu, jako například "existuje 51% šance, že další bit je 1".

Poznámka; že generátory postavené na jednosměrných funkcích jsou velmi pomalé praktické provedení jsou vyžadovány speciální procesory.

Další dva přístupy informace teoretické a náhodné nenašly široké praktické uplatnění.

Od pohledu informačně-teoretické nejvíce nejlepší lék v boji proti kryptoanalytikovi, který má nekonečné výpočetní zdroje a čas, je jednorázová páska nebo jednorázová podložka.

V případě randomizované Cílem je zvýšit počet bitů, se kterými musí kryptoanalytik pracovat (bez navyšování klíče). Toho lze dosáhnout použitím velkých náhodných veřejných řetězců. Klíč bude indikovat, které části těchto řetězců je třeba použít pro šifrování a dešifrování. Pak bude muset kryptoanalytik použít metodu totálního prohledávání možností (brute force) na náhodných řetězcích.

Sílu této metody lze vyjádřit jako průměrný počet bitů, které by musel kryptoanalytik prozkoumat, než se šance na určení klíče stanou lepšími než prostým hádáním.

Ueli Maurer popsal takové schéma. Pravděpodobnost prolomení takového kryptosystému závisí na množství paměti, kterou má kryptoanalytik k dispozici (nezávisí však na jeho výpočetních zdrojích).

Aby toto schéma nabylo praktické podoby, je zapotřebí asi 100 bitových sekvencí. 10 20 bit každý. Digitalizace měsíčního povrchu je jedním ze způsobů, jak získat takový počet bitů.

Na závěr poznamenáváme, že k sestavení generátoru PSP je nutné získat několik náhodných kousků. Nejjednodušší způsob je použít nejméně významný bit časovače počítače.

Pomocí této metody nemůžete přijímat mnoho bitů, protože Každé volání procedury generování bitů může trvat sudé číslo kroky časovače, což jistě ovlivní vlastnosti sekvence.

Většina nejlepší způsob získat náhodné číslo znamená uchýlit se k přirozené náhodě skutečný svět– v důsledku toho hluk přechodné procesy PROTI polovodičové diody, tepelný šum vysokých rezistorů, radioaktivní rozpad atd. V počítačích v zásadě existuje prvek náhodnosti:

denní doba;

zatížení CPU;

Čas příjezdu síťové pakety atd.

Problém není najít zdroje náhodnosti, ale udržet náhodnost v měření.

Lze to udělat například takto: najdeme událost, která se děje pravidelně, ale náhodně (šum překročí určitou hranici). Změřme čas mezi první a druhou událostí, pak mezi druhou a třetí. Li t 1.2  t 2.3, pak nastavíme výstup generátoru rovný 1; Li t 1,2 < t 2.3, pak je výstup 0. Budeme pokračovat v procesu.

Americký národní standardizační institut (ANSI) vyvinul metodu pro generování 64bitových klíčů pomocí algoritmu DES (ANSI X9.17). Jeho hlavním účelem je získat velké množství klíčů pro více komunikačních relací. Místo algoritmu DES můžete použít jakýkoli jiný silný šifrovací algoritmus.

Nechme funkci E K (P) zašifrovat P pomocí algoritmu DES na předem připraveném klíči K, který slouží pouze ke generování tajných klíčů. Dále nechť V 0 je počáteční 64bitová hodnota, která je utajena před nepřítelem, a T i představuje datum a čas, když i-tý klíč. Pak další náhodný klíč R i se vypočítá pomocí transformace:

R i = EK (EK (T i) Å V i)

Chcete-li získat další hodnotu V i, musíte vypočítat

V i = EK (EK (T i) Å R i)

Významným problémem systémů pro generování náhodných dat je přítomnost odchylek a korelací v generované sekvenci. Samotné procesy mohou být náhodné, ale během procesu měření mohou nastat problémy. Jak se s tím vypořádat?

1) Přidání podle mod 2 dvě nezávislé sekvence: pokud je náhodný bit posunut na 0 o hodnotu ε , pak pravděpodobnost výskytu 0 lze zapsat jako P(0)=0,5+e.

Přidání podle mod 2: dva rovnoměrně distribuované nezávislé bity dají: P(0)=(0.5 +ε) 2+(0,5-ε) 2=0.5 +2×ε 2, přidáním čtyř bitů dostaneme: P(0)=0.5+8 ε 4 atd. Proces konverguje k ekvipravděpodobnému rozdělení 0 a 1.

2) Nechť rozdělení jedniček a nul v posloupnosti jsou veličiny p A q respektive. Použijme metodu kódování: zvažte dva bity:

Pokud se jedná o stejné bity, pak je vyhoďte a zvažte další pár;

Pokud jsou bity různé, pak bereme jako výstupní hodnotu první bit.

Tato metoda umožňuje vyřešit problém zkreslení při zachování vlastností náhodnosti zdroje (s určitou ztrátou objemu dat).

Potenciální problém Problém obou metod spočívá v tom, že pokud existuje korelace mezi sousedními bity, tyto metody posun zvyšují. Jedním ze způsobů, jak se tomu vyhnout, je použití různých zdrojů náhodných čísel.

To, že generátor náhodných čísel má zkreslení, obecně řečeno neznamená, že je nevhodný. Například pro vygenerování 112bitového klíče pro „trojitý“ algoritmus DES(Trojitý DES) je použit generátor s předpětím na nulu: P(xt=0)=0,55, P(xt=l)=0,45(entropie N= 0,99277 na klíčový bit ve srovnání s 1 pro ideální generátor).

V tomto případě může útočník optimalizovat celkovou proceduru vyhledávání klíčů hledáním klíče počínaje nejpravděpodobnější hodnotou ( 00…0 ) a končící nejméně pravděpodobnou ( 11…1 ). Vzhledem k přítomnosti zkreslení můžeme očekávat, že klíč najdeme v průměru 2 109 pokusy. Pokud by nedošlo k přesunu, pak by to bylo nutné 2 111 pokusy. Existuje zisk, ale je zanedbatelný.