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.
Posunovací registr s zpětná vazba sestává ze dvou částí: posuvného registru a zpětné vazby (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ě platí, že neexistuje lehká cesta generujte 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élka, procházením hodnot 232-1 k opakování.
dešifrování - p i = D (ki, c i), jak je znázorněno na Obr. 7.21.
Rýže. 7.21.
Streamové šifry jsou rychlejší než blokové šifry. Hardwarová implementace proudové šifry je také jednodušší. Když musíme zašifrovat binární toky a přenášet je konstantní rychlostí, Nejlepší volba- použít proudovou šifru. Streamové šifry mají větší ochranu proti poškození bitů během přenosu.
V moderní proudové šifře každý r -bitword v proudu prostého textu je zašifrováno pomocí r -bit word v toku klíčů k vytvoření odpovídajícího r -bitové slovo v proudu šifrovaného textu.
Rýže. 7.22.
Jednorázová podložka je perfektní šifra. Je dokonalý. Neexistuje žádná metoda, která by dala protivníkovi schopnost rozpoznat klíč nebo statistiku šifrového a otevřeného textu. Mezi původním a šifrovaným textem není žádný vztah. Jinými slovy, šifrovaný text je skutečným náhodným bitovým tokem, i když získáte nějaké vzorky prostého textu. Eva nemůže prolomit šifru, pokud nezkusí všechny možné náhodné toky klíčů, což by bylo 2n, pokud je velikost otevřeného textu n bitů. S tím je však problém. Vysílač a přijímač, aby mohli sdílet jednorázový blok kláves, musí navázat spojení pokaždé, když si chtějí vyměňovat informace. Musí se nějak dohodnout na náhodném klíči. Tato dokonalá a ideální šifra je tedy velmi obtížně realizovatelná.
Příklad 7.17
Jaká je forma šifrového textu při použití jednorázové blokové šifry v každém z následujících případů?
A. Původní text se skládá z n nul.
b. Zdrojový text se skládá z n jednotek.
proti. Původní text se skládá ze střídání nul a jedniček.
d. Původní text je náhodný řetězec bitů.
Řešení
A. Pokud 
, pak bude proud šifrovaného textu odpovídat klíčovému proudu. Pokud je klíč náhodný, je náhodný i šifrovaný text. Fragmenty původního textu nejsou v šifrovém textu zachovány.
b. Pokud 
, kde je výplň, proud šifrovaného textu je výplň klíčového proudu. Pokud je klíčový proud náhodný, pak je náhodný i šifrovaný text, bity otevřeného textu se v šifrovaném textu neukládají.
C. V tomto případě je každý bit v toku šifrovaného textu buď stejný jako v toku klíčů, nebo jeho doplněk. Proto je výsledek také náhodný, pokud je klíčový proud náhodný.
d. PROTI tento případšifrovaný text je jasně náhodný, protože XORing dvou náhodných bitů vede k náhodnému proudu bitů.
Posuvný registr zpětné vazby
Jedno vylepšení jednorázové podložky je (FSR - Feedback Shift Register). FSR lze implementovat buď v software, nebo v hardwaru, ale pro jednoduchost budeme uvažovat o hardwarové implementaci. Posuvný registr zpětné vazby skládá se z funkce posuvného registru a zpětné vazby, jak je znázorněno na Obr. 7.23.
Rýže. 7.23.
Posuvný registr je sekvence m buněk od b 0 do b m-1, kde každá buňka je vyhrazena pro uložení jednoho bitu. S buňkami se zachází jako s n -bitovým slovem, které se na začátku nazývá "hodnota seed" resp zdroj. Kdykoli je potřeba vyvést bit (například na signálu v určitou dobu), každý bit se posune o jednu buňku doprava. To znamená, že hodnota každé buňky je přiřazena pravé sousední buňce a přebírá hodnotu levé buňky. Buňka zcela vpravo b 0 je považována za výstup a udává výstupní hodnotu (ki). Buňka zcela vlevo, b m-1 , získá svou hodnotu podle hodnoty informace funkce zpětné vazby. Výstup funkce označíme zpětnovazební informací b m . Funkce zpětné vazby určuje, jaké hodnoty mají buňky, aby bylo možné vypočítat b m . Posuvný registr zpětné informace může být lineární nebo nelineární.
Posunový registr lineární zpětné vazby (LFSR). Předpokládejme, že b m je lineární funkce b 0 , b 1 ,…..., b m-1 , pro kterou
Lineární zpětnovazební posuvný registr pracuje s binárními číslicemi, takže násobení a sčítání jsou v poli GF(2), takže hodnota C i je buď 1 nebo 0, ale C 0 musí být 1, aby se na výstupu získaly zpětnovazební informace. Operace přidání je operace VÝHRADNÍ NEBO. Jinými slovy,
Příklad 7.18
Postavme lineární zpětnovazební posuvný registr s 5 buňkami, ve kterém .
Řešení
Jestliže C i = 0, bi nehraje roli při výpočtu b m, pak to znamená, že b i není spojeno s funkcí zpětné informace. Jestliže c i = 1 , b i je zahrnuto do výpočtu b m . V tomto příkladu jsou c 1 a c 3 nuly, což znamená, že máme pouze tři spojení. Obrázek 7.24 ukazuje obvod posuvného registru s lineární zpětnou vazbou.
Rýže. 7.24.
Příklad 7.19
Postavme lineární zpětnovazební posuvný registr se 4 buňkami, ve kterém 
. Zobrazit hodnotu registru po 20 operace (směny) pokud je původní hodnota (0001) 2 .
Řešení
Obrázek 7.25 ukazuje návrh a použití posuvného registru s lineární zpětnou vazbou pro šifrování.
Rýže. 7.25.
Tabulka 7.6. ukazuje hodnotu klíčového proudu. Pro každý přechod je vypočítána první hodnota b 4 a poté je každý bit posunut o jednu buňku doprava.
| současná hodnota | b 4 | b 3 | b 2 | b 1 | b 0 | k i |
|---|---|---|---|---|---|---|
| Počáteční hodnota | 1 | 0 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 1 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 0 | 1 | 1 | 0 |
| 8 | 1 | 0 | 1 | 0 | 1 | 1 |
| 9 | 1 | 1 | 0 | 1 | 0 | 1 |
| 10 | 1 | 1 | 1 | 0 | 1 | 0 |
| 11 | 1 | 1 | 1 | 1 | 0 | 1 |
| 12 | 0 | 1 | 1 | 1 | 1 | 0 |
| 13 | 0 | 0 | 1 | 1 | 1 | 1 |
| 14 | 0 | 0 | 0 | 1 | 1 | 1 |
| 15 | 1 | 0 | 0 | 0 | 1 | 1 |
| 16 | 0 | 1 | 0 | 0 | 0 | 1 |
| 17 | 0 | 0 | 1 | 0 | 0 | 0 |
| 18 | 1 | 0 | 0 | 1 | 0 | 0 |
| 19 | 1 | 1 | 0 | 0 | 1 | 0 |
| 20 | 1 | 1 | 1 | 0 | 0 | 1 |
Všimněte si, že klíčový proud je 1000100110101111 1001…… . Na první pohled to vypadá jako náhodná sekvence, ale když se podíváte velké číslo transakce (posuny), vidíme, že sekvence jsou periodické. Toto opakování 15 bitů je znázorněno níže.
Klíč toku generuje pomocí posuvného registru s lineární zpětnou vazbou pseudonáhodná sekvence, ve kterých se sekvence délky N opakují. Tok je periodický. Závisí na obvodu generátoru a počátečních informacích a nemůže být větší než 2 m-1. Každé schéma generuje m-bitové sekvence od obsahujících všechny nuly po všechny jedničky. Pokud se však počáteční sekvence skládá pouze z nul, výsledek je k ničemu - původní text by byl proudem všech nul. Proto je taková počáteční sekvence vyloučena.
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 naplnění registru bude opět rovnat počáteční hodnota 0101 a generování bitové sekvence se začne opakovat. Výstupní sekvence registru bude řetězec nejméně významných bitů (až vodorovná čára na Obr. 90): 101011110001001. Velikost bitové sekvence před jejím opakováním se nazývá tečka. 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.
Posunový registr s lineární zpětnou vazbou(RSLOS, angl. lineární zpětnovazební posuvný registr, LFSR ) je posuvný registr bitových slov, ve kterém je hodnota vstupního (posuvného) bitu rovna lineární booleovské funkci z hodnot zbývajících bitů registru před posuvem. Může být organizován jak softwarově, tak hardwarově. Používá se ke generování bitů „pseudonáhodných sekvencí“, což se používá zejména v kryptografii.
Popis
Řízení registru v hardwarových implementacích se provádí aplikací posuvného impulsu (jinak nazývaného taktovaný nebo synchronizační puls) pro všechny buňky. Správa registrů v softwarových implementacích se provádí prováděním smyčky. Při každé iteraci smyčky se vypočítá zpětná vazba a bity ve slově se posunou.
Princip činnosti
Lineární složitost
Korelační nezávislost
Ve snaze získat vysokou lineární složitost generované sekvence kryptografové nelineárně kombinují výstupy několika posuvných registrů. V tomto případě lze jednu nebo více výstupních sekvencí (nebo i výstupů jednotlivých LFSR) propojit společným proudem a otevřít kryptoanalytikem. Hackování založené na takové zranitelnosti se nazývá korelační otevření. Hlavní myšlenkou takového hacku je najít nějakou korelaci mezi výstupem generátoru a jeho výstupy. součásti. Pak lze pozorováním výstupní sekvence získat informace o těchto mezivýstupech, a tak hacknout generátor. Thomas Siegenthaler ukázal, že je možné přesně definovat korelační nezávislost a že existuje kompromis mezi korelační nezávislostí a lineární složitostí.
Implementace softwaru
Softwarové implementace RSLOS jsou poměrně pomalé a pracují rychleji, pokud jsou napsány v assembleru. Jedním z řešení je paralelní použití 16 RLLS (nebo 32, v závislosti na délce slova v architektuře počítače). V takovém schématu se používá pole slov, jejichž velikost se rovná délce posuvného registru a každý bit slova odkazuje na svůj vlastní LFSR. Vzhledem k tomu, že se používá stejný počet odbočovacích sekvencí, může to přinést znatelné zvýšení výkonu generátoru.
Fibonacciho konfigurace
Zvažte 32bitový posuvný registr. Má únikovou sekvenci (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)). To znamená, že pro vygenerování nového bitu je nutné sečíst 31., 30., 29., 27., 25. a 0. bit pomocí operace XOR. Výsledný LFSR má maximální periodu 2 32 − 1 (\displaystyle 2^(32)-1). Kód takového registru v C je následující:
int LFSR_Fibonacci (void) ( statické bez znaménka dlouhé S = 0x00000001 ; S = ((((S >> 31) ^ (S >> 30) ^ (S >> 29) ^ (S >> 27) ^ (S >> 25) ^ S) & 0x00000001)<< 31 ) | (S >> 1); návrat S & 0x00000001 ; )
Konfigurace Galois
Tento generátor nemá větší kryptografickou sílu, ale přináší zvýšení výkonu: všechny operace XOR lze provádět v jedné operaci prostřednictvím paralelizace a ne postupně jednu po druhé, jako v konfiguraci Fibonacci. Toto schéma bude také přínosem v implementaci hardwaru.
Kód pro 32bitový posuvný registr v C je následující:
int LFSR_Galois (void) ( statické bez znaménka dlouhé S = 0x00000001 ; if (S & 0x00000001 ) ( S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; návrat 1 ;) 0 jinak ( S)
Je třeba poznamenat, že smyčka pevného počtu volání funkce LFSR_Galois v konfiguraci Galois se provádí přibližně 2krát rychleji než funkce LFSR_Fibonacci v konfiguraci Fibonacci (kompilátor MS VS 2010 na Intel Core i5).
Příklad vygenerované sekvence
Fibonacciho konfigurace
Nechť LFSR je dán charakteristickým polynomem x 3 + x + 1 (\displaystyle x^(3)+x+1). To znamená, že odbočovací bity budou 2. a 0. a jednotka ve vzorci polynomu znamená, že vstupem je 0. bit. Funkce zpětné vazby má tvar S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Předpokládejme, že počátečním stavem posuvného registru byla sekvence . Další stavy registru jsou uvedeny v tabulce níže:
| Číslo kroku | Stát | Vygenerován bit |
|---|---|---|
| 0 | [ 0 , 0 , 1 ] (\displaystyle \left) | 1 |
| 1 | 0 | |
| 2 | 0 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 0 | |
| 7 | [ 0 , 0 , 1 ] (\displaystyle \left) | 1 |
Protože se vnitřní stav v sedmém kroku vrátil do původního stavu, počínaje od další krok, bude opakování rytmu. Vygenerovaná sekvence je tedy: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle\left)(pořadí bitů v sekvenci odpovídá pořadí, ve kterém byly generovány LFSR). Perioda posloupnosti je tedy 7, tedy maximální možná hodnota, ke které došlo díky primitivnosti daného polynomu.
Konfigurace Galois
Vezměme stejný charakteristický polynom, tj. c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). K výstupnímu bitu je přidán pouze 1. bit. Výchozí stav je stejný. Další stavy registru:
| Číslo kroku | Stát | Vygenerován bit |
|---|---|---|
| 0 | [ 0 , 0 , 1 ] (\displaystyle \left) | - |
| 1 | [ 1 , 0 , 0 ] (\displaystyle \left) | 0 |
| 2 | [ 0 , 1 , 1 ] (\displaystyle \left) | 1 |
| 3 | [ 1 , 0 , 1 ] (\displaystyle \left) | 1 |
| 4 | [ 1 , 1 , 1 ] (\displaystyle \left) | 1 |
| 5 | [ 1 , 1 , 0 ] (\displaystyle \left) | 0 |
| 6 | [ 0 , 1 , 0 ] (\displaystyle \left) | 0 |
| 7 | [ 0 , 0 , 1 ] (\displaystyle \left) | 1 |
Vnitřní stav registru se v sedmém kroku vrátil do původního stavu, proto je jeho perioda také rovna 7. Na rozdíl od Fibonacciho konfigurace se vnitřní stavy registru ukázaly být odlišné, ale vygenerovaná sekvence je stejná , posunuto pouze o 4 cykly: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle\left)(pořadí bitů v sekvenci odpovídá pořadí, ve kterém byly generovány LFSR).
Generování primitivních polynomů
| kousky, n (\displaystyle n) | Primitivní polynom | Doba, 2 n − 1 (\displaystyle 2^(n)-1) | Počet primitivních polynomů |
|---|---|---|---|
| 2 | x 2 + x + 1 (\displaystyle x^(2)+x+1) | 3 | 1 |
| 3 | x 3 + x 2 + 1 (\displaystyle x^(3)+x^(2)+1) | 7 | 2 |
| 4 | x 4 + x 3 + 1 (\displaystyle x^(4)+x^(3)+1) | 15 | 2 |
| 5 | x 5 + x 3 + 1 (\displaystyle x^(5)+x^(3)+1) | 31 | 6 |
| 6 | x 6 + x 5 + 1 (\displaystyle x^(6)+x^(5)+1) | 63 | 6 |
| 7 | x 7 + x 6 + 1 (\displaystyle x^(7)+x^(6)+1) | 127 | 18 |
| 8 | x 8 + x 6 + x 5 + x 4 + 1 (\displaystyle x^(8)+x^(6)+x^(5)+x^(4)+1) | 255 | 16 |
| 9 | x 9 + x 5 + 1 (\displaystyle x^(9)+x^(5)+1) | 511 | 48 |
| 10 | x 10 + x 7 + 1 (\displaystyle x^(10)+x^(7)+1) | 1023 | 60 |
| 11 | x 11 + x 9 + 1 (\displaystyle x^(11)+x^(9)+1) | 2047 | 176 |
| 12 | x 12 + x 11 + x 10 + x 4 + 1 (\displaystyle x^(12)+x^(11)+x^(10)+x^(4)+1) | 4095 | 144 |
| 13 | x 13 + x 12 + x 11 + x 8 + 1 (\displaystyle x^(13)+x^(12)+x^(11)+x^(8)+1) | 8191 | 630 |
| 14 | x 14 + x 13 + x 12 + x 2 + 1 (\displaystyle x^(14)+x^(13)+x^(12)+x^(2)+1) | 16383 | 756 |
| 15 | x 15 + x 14 + 1 (\displaystyle x^(15)+x^(14)+1) | 32767 | 1800 |
| 16 | x 16 + x 14 + x 13 + x 11 + 1 (\displaystyle x^(16)+x^(14)+x^(13)+x^(11)+1) | 65535 | 2048 |
| 17 | x 17 + x 14 + 1 (\displaystyle x^(17)+x^(14)+1) | 131071 | 7710 |
| 18 | x 18 + x 11 + 1 (\displaystyle x^(18)+x^(11)+1) | 262143 | 7776 |
| 19 | x 19 + x 18 + x 17 + x 14 + 1 (\displaystyle x^(19)+x^(18)+x^(17)+x^(14)+1) | 524287 | 27594 |
| 20 - 168 | |||
| 2 - 786, 1024, 2048, 4096 | |||
Výhody a nevýhody
Výhody
- vysoký výkon kryptografických algoritmů vytvořených na základě LFSR (například proudové šifry);
- použití pouze nejjednodušších bitových operací sčítání a násobení, implementovaných hardwarově téměř ve všech výpočetních zařízeních;
- dobré kryptografické vlastnosti (LFSR mohou generovat dlouhé periody s dobrými statistickými vlastnostmi);
- díky jejich struktuře se LFSR snadno analyzují pomocí algebraických metod.
Nedostatky
Způsoby, jak zlepšit kryptografickou sílu generovaných sekvencí
Generátory s více posuvnými registry
Tento typ generátoru se skládá z několika lineárních zpětnovazebních posuvných registrů, které generují bity x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\tečky ,\;x_(M,i)) resp. Dále jsou vygenerované bity transformovány pomocí nějaké booleovské funkce f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\tečky ,\;x_(M) ,i))). Je třeba poznamenat, že generátory tohoto typu mají délky registrů L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\tečky ,\;M), jsou coprime mezi sebou.
Období tohoto generátoru je T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 LM − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), kde L = ∑ i = 1 M L i (\displaystyle L=\součet \limits _(i=1)^(M)L_(i))- celkový počet buněk. Proto použití několika LFSR zvyšuje periodu generované sekvence ve srovnání s jedním registrem, což zvyšuje kryptografickou sílu generátoru. Zvyšuje také lineární složitost nebo délku nejkratšího registru odpovídajícího danému generátoru. Takový registr je nalezen pomocí Berlekamp-Masseyho algoritmu pomocí vygenerované sekvence. Jeho délka je v nejlepším případě úměrná periodě generované sekvence.
Generátory s nelineární transformací
Blokové schéma takového generátoru se neliší od schématu předchozího generátoru. Hlavní rozdíl je v tom, že transformační zařízení je dáno nelineární booleovskou funkcí f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\tečky ,x_(M))). Například Zhegalkinův polynom je brán jako taková funkce (podle Zhegalkinovy věty jakákoli booleovská funkce může být jednoznačně reprezentován Zhegalkinovým polynomem).
Nelineární generátor může být také implementován na posuvný registr s nelineární zpětnou vazbou. Může dát 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L)) varianty sekvencí maximální perioda , což je více než u LFSR .
Kryptografická síla tohoto generátoru je zvýšena díky nelinearitě použité funkce. Určení stavu registrů z vygenerované bitové sekvence je složitý matematický problém, protože není znám žádný algoritmus, který obnovuje původní stavy.
Tato metoda se používá např generátor Geff a zobecněný Geffův generátor, nicméně takové generátory mohou být rozbity korelačním útokem.
Generátory s různým časováním posuvného registru
stop-go generátor
stop-go generátor(anglicky Stop-and-Go , Both-Piper ) používá výstup LFOS-1 k řízení hodinové frekvence LFOS-2, takže LFSR-2 změní svůj stav v určitém okamžiku pouze v případě, že výstup LFOS-1 v té době se rovnala jednotce. Toto schéma neodolalo otevření korelace.
Bylo navrženo, aby se zvýšila kryptografická síla stop-and-go alternátor. Využívá tři posuvné registry různých délek. Zde LFOS-1 řídí hodinový kmitočet 2. a 3. registru, tj. LFSR-2 změní svůj stav, když je výstup LFSR-1 roven jedné, a LFSR-3 - když je výstup LFSR-1 roven nule. Výstup generátoru je operace přidání modulo dvou výstupů RSLOS-2 a RSLOS-3. Tento generátor má velkou periodu a velkou lineární složitost. Existuje metoda otevírání korelace RLOS-1, ale to nijak výrazně neoslabuje kryptografické vlastnosti generátoru.
Je použito sofistikované schéma taktování dvoucestný stop-and-go generátor, který používá 2 posuvné registry stejné délky. Pokud je výstup RLOS-1 v určitém okamžiku t i − 1 (\displaystyle t_(i-1))- jedna, pak RLOS-2 není v daném čase taktován t i (\displaystyle t_(i)). Pokud je výstup RLOS-2 v okamžiku času t i − 1 (\displaystyle t_(i-1)) se rovná nule a v čase t i − 2 (\displaystyle t_(i-2))- jeden, a pokud je tento registr v daném čase taktován t i (\displaystyle t_(i)), pak současně není RLOS-1 taktován. Lineární složitost tohoto obvodu je přibližně rovna periodě generované sekvence.
Samodecimační generátor
Vícerychlostní oscilátor s vnitřním produktem
Tento generátor používá dva posuvné registry RSLOS-1 a RSLOS-2. Hodinová frekvence RSLOS-2 palce d (\displaystyle d) krát více než u RSLOS-1. Některé bity těchto registrů se navzájem násobí pomocí operace AND. Výsledky násobení se sečtou operací XOR a získá se výstupní sekvence. Tento generátor má vysokou lineární složitost a má dobré statistické vlastnosti. Jeho stav však lze určit z výstupní sekvence délek L 1 + L 2 + log 2 d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), kde L 1 (\displaystyle L_(1)) a L 2 (\displaystyle L_(2)) jsou délky LFOS-1 a LFOS-2, resp d (\displaystyle d)- poměr jejich hodinových frekvencí.
Kaskáda Gollmann
Tento obvod je vylepšenou verzí 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 RLOS-1 v té době t i (\displaystyle t_(i)) je 1, pak je taktován RLOS-2. Pokud je výstup RLOS-2 v okamžiku času t i (\displaystyle t_(i)) je 1, pak je taktován RLOS-3 a tak dále. Výstupem posledního LFSR je výstup generátoru. Pokud je délka všech LFSR stejná a rovna L (\displaystyle L), pak období systému od M (\displaystyle M) LFSR se rovná (2 L − 1) M (\displaystyle (2^(L)-1)^(M)) a lineární složitost je L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .
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 citliví na pitvu tzv zamykání(angl. lock-in) když
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 - jednoduchá obsluha XOR přes některé bity 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ý parametr generátor založený na RLSS, 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.
Kromě LFSR se používají i posuvné registry s nelineární zpětnou vazbou, přenosovou zpětnou vazbou atd.
Na základě číselně teoretického přístupu byla vyvinuta řada generátorů (Blum-Micaliho generátory, RSA, BBS, kompresní, aditivní generátory atd.).
Matematická podpora pro syntézu proudových kryptografických algoritmů byla ve srovnání s blokovými kryptografickými algoritmy vyvinuta úplněji a podrobněji. K vytvoření proudových šifer se však často používají algoritmy blokové šifry v režimech OFB nebo CFB.