Linearni povratni premični register. Linearni rekurentni register

Povratni premični register ( FSR ) sestoji iz dveh delov: premični register in povratne funkcije .

Shift register (Napaka: Referenčni vir ni najden) je zaporedje bitov. Ko je treba bit ekstrahirati, se vsi biti premikalnega registra premaknejo v desno za 1 mesto. Novi skrajni levi bit je vrednost povratne funkcije preostalih bitov v registru. Pika Shift register je dolžina nastalega zaporedja, preden se začne ponavljati.

Najenostavnejši tip povratnega premikalnega registra je linearni premikalni register s povratno zvezo (LFSR – levo Povratne informacije Shift Registrirajte se) (Napaka: Referenčni vir ni bil najden). Povratna informacija je preprosto XOR nekaterih p bitov. register, se imenuje seznam teh bitov bypass zaporedje.

n-bit LFSR je lahko v enem od 2 n -1 notranja stanja. To pomeni, da lahko teoretično tak register ustvari psevdonaključno zaporedje s piko 2 n -1 bitov. Število notranjih stanj in perioda sta enaka, saj bo polnjenje registra z ničlami ​​povzročilo neskončno zaporedje ničel, kar je popolnoma neuporabno. Samo z določenimi zaporedji dotikov bo LFSR krožil skozi vse 2 n -1 notranja stanja. Takšni LFSR se imenujejo LFSRz najdaljšim obdobjem.

Da ima določena LFSR največjo periodo, polinom, ki je sestavljen iz zaporedja pipa in konstante 1 mora biti primitiven modulo 2 .

Izračun primitivnosti polinoma je dokaj zapleten matematični problem. Zato obstajajo že pripravljene tabele, v katerih so navedena števila zaporedij pipov, ki zagotavljajo največje obdobje generatorja. Na primer, za 32-bitni premični register lahko najdete naslednji vnos: (32,7,5,3,2,1,0) . To pomeni, da morate za ustvarjanje novega bita sešteti dvaintrideseti, sedmi, peti, tretji, drugi in prvi bit s funkcijo XOR.

Koda za takšen LFSR v C++ bi bila:

// Katera koli vrednost, ki ni nič

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^ShiftRegister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

vrni ShiftRegister & 0x00000001;

Programske implementacije LFSR so precej počasne in delujejo hitreje, če so napisane v asemblerju in ne v C. Ena od rešitev je uporaba 16 LFSR vzporedno (ali 32, odvisno od dolžine besede v arhitekturi določenega računalnika). V tej shemi je uporabljen niz besed, katerega velikost je enaka dolžini LFSR, vsaka enota besede v nizu pa se nanaša na svoj LFSR. Pod pogojem, da se uporabljajo iste zaporedne številke dotika, lahko to povzroči opazno izboljšanje zmogljivosti.

Z povratno vezje je mogoče tudi spremeniti. Generator v tem primeru ne bo imel večje kriptografske moči, vendar ga bo lažje programsko implementirati. Namesto da bi za generiranje novega bita uporabili skrajno levi bit bitov odcepnega zaporedja, XOR vsak bit odcepnega zaporedja z izhodom generatorja in ga nadomestite z rezultatom tega dejanja, potem rezultat generatorja postane nov skrajni levi bit ( Napaka: Referenčni vir ni bil najden).

Ta sprememba se imenuje Konfiguracija Galois. V jeziku C je videti takole:

statični nepredznačeni dolgi ShiftRegister = 1;

void seed_LFSR (nepodpisano dolgo seme)

ShiftRegister = seme;

int Galua_LFSR(void)

