Posuvný registr s lineární zpětnou vazbou. Lineární rekurentní registr

Posuvný registr zpětné vazby ( FSR ) se skládá ze dvou částí: posuvný registr A funkce zpětné vazby .

Posuvný registr (Chyba: Reference source not found) je sekvence bitů. Když je potřeba extrahovat bit, všechny bity posuvného registru se posunou doprava o 1 pozici. Nový bit nejvíce vlevo je hodnota zpětné vazby ze zbývajících bitů v registru. Doba Posuvný registr je délka výsledné sekvence, než se začne opakovat.

Nejjednodušší typ zpětnovazebního posuvného registru je lineární posuvný registr se zpětnou vazbou (LFSR – Vlevo, odjet Zpětná vazba Posun Registrovat) (Chyba: Referenční zdroj nebyl nalezen). Zpětná vazba je jednoduše XOR některých p bitů. registru se nazývá seznam těchto bitů bypass sekvence.

n-bit LFSR může být v jednom z 2 n -1 vnitřní stavy. To znamená, že teoreticky může takový registr generovat pseudonáhodnou sekvenci s tečkou 2 n -1 bitů. Počet vnitřních stavů a ​​perioda jsou stejné, protože zaplnění registru nulami způsobí, že vytvoří nekonečnou posloupnost nul, což je naprosto zbytečné. Pouze s určitými sekvencemi klepnutí bude LFSR cyklicky procházet všemi 2 n -1 vnitřní stavy. Takové LFSR se nazývají LFSRs maximální dobou.

Aby měl konkrétní LFSR maximální periodu, polynom vytvořený z odbočovací sekvence a konstanty 1 musí být primitivní modulo 2 .

Výpočet primitivnosti polynomu je poměrně složitý matematický problém. Proto jsou připraveny tabulky, které uvádějí počty odbočovacích sekvencí, které poskytují maximální periodu generátoru. Například pro 32bitový posuvný registr můžete najít následující položku: (32,7,5,3,2,1,0) . To znamená, že pro vygenerování nového bitu je potřeba sečíst třicátý druhý, sedmý, pátý, třetí, druhý a první bit pomocí funkce XOR.

Kód pro takový LFSR v C++ by byl:

// Jakákoli hodnota jiná než nula

