Posuvný registr s lineární zpětnou vazbou. Lineární posuvný registr se zpětnou vazbou Příklad lineárního posuvného registru

Pro sestavení proudových šifer se velmi často používají sekvence na posuvných registrech. Zpětnovazební posuvný registr se skládá ze dvou částí: posuvného registru a zpětnovazební funkce, jak je znázorněno na obr. 87. Samotný posuvný registr je posloupnost bitů, jejichž počet určuje délku registru. Pokud je tedy v registru zahrnuto n bitů, pak říkají, že n-bitový posuvný registr. Pokaždé, když je bit načten, všechny bity posuvného registru se posunou doprava o jednu pozici, obvykle směrem k nejméně významným bitům. Perioda posuvného registru je délka výsledné sekvence, než se začne opakovat.

Rýže. 87.

Jakákoli matematická funkce, která provádí operaci s bity, může fungovat jako zpětná vazba. Nejjednodušším typem zpětnovazebního posuvného registru je lineární zpětnovazební posuvný registr (LFSR). V LFSR je zpětná vazba jednoduše operace sčítání modulo 2 (XOR) na některých bitech registru; seznam těchto bitů se nazývá posloupnost odboček nebo sběrných bodů, jak je znázorněno na Obr. 88. Někdy se takovému vzoru říká Fibonacciho konfigurace. Díky jednoduchosti zpětnovazební sekvence lze k analýze LFSR použít poměrně rozvinutou matematickou teorii. V každém případě je kvalita vyrobeného RRD hodnocena speciální sadou testů.

Rýže. 88.

LFSR jsou psány ve formě polynomů. V tomto případě stupeň prvního prvku polynomu udává počet bitů v posuvném registru a exponenciální exponenty zbývajících členů polynomu udávají, které snímací body budou použity. Takže například zápis x 4 + x + 1 znamená, že bude použit registr čtyř prvků, u kterých se bity bi a b 0 budou podílet na tvorbě zpětné vazby (obr. 89).

Rýže. 89,4

Zvažte činnost registru znázorněného na obr. 89. Inicializujte jej např. hodnotou 0101 (počáteční inicializaci lze provést libovolnou sekvencí bitů kromě sekvence pouze nul, protože v tomto případě bude zpětná vazba vždy tvořit hodnotu nula a registr bude neprodukují očekávané PSP). Takže v registru je posun o jednu pozici doprava. Nejméně významný bit, rovný 1, je vytlačen z registru a tvoří první bit PRS. Ty bity, které byly v pozicích b a b 0 před posunem, jsou přidány modulo 2 a tvoří nový

vysoký bit registru. Názorný příklad činnosti uvažovaného LFSR je na Obr. 90.

Rýže. 90.

Jak je patrné z Obr. 90, výplň registru projde váhou 15 z 16 možných stavů (dříve jsme určili, že šestnáctý stav, kdy LFSR je 0000, nelze uvažovat). Poté se zaplnění registru bude opět rovnat počáteční hodnotě 0101 a generování bitové sekvence se začne opakovat. Výstupní sekvencí registru bude řetězec nejméně významných bitů (až po vodorovnou čáru na obr. 90): 101011110001001. Velikost bitové sekvence před jejím opakováním se nazývá perioda. Aby byla zajištěna maximální perioda konkrétního LFSR (tj. aby registr prošel všemi možnými vnitřními stavy), musí být polynom, který určuje činnost registru, primitivní modulo 2. Stejně jako u velkých prvočísel neexistuje způsob, jak vytvářet takové polynomy. Lze pouze vzít polynom a zkontrolovat, zda je neredukovatelný modulo 2 nebo ne. V obecném případě je primitivní polynom stupně n takový ireducibilní polynom, který je dělitelem x 2"+1, ale není dělitelem xd +1 pro všechna d, která jsou děliteli 2"-1. B. Schneier poskytuje tabulku některých polynomů, které jsou neredukovatelné modulo 2.

Shrneme-li poznatky získané jako výsledek uvažování příkladu činnosti LFSR (obr. 90), můžeme říci, že n-bitový LFSR může být v jednom z vnitřních stavů 2”-1. Teoreticky může takový registr generovat pseudonáhodnou sekvenci s periodou 2 n -1 bitů. Takové registry se nazývají registry LFSR s maximální periodou. Výsledný výstup se nazývá t-sekvence.

Ministerstvo školství a vědy

RUSKÁ STÁTNÍ SOCIÁLNÍ UNIVERZITA

FAKULTA INFORMAČNÍCH TECHNOLOGIÍ

ODDĚLENÍ OCHRANY INFORMACÍ

Kryptografické metody a prostředky k zajištění informační bezpečnosti

Práce na kurzu

"R posuvné registry s lineární zpětnou vazbou jako generátory pseudonáhodných čísel“

Dokončeno:

Student 3. ročníku

Skupina KZOI-D-3

Larionov I.P.

Kontrolovány:

Doc. Baranová E.K.

Moskva 2011
OBSAH

Úvod ……………………………..…………………………………….3

Teoretické základy práce…………………………………………4
1. Obecné informace o zpětnovazebních posuvných registrech…………..4
  1. O proudových šifrách založených na RgCsLOS……………………….………10
  2. O lineární složitosti generované pseudonáhodné sekvence PgCsLOS…………………………………….……12
  3. O korelační nezávislosti generované sekvence pseudonáhodných čísel PrCsLOS………..….13
  4. O jiných způsobech otevření vygenerované sekvence pseudonáhodných čísel RgCsLOS…………………………………………..14
Softwarová implementace RgCsLOS jako generátoru pseudonáhodné posloupnosti….…………………………….15
1. Zobecněné schéma algoritmu………………………………………......15
2. Popis softwarových modulů a rozhraní.……………….16
3. Návod k použití ……………………………………… 20

Závěr ………………………………………………………………22

Bibliografie………………………………………………….....23

Příloha A ….………………………………………………………..24

ÚVOD

Účelem této práce je vyvinout softwarovou aplikaci, která implementuje činnost generátoru pseudonáhodných čísel na bázi posuvných registrů se zpětnou vazbou. Vývoj této aplikace s grafickým rozhraním probíhá v jazyce C++ pro OS Windows.