če (ShiftRegister & 0x00000001) (

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

ShiftRegister >>= 1;

Izplačilo je, da se vsi XOR-ji izvedejo v eni operaciji. To vezje je lahko tudi vzporedno.

LFSR-ji so sami po sebi dobri generatorji psevdonaključnih zaporedij, vendar imajo nekatere nezaželene nenaključne lastnosti. Zaporedni biti so linearni, zaradi česar so neuporabni za šifriranje. Za dolžino LFSR n notranje stanje predstavlja prejšnje n izhodni bit generatorja. Tudi če je shema povratnih informacij tajna, jo lahko določi 2 n izhodnih bitov generatorja z uporabo posebnih algoritmov. Poleg tega so velika naključna števila, ustvarjena z uporabo zaporednih bitov tega zaporedja, močno korelirana in za nekatere vrste aplikacij niso naključna. Kljub temu se LFSR pogosto uporabljajo za ustvarjanje šifrirnih algoritmov. Za to se uporablja več LFSR-jev, običajno z različnimi dolžinami in zaporednimi številkami pipe. Ključno je začetno stanje registrov. Vsakič, ko je potreben nov bit, se premaknejo vsi registri. Ta operacija se imenuje taktiranje. Izhodni bit je funkcija, po možnosti nelinearna, nekaterih bitov LFSR. Ta funkcija se imenuje združevanje, in generator kot celota - kombinirani generator. Mnogi od teh generatorjev so še danes varni.

Shift register z linearno povratno zvezo(RSLOS, angl. linearni povratni premikalni register, LFSR ) je premični register bitnih besed, v katerem je vrednost vhodnega (drsnega) bita enaka linearni logični funkciji od vrednosti preostalih bitov registra pred premikom. Organizira se lahko s programsko in strojno opremo. Uporablja se za generiranje psevdonaključnih zaporedij bitov, kar se uporablja zlasti v kriptografiji.

Opis

Nadzor registra v izvedbah strojne opreme se izvaja z uporabo impulza premika (sicer imenovanega nastavljen na uro oz sinhronizacijski impulz) za vse celice. Upravljanje registra v programskih implementacijah se izvaja z izvajanjem zanke. Pri vsaki ponovitvi zanke se izračuna povratna funkcija in biti v besedi premaknejo.

Načelo delovanja

Linearna kompleksnost

Korelacija Neodvisnost

Da bi dosegli visoko linearno kompleksnost generiranega zaporedja, kriptografi nelinearno združijo izhode več premikalnih registrov. V tem primeru lahko eno ali več izhodnih sekvenc (ali celo izhodov posameznih LFSR) poveže s skupnim tokom in odpre kriptoanalitik. Vdiranje na podlagi takšne ranljivosti se imenuje korelacija odpiranje. Glavna ideja takšnega vdora je najti neko korelacijo med izhodom generatorja in izhodi njegovih sestavnih delov. Nato lahko z opazovanjem izhodnega zaporedja pridobimo informacije o teh vmesnih izhodih in tako vdremo v generator. Thomas Siegenthaler je pokazal, da je mogoče natančno opredeliti korelacijsko neodvisnost in da obstaja kompromis med korelacijsko neodvisnostjo in linearno kompleksnostjo.

Izvedba programske opreme

Programske implementacije RSLOS so precej počasne in delujejo hitreje, če so napisane v asemblerju. Ena od rešitev je vzporedna uporaba 16 RLLS (ali 32, odvisno od dolžine besede v računalniški arhitekturi). V takšni shemi se uporablja niz besed, katerih velikost je enaka dolžini premikalnega registra, vsak bit besede pa se nanaša na svoj LFSR. Ker se uporablja enako število zaporedij pipov, lahko to povzroči opazno povečanje zmogljivosti generatorja.

Fibonaccijeva konfiguracija

Razmislite o 32-bitnem premikalnem registru. Ima zaporedje pobega (32, 31, 30, 28, 26, 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\desno)). To pomeni, da je za generiranje novega bita potrebno sešteti 31., 30., 29., 27., 25. in 0. bit z uporabo operacije XOR. Nastali LFSR ima največjo dobo 2 32 − 1 (\displaystyle 2^(32)-1). Koda za tak register v C je naslednja:

