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

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

Posuvný registr s lineární zpětnou vazbou ( LFSR ) je posuvný registr bitových , 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 posunem. Může být organizován jak softwarově, tak hardwarově. Slouží ke generování pseudonáhodných bitových sekvencí , čehož se využívá zejména v kryptografii [1] . Na podobném principu funguje posuvný registr s carry feedbackem . zobecněný zpětný posuvný registr .

Popis

V posuvném registru s lineární zpětnou vazbou (RSLOS) jsou dvě části (moduly):

skutečný posuvný registr;
zpětnovazební obvod (nebo podprogram), který vypočítává hodnotu vloženého bitu.

Registr se skládá z funkčních paměťových buněk (bitů jednoho nebo více strojových slov), z nichž každá ukládá aktuální stav (hodnotu) jednoho bitu. Počet buněk se nazývá délka registru. Bity (buňky) se obvykle číslují čísly , obsah -té buňky se značí . Hodnota nového bitu je určena před bitovým posunem v registru a teprve po zápisu posunu do buňky a další vygenerovaný bit je extrahován z buňky. $L$ $i = 0,\;1,\;\tečky,\;L-1$ $i$ $S_{(L-1)-i}$ $S_L$ $0$ $L-1$

Zpětná vazba pro LFSR je lineární booleovská funkce hodnot všech nebo některých bitů registru. Funkce vynásobí bity registru koeficienty , kde . Počet koeficientů je stejný jako počet bitů registru . Koeficienty nabývají hodnot a poslední koeficient je roven , protože LFSR je dán charakteristickým polynomem stupně . Sčítání Modulo 2 (operace „XOR“, ve vzorcích označená symbolem „ “) nebo jeho logická inverze „ XNOR “ jsou lineární booleovské funkce a v takových registrech se používají nejčastěji [2] . V tomto případě se bity, které jsou proměnnými funkce zpětné vazby, nazývají taps a samotný registr se nazývá Fibonacciho konfigurace [3] . $c_{i}$ $i = 1, \; 2,\; \tečky,\; L$ $L$ $c_{i}$ $\{ 0, \; jeden \}$ $c_L$ $c_L = 1$ $L$ $\oplus$

Řízení registru v hardwarových implementacích se provádí aplikací posuvného impulsu (jinak nazývaného hodinový nebo hodinový impuls ) na všechny buňky. Správa registrů v softwarových implementacích se provádí spuštěním smyčky . Při každé iteraci smyčky se vypočítá zpětná vazba a provede se bitový posun ve slově.

Jak to funguje

Během každého hodinového cyklu provádí posuvný registr s lineární zpětnou vazbou následující operace:

přečte se bit umístěný v buňce ; tento bit je dalším bitem ve výstupní sekvenci; $L-1$
funkce zpětné vazby vypočítá novou hodnotu pro buňku pomocí aktuálních hodnot buněk; $0$
obsah každé buňky se přesune do další buňky , kde ; $i$ $i+1$ $i = 0,\;1,\;\tečky,\;L-2$
buňka je zapsána do bitu dříve vypočítaného zpětnovazební funkcí. $0$

Pokud funkce zpětné vazby provádí logickou operaci " XOR " (exkluzivní OR), lze hodnoty bitů (buněk) vypočítat pomocí následujících vzorců [4] :

$S_L=(c_1*S_{L-1})\oplus(c_2*S_{L-2})\oplus\tečky\oplus(c_L*S_{0})$

$S_{L+1}=(c_1*S_{L})\oplus(c_2*S_{L-1})\oplus\tečky\oplus(c_L*S_{1})$ $...$ $S_{L+j-1}=(c_1*S_{L+j-2})\oplus(c_2*S_{L+j-3})\oplus\tečky\oplus(c_L*S_{j-1} )$

Vlastnosti

Periodicita