S rozvojem kryptografie ve 20. století byli kryptografové postaveni před úkol vytvořit šifrovací zařízení a stroje, které by dokázaly rychle a spolehlivě šifrovat a dešifrovat zprávy. Symetrické šifrovací systémy již v té době otevřené tento požadavek splňovaly, ale jejich slabou stránkou byla silná závislost na klíči a jeho utajení. Nejvhodnější třídou šifer, kterou lze pro tento účel použít, jsou herní šifry. Problém nastal s generováním gama, které nebylo možné detekovat při dešifrování zprávy. Teoreticky to bylo možné, pokud by gama byla pokaždé náhodná a měnila se v průběhu času. Při použití zcela náhodně se měnícího gama by však bylo obtížné zajistit spolehlivé šifrování-dešifrování zprávy. Kryptografové se chopili úkolu vyřešit tento problém, jehož účelem bylo najít algoritmus, který implementuje generování náhodného rozsahu podle určitého pravidla, taková sekvence by měla obsahovat nuly a jedničky na „domněle“ náhodných pozicích a počet jedniček a nul by měl být přibližně stejný. Tato náhodná sekvence se nazývápseudonáhodnéprotože byl generován podle určitého pravidla a ne náhodně.

Řešení bylo brzy nalezeno. Studium vlastností posuvných registrů umožnilo zjistit, že zpětnovazební posuvné registry jsou schopny generovat pseudonáhodné sekvence, které jsou díky své vnitřní struktuře dostatečně odolné vůči dekódování.

1.Teoretické základy práce

1.1 Obecné informace o posuvných registrech s lineární zpětnou vazbou

Sekvence posuvných registrů se používají jak v kryptografii, tak v teorii kódování. Jejich teorie je dobře rozvinutá, proudové šifry založené na posuvných registrech byly tahounem vojenské kryptografie dlouho před příchodem elektroniky.

Zpětnovazební posuvný registr (dále jen PgCsOS) se skládá ze dvou částí: posuvného registru a zpětné vazby.Posuvný registr je posloupnost bitů. Počet bitů je určendélka posuvného registru, pokud je délka n bitů, pak se zavolá registrn-bitový posuvný registr. Kdykoli je potřeba extrahovat bit, všechny bity posuvného registru se posunou doprava o 1 pozici. Nový bit nejvíce vlevo je funkcí všech ostatních bitů v registru. Výstupem posuvného registru je jeden, obvykle nejméně významný bit.Období směnného registruje délka výsledné sekvence, než se začne opakovat.

Obrázek Zpětná vazba Shift Register

Posunovací registry rychle našly použití v proudových šifrách, protože byly snadno implementovány pomocí digitálního hardwaru. V roce 1965 Ernst Selmer, hlavní kryptograf norské vlády, vyvinul teorii sekvence posuvného registru. Solomon Golomb, matematik NSA, napsal knihu, ve které nastínil některé jeho výsledky a výsledky Selmera. Nejjednodušší typ zpětnovazebního posuvného registru jelineární zpětnovazební posuvný registr ( lineární zpětnovazební posuvný registr, dále jen LFSR nebo RgCsLOS) . Zpětná vazba takových registrů je jednoduše XOR (modulo two add) některých bitů registru, seznam těchto bitů se nazývá tap sekvence. Někdy se takový registr nazývá Fibonacciho konfigurace. Díky jednoduchosti zpětnovazební sekvence lze k analýze PgCsLOC použít poměrně rozvinutou matematickou teorii. Analýzou výsledných výstupních sekvencí můžete ověřit, že tyto sekvence jsou dostatečně náhodné, aby byly bezpečné. Posuvné registry se v kryptografii používají častěji než jiné posuvné registry.

Obrázek PgCsLOS Fibbonacci

Obecně platí, že n -bit PrCsLOS může být v jednom z N=2n -1 vnitřní stavy. To znamená, že teoreticky může takový registr generovat pseudonáhodnou sekvenci s periodou T=2 n -1 bit. (Počet vnitřních stavů a perioda jsou stejné N=Tmax=2n -1, protože vyplnění PrCsLOC nulami způsobí, že posuvný registr vydá nekonečnou sekvenci nul, což je naprosto zbytečné). Pouze s určitými sekvencemi odboček bude PrCsLOS cyklicky procházet všemi 2 n -1 vnitřní stavy, jako jsou RgCsLOSRgSsLOS s maximální periodou. Výsledný výsledek se nazýváM-sekvence.

Příklad . Obrázek níže ukazuje 4bitový PrCsLOS s odbočkou z prvního a čtvrtého bitu. Pokud je inicializován hodnotou 1111, pak před opakováním nabude registr následující vnitřní stavy:

Číslo Shift tick (interní stav)	Stav registrace	výstupní bit
Číslo Shift tick (interní stav)		výstupní bit
Počáteční hodnota














15 (návrat do původního stavu)
16 (opakované stavy)

Výstupní sekvence bude řetězec nejméně významných bitů: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 s periodou T=15, celkový počet možných vnitřních stavů (kromě nuly), N=24-1=16-1=15= Tmax , proto je výstupní sekvence M -sekvence.

Aby měl konkrétní PgCsLOS maximální periodu, musí být polynom vytvořený z odbočovací sekvence a konstanta 1 primitivní modulo 2. Polynom je reprezentován jako součet mocnin, například polynom stupně n vypadá takto:

anxn +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =anxn +a n-1 x n-1 +…+a 1 x+a 0 , kde a i =(0, 1 ) pro i=1…n, axi – označuje bit .

Stupeň polynomu je délka posuvného registru. Primitivní polynom stupně n je ireducibilní polynom, který je dělitelem x 2n−1 +1, ale není dělitelem x d +1 pro všechna d jsou dělitelé 2 n -jeden. Odpovídající matematickou teorii lze nalézt v .

Obecně neexistuje snadný způsob, jak generovat primitivní polynomy daného stupně modulo 2. Nejjednodušší způsob je vybrat polynom náhodně a zkontrolovat, zda je primitivní. Není to snadné a je to trochu jako kontrola, zda náhodně vybrané číslo není prvočíslo - ale mnoho matematických softwarových balíků může tento problém vyřešit.

Některé, ale rozhodně ne všechny, polynomy různých stupňů, primitivní modulo 2, jsou uvedeny níže. Například vstup

(32, 7, 5, 3, 2, 1, 0) znamená, že následující polynom je primitivní modulo 2: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