int LFSR_Fibonacci (void) (statična nepredznačena dolga S = 0x00000001; S = ((((S >> 31) ^ (S >> 30) ^ (S >> 29) ^ (S >> 27) ^ (S >> 25) ^ S) & 0x00000001)<< 31 ) | (S >> 1); vrni S & 0x00000001 ; )

Konfiguracija Galois

Ta generator nima večje kriptografske moči, vendar daje povečanje zmogljivosti: vse operacije XOR prek paralelizacije se lahko izvajajo v eni operaciji in ne zaporedno eno za drugo, kot v Fibonaccijevi konfiguraciji. Ta shema bo prinesla tudi dobiček pri implementaciji strojne opreme.

Koda za 32-bitni premični register v C je naslednja:

int LFSR_Galois (void) (statično nepredznačeno dolgo S = 0x00000001; če (S & 0x00000001) (S = (S ^ 0x80000057 >> 1) | 0x80000000; vrni 1;) else (S >>= 1; vrni 0;))

Omeniti velja, da je cikel fiksnega števila klicev funkcije LFSR_Galois v konfiguraciji Galois približno 2-krat hitrejši od funkcije LFSR_Fibonacci v konfiguraciji Fibonacci (prevajalnik MS VS 2010 na Intel Core i5).

Primer generiranega zaporedja

Fibonaccijeva konfiguracija

Naj bo LFSR podan s karakterističnim polinomom x 3 + x + 1 (\displaystyle x^(3)+x+1). To pomeni, da bosta odcepna bita 2. in 0., enota v polinomski formuli pa pomeni, da je 0. bit vhod. Funkcija povratne informacije ima obliko S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Recimo, da je bilo začetno stanje premikalnega registra zaporedje . Nadaljnja stanja registra so prikazana v spodnji tabeli:

Ker se je notranje stanje v sedmem koraku vrnilo v prvotno stanje, se bodo bitovi ponovili od naslednjega koraka. Ustvarjeno zaporedje je torej: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle\levo)(vrstni red bitov v zaporedju ustreza vrstnemu redu, v katerem jih je ustvaril LFSR). Tako je perioda zaporedja 7, torej največja možna vrednost, ki se je zgodila zaradi primitivnosti danega polinoma.

Konfiguracija Galois

Vzemimo enak karakteristični polinom, tj. c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). Izhodnemu bitu se doda samo 1. bit. Začetno stanje je enako. Dodatna stanja registra:

Notranje stanje registra se je v sedmem koraku vrnilo v prvotno stanje, zato je tudi njegova perioda enaka 7. Za razliko od Fibonaccijeve konfiguracije se je notranja stanja registra izkazala za drugačna, vendar je generirano zaporedje enako. , premaknjeno le za 4 cikle: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle\levo)(vrstni red bitov v zaporedju ustreza vrstnemu redu, v katerem jih je ustvaril LFSR).

Generiranje primitivnih polinomov

Prednosti in slabosti

Prednosti

• visoka zmogljivost kriptografskih algoritmov, ustvarjenih na podlagi LFSR (na primer pretočne šifre);
• uporaba samo najpreprostejših bitnih operacij seštevanja in množenja, implementiranih v strojni opremi v skoraj vseh računalniških napravah;
• dobre kriptografske lastnosti (LFSR lahko generirajo zaporedja z dolgo periodo z dobrimi statističnimi lastnostmi);
• zaradi svoje strukture je LFSR enostavno analizirati z algebrskimi metodami.

Napake

Načini za izboljšanje kriptografske trdnosti generiranih zaporedij

Generatorji z več premičnimi registri

Ta tip generatorja je sestavljen iz več linearnih povratnih premikovnih registrov, ki generirajo bite x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\pike ,\;x_(M,i)) oz. Nadalje se generirani biti transformirajo z neko logično funkcijo f (x 1, i, x 2, i, …, x M, i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\pike,\;x_(M ,jaz))). Upoštevati je treba, da imajo generatorji tega tipa dolžine registrov L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\pike ,\;M), so praprosti drug z drugim.