Perioda posuvného registru je minimální délka výsledné sekvence, než se začne opakovat. Délka LFSR má počáteční stavy, které definují hodnoty bitů v buňkách. Z nich jsou stavy nenulové, takže vygenerovaná sekvence má periodu . Perioda generované sekvence je maximální a rovna , pokud je zpětnovazební polynom (nebo charakteristický polynom) nad polem primitivní . K tomu je nutné (nikoli však postačující) splnit následující 2 podmínky: $L$ $2^{{L}}$ $2^{L}-1$ $T\leq2^{L}-1$ $2^{L}-1$ $C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+\dots +c_{1}x+1$ ${\mathrm {GF}} (2)$

sudý počet kohoutků;
čísla klepnutí, braná jako celek, a nikoli v párech, jsou coprime .

Počet všech možných primitivních polynomů je , kde je Eulerova funkce [5] . Registr daný takovým polynomem se nazývá posuvný registr s maximální periodou (neboli generátor pseudonáhodné posloupnosti ) a generované sekvence se nazývají sekvence s maximální periodou (neboli M-sekvence ) [4] [6] . $\tfrac{\phi(2^L-1)}{L}$ $\phi$

Lineární složitost

Lineární složitost nekonečné binární posloupnosti je číslo, které je definováno takto: $S=(S_0,\;S_1,\;S_2,\;\tečky)$ $L(S)$

if je nulová posloupnost, pak ; $S=(0,\;0,\;0,\;\tečky)$ $L(S)=0$
pokud neexistuje žádný LFSR, který generuje , pak ; $S$ $L(S) = \infty$
jinak se rovná délce nejkratšího LFSR, který generuje . $L(S)$ $S$

Lineární složitost konečné binární sekvence je číslo rovné délce nejkratšího LFSR, který generuje tuto sekvenci. $S_n=(S_0,\;S_1,\;\tečky,\;S_n)$ $L(S_n)$