ShiftRegister = (((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^ShiftRegister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

return ShiftRegister & 0x00000001;

Softwarové implementace LFSR jsou poměrně pomalé a běží rychleji, pokud jsou napsány v assembleru spíše než v C. Jedním z řešení je použít 16 LFSR paralelně (nebo 32 v závislosti na délce slova v architektuře konkrétního počítače). V tomto schématu je použito pole slov, jehož velikost se rovná délce LFSR a každá jednotka slova v poli odkazuje na svůj vlastní 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.

S lze také upravit zpětnovazební obvod. V tomto případě generátor nebude mít větší kryptografickou sílu, ale bude jednodušší jej programově implementovat. Namísto použití levého bitu sekvence odboček ke generování nového bitu 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 ( Chyba: Referenční zdroj nebyl nalezen).

Tato úprava se nazývá Konfigurace Galois. V jazyce C to vypadá takto:

static unsigned long ShiftRegister = 1;

void seed_LFSR (nepodepsané dlouhé semeno)

ShiftRegister = semeno;

int Galua_LFSR(void)

if (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ maska ​​>> 1) | 0x8000000;

ShiftRegister >>= 1;

Výplatou je, že všechny XOR jsou provedeny v jedné operaci. Tento obvod lze také paralelizovat.

Samy o sobě jsou LFSR dobrými generátory pseudonáhodných sekvencí, ale mají některé nežádoucí nenáhodné vlastnosti. Sekvenční bity jsou lineární, takže jsou pro šifrování nepoužitelné. Pro délku LFSR n vnitřní stav představuje předchozí n výstupní bity generátoru. I když je schéma zpětné vazby drženo v tajnosti, lze jej určit pomocí 2 n výstupní bity generátoru pomocí speciálních algoritmů. 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á. Navzdory tomu se LFSR často používají k vytváření šifrovacích algoritmů. K tomu se používá několik LFSR, obvykle s různou délkou a pořadovými čísly kohoutků. Klíčem je počáteční stav registrů. Pokaždé, když je potřeba nový bit, všechny registry se posunou. Tato operace se nazývá taktování. Výstupní bit je funkcí, přednostně nelineární, některých bitů LFSR. Tato funkce se nazývá kombinování a generátor jako celek - kombinovaný generátor. Mnohé z těchto generátorů jsou i dnes bezpečné.

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 posunem. 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á funkce zpětné vazby 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 kryptoanalytik. 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 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í.

Softwarová implementace

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, 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.

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 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 ) ( statické bez znaménka dlouhé S = 0x00000001 ; if (S & 0x00000001 ) ( S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; návrat 1 ;) 0 jinak ( S)

Za zmínku stojí, že cyklus pevného počtu volání funkce LFSR_Galois v konfiguraci Galois je přibližně 2krát rychlejší 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:

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. 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:

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ů

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)) respektive. 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 L M − 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. V nejlepším případě je jeho délka ú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))). Za takovou funkci je brán například Zhegalkinův polynom (podle Zhegalkinovy ​​věty lze libovolnou booleovskou funkci jednoznačně reprezentovat 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 rovnal jednotce. Toto schéma otevření korelace neodolalo.

Aby se zvýšila kryptografická síla, bylo navrženo 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 způsob 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 taktovaný t i (\displaystyle t_(i)), pak ve stejném okamžiku 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ýstup posledního LFSR je výstupem 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ž

Linear Feedback Shift Register (LFSR) je mechanismus pro vytváření pseudonáhodné sekvence binárních bitů. Registr (obr. 1) se skládá z řady buněk, které jsou nastaveny inicializačním vektorem (nejčastěji tajným klíčem). Činnost registru je určena přítomností nebo nepřítomností spojení každého bitu se zpětnou vazbou. Odbočky registru zpětné vazby nejsou pevné, ale jsou součástí klíče. V dalším kroku se obsah buněk registru posune o jednu pozici doprava a jeden bit ponechaný volný v důsledku operace XOR se umístí do buňky nejvíce vlevo.

Rýže. 1. Lineární posuvný registr se zpětnou vazbou

Pro dosažení maximální periody šifry gama počet číslic m posuvný registr je vybrán jako jedno z Mersennových prvočísel (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), a vnitřní odkazy registru musí být zvolena podle s neredukovatelnými primitivními polynomy s nejvyšším stupněm m. V tomto případě může perioda šifry gama dosáhnout (2 m-1).

LFSR se rychle a snadno implementuje do softwaru i hardwaru. Při správné volbě bitů zpětné vazby mají generované sekvence dobré statistické vlastnosti. LFSR se používá jako základní prvek pro budování vysoce bezpečných systémů.

Kaskáda registrů je sada LFSR propojených takovým způsobem, že chování jednoho LFSR závisí na chování předchozího LFSR v kaskádě. Toto "závislé" chování je obvykle nastaveno tak, aby řídilo počítadlo posunu dalšího LFSR prvním LFSR.

Například registr je posunut o jeden krok, pokud je hodnota předchozího registru 1, a pokud je hodnota 0, pak se registr posune o dva kroky nebo jinak. Velké množství takových kombinací umožňuje velmi vysokou bezpečnost.

Nejbezpečnější sekvence jsou vytvářeny zmenšujícím se generátorem na základě jednoduché interakce mezi výsledky dvou registrů LFSR. Bity jednoho výsledku určují, zda budou odpovídající bity druhého výsledku použity jako součást úplného "klíče proudu". Generátor komprese je jednoduchý, škálovatelný a má dobré bezpečnostní vlastnosti. Jeho nevýhodou je, že rychlost generování „streamovacího klíče“ nebude konstantní, pokud nebudou přijata určitá opatření.

Fibonacciho metoda se zpožděním Jeden z široce používaných Fibonacciho generátorů je založen na následujícím iterativním vzorci:

Kde Y k- reálná čísla z rozsahu

Rýže. 2. Round-robin šifrování

Režim výstupní zpětné vazby DES lze použít ke generování pseudonáhodných čísel, podobně jako se používá pro šifrování toku. Výstupem každého stupně šifrování je 64bitová hodnota, z níž je pouze horních j bitů vráceno zpět pro šifrování. 64bitové výstupy tvoří sekvenci pseudonáhodných čísel s dobrými statistickými vlastnostmi.

Generátor pseudonáhodných čísel, popsaný ve standardu ANSI X9.17, je jedním z kryptograficky nejbezpečnějších generátorů pseudonáhodných čísel. Aplikace využívající tuto technologii zahrnují aplikace finančního zabezpečení a PGP.

Generátor ANSI X9.17 se skládá z následujících částí (obrázek 3):

1. Vstup: Generátor je řízen dvěma pseudonáhodnými vstupy. První vstup je 64bitová reprezentace aktuálního data a času ( DT i), které se mění při každém vygenerování čísla. Druhým vstupem je 64bitová počáteční hodnota, která je inicializována na nějakou libovolnou hodnotu a změněna během generování sekvence pseudonáhodných čísel ( Vi).

2. Klíče: Generátor používá tři trojité DES moduly se dvěma klíči K 1 , K 2 . Všechny tři používají stejný 56bitový pár klíčů, který musí být utajen a použit pouze ke generování pseudonáhodného čísla.

Rýže. 3. Generátor pseudonáhodných čísel ANSI X9.17

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 na každém jeho bitu operace XOR s výstupem generátoru, která 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 pro 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.

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-Micali generátory, RSA, BBS, kompresní, aditivní generátory atd.).