Obdobje tega generatorja 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)), Kje L = ∑ i = 1 M L i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- skupno število celic. Zato uporaba več LFSR-jev poveča obdobje generiranega zaporedja v primerjavi z enim samim registrom, kar poveča kriptografsko moč generatorja. Prav tako poveča linearno kompleksnost ali dolžino najkrajšega registra, ki ustreza danemu generatorju. Tak register najdemo z algoritmom Berlekamp-Massey z uporabo generiranega zaporedja. V najboljšem primeru je njegova dolžina sorazmerna z obdobjem generiranega zaporedja.

Generatorji z nelinearnimi transformacijami

Blokovni diagram takšnega generatorja se ne razlikuje od diagrama prejšnjega generatorja. Glavna razlika je v tem, da je transformator podana z nelinearno logično funkcijo f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\pike ,x_(M))). Kot taka funkcija se na primer vzame Zhegalkinov polinom (v skladu z Zhegalkinovim izrekom je lahko katera koli logična funkcija enolično predstavljena z Zhegalkinovim polinomom).

Na njem je mogoče implementirati tudi nelinearni generator nelinearni povratni premikalni register. Lahko da 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L)) različice zaporedij maksimalna perioda, ki je večja od tiste pri LFSR.

Kriptografska moč tega generatorja je povečana zaradi nelinearnosti uporabljene funkcije. Določanje stanja registrov iz generiranega bitnega zaporedja je zapleten matematični problem, saj ni poznanega algoritma, ki bi obnovil prvotna stanja.

Ta metoda se uporablja na primer v generator Geff in posplošenega Geffovega generatorja, vendar se lahko takšni generatorji prekinejo s korelacijskim napadom.

Generatorji z različnim časovnim premičnim registrom

stop-go generator

stop-go generator(angleško Stop-and-Go , Both-Piper) uporablja izhod LFOS-1 za nadzor taktne frekvence LFOS-2, tako da LFSR-2 spremeni svoje stanje na neki točki v času samo, če je izhod LFOS-1 takrat je bila enaka enoti. Ta shema se ni upirala odprtju korelacije.

Da bi povečali kriptografsko moč, je bilo predlagano alternator stop and go. Uporablja tri premikalne registre različnih dolžin. Tukaj LFOS-1 nadzoruje urno frekvenco 2. in 3. registra, tj. LFSR-2 spremeni svoje stanje, ko je izhod LFSR-1 enak eni, in LFSR-3 - ko je izhod LFSR-1 enak nič. Izhod generatorja je operacija seštevanja modulo dveh izhodov RSLOS-2 in RSLOS-3. Ta generator ima veliko periodo in veliko linearno kompleksnost. Obstaja metoda korelacijskega odpiranja RLOS-1, vendar to ne oslabi močno kriptografskih lastnosti generatorja.

Uporablja se sofisticirana časovna shema dvosmerni generator stop and go, ki uporablja 2 premikalna registra enake dolžine. Če izhod RLOS-1 na neki točki v času t i − 1 (\displaystyle t_(i-1))- ena, potem RLOS-2 v tem trenutku ni umerjen t i (\displaystyle t_(i)). Če je izhod RLOS-2 v trenutku t i − 1 (\displaystyle t_(i-1)) je enako nič in v času t i − 2 (\displaystyle t_(i-2))- ena, in če je ta register v tem trenutku taktiran t i (\displaystyle t_(i)), potem se v istem trenutku RLOS-1 ne taktira. Linearna kompleksnost tega vezja je približno enaka periodi generiranega zaporedja.

Samodecimalni generator

Večstopenjski oscilator z notranjim produktom