Lineární složitost lineárního zpětnovazebního posuvného registru ukazuje, jak blízko je generovaná sekvence náhodě . Efektivní algoritmus pro stanovení lineární složitosti konečné binární posloupnosti je Berlekamp-Massey algoritmus .

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 . Hack založený na takové zranitelnosti se nazývá korelační útok . Hlavní myšlenkou takového hacku je najít nějakou korelaci mezi výstupem generátoru a výstupy jeho součástí. 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í [7] .

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 RSLOS (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, jehož 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 [3] .

Konfigurace Fibonacci

Zvažte 32bitový posuvný registr. Existuje pro něj úniková sekvence . 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 . Kód takového registru v C je následující: $\left(32,\;31,\;30,\;28,\;26,\;1\right)$ $2^{32}-1$

int LFSR_Fibonacci ( void ) { static unsigned long S = 0x00000001 ; S = (((( S >> 31 ) ^ ( S >> 30 ) ^ ( S >> 29 ) ^ ( S >> 27 ) ^ ( S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | ( S >> 1 ); návrat S & 0x00000001 ; }

Konfigurace Galois

Stejně jako ve Fibonacciho konfiguraci je zpětnovazební obvod sada operací XOR odbočovacích bitů s výstupem generátoru, ale pořadí bitů v registru je obrácené: -tý bit je vstup a -tý bit . je výstup . Výsledek sčítání se zapíše do další buňky a nový výstupní bit se zapíše do -th. Pokud je tedy vygenerovaný bit roven nule, pak jsou všechny bity v buňkách posunuty doprava beze změn, pokud je vygenerovaný bit roven jedné, pak bity tap změní svou hodnotu na opačnou a všechny bity se posunou doprava. Jak Fibonacciho konfigurace, tak i Galoisova konfigurace stejné délky generují stejné sekvence, ale posunuté v čase od sebe (v tomto případě se vnitřní stavy registrů mohou lišit) [8] . $L-1$ $0$ $L-1$

Tento generátor nemá větší kryptografickou sílu , ale přináší zvýšení výkonu: všechny operace XOR prostřednictvím paralelizace lze provádět v jedné operaci a ne postupně jednu po druhé, jako v konfiguraci Fibonacci. Toto schéma také přinese zisk v implementaci hardwaru.

Kód pro 32bitový posuvný registr v C je následující:

int LFSR_Galois ( void ) { // pro polynom 0x80000057, obrácený 0xea000001 static unsigned long S = 0x00000001 ; if ( S & 0x00000001 ) { S = (( S ^ 0x80000057 ) >> 1 ) | 0x80000000 ; vrátit 1 ;} jinak { S >>= 1 ; vrátit 0 ;} }

Za zmínku stojí, že smyčka pevného počtu volání funkcí LFSR_Galoisv konfiguraci Galois je přibližně 2x rychlejší než funkce LFSR_Fibonacciv konfiguraci Fibonacci ( kompilátor MS VS 2010 na Intel Core i5 ).

Příklad vygenerované sekvence

Konfigurace Fibonacci

Nechť LFSR je dán charakteristickým polynomem . 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 . Řekněme, že počátečním stavem posuvného registru byla sekvence . Další stavy registru jsou uvedeny v tabulce níže: $x^{3}+x+1$ $S_j=S_{j-1}\oplus S_{j-3}$ $\left[0,\;0,\;1\right]$

Číslo kroku	Stát	Vygenerován bit
0	$\left[0,\;0,\;1\right]$	jeden
jeden	$\left[1,\;0,\;0\right]$	0
2	$\left[1,\;1,\;0\right]$	0
3	$\left[1,\;1,\;1\right]$	jeden
čtyři	$\left[0,\;1,\;1\right]$	jeden
5	$\left[1,\;0,\;1\right]$	jeden
6	$\left[0,\;1,\;0\right]$	0
7	$\left[0,\;0,\;1\right]$	jeden

Protože se vnitřní stav v sedmém kroku vrátil do původního stavu, budou se bity počínaje dalším krokem opakovat. To znamená, že vygenerovaná sekvence je následující: (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. $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$

Konfigurace Galois

Vezměme stejný charakteristický polynom, tedy , . K výstupnímu bitu je přidán pouze 1. bit. Výchozí stav je stejný. Další stavy registru: $c_3=c_1=1$ $c_2=0$

Číslo kroku	Stát	Vygenerován bit
0	$\left[0,\;0,\;1\right]$	jeden
jeden	$\left[1,\;0,\;1\right]$	jeden
2	$\left[1,\;1,\;1\right]$	jeden
3	$\left[1,\;1,\;0\right]$	0
čtyři	$\left[0,\;1,\;1\right]$	jeden
5	$\left[1,\;0,\;0\right]$	0
6	$\left[0,\;1,\;0\right]$	0
7	$\left[0,\;0,\;1\right]$	jeden

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á , pouze posunuto o 4 cykly : (pořadí bitů v sekvenci odpovídá pořadí jejich generování LFSR). $\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;...\right]$

Maticová reprezentace LFSR

část anglického článku

Generování primitivních polynomů

Výpočet primitivního polynomu nad polem je poměrně komplikovaný matematický problém: k vytvoření primitivního polynomu stupně potřebujete znát faktory čísla . Jednodušší je náhodně vybrat polynom a otestovat ho na primitivnost [3] . Další metodou je použití hotových tabulek, které vypisují počty tap sekvencí, které poskytují maximální periodu generátoru. Níže je uvedena tabulka primitivních polynomů nad polem pro posuvné registry s maximální periodou až 19 bitů [5] . Stojí za zvážení, že generátor libovolné délky může mít podle svých vlastností více než jeden primitivní polynom . Kompletní seznam pro registry o délce 4 až 32 bitů naleznete zde . ${\mathrm {GF}} (2)$ $k$ $2^{k}-1$ ${\mathrm {GF}} (2)$

bity, $n$	Primitivní polynom	Doba, $2^{n}-1$	Počet primitivních polynomů
2	$x^{2}+x+1$	3	jeden
3	$x^3+x^2+1$	7	2
čtyři	$x^4+x^3+1$	patnáct	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{ 7 }+x^{ 6 }+1$	127	osmnáct
osm	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	16
9	$x^{9}+x^{5}+1$	511	48
deset	$x^{10}+x^{7}+1$	1023	60
jedenáct	$x^{11}+x^{9}+1$	2047	176
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$	4095	144
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$	8191	630
čtrnáct	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
patnáct	$x^{15}+x^{14}+1$	32767	1800
16	$x^{16}+x^{14}+x^{13}+x^{11}+1$	65535	2048
17	$x^{17}+x^{14}+1$	131071	7710
osmnáct	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20 - 168	[jeden]
2 – 786, 1024, 2048, 4096	[2]

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.

Nevýhody

Jedním z hlavních problémů LFSR je, že jejich softwarová implementace je extrémně neefektivní: je třeba se vyhnout polynomům s řídkou zpětnou vazbou, protože vedou ke snadnějšímu hackování korelačním útokem a husté polynomy se velmi pomalu počítají. Proto softwarová implementace takového generátoru není rychlejší než implementace DES .
Linearita sekvence na výstupu registru umožňuje jednoznačně určit zpětnovazební polynom přes sériové bity pomocí Berlekamp-Masseyho algoritmu nebo Euklidova algoritmu [3] [4] . $C(x)$ $2L$
Relativní snadnost analýzy algebraickými metodami nejen usnadňuje vývoj, ale také zvyšuje šance na rozbití generátoru založeného na LFSR.

Způsoby, jak zlepšit šifrovací 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í jednotlivé bity. Dále se vygenerované bity převedou pomocí nějaké booleovské funkce . Je třeba poznamenat, že u generátorů tohoto typu jsou délky registrů , , vzájemně relativně prvotřídní . $x_{1,i},\;x_{2,i},\;\tečky,\;x_{M,i}$ $f(x_{1,i},\;x_{2,i},\;\tečky,\;x_{M,i})$ $L_i$ $i=1,\;2,\;\tečky,\;M$

Perioda tohoto generátoru je , kde je 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 [4] . $T=(2^{L_1}-1)\cdot(2^{L_2}-1)\cdots(2^{L_M}-1)\lesssim2^L$ $L=\sum\limits_{i=1}^M L_i$

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í . Jako taková funkce se bere například Zhegalkinův polynom (podle Zhegalkinovy věty může být jakákoli booleovská funkce jednoznačně reprezentována Zhegalkinovým polynomem). $f(x_1, x_2, \tečky, x_M)$

Na posuvném registru s nelineární zpětnou vazbou lze implementovat i nelineární generátor . Může poskytnout varianty sekvencí s maximální periodou , což je více než u LFSR [5] . $2^{2^{L-1}-L}$

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 je používána např. v Geff generátoru a zobecněném Geff generátoru, nicméně takové generátory lze hacknout korelační analýzou [7] .

Oscilátory s různým časováním posuvného registru

Generátor stop-and-go

Generátor Stop-and-Go ( eng. Stop-and-Go , Both-Piper ) využívá výstup LFSR-1 k řízení hodinové frekvence LFSR-2, takže LFSR-2 v určitém okamžiku změní svůj stav. pouze v případě, že výstup LFSR-1 v daném okamžiku byl roven jedné. Toto schéma neodolalo otevření korelace [3] . $t_{i}$ $t_{i-1}$

Aby se zvýšila kryptografická síla, byl navržen prokládaný stop-go generá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 provoz modulo dva z výstupů RLOS-2 a RLLS-3. Tento generátor má velkou periodu a velkou lineární složitost. Existuje způsob otevírání korelace RLOS-1, ale to nijak výrazně neoslabuje kryptografické vlastnosti generátoru.

Složitější schéma taktování se používá u dvoucestného generátoru stop-and-go , který používá 2 posuvné registry stejné délky. Pokud je výstup LFSR-1 v určitém časovém okamžiku roven nule a v časovém okamžiku je roven jedné, pak LFSR-2 není v daném časovém okamžiku taktován . Pokud je výstup LFSR-2 v okamžiku času roven nule a v časovém okamžiku je roven jedné, a pokud je tento registr taktován v okamžiku času , pak je ve stejném okamžiku LFSR-1 není taktovaný. Lineární složitost tohoto obvodu je přibližně rovna periodě generované sekvence. $t_{i-1}$ $t_{i-2}$ $t_{i}$ $t_{i-1}$ $t_{i-2}$ $t_{i}$

Samodecimační generátor

Samodecimované oscilátory řídí svou vlastní frekvenci . Existují dva typy takových generátorů. První navrhl Rainer Rüppel . Skládá se z posuvného registru a lineárního zpětnovazebního obvodu, který taktuje registr na základě výstupu posuvného registru. Pokud je výstup LFSR roven jedné, pak je registr taktován jednou frekvencí a pokud je výstup nulový, pak jinou. Druhý typ navrhli Bill Chambers a Dieter Kollman . Zpětnovazební obvod nepřijímá samotný výstupní signál, ale výsledek činnosti XOR určitých bitů LFSR.

Existují také smršťovací a samosmršťovací generátory . _ _ _ _ Jsou zcela nové a ne všechny jejich vlastnosti jsou dobře prozkoumány. První používá dva LFSR. Pokud je na generátor aplikován hodinový impuls a výstup RLOS-1 je jedna, pak výstup generátoru bude výstupem RLLS-2. V opačném případě, když je aplikován hodinový impuls, oba bity se resetují a hodiny začnou znovu. Ve druhém generátoru se místo kontroly výstupů dvou registrů pro 0 nebo 1 kontrolují 2 bity jednoho registru.

Decimovaný generátor může být hacknut, pokud jsou zdecimovány zpětnovazební polynomy. Navíc jeho generační rychlost není konstantní. Samodecimační generátor potřebuje asi 2x méně paměti než ten první, ale pracuje 2x pomaleji [7] .

Vícerychlostní oscilátor s vnitřním součinem

Tento generátor používá dva posuvné registry RSLOS-1 a RSLOS-2. Hodinová frekvence RSLOS-2 je několikrát vyšší než frekvence 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élky , kde a jsou délky LFSR-1 a LFSR-2, v tomto pořadí, a je poměrem jejich hodinových frekvencí. $d$ $L_1 + L_2 + \log_2{d}$ $L_{1}$ $L_{2}$ $d$

Gollmann Cascade

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 LFSR-1 v daném okamžiku 1, pak je LFSR-2 taktován. Pokud je výstup LFSR-2 v daném okamžiku 1, pak je LFSR-3 taktován a tak dále. Výstup posledního LFSR je výstupem generátoru. Pokud je délka všech LFSR stejná a rovna , pak perioda systému LFSR je , a lineární složitost je [7] . $t_{i}$ $t_{i}$ $L$ $M$ $(2^L - 1)^M$ $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 náchylné k útoku zvanému lock - in , kdy kryptoanalytik , obnovující nejprve vstupní sekvenci posledního registru v kaskádě, rozbije celou kaskádu, registr po registru. S rostoucím počtem registrů se vygenerovaná sekvence blíží náhodné , takže je lepší použít více LFSR malé délky než méně dlouhých LFSR. $M$

Generátory většiny

Většinový (neboli prahový ) generátor se skládá z velkého počtu posuvných registrů, jejichž výstupy jdou do zařízení určeného majorizační funkcí, např. majoritního prvku . Zvláštností tohoto generátoru je, že každý z posuvných registrů má svůj vlastní hodinový bit , , což jsou proměnné většinové funkce. Například pro tři registry má taková funkce tvar . Posouvají se pouze ty registry, jejichž hodinové bity se rovnají hodnotě , to znamená, že k posunu registrů dochází u většiny hodnot těchto bitů: 0 nebo 1. $a_{i}$ $i=1,\;2,\;\tečky,\;M$ $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ $b(t)$

Získáme tak generátor s proměnným počtem LFSR. Jeho lineární složitost je , kde je délka -tého registru [7] . Nevýhodou takového generátoru je možnost přímého výčtu a otevírání korelace (každý výstupní bit dává nějakou informaci o stavu posuvného registru, přesněji - 0,189 bitu). $L(S) = \sum\limits_{i,j=1}^M L_iL_j$ $L_i$ $i$

Podobné generátory se používají v šifrovacích algoritmech A5 (A5/1, A5/2).

Aplikace

Posuvné registry s lineární zpětnou vazbou mohou být implementovány v hardwaru, což umožňuje jejich použití pro rychlé generování pseudonáhodné sekvence , jako je přímá sekvence rozprostřeného spektra nebo generování šumového signálu [9] .

Použití v kryptografii

Lineární zpětnovazební posuvné registry se dlouho používaly jako generátory pseudonáhodných sekvencí pro proudové šifry (zejména ve vojenské kryptografii ). LFSR je však lineární schéma a v některých případech může být snadno hacknuto. Například kryptoanalytik může zachytit část šifrového textu a použít jej pomocí výše uvedeného Berlekamp-Masseyho algoritmu k rekonstrukci minimální velikosti LFSR, která napodobuje původní LFSR. Poté může být zachycený text vložen do přijatého registru a dešifrován. Metody pro zvýšení kryptografické síly proudových šifer založených na LFSR jsou uvedeny výše .

Lineární zpětnovazební posuvný registr je základem pro proudové šifry, jako jsou A5/1 a A5/2 používané ve standardu GSM , a šifra E0 používaná v Bluetooth . Šifra A5/2 byla prolomena a šifry A5/1 a E0 jsou vážně chybné [10] [11] .

Lineární zpětnovazební posuvný registr úzce souvisí s lineárním kongruenciálním generátorem [12] .

Použít jako čítače

Frekvence generované sekvence LFSR umožňuje její použití jako hodinový dělič nebo čítač [13] . Čítač založený na takovém oscilátoru má na rozdíl od konvenčních čítačů binárních nebo Grayových kódů zjednodušený zpětnovazební obvod, a proto může pracovat při vysokých rychlostech hodin. Musíte se však ujistit, že takový čítač nikdy nevstoupí do nulového stavu.

Testování digitálních zařízení

Na rozdíl od konvenčního čítače nepřechází LFSR z jednoho stavu do druhého v pořadí binárního počítání, což umožňuje jeho použití pro generování testovacího signálu při detekci chyb v logických obvodech [6] .

Také posuvné registry s lineární zpětnou vazbou se používají ve vestavěném autotestu [ ( vestavěný autotest , BIST ) pro analýzu signatur (detekce bitové chyby) v logických obvodech. Takové systémy se používají kvůli omezenému počtu mikroobvodových výstupů (ne všechny mezilehlé bitové hodnoty lze použít na výstup). Systém BIST se skládá ze 3 bloků: generátoru testovací sekvence a analyzátoru signatur, které jsou postaveny na bázi LFSR, a testovacího kontroléru. Posuvný registr v analyzátoru "zkomprimuje" výsledek obvodu pro testovací sekvenci do podpisu a pokračuje v práci, dokud se všechny jeho bity, kromě 0, nestanou nulou, tedy stavu . Spolu s LFSR existuje binární čítač, který počítá počet cyklů od konce komprese testovací reakce. Pokud počáteční stav registru odpovídal referenčnímu podpisu (podpisu bezchybného obvodu), pak čtení čítače odpovídá číslu chybného bitu [14] [15] . $\left[1,\;0,\;0,\;...,\;0\right]$

Protože LFSR provádí ztrátovou kompresi, je pravděpodobné, že ve schématu s chybami bude výsledný podpis roven referenčnímu. Tomu se lze vyhnout použitím analyzátoru signatur s více vstupy.

Scrambling

Lineární zpětnovazební posuvné registry se používají při kódování k vytvoření digitálního proudu s vlastnostmi náhodné sekvence . Pseudonáhodná sekvence LFSR maximální délky je přidána modulo 2 k přenášenému bitovému toku a sekvence je generována stejnou rychlostí jako datový přenos. Některé systémy a technologie využívající scrambling jsou:

ATSC [16] ;
DAB ;
DVB-T ;
NICAM ;
CDMA ;
100BASE-T2 Fast Ethernet ;
1000BASE-T Gigabit Ethernet ;
PCI Express 3.0 ;
SATA ;
Serial Attached SCSI ;
USB 3.0 ;
IEEE 802.11a ;
Bluetooth L.E.

Viz také

Poznámky

↑ B. Sklyar, 2007 .
↑ Registry posunu lineární zpětné vazby v zařízeních Virtex . Získáno 19. listopadu 2014. Archivováno z originálu 2. listopadu 2013. (neurčitý)
↑ 1 2 3 4 5 B. Schneier, 2013 .
↑ 1 2 3 4 Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ 1 2 3 Yu.B. Kobzarev, 2013 .
↑ 1 2 Larin, 2008 .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Beker, Piper, 1982 .
↑ A. Sizoněnko, 2012 .
↑ E. Barklan, E. Biham, N. Keller, 2008 .
↑ Y. Lu, W. Meier, S. Vaudenay, 2005 .
↑ D. Eastlake, J. Schiller, S. Crocker, 2005 .
↑ Efektivní posuvné registry, čítače LFSR a generátory dlouhých pseudonáhodných sekvencí . Získáno 18. listopadu 2014. Archivováno z originálu 25. ledna 2021. (neurčitý)
↑ B. Harrington, 2008 .
↑ O. Djačenko .
↑ V. Vargauzin, 1999 .

Literatura

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C. - Triumf, 2013. - 816 s. - ISBN 978-5-89392-527-2 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informační bezpečnost : učebnice - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Larin A. L. Základy digitální elektroniky - M .: MIPT , 2008. - 314 s. — ISBN 978-5-7417-0228-4
Sklyar B. Digitální komunikace. Teoretické základy a praktická aplikace. - Williams, 2007. - 1104 s. - ISBN 978-5-8459-0497-3 .
Kobzarev Yu. B. Moderní radar. - Ripol Classic, 2013. - 708 s. — ISBN 978-5-4584-7357-6 .
Fomichev V. M. Diskrétní matematika a kryptologie : Kurz přednášek / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - 397 s. — ISBN 978-5-86404-185-7
Beker H. , Piper F. Cipher systems: the protection of communications (anglicky) - London : Northwood Books , 1982. - 427 s. — ISBN 978-0-7198-2611-5
Sizonenko AB Vícekanálový digitální zdroj šumu založený na rekurentním posuvném registru . - Special Equipment and Communications Magazine č. 3, 2012. Archivní kopieze dne 29. listopadu 2014 naWayback Machine
Barklan E. , Biham E. , Keller N. Okamžitá kryptoanalýza šifrované komunikace GSM pouze pomocí šifrovaného textu . - Journal of cryptology č. 21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Okamžitá kryptoanalýza pouze šifrované komunikace GSM . - Krypto č. 3621, 2005. (nepřístupný odkaz)
Eastlake D. , Schiller J. , Crocker S. Požadavky na náhodnost pro bezpečnost . — 2005.
Harrington B. Získejte podporu od BIST . — 2008. (nepřístupný odkaz)
Dyachenko O. N. Kompaktní analýza nad polem GF(3).
Vargauzin V. Principy digitální televize standardu ATSC. - Časopis Tele-Sputnik č. 9 (47), 1999.

Odkazy

Reference LFSR . LFSR Theory and Implementation, Maximum Length Sequence a Complete Tap Sequence Tables pro délky od 7 do 16 milionů (3 až 24 bitů) a dílčí tabulky pro délky do 4 miliard (25 až 32 bitů) (nedostupný odkaz) Archivováno 1. října 2018 .
Doporučení Mezinárodní telekomunikační unie O.151 . srpna 1992
Rutina generování pseudonáhodných čísel Archivováno 25. prosince 2008 na Wayback Machine
[3 ]
Jednoduché vysvětlení LFSR pro inženýry
Podmínky zpětné vazby
Implementace kryptograficky bezpečného generátoru pseudonáhodných čísel
Metody a úkoly ochrany kryptografických informací (nepřístupný odkaz)