Matematická podpora syntézy proudových kryptografických algoritmů byla ve srovnání s blokovými kryptografickými algoritmy vyvinuta úplněji a podrobněji. K vytváření proudových šifer se však často používají algoritmy blokové šifry v režimech OFB nebo CFB.

Nejjednodušším druhem zpětné vazby je lineární funkce, jako je modulo 2 součet obsahů určitých bitů. Takový registr se nazývá Linear Feedback Shift Register (zkráceně LFSR). V obecném případě je lineární zpětná vazba dána vzorcem . Tady c k= 1 pokud k bit se používá ve funkci zpětné vazby a c k= 0 jinak. Symbol Å znamená sčítání modulo 2 (exkluzivní OR).

Uvažujme například LFSR s funkcí zpětné vazby (viz obrázek).

Pokud je počáteční stav registru 1111, pak v následujících taktech přijme následující řadu stavů: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0010, 0 , 1110, 1111, 1111, 1111 …

Výstupní sekvence je vytvořena z nejméně významné (pravé) číslice registru. Bude to vypadat takto: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Je vidět, že vygenerovaná bitová sekvence je zcela určena počátečním stavem registru a zpětnovazební funkcí. Protože počet možných stavů registru je konečný (je roven 2 L), dříve nebo později se sekvence kláves začne opakovat. Maximální délka neopakující se části sekvence kláves se nazývá její perioda. T. Perioda závisí na funkci zpětné vazby. Maximální možná doba je T max=2 L-1 (registr má všechny možné stavy kromě 0000...0). Je volána výstupní sekvence LFSR s maximální periodou M-sekvence.

Pro zjištění podmínek, za kterých bude mít LFSR maximální periodu, se zpětnovazební funkce shodují s charakteristickým polynomem . Takže výše uvedený registr jako příklad odpovídá polynomu . Teoretická analýza ukazuje, že LFSR bude mít maximální periodu právě tehdy, pokud je polynom P(X) je primitivní. Níže jsou uvedeny některé primitivní polynomy doporučené pro praktické použití. Tabulka ukazuje stupně proměnné X v polynomu. Například záznam (31, 3) odpovídá polynomu .

LFSR byly původně navrženy tak, aby byly implementovány v hardwaru jako sada digitálních obvodů. Softwarové implementace LFSR jsou obvykle pomalejší než hardwarové implementace. Pro zvýšení výkonu je výhodné ukládat stav registru jako celé číslo L- číslo bitu, jehož jednotlivé bity odpovídají binárním číslicím registru. Poté se pro přístup k jednotlivým bitům používají bitové operace (posun, maskování atd.).