Ta generator uporablja dva premikalna registra RSLOS-1 in RSLOS-2. Urna frekvenca RSLOS-2 in d (\displaystyle d) krat več kot pri RSLOS-1. Določeni biti teh registrov se med seboj pomnožijo z operacijo IN. Rezultati množenja se seštejejo z operacijo XOR in dobimo izhodno zaporedje. Ta generator ima visoko linearno kompleksnost in dobre statistične lastnosti. Vendar pa je njegovo stanje mogoče določiti iz izhodnega zaporedja dolžine L 1 + L 2 + log 2 ⁡ d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), Kje L 1 (\displaystyle L_(1)) in L 2 (\displaystyle L_(2)) sta dolžini LFOS-1 oziroma LFOS-2 in d (\displaystyle d)- razmerje njihovih taktnih frekvenc.

Gollmannova kaskada

To vezje je izboljšana različica generatorja stop-go. Sestavljen je iz zaporedja LFSR, od katerih časovno razporeditev vsakega nadzira prejšnji LFSR. Če je izhod RLOS-1 v času t i (\displaystyle t_(i)) je 1, potem je RLOS-2 takt. Če je izhod RLOS-2 v trenutku t i (\displaystyle t_(i)) je 1, potem je takt RLOS-3 in tako naprej. Izhod zadnjega LFSR je izhod generatorja. Če je dolžina vseh LFSR enaka in enaka L (\displaystyle L), nato obdobje sistema od M (\displaystyle M) LFSR je enako (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), linearna kompleksnost pa je L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .

Ta ideja je preprosta in jo je mogoče uporabiti za ustvarjanje zaporedij z velikimi periodami, velikimi linearnimi zapletenostmi in dobrimi statističnimi lastnostmi. A žal so občutljivi na obdukcijo, imenovano zaklepanje(ang. lock-in) ko

Linearni povratni Shift Register (LFSR) je mehanizem za ustvarjanje psevdo-naključnega zaporedja binarnih bitov. Register (slika 1) je sestavljen iz določenega števila celic, ki jih nastavi inicializacijski vektor (najpogosteje tajni ključ). Delovanje registra je določeno s prisotnostjo ali odsotnostjo povezave od vsakega bita do povratne informacije. Pipe povratnega registra niso fiksne, ampak so del ključa. V naslednjem koraku se vsebina celic registra premakne za en položaj v desno in en bit, ki ostane prost zaradi operacije XOR, se postavi v skrajno levo celico.

riž. 1. Linearni premični register s povratno zvezo

Da bi dosegli največjo šifro gama obdobje, število števk m premikalni register je izbran kot eno od Mersennovih praštevil (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), in notranje povezave registra je treba izbrati glede na ireduktibilne primitivne polinome z najvišjo stopnjo m. V tem primeru lahko obdobje šifre gama doseže (2 m-1).

LFSR je hiter in enostaven za implementacijo v programsko in strojno opremo. S pravilno izbiro povratnih bitov imajo generirana zaporedja dobre statistične lastnosti. LFSR se uporablja kot osnovni element za gradnjo visoko varnih sistemov.

Kaskada registrov je niz LFSR-jev, povezanih tako, da je obnašanje enega LFSR-ja odvisno od obnašanja prejšnjega LFSR-ja v kaskadi. To "odvisno" vedenje je običajno nastavljeno za nadzor števca premikov naslednjega LFSR s prvim LFSR.

Na primer, register se premakne za en korak, če je vrednost prejšnjega registra 1, in če je vrednost 0, se register premakne za dva koraka ali drugače. Veliko število takih kombinacij omogoča zelo visoko varnost.

Najbolj varna zaporedja so proizvedena s skrčenim generatorjem, ki temelji na preprosti interakciji med rezultati dveh registrov LFSR. Biti enega rezultata določajo, ali bodo ustrezni biti drugega rezultata uporabljeni kot del celotnega "ključa toka". Generator stiskanja je preprost, razširljiv in ima dobre varnostne lastnosti. Njegova pomanjkljivost je, da hitrost generiranja "pretočnega ključa" ne bo konstantna, razen če so sprejeti nekateri previdnostni ukrepi.

Fibonaccijeva metoda z zamudami Eden od pogosto uporabljenih Fibonaccijevih generatorjev temelji na naslednji iterativni formuli:

Kje Y k- realna števila iz obsega

riž. 2. Round-robin šifriranje

Izhodni povratni način DES se lahko uporablja za ustvarjanje psevdo-naključnih števil, podobno kot se uporablja za šifriranje toka. Izhod vsake stopnje šifriranja je 64-bitna vrednost, od katere se samo zgornjih j bitov vrne za šifriranje. 64-bitni izhodi sestavljajo zaporedje psevdonaključnih števil z dobrimi statističnimi lastnostmi.

Generator psevdonaključnih števil, opisan v standardu ANSI X9.17, je eden najbolj kriptografsko varnih generatorjev psevdonaključnih števil. Aplikacije, ki uporabljajo to tehnologijo, vključujejo finančno varnost in aplikacije PGP.

Generator ANSI X9.17 je sestavljen iz naslednjih delov (slika 3):

1. Vhod: Generator krmilita dva psevdonaključna vhoda. Prvi vhod je 64-bitna predstavitev trenutnega datuma in ure ( DT i), ki se spremenijo vsakič, ko je številka ustvarjena. Drugi vhod je 64-bitna začetna vrednost, ki je inicializirana na neko poljubno vrednost in spremenjena med generiranjem zaporedja psevdonaključnih števil ( Vi).

2. Tipke: Generator uporablja tri trojne DES module z dvema ključema K 1 , K 2 . Vsi trije uporabljajo isti 56-bitni par ključev, ki mora biti tajen in uporabljen samo za ustvarjanje psevdo-naključnega števila.

riž. 3. Generator psevdonaključnih števil ANSI X9.17

Povratni premični register je sestavljen iz dveh delov: premikalnega registra in povratne funkcije.

Slika 19. Pomični register povratne informacije.

Na splošno je premični register zaporedje nekaterih elementov obroča ali polja. Najpogosteje uporabljena bit menjalni registri. Dolžina takega registra je izražena kot število bitov. Vsakič, ko je bit priklican, se vsi biti v registru premaknejo v desno za en položaj. Nov najpomembnejši bit se izračuna kot funkcija vseh drugih bitov v registru. Izhod je običajno najmanj pomemben bit. Perioda premikalnega registra je dolžina izhodnega zaporedja, preden se začne ponavljati.

Najenostavnejša vrsta premikalnih registrov je premikalni register z linearno povratno zvezo (LFSR ali LRS). Povratna informacija je preprosta operacija XOR na nekaterih delih registra. Seznam teh bitov je določen karakteristični polinom in poklical zaporedje tapkanja. Včasih se ta shema imenuje Fibonaccijeva konfiguracija.

Slika 20. LFOS Fibonaccijeve konfiguracije.

Pri programski implementaciji LFSR se uporablja spremenjena shema: za generiranje novega pomembnega bita se namesto uporabe bitov zaporedja pipa izvede operacija XOR na vsakem od njegovih bitov z izhodom generatorja, ki nadomesti staro bit zaporedja tapkanja. Ta sprememba se včasih imenuje Konfiguracija Galois.

Slika 21. RLOS konfiguracije Galois.

n-bitni LFSR je lahko v enem od 2 n– 1 notranja stanja. To pomeni, da lahko teoretično tak register ustvari psevdonaključno zaporedje s periodo 2 n– 1 bitov (polnjenje z ničlami ​​je popolnoma neuporabno). Prehod vseh 2 n– 1 notranja stanja možna le pri določenih zaporedjih dotikov. Takšni registri se imenujejo LFSR z najvišjo dobo. Za zagotovitev največjega obdobja LFSR je potrebno, da je njegov značilni polinom primitiven modulo 2. Stopnja polinoma je dolžina premikalnega registra. Polinom primitivne stopnje n- tako je ireduktibilen polinom, ki je delitelj, vendar ni delitelj x d+ 1 za vse d, ki sta delitelja 2 n– 1. (Ko govorimo o polinomih, izraz praštevilo nadomesti z izrazom ireduktibilni polinom). Karakteristični polinom LFSR, prikazan na slikah:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