To lze snadno zobecnit na PrCcLOC s maximální periodou. První číslo je délka PrCsLOS. Poslední číslo je vždy 0 a lze jej vynechat. Všechna čísla kromě 0 určují sekvenci klepnutí, počítanou od levého okraje posuvného registru. To znamená, že členy polynomu s nižším stupněm odpovídají pozicím blíže pravému okraji registru.

Pokračujeme-li v příkladu, zápis (32, 7, 5, 3, 2, 1, 0) znamená, že pro daný 32bitový posuvný registr je generován nový bit XORingem třicáté sekundy, sedmé, páté, třetí, druhé a první bity, výsledný RgCsLOS bude mít maximální délku a bude se cyklicky opakovat po 2 32 -1 hodnoty.

Obrázek 4 32bitový PrCsLOS s maximální délkou

Uvažujme programový kód PgCsLOS, ve kterém je tap sekvence charakterizována polynomem (32, 7, 5, 3, 2, 1, 0). V jazyce C to vypadá takto:

int LFSR()(

static unsigned long ShiftRegister = 1;

/* Všechny kromě 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

vrátit ShiftRegister & 0 x 00000001;)

Pokud je posuvný registr delší než počítačové slovo, kód se zkomplikuje, ale ne o mnoho. V aplikaci B je uvedena tabulka některých primitivních polynomů modulo 2, použijeme ji později k identifikaci některých vlastností těchto polynomů a také v softwarové implementaci k nastavení sekvence tapů.

Je třeba poznamenat, že všechny prvky tabulky mají lichý počet koeficientů. Takto dlouhá tabulka je určena pro další práci s PrCfLOC, protože PrCfLOC se často používá pro kryptografii s proudovými šiframi a v generátorech pseudonáhodných čísel. V našem případě můžeme použít polynomy s nejvyšším stupněm nejvýše sedm.

Je-li p(x) primitivní, pak je i x n p(1/x), takže každý prvek tabulky ve skutečnosti definuje dva primitivní polynomy. Pokud je například (a, b, 0) primitivní, pak je primitivní také (a, a-b, 0). Pokud je (a, b, c, d, 0) primitivní, pak je primitivní také (a, a-d, a-c, a-b, 0). Matematicky:

je-li x primitivní a+xb +1, pak je primitivní a x a+x a-b+1,

je-li x primitivní a + x b + x c + x d +1, pak je primitivní a x a + x a-d + x a-c + x a-b +1. Programově se nejrychleji implementují primitivní trinomy, protože pro vygenerování nového bitu potřebujete XOR pouze dva bity posuvného registru (nebere se v úvahu nulový člen, tj. x 0 =1, viz příklad výše). Všechny zpětnovazební polynomy uvedené v tabulce jsou skutečně řídké, to znamená, že mají málo koeficientů. Sparita je vždy zdrojem slabosti, což někdy stačí k otevření algoritmu. Pro kryptografické algoritmy je mnohem lepší používat husté primitivní polynomy, ty, které mají mnoho koeficientů. Použitím hustých polynomů, zejména jako součásti klíče, lze použít mnohem kratší PrCcLOC.

Generování hustých primitivních polynomů modulo 2 není snadné. V obecném případě, abychom mohli generovat primitivní polynomy stupně k, potřebujeme znát faktorizaci čísla 2 k-1.

PgCsLOS jsou samy o sobě dobrými generátory pseudonáhodných sekvencí, ale mají některé nežádoucí nenáhodné (deterministické) vlastnosti. Sekvenční bity jsou lineární, takže jsou pro šifrování nepoužitelné. Pro PgCsLOS délky n je vnitřním stavem předchozích n výstupních bitů generátoru. I když je schéma zpětné vazby utajeno, lze jej určit z 2n výstupních bitů generátoru pomocí vysoce účinného Berlekamp-Masseyho algoritmu.

Navíc velká náhodná čísla generovaná pomocí po sobě jdoucích bitů této sekvence jsou vysoce korelovaná a pro některé typy aplikací nejsou náhodná vůbec. Navzdory tomu se PrCsLOS často používají k vytváření šifrovacích algoritmů jako součásti systémů a šifrovacích algoritmů.

1.2 O proudových šifrách založených na RgCsLOS

Základní přístup k návrhu generátoru keystreamu založeného na PrCsLOS je jednoduchý. Nejprve se vezme jeden nebo více PrCsLOS, obvykle s různými délkami a různými polynomy zpětné vazby. (Pokud jsou délky coprime a všechny zpětnovazební polynomy primitivní, pak bude mít výsledný generátor maximální délku.) Klíčem je počáteční stav registrů PrCcLOC. Pokaždé, když je potřeba nový bit, posuňte registry PrCsLOS o bit (někdy nazývané taktování). Výstupní bit je funkcí, přednostně nelineární, některých bitů registrů PrCsLOC. Tato funkce se nazývá kombinační funkce a generátor jako celek se nazývá kombinační generátor. (Pokud je výstupní bit funkcí jednoho PgCsLOS, pak se oscilátor nazývá oscilátor filtru.) Velká část teorie za těmito druhy zařízení byla vyvinuta Selmerem a Nealem Zierlerem. Můžete zavést řadu komplikací. V některých generátorech se pro různé PgCsLOS používají různé hodinové frekvence, někdy frekvence jednoho generátoru závisí na výstupu druhého. Toto jsou všechny elektronické verze myšlenek šifrovacích strojů z doby před druhou světovou válkou nazývaných oscilátory řízené hodinami ( generátory řízené hodinami ). Řízení hodin může být dopředné, kdy výstup jednoho PgSsLOS řídí rychlost hodin druhého PgSsLOS, nebo se zpětnou vazbou, kdy výstup jednoho PgSsLOS řídí vlastní hodiny. Zatímco všechny tyto generátory jsou citlivé, alespoň teoreticky, na vnořené útoky a pravděpodobné korelace, mnohé z nich jsou stále bezpečné.

Ian Cassells, bývalý předseda čisté matematiky v Cambridge a kryptoanalytik v Bletchly Park, řekl, že „kryptografie je směsí matematiky a zmatku a bez zmatku může být matematika použita proti vám“. Měl na mysli, že v proudových šifrách jsou určité matematické struktury, jako je PrCcLOC, potřeba k zajištění maximální délky a dalších vlastností, ale musí být zavedena nějaká složitá nelineární nepořádek, aby se zabránilo tomu, že někdo získá obsah registru a prolomí jej. algoritmu. Tato rada platí také pro blokové algoritmy.

Většina skutečných proudových šifer je založena na PrCsLOS. Dokonce i v počátcích elektroniky bylo snadné je postavit. Posuvný registr není nic jiného než pole bitů a zpětná vazba je sada hradel XOR. I při použití VLSI poskytuje proudová šifra založená na PrCsLOS značné zabezpečení pomocí několika logických hradel. Problémem PgCsLOS je, že jejich softwarová implementace je velmi neefektivní. Musíte se vyhnout polynomům s řídkou zpětnou vazbou – usnadňují korelační útoky – a polynomy s hustou zpětnou vazbou jsou neefektivní.

Toto odvětví kryptografie rychle roste a je pod bedlivou vládní kontrolou NSA . Většina vývoje je klasifikována - mnoho vojenských šifrovacích systémů, které se dnes používají, je založeno na PrCsLOS. Ve skutečnosti má většina počítačů Cray (Cray 1, Cray X-MP, Cray Y-MP) velmi zajímavou instrukci běžně označovanou jako „počet populace“. Počítá počet 1s v registru a lze jej použít jak k efektivnímu výpočtu Hammingovy vzdálenosti mezi dvěma binárními slovy, tak k implementaci vektorizované verze PrCcLOC. Tato instrukce je považována za kanonickou instrukci NSA a objevuje se téměř ve všech počítačových smlouvách.

Na druhou stranu bylo napadeno překvapivě velké množství zdánlivě složitých generátorů posuvných registrů. A samozřejmě, počet takových generátorů hacknutých vojenskými kryptoanalytickými institucemi, jako je NSA, je ještě větší.

1.3 O lineární složitosti generované sekvence pseudonáhodných čísel PrCsLOS

Proudové šifry se často analyzují snadněji než blokové šifry. Například důležitým parametrem používaným k analýze generátorů založených na PgCsLOC je lineární složitost neboli lineární interval. Je definována jako délka n nejkratšího PrCsLOS, který může simulovat výstup generátoru. Jakákoli sekvence generovaná konečným automatem nad konečným polem má konečnou lineární složitost. Lineární složitost je důležitá, protože pomocí jednoduchého algoritmu zvaného Berlekamp-Masseyův algoritmus lze tento PrCcLOC určit zkoumáním pouze 2n bitů klíčového proudu. Opětovným vytvořením požadovaného PrCsLOS prolomíte proudovou šifru.

Tuto myšlenku lze rozšířit z polí na kruhy a na případy, kdy je výstupní sekvence považována za čísla v poli s lichou charakteristikou. Další rozšíření vede k zavedení konceptu lineárního profilu složitosti, který určuje lineární složitost sekvence při jejím prodlužování. Existují také koncepty sférické a kvadratické složitosti. V každém případě je třeba mít na paměti, že vysoká lineární složitost nemusí nutně zaručovat bezpečnost generátoru, ale nízká lineární složitost ukazuje na nedostatečnou bezpečnost generátoru.

1.4 O korelační nezávislosti generované sekvence pseudonáhodných čísel PrCsLOS

Kryptografové se snaží získat vysokou lineární složitost kombinováním výsledků některých výstupních sekvencí nelineárním způsobem. Nebezpečí zde spočívá v tom, že jednu nebo více vnitřních výstupních sekvencí – často jen výstupy jednotlivých PrCsLOC – lze propojit společným proudem klíčů a odhalit pomocí lineární algebry. Často se takové zúčtování nazývá korelační zúčtování nebo zúčtování rozděl a panuj. Thomas Siegenthaler ukázal, že korelační nezávislost lze přesně definovat a že existuje kompromis mezi korelační nezávislostí a lineární složitostí.

Hlavní myšlenkou korelačního otevření je najít nějakou korelaci mezi výstupem generátoru a výstupem jedné z jeho součástí. Potom lze pozorováním výstupní sekvence získat informace o tomto mezivýstupu. Pomocí těchto informací a dalších korelací lze shromažďovat další mezivýstupy, dokud není generátor hacknut.

Korelační útoky a jejich variace, jako jsou rychlé korelační útoky, byly úspěšně použity proti mnoha generátorům klíčových proudů založených na PrCsLOC, které nabízejí kompromis mezi výpočetní složitostí a efektivitou.

1.5 O dalších způsobech otevření vygenerované sekvence pseudonáhodných čísel PgCsLOS

Existují další způsoby, jak rozbít generátory klíčových proudů. Test lineární konzistence se snaží najít nějakou podmnožinu šifrovacího klíče pomocí maticové techniky. Existuje také konzistenční útok na správnost setkání. Algoritmus lineárního syndromu je založen na schopnosti zapsat fragment výstupní sekvence jako lineární rovnici. Existuje útok s nejlepší afinní aproximací a útok odvozené sekvence. Metody diferenciální a lineární kryptoanalýzy lze také aplikovat na proudové šifry.

2. Popis softwarové implementace PrCsLOS jako generátoru pseudonáhodné posloupnosti

2.1 Zobecněné schéma algoritmu

2.2 Popis softwarových modulů a rozhraní

Obrázek 3 níže ukazuje okno programu.

Obrázek Rozhraní programu

Nabídka má následující funkce:

Soubor->Uložit zprávu

Tato funkce vygeneruje soubor reportu, kde se zapíše počáteční stav PrCsLOS, sekvence tap, perioda přijaté pseudonáhodné bitové sekvence, samotná sekvence a tabulka stavů. Pokud byl soubor úspěšně uložen, zobrazí se zpráva o úspěšném uložení (obrázek 4). Doporučená přípona souboru pro sestavu je *. txt.

Výkres

Soubor->Konec

Tato funkce zajišťuje uzavření aplikace.

Nastavte sekvenci escape

Tato funkce generuje sekvenci klepnutí načtením hodnot z buněk, které uživatel zaškrtl ve formuláři obrazovky. Poté upozorní uživatele na vytvoření sekvence klepnutí (obrázek 5). Sekvence tap určuje, které klopné obvody posuvného registru obdrží zpětnou vazbu. XOR k vytvoření ofsetového bitu. Standardně je zpětná vazba od prvního spouštěče vždy zapnutá, při absenci dalších spojení se provede posun doleva se změnou nejméně významného bitu na pozici nejvýznamnějšího.

Výkres

Nastavte počáteční hodnotu

Tato funkce čte z okna počáteční hodnotu registru zadanou uživatelem Upravit 1 a zkontroluje zadanou hodnotu podle zadaných podmínek: zadaný řetězec je neprázdný (obrázek 6), zadaný řetězec má délku osm (8bit=1byte, obrázek 7), zadaný řetězec obsahuje pouze nuly a/nebo jedniček (obrázek 8), zadaný řetězec je nenulový (obrázek 9). V opačném případě se zobrazí chybová hlášení, uživatel je musí opravit a znovu stisknout tlačítko. V případě úspěšné kontroly bude počáteční hodnota zapsána do stavové tabulky v řádku "Počáteční" a bude vydáno upozornění (obrázek 10).

Výkres

Proveďte posun registru

Tato funkce emuluje činnost posuvného registru. Postupným provedením 256 posunů každý posun generuje výstupní bit pseudonáhodné sekvence a nový stav registru. Jakmile je stav registru roven počátečnímu, je vypočítána perioda a zobrazena v poli poznámka 1 přijatá pseudonáhodná sekvence.

Nápověda-> O aplikaci

Tato funkce zobrazuje stručný popis programu a pokyny (obrázek 11).

Výkres

Nápověda-> O autorovi

Tato funkce zobrazuje informace o autorovi programu (obrázek 12).

Výkres

2.3 Uživatelská příručka

Nejprve nastavte počáteční stav registru. Musí obsahovat osm binárních znaků. V opačném případě se zobrazí chybové hlášení a zadanou hodnotu budete muset opravit. Stiskněte položku nabídky "Nastavit počáteční hodnotu".
Poté zaškrtněte políčka pro registraci zpětné vazby (klepněte na Sekvence). Stiskněte položku nabídky "Set Tap Sequence".
Dále klikněte na položku nabídky "Register Shift". Než to uděláte, ujistěte se, že jste dokončili kroky 1 a 2, jinak dojde k chybě softwaru.
Po obdržení výsledků je můžete uložit kliknutím na položku nabídky "Soubor->Uložit zprávu". Než to uděláte, ujistěte se, že jste dokončili kroky 1-3, jinak dojde k chybě softwaru.
Chcete-li získat nápovědu, klikněte na položky nabídky „Soubor->O“, „Soubor->O autorovi“.
Chcete-li vidět činnost registru s jinými hodnotami sekvence klepnutí a počátečním stavem registru, opakujte postupně kroky 1-3 a zadejte další parametry.

ZÁVĚR

V tomto článku byly RgCsLOS považovány za generátory pseudonáhodných čísel. Program může sloužit jako názorná ukázka principů činnosti posuvných registrů se zapnutou lineární zpětnou vazbou XOR . Na něm můžete studovat princip tvorby pseudonáhodné sekvence bitů, vztah mezi počáteční hodnotou registru a hodnotou pseudonáhodné sekvence, tap sekvence a perioda. Výsledná pseudonáhodná gama může být použita v jiné softwarové aplikaci (například softwarová implementace gama šifry).

Tyto registry se dodnes nepoužívají jako nezávislé generátory pseudonáhodných čísel, ale jsou součástí složitějších zařízení. Byli to však oni, kdo otevřel nové směry v matematice (hledání primitivních polynomů v konečných tělesech, matematické metody pro rozbití generátorů pseudonáhodných čísel). Bez znalosti principů činnosti generátorů na RgCsLOS nelze pochopit činnost složitějších zařízení. Díky jejich jednoduché hardwarové implementaci jsou široce používány v technologii. Výzkum PgCsOS vedl ke vzniku nových šifer - blokových a streamových - založených na těchto typech registrů (posuvná permutační šifra, DES atd.; EDS, hashovací funkce).

Obecně výzkum v této oblasti vážně urychlil rozvoj kryptografie a kryptoanalytiků, počítačů a zařízení a také umožnil implementovat řadu dalších užitečných funkcí (například opravy cyklických kódů).

BIBLIOGRAFIE

Schneier Bruce. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C. - M.: Triumph, 2002
Babash A.V. Kryptografické a automatově teoretické aspekty moderní informační bezpečnosti. Svazek 1 - M .: Ed. Centrum EAOI, 2009. - 414 s.
E.S. Selmer. Monografie: "Lineární rekurze v konečném poli". Univerzita v Bergenu, Norsko, 1966.
N. Zierler a J. Brillhart. "On Primitive Trinomials Modulo 2", Journal of Information and Control, svazek 13 č. 6. prosince 1968, str. 541-544.
K.Kh. Meyer a W. L. Tuchman. "Pseudonáhodné kódy lze prolomit," Electronic Design Magazine, no. 23. listopadu 1972.
J. L. Massey. „Zobecnění posuvných registrů a dekódování kódu Bose-Chowdhury-Hokvingham“, IEEE Transactions on Information Theory, v. IT-15, n . 1, leden 1969, s. 122-127.
S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (přetištěno Aigean Park Press, 1982).

Příloha A

Tabulka některých primitivních polynomů modulo 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Vstup počátečního stavu (IS)

ověření vstupu

Vydání chybové zprávy

Nastavení sekvence poklepání

Záznam IP ve stavové tabulce

Záznam i -tý stavový registr a výstupní bit do stavové tabulky

IS==Současný stav

Ukládání výsledků

Výstup pseudonáhodné sekvence

Výstup

zahájení

Ano

V posuvném registru s lineární zpětnou vazbou se rozlišují dvě části (moduly): samotný posuvný registr a obvod (nebo podprogram), který vypočítává hodnotu vkládaného bitu. Registr se skládá z funkčních buněk (nebo bitů strojového slova nebo několika slov), z nichž každá ukládá aktuální stav jednoho bitu. Počet buněk se nazývá délka registru. Bity (buňky) jsou obvykle číslovány čísly, z nichž každé je schopno uložit bit a vypočítaný bit se vloží do buňky a další vygenerovaný bit se z buňky vytáhne. Výpočet vloženého bitu se obvykle provádí před posunem registru a teprve po posunu se do buňky umístí hodnota vypočítaného bitu.

Perioda posuvného registru je minimální délka výsledné sekvence, než se začne opakovat. Protože registr bitových buněk má pouze různé nenulové stavy, pak v zásadě perioda registru nemůže překročit toto číslo. Pokud je perioda registru rovna tomuto číslu, pak se takový registr nazývá registr maximální periody.

Pro LFSR je zpětnovazební funkce lineární booleovská funkce stavů všech nebo některých bitů registru. Například součet modulo dva nebo jeho logická inverze je lineární booleovská funkce (operace XOR, označovaná jako ve vzorcích) a v takových registrech se používá nejčastěji.

V tomto případě se obvykle volají ty bity, které jsou proměnnými funkce zpětné vazby zatáčky.

Řízení registru v hardwarových implementacích se provádí aplikací posuvného impulsu (jinak nazývaného hodiny nebo synchronizační puls) do všech buněk, softwarově - provedením programového cyklu včetně výpočtu zpětnovazební funkce a bitového posunu ve slově.

Během každého tikání hodin se provádějí následující operace:

Posunový registr s lineární zpětnou vazbou

Logická operace XOR (exkluzivní OR) je tedy brána jako funkce zpětné vazby, to znamená:

Vlastnosti primitivních polynomů

Vlastnosti

Vlastnosti sekvence produkované LFSR úzce souvisí s vlastnostmi asociovaného polynomu. Jeho nenulové koeficienty se nazývají zatáčky a také odpovídající buňky registru, které dodávají hodnoty argumentů funkce zpětné vazby.

Lineární složitost

Lineární složitost binární sekvence je jednou z nejdůležitějších charakteristik provozu LFSR. Představme si následující zápis:

Definice

Lineární složitost nekonečné binární posloupnosti se nazývá číslo, které je definováno takto:

Lineární složitost konečné binární posloupnosti se nazývá číslo , které se rovná délce nejkratšího LFSR, který generuje posloupnost, která má jako první členy .

Vlastnosti lineární složitosti

Nechť a být binární posloupnosti. Pak:

Korelační nezávislost

Aby získali vysokou lineární složitost, kryptografové se snaží nelineárně kombinovat výsledky více výstupních sekvencí. V tomto případě je nebezpečí, že jednu nebo více výstupních sekvencí (často i výstupy jednotlivých LFSR) lze propojit společným klíčem a otevřít pomocí lineární algebry. Hackování založené na takové zranitelnosti se nazývá korelační pitva. Thomas Siegenthaler ukázal, že korelační nezávislost lze přesně definovat a že existuje kompromis mezi korelační nezávislostí a lineární složitostí.

Hlavní myšlenkou tohoto hacku je najít nějakou korelaci mezi výstupem generátoru a výstupem jedné z jeho součástí. Potom lze pozorováním výstupní sekvence získat informace o tomto mezivýstupu. Pomocí těchto informací a dalších korelací je možné sbírat data o dalších mezivýstupech, dokud není generátor hacknut.

Korelační útoky nebo variace, jako jsou rychlé korelační útoky, byly úspěšně použity proti mnoha generátorům keystreamu založených na lineárních zpětnovazebních posuvných registrech, které zahrnují kompromis mezi výpočetní složitostí a účinností.

Příklad

Pro LFSR s přidruženým polynomem má vygenerovaná sekvence tvar . Předpokládejme, že před začátkem procesu je sekvence zapsána do registru, pak bude perioda generovaného bitového toku rovna 7 s následující sekvencí:

Číslo kroku	Stát	Vygenerován bit
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Protože se vnitřní stav v sedmém kroku vrátil do původního stavu, počínaje dalším krokem dojde k opakování. Jinými slovy, perioda posloupnosti se ukázala být rovna 7, což se stalo díky primitivnosti polynomu.

Algoritmy pro generování primitivních polynomů

Připravené stoly

Výpočet primitivnosti polynomu je poměrně složitý matematický problém. Proto existují hotové tabulky, které vypisují počty odbočovacích sekvencí, které poskytují maximální periodu generátoru. Například pro 32bitový posuvný registr existuje sekvence . To znamená, že pro vygenerování nového bitu je nutné sečíst 31., 30., 29., 27., 25. a 0. bit pomocí funkce XOR. Kód pro takový LFSR v jazyce C je následující:

Int LFSR (void) ( statické bez znaménka dlouhé S = 1; S = ((((S>> 31) ^ (S>> 30) ^ (S>> 29) ^ (S>> 27) ^ (S>> 25) ^ S) & 1)<< 31 ) | (S>> 1); návrat S & 1 ; )

Softwarové implementace generátorů RSLOS jsou poměrně pomalé a pracují rychleji, pokud jsou napsány v assembleru spíše než v C. Jedním z řešení je použít 16 RLLS paralelně (nebo 32, v závislosti na délce slova v architektuře konkrétního počítače). V takovém schématu se používá pole slov, jehož velikost se rovná délce LFSR a každý bit slova pole odkazuje na jeho LFSR. Za předpokladu, že se použijí stejná sekvenční čísla odboček, může to přinést znatelné zvýšení výkonu. [potřebujete ukázkový kód] (Viz: bitslice).

Konfigurace Galois

Galoisova konfigurace lineárního zpětnovazebního posuvného registru

Schéma zpětné vazby lze také upravit. V tomto případě generátor nebude mít větší kryptografickou sílu, ale bude jednodušší jej programově implementovat. Namísto použití bitů sekvence odboček ke generování nového bitu nejvíce vlevo, XOR každý bit sekvence odbočení s výstupem generátoru a jeho nahrazením výsledkem této akce, pak se výsledek generátoru stane novým bitem nejvíce vlevo. . V jazyce C to vypadá takto:

Int LFSR (void) ( statické bez znaménka dlouhé Q = 1; Q = (Q>> 1) ^ (Q& 1? 0x80000057: 0); návrat Q & 1;

Výhodou je, že všechny XOR se provádějí v jedné operaci.

lze dokázat, že Fibonacciho konfigurace uvedená jako první a zde uvedená Galoisova konfigurace dávají stejné sekvence (o délce 2 32 −1), ale fázově posunuté jedna od druhé
smyčka pevného počtu volání funkce LFSR v konfiguraci Galois je přibližně dvakrát rychlejší než v konfiguraci Fibonacci (kompilátor MS VS 2010 na Intel Core i5)
všimněte si, že v konfiguraci Galois je pořadí bitů ve slově zpětné vazby obrácené ve srovnání s konfigurací Fibonacci

Příklady generátorů

stop-go generátory

Střídavý generátor Stop-and-Go

Tento oscilátor využívá výstup jednoho LFSR k řízení hodinového kmitočtu jiného LFSR. Hodinový výstup RSLOS-2 je řízen výstupem RSLOS-1, takže RSLOS-2 může změnit svůj stav v čase t pouze v případě, že výstup RSLOS-1 v čase t-1 byl roven jedné. Toto schéma však otevření korelace neodolalo.

Proto byl navržen vylepšený generátor založený na stejné myšlence. Říká se tomu prokládaný generátor stop-and-go. Používá tři LFSR různých délek. LFSR-2 je taktován, když je výstup LFSR-1 roven jedné, a LFSR-3, když je výstup LFSR-1 roven nule. Výstupem generátoru je modulo 2 součet RSLOS-2 a RSLOS-3. Tento generátor má velkou periodu a velkou lineární složitost. Jeho autoři také ukázali metodu pro otevření korelace RLOS-1, ale to příliš neoslabuje generátor.

Kaskáda Gollmann

Gollmann Cascade je vylepšená verze stop-go generátoru. Skládá se ze sekvence LFSR, časování každého z nich je řízeno předchozím LFSR. Pokud je výstup LFSR-1 v čase t 1, pak je LFSR-2 taktován. Pokud je výstup LFSR-2 v čase t 1, pak je LFSR-3 taktován a tak dále. Výstupem posledního LFSR je výstup generátoru. Pokud je délka všech LFSR stejná a rovná se n, pak lineární složitost systému k LFSR je .

Tato myšlenka je jednoduchá a lze ji použít ke generování sekvencí s velkými periodami, velkou lineární složitostí a dobrými statistickými vlastnostmi. Ale bohužel jsou náchylné k otevření, nazývanému "uzamčení" (lock-in). Pro větší stabilitu se doporučuje použít k alespoň 15. Navíc je lepší použít kratší LFSR než méně dlouhé LFSR.

prahový generátor

Tento generátor se pokouší obejít bezpečnostní problémy předchozích generátorů pomocí proměnného počtu posuvných registrů. Teoreticky při použití většího počtu posuvných registrů narůstá složitost šifry, což bylo provedeno v tomto generátoru.

Tento generátor se skládá z velkého množství posuvných registrů, jejichž výstupy jsou přiváděny do majorizační funkce. Pokud je počet jednotek na výstupech registrů více než poloviční, pak generátor vyrábí jednotku. Pokud je počet nul na výstupech větší než polovina, pak generátor vytvoří nulu. Aby bylo možné porovnání počtu nul a jedniček, musí být počet posuvných registrů lichý. Délky všech registrů musí být relativně prvočísla a zpětnovazební polynomy musí být primitivní, aby perioda generované sekvence byla maximální.

V případě tří posuvných registrů může být generátor reprezentován jako:

Tento generátor je podobný generátoru Geff, kromě toho, že generátor prahů má lineárnější složitost. Jeho lineární složitost je:

kde , , jsou délky prvního, druhého a třetího posuvného registru.

Jeho nevýhodou je, že každý výstupní bit dává nějakou informaci o stavu posuvného registru. Přesněji 0,189 bitu. Proto tento generátor nemusí odolávat otevření korelace.

Jiné typy

Samoředění

Samoklesající generátory se nazývají generátory, které řídí vlastní frekvenci. Byly navrženy dva typy takových generátorů. První se skládá z posuvného registru s lineární zpětnou vazbou a nějakého obvodu, který tento registr taktuje, podle toho, jaké jsou výstupní hodnoty posuvného registru. Pokud je výstup LFSR roven jedné, pak je registr taktován d krát. Pokud je výstup nulový, pak je registr taktován kkrát. Druhý má téměř stejný design, ale je mírně upravený: v taktovacím obvodu se jako kontrola 0 nebo 1 nepřijímá samotný výstupní signál, ale XOR určitých bitů posuvného registru s lineární zpětnou vazbou. Bohužel tento druh generátoru není bezpečný.

Vícerychlostní oscilátor s vnitřním produktem

Tento generátor využívá dva posuvné registry s lineární zpětnou vazbou s různými hodinovými frekvencemi: LFSR-1 a LFSR-2. Hodinová frekvence RLOS-2 je d krát vyšší než frekvence RLLS-1. Jednotlivé bity těchto registrů jsou kombinovány operací AND. Výstupy operace AND jsou pak XORed. Výstupní sekvence je převzata z tohoto bloku XOR. Opět platí, že tento generátor není dokonalý (Nepřežil otevření lineární konzistence. Jestliže - délka LFSR-1, - délka LFSR-2, ad je poměr hodinových frekvencí, pak vnitřní stav generátor lze získat z výstupní sekvence délky ), ale má vysokou lineární složitost a vynikající statistický výkon.

Posuvný registr zpětné vazby se skládá ze dvou částí: posuvného registru a funkce zpětné vazby.

Obrázek 19. Posuvný registr zpětné vazby.

Obecně je posuvný registr posloupnost některých prvků kruhu nebo pole. Nejčastěji používané bit posuvné registry. Délka takového registru je vyjádřena jako počet bitů. Při každém načtení bitu se všechny bity v registru posunou o jednu pozici doprava. Nový nejvýznamnější bit je vypočítán jako funkce všech ostatních bitů v registru. Výstup je obvykle nejméně významný bit. Perioda posuvného registru je délka výstupní sekvence, než se začne opakovat.

Nejjednodušším typem posuvných registrů je posuvný registr s lineární zpětnou vazbou (LFSR nebo LRS). Zpětná vazba je jednoduchá operace XOR na některých bitech registru. Seznam těchto bitů je definován charakteristický polynom a zavolal sekvence klepnutí. Někdy se toto schéma nazývá Fibonacciho konfigurace.

Obr.20. LFOS konfigurace Fibonacci.

V softwarové implementaci LFSR se používá upravené schéma: pro generování nového významného bitu se namísto použití bitů sekvence odboček provede operace XOR na každém z jeho bitů s výstupem generátoru, čímž se nahradí starý bit. bit sekvence tap. Této úpravě se někdy říká Konfigurace Galois.

Obr.21. RLOS konfigurace Galois.

n-bit LFSR může být v jednom ze 2 n– 1 vnitřní stavy. To znamená, že teoreticky může takový registr generovat pseudonáhodnou sekvenci s periodou 2 n– 1 bit (vyplnění nulami je zcela zbytečné). Průchod všech 2 n– 1 vnitřní stavy jsou možné pouze s určitými sekvencemi klepnutí. Takové registry se nazývají LFSR s maximální periodou. Pro zajištění maximální periody LFSR je nutné, aby její charakteristický polynom byl primitivní modulo 2. Stupeň polynomu je délka posuvného registru. Polynom primitivního stupně n- je to tak neredukovatelný polynom, který je dělitel, ale není dělitel xD+ 1 za všechny d, což jsou dělitelé 2 n– 1. (Při probírání polynomů termín prvočíslo nahrazen termínem neredukovatelný polynom). Charakteristický polynom LFSR znázorněný na obrázcích:

X 32 + X 7 + X 5 + X 3 + X 2 + X + 1

je primitivní modulo 2. Perioda takového registru bude maximální a bude procházet všemi 2 32 - 1 hodnotami, dokud se nebudou opakovat. Nejčastěji se používají ztenčené polynomy, tzn. které mají jen některé koeficienty. nejoblíbenější trinomy.

Důležitým parametrem generátoru na bázi LFSR je lineární složitost. Je definována jako délka n nejkratší LFSR, který dokáže simulovat výstup generátoru. Lineární složitost je důležitá, protože s jednoduchým Algoritmus Berlenkamp-Massey je možné znovu vytvořit takový LFSR zaškrtnutím pouze 2 n gama bitů. S definicí požadovaného LFSR je proudová šifra ve skutečnosti prolomena.

Zpětnovazební posuvný registr se skládá ze dvou částí: posuvného registru a zpětnovazební funkce (obrázek 1.2.1). Posuvný registr je posloupnost bitů. (Počet bitů je určen délkou posuvného registru. Pokud je délka n bitů, pak se registr nazývá nbitový posuvný registr.) Kdykoli je potřeba extrahovat bit, všechny bity posuvného registru jsou posunuto doprava o 1 pozici. Nový bit nejvíce vlevo je funkcí všech ostatních bitů v registru. Výstupem posuvného registru je jeden, obvykle nejméně významný bit. Perioda posuvného registru je délka výsledné sekvence, než se začne opakovat.

Rýže. 1.2.1.

Kryptografové měli rádi proudové šifry založené na posuvném registru: bylo snadné je implementovat pomocí digitálního hardwaru. Jen krátce se dotknu matematické teorie. V roce 1965 Ernst Selmer, hlavní kryptograf norské vlády, vyvinul teorii sekvencí posuvných registrů. Solomon Golomb, matematik NSA, napsal knihu, ve které nastínil některé jeho a Selmerovy výsledky.

Nejjednodušším typem zpětnovazebního posuvného registru je lineární zpětnovazební posuvný registr neboli LFSR (obrázek 1.2.2). Zpětná vazba je jednoduše XOR některých bitů v registru, seznam těchto bitů se nazývá tap sekvence. Někdy se takový registr nazývá Fibonacciho konfigurace. Kvůli jednoduchosti sekvence zpětné vazby lze k analýze LFSR použít poměrně pokročilou matematickou teorii. Kryptografové rádi analyzují sekvence a přesvědčují sami sebe, že tyto sekvence jsou dostatečně náhodné, aby byly bezpečné. LFSR se v kryptografii používají častěji než jiné posuvné registry.

Rýže. 1.2.2.

Na Obr. 1.2.3 ukazuje 4bitový LFSR s klepnutím na první a čtvrtý bit. Pokud je inicializován hodnotou 1111, pak před opakováním nabude registr následující vnitřní stavy:

Rýže. 1.2.3. 4

Výstupní sekvence bude řetězec nejméně významných bitů:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

N-bitový LFSR může být v jednom z vnitřních stavů 2n-1. To znamená, že teoreticky může takový registr generovat pseudonáhodnou sekvenci s periodou 2n-1 bitů. (Počet vnitřních stavů a perioda jsou 2n-1, protože zaplnění LFSR nulami způsobí, že posuvný registr bude vydávat nekonečnou sekvenci nul, což je absolutně k ničemu.) Pouze s určitými odbočovacími sekvencemi bude LFSR cyklicky procházet všechny vnitřní stavy 2n-1, takové LFSR jsou LFSR s maximální periodou. Výsledný výsledek se nazývá M-sekvence.

Aby měl konkrétní LFSR maximální periodu, musí být polynom vytvořený z odbočovací sekvence a konstanta 1 primitivní modulo 2. Stupeň polynomu je délka posuvného registru. Primitivní polynom stupně n je ireducibilní polynom, který je dělitelem, ale není dělitelem xd+1 pro všechna d, která jsou děliteli 2n-1.

Obecně neexistuje snadný způsob, jak generovat primitivní polynomy daného stupně modulo 2. Nejjednodušší způsob je vybrat polynom náhodně a zkontrolovat, zda je primitivní. Není to snadné - a trochu jako kontrolovat, zda je náhodně vybrané číslo prvočíslo - ale mnoho matematických softwarových balíků to umí.

Některé, ale rozhodně ne všechny, polynomy různých stupňů jsou primitivní modulo 2. Například zápis (32, 7, 5, 3, 2, 1, 0) znamená, že následující polynom je primitivní modulo 2:

x32 + x7 +x5 + x3 + x2 + x + 1

To lze snadno zobecnit na LFSR s maximální periodou. První číslo je délka LFSR. Poslední číslo je vždy 0 a lze jej vynechat. Všechna čísla kromě 0 určují sekvenci klepnutí, počítanou od levého okraje posuvného registru. To znamená, že členy polynomu s nižším stupněm odpovídají pozicím blíže pravému okraji registru.

Pokračujeme-li v příkladu, zápis (32, 7, 5, 3, 2, 1, 0) znamená, že pro daný 32bitový posuvný registr je generován nový bit XORingem třicáté sekundy, sedmé, páté, třetí, druhé a první bity bude mít výsledný LFSR maximální délku a před iterací bude cyklicky procházet hodnotami 232-1.