je primitiven modulo 2. Obdobje takega registra bo največje, kroži skozi vseh 2 32 - 1 vrednosti, dokler se ne ponovijo. Najpogosteje uporabljeni so stanjšani polinomi, tj. ki imajo le nekaj koeficientov. najbolj priljubljeni trinomi.

Pomemben parameter generatorja, ki temelji na LFSR, je linearna kompleksnost. Opredeljena je kot dolžina n najkrajši LFSR, ki lahko simulira izhod generatorja. Linearna zapletenost je pomembna, ker s preprostim Berlenkamp-Masseyjev algoritem mogoče je ponovno ustvariti takšen LFSR s preverjanjem samo 2 n gama bitov. Z definicijo želenega LFSR je šifra toka dejansko pokvarjena.

Poleg LFSR se uporabljajo tudi premični registri z nelinearno povratno zvezo, prenosno povratno zvezo itd.

Na osnovi številsko-teoretičnega pristopa je bilo razvitih več generatorjev (Blum-Micali generatorji, RSA, BBS, kompresijski, aditivni generatorji itd.).

Matematična podpora za sintezo tokovnih kriptografskih algoritmov je bila razvita bolj celovito in podrobneje v primerjavi z blokovnimi kriptografskimi algoritmi. Vendar se za ustvarjanje tokovnih šifer pogosto uporabljajo algoritmi blokovnega šifriranja v načinih OFB ali CFB.

Najenostavnejša vrsta povratne funkcije je linearna funkcija, kot je vsota modula 2 vsebine določenih bitov. Takšen register se imenuje premični register z linearno povratno zvezo (na kratko LFSR). V splošnem primeru je linearna povratna funkcija podana s formulo . Tukaj c k= 1 če k th bit se uporablja v funkciji povratne informacije in c k= 0 sicer. Simbol Å pomeni seštevanje po modulu 2 (izključni ALI).

Na primer, razmislite o LFSR s povratno funkcijo (glejte sliko).

Če je začetno stanje registra 1111, potem bo v nadaljnjih taktih sprejel naslednje nize stanj: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100 , 1110, 1111, 1111, 1111 …

Izhodno zaporedje se oblikuje iz najmanj pomembne (skrajno desne) števke registra. Videti bo takole: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Vidimo, da je generirano bitno zaporedje v celoti določeno z začetnim stanjem registra in povratno funkcijo. Ker je število možnih stanj registra končno (je enako 2 L), potem se bo slej ko prej zaporedje tipk začelo ponavljati. Največja dolžina neponavljajočega se dela ključnega zaporedja se imenuje njegova perioda. T. Obdobje je odvisno od povratne funkcije. Največje možno obdobje je T max=2 L-1 (register sprejme vsa možna stanja razen 0000...0). Pokliče se izhodno zaporedje LFSR z največjo periodo M-zaporedje.

Če želite izvedeti pogoje, pod katerimi bo imel LFSR največjo periodo, se povratne funkcije ujemajo z značilnim polinomom. Torej zgornji register kot primer ustreza polinomu . Teoretična analiza kaže, da bo imel LFSR največjo periodo, če in samo če je polinom p(x) je primitiven. Spodaj je nekaj primitivnih polinomov, priporočenih za praktično uporabo. Tabela prikazuje stopnje spremenljivke x v polinomu. Na primer, vnos (31, 3) se ujema s polinomom.

LFSR so bili prvotno zasnovani za implementacijo v strojno opremo kot niz digitalnih vezij. Programske izvedbe LFSR so običajno počasnejše od strojnih izvedb. Za povečanje zmogljivosti je koristno shraniti stanje registra kot celo število L- bitna številka, katere posamezni biti ustrezajo binarnim cifram registra. Nato se za dostop do posameznih bitov uporabljajo bitne operacije (premik, maskiranje itd.).