Uvod u osnove modernih šifri sa simetričnim ključem. Linearni pomični registri povratne sprege kao generatori pseudo-slučajnih brojeva

U registru pomaka sa linearnom povratnom spregom razlikuju se dva dijela (modula): sam pomakni registar i kolo (ili potprogram) koji izračunava vrijednost umetnutog bita. Registar se sastoji od funkcijskih ćelija (ili bitova strojne riječi ili nekoliko riječi), od kojih svaka pohranjuje trenutno stanje jednog bita. Broj ćelija naziva se dužina registra. Bitovi (ćelije) se obično numerišu brojevima, od kojih je svaki sposoban pohraniti bit, a izračunati bit se gura u ćeliju, a sljedeći generirani bit se izvlači iz ćelije. Proračun umetnutog bita se obično vrši prije pomaka registra, a tek nakon pomaka se vrijednost izračunatog bita stavlja u ćeliju.

Period registra pomaka je minimalna dužina rezultujuće sekvence prije nego što se počne ponavljati. Pošto registar bitnih ćelija ima samo različita stanja različita od nule, onda, u principu, period registra ne može preći ovaj broj. Ako je period registra jednak ovom broju, onda se takav registar naziva registar maksimalnog perioda.

Za LFSR, funkcija povratne sprege je linearna Boolean funkcija stanja svih ili nekih bitova registra. Na primjer, zbroj po modulu dva ili njegov logički inverz je linearna Boolean funkcija (XOR operacija, označena kao u formulama) i najčešće se koristi u takvim registrima.

U ovom slučaju obično se pozivaju oni bitovi koji su varijable funkcije povratne sprege krivine.

Kontrola registra u hardverskim implementacijama se izvodi primjenom impulsa pomaka (inače se naziva sat ili sinhronizacijski puls) svim ćelijama, u softveru - izvršavanjem programskog ciklusa, uključujući izračunavanje funkcije povratne sprege i pomaka bita u riječi.

Za vrijeme svakog otkucaja sata izvode se sljedeće operacije:

Registar pomaka s linearnom povratnom spregom

Dakle, logička operacija XOR (isključivo OR) uzima se kao povratna funkcija, odnosno:

Svojstva primitivnih polinoma

Svojstva

Svojstva sekvence koju proizvodi LFSR usko su povezana sa svojstvima pridruženog polinoma. Njegovi koeficijenti različiti od nule se nazivaju krivine, kao i odgovarajuće ćelije registra, dajući vrijednosti argumenata povratne funkcije.

Linearna složenost

Linearna složenost binarne sekvence jedna je od najvažnijih karakteristika LFSR operacije. Hajde da uvedemo sljedeću notaciju:

Linearna složenost beskonačnog binarnog niza se zove broj, koji se definiše na sledeći način:

Linearna složenost konačnog binarnog niza naziva se broj , koji je jednak dužini najkraćeg LFSR-a, koji generiše niz koji ima kao prve članove .

Svojstva linearne složenosti

Neka i budu binarni nizovi. onda:

Korelaciona nezavisnost

Da bi dobili visoku linearnu složenost, kriptografi pokušavaju nelinearno kombinirati rezultate višestrukih izlaznih sekvenci. U ovom slučaju, opasnost je da se jedna ili više izlaznih sekvenci (često čak i izlazi pojedinačnih LFSR-ova) mogu povezati zajedničkim ključem i otvoriti korištenjem linearne algebre. Hakiranje zasnovano na takvoj ranjivosti se zove korelacione autopsije. Thomas Siegenthaler je pokazao da je moguće tačno definisati korelacione nezavisnosti i da postoji kompromis između korelacione nezavisnosti i linearne složenosti.

Glavna ideja iza ovog haka je pronaći neku korelaciju između izlaza generatora i izlaza jednog od njegovih sastavnih dijelova. Zatim, posmatranjem izlaznog niza, mogu se dobiti informacije o ovom međuizlazu. Koristeći ove informacije i druge korelacije, moguće je prikupiti podatke o drugim srednjim izlazima dok generator ne bude hakovan.

Korelacioni napadi ili varijacije kao što su napadi brze korelacije uspešno su korišćeni protiv mnogih generatora tokova ključeva baziranih na linearnoj povratnoj sprezi, koji uključuju kompromis između složenosti računara i efikasnosti.

Primjer

Za LFSR sa pridruženim polinomom, generirani niz ima oblik . Pretpostavimo da je prije početka procesa sekvenca upisana u registar, tada će period generiranog toka bitova biti jednak 7 sa sljedećim nizom:

Pošto se unutrašnje stanje na sedmom koraku vratilo u prvobitno stanje, onda će, počevši od sledećeg koraka, doći do ponavljanja. Drugim riječima, ispostavilo se da je period niza jednak 7, što se dogodilo zbog primitivnosti polinoma.

Algoritmi za generisanje primitivnih polinoma

Spremni stolovi

Izračunavanje primitivnosti polinoma je prilično složen matematički problem. Stoga postoje gotove tabele koje navode brojeve sekvenci slavina koje daju maksimalan period generatora. Na primjer, za 32-bitni pomakni registar postoji niz . To znači da je za generiranje novog bita potrebno sabrati 31., 30., 29., 27., 25. i 0. bit koristeći XOR funkciju. Kod za takav LFSR u jeziku C je sljedeći:

Int LFSR (void ) ( statički neoznačeni dug S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); povratak S & 1 ; )

Softverske implementacije RSLOS generatora su prilično spore i rade brže ako su napisane na asembleru, a ne u C. Jedno rešenje je da se paralelno koristi 16 RLLS (ili 32, u zavisnosti od dužine reči u arhitekturi određenog računara). U takvoj šemi koristi se niz riječi čija je veličina jednaka dužini LFSR-a, a svaki bit riječi niza se odnosi na svoj LFSR. Pod uslovom da se koriste isti redosledni brojevi slavina, ovo može dati primetno povećanje performansi. [potreban je uzorak koda] (Vidi: bitslice).

Galois konfiguracija

Galois konfiguracija linearnog registra pomaka povratne sprege

Šema povratnih informacija se također može mijenjati. U tom slučaju generator neće imati veću kriptografsku snagu, ali će ga biti lakše programski implementirati. Umjesto korištenja bitova tap sekvence za generiranje novog krajnjeg lijevog bita, XOR svaki bit tap sekvence sa izlazom generatora i zamijenite ga rezultatom ove akcije, tada rezultat generatora postaje novi krajnji lijevi bit . U jeziku C to izgleda ovako:

Int LFSR (void) ( statički neoznačeni dugi Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; vrati Q & 1 ; )

Prednost je što se svi XOR-ovi izvode u jednoj operaciji.

• može se dokazati da Fibonačijeva konfiguracija data prva i Galoisova konfiguracija daju iste sekvence (dužine 2 32 −1), ali pomaknute u fazi jedna od druge
• petlja fiksnog broja poziva funkciji LFSR u Galois konfiguraciji je otprilike dvostruko brža nego u Fibonacci konfiguraciji (MS VS 2010 kompajler na Intel Core i5)
• imajte na umu da je u Galois konfiguraciji redoslijed bitova u povratnoj riječi obrnut u odnosu na Fibonaccijevu konfiguraciju

Primjeri generatora

stop-go generatori

Stop-and-Go naizmjenični generator

Ovaj oscilator koristi izlaz jednog LFSR-a za kontrolu frekvencije takta drugog LFSR-a. Izlaz takta RSLOS-2 kontroliše izlaz RSLOS-1, tako da RSLOS-2 može promijeniti svoje stanje u trenutku t samo ako je izlaz RSLOS-1 u trenutku t-1 bio jednak jedan. Ali ova šema nije odoljela otvaranju korelacije.

Stoga je predložen poboljšani generator baziran na istoj ideji. Zove se stop-and-go interleaved generator. Koristi tri LFSR-a različitih dužina. LFSR-2 se taktira kada je izlaz LFSR-1 jednak jedan, a LFSR-3 kada je izlaz LFSR-1 jednak nuli. Izlaz generatora je modulo 2 zbir RSLOS-2 i RSLOS-3. Ovaj generator ima veliki period i veliku linearnu složenost. Njegovi autori su pokazali i metodu za otvaranje korelacije RLOS-1, ali to ne slabi mnogo generator.

Gollmann Cascade

Gollmann Cascade

Gollmann Cascade je poboljšana verzija stop-go generatora. Sastoji se od niza LFSR-ova, od kojih je vrijeme svakog od njih kontrolirano prethodnim LFSR-om. Ako je izlaz LFSR-1 u trenutku t 1, tada je LFSR-2 takt. Ako je izlaz LFSR-2 u trenutku t 1, tada je LFSR-3 takt, i tako dalje. Izlaz posljednjeg LFSR-a je izlaz generatora. Ako je dužina svih LFSR-ova ista i jednaka je n, tada je linearna složenost sistema od k LFSR-a .

Ova ideja je jednostavna i može se koristiti za generiranje sekvenci sa velikim periodima, velikom linearnom složenošću i dobrim statističkim svojstvima. Ali, nažalost, podložni su otvaranju, zvanom "zaključavanje" (zaključavanje). Za veću stabilnost, preporučuje se korištenje k najmanje 15. Štaviše, bolje je koristiti više kratkog LFSR nego manje dugog LFSR.

generator praga

generator praga

Ovaj generator pokušava zaobići sigurnosne probleme prethodnih generatora korištenjem promjenjivog broja pomičnih registara. U teoriji, kada se koristi veći broj pomačnih registara, povećava se složenost šifre, što je i urađeno u ovom generatoru.

Ovaj generator se sastoji od velikog broja pomačnih registara, čiji se izlazi napajaju funkciji majorizacije. Ako je broj jedinica na izlazima registara veći od polovine, tada generator proizvodi jedinicu. Ako je broj nula na izlazima veći od polovine, tada generator proizvodi nulu. Da bi poređenje broja nula i jedinica bilo moguće, broj pomeračkih registara mora biti neparan. Dužine svih registara moraju biti relativno proste, a polinomi povratne sprege moraju biti primitivni tako da period generiranog niza bude maksimalan.

Za slučaj tri registra pomaka, generator se može predstaviti kao:

Ovaj generator je sličan Geff generatoru, osim što generator praga ima više linearne složenosti. Njegova linearna složenost je:

gdje su , , dužine prvog, drugog i trećeg registra pomaka.

Njegov nedostatak je što svaki izlazni bit daje neke informacije o stanju registra pomaka. Tačnije 0,189 bita. Stoga ovaj generator možda neće odoljeti otvaranju korelacije.

Druge vrste

Samostanjivanje

Samoopadajući generatori nazivaju se generatori koji kontroliraju vlastitu frekvenciju. Predložena su dva tipa ovakvih generatora. Prvi se sastoji od linearnog povratnog registra pomaka i nekog kola koje taktira ovaj registar ovisno o tome koje su izlazne vrijednosti registra pomaka. Ako je LFSR izlaz jednak jedan, tada se registar taktuje d puta. Ako je izlaz nula, tada se registar taktova k puta. Drugi ima skoro isti dizajn, ali je malo izmijenjen: u krugu takta, kao provjera za 0 ili 1, ne prima se sam izlazni signal, već XOR određenih bitova pomačnog registra s linearnom povratnom spregom. Nažalost, ovakav generator nije siguran.

Oscilator sa više brzina sa unutrašnjim proizvodom

Ovaj generator koristi dva registra pomaka sa linearnom povratnom spregom sa različitim taktnim frekvencijama: LFSR-1 i LFSR-2. Frekvencija takta RLOS-2 je d puta veća od frekvencije RLLS-1. Pojedinačni bitovi ovih registara su kombinovani sa AND operacijom. Izlazi operacije AND su zatim XOR. Izlazni niz se uzima iz ovog XOR bloka. Opet, ovaj generator nije savršen (Nije preživio otvaranje linearne konzistencije. Ako je - dužina LFSR-1, - dužina LFSR-2, a d je omjer taktnih frekvencija, onda je unutrašnje stanje generator se može dobiti iz izlaznog niza dužine ), ali ima visoku linearnu složenost i odlične statističke performanse.

Sekvence registra pomaka se koriste i u kriptografiji i u teoriji kodiranja. Njihova teorija je dobro razvijena, šifre toka zasnovane na registru pomaka bile su radni konj vojne kriptografije mnogo prije pojave elektronike.

Registar pomaka sa povratnom spregom sastoji se od dva dijela: registra pomaka i funkcije povratne sprege (slika 1.2.1). Registar pomaka je niz bitova. (Broj bitova je određen dužinom registra pomaka. Ako je dužina n bitova, tada se registar naziva n-bitni pomakni registar.) Kad god je potrebno izdvojiti bit, svi bitovi pomaknog registra su pomaknut udesno za 1 poziciju. Novi krajnji lijevi bit je funkcija svih ostalih bitova u registru. Izlaz registra pomaka je jedan, obično najmanje značajan bit. Period registra pomaka je dužina rezultujuće sekvence prije nego što se počne ponavljati.

Rice. 1.2.1.

Kriptografi su voljeli stream šifre zasnovane na registru pomaka: bilo ih je lako implementirati pomoću digitalnog hardvera. Samo ću se ukratko dotaknuti matematičke teorije. Godine 1965, Ernst Selmer, glavni kriptograf norveške vlade, razvio je teoriju sekvenci registra pomaka. Solomon Golomb, NSA matematičar, napisao je knjigu u kojoj su navedeni neki od njegovih i Selmerovih rezultata.

Najjednostavniji tip registra pomaka povratne sprege je linearni pomakni registar povratne sprege ili LFSR (slika 1.2.2). Povratna informacija je jednostavno XOR nekih bitova u registru, lista ovih bitova se naziva tap sekvenca. Ponekad se takav registar naziva Fibonačijeva konfiguracija. Zbog jednostavnosti sekvence povratne sprege, prilično napredna matematička teorija može se koristiti za analizu LFSR-a. Kriptografi vole da analiziraju sekvence, ubeđujući sebe da su ove sekvence dovoljno nasumične da bi bile sigurne. LFSR-ovi se češće koriste u kriptografiji nego drugi registri pomaka.

Rice. 1.2.2.

Na sl. 1.2.3 prikazuje 4-bitni LFSR sa dodirom na prvi i četvrti bit. Ako je inicijaliziran vrijednošću 1111, tada će prije ponavljanja registar poprimiti sljedeća interna stanja:

Rice. 1.2.3. 4

Izlazni niz će biti niz najmanjih bitova:

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

n-bitni LFSR može biti u jednom od 2n-1 internih stanja. To znači da, teoretski, takav registar može generirati pseudo-slučajni niz s periodom od 2n-1 bita. (Broj internih stanja i period su 2n-1, jer će popunjavanje LFSR-a nulama uzrokovati da registar pomaka ispusti beskonačan niz nula, što je apsolutno beskorisno.) Samo sa određenim tap sekvencama, LFSR će ciklirati kroz sva 2n-1 interna stanja, takvi LFSR-ovi su LFSR-ovi sa maksimalnim periodom. Rezultirajući rezultat naziva se M-sekvenca.

Da bi određeni LFSR imao maksimalan period, polinom formiran od tap sekvence i konstante 1 mora biti primitivan po modulu 2. Stepen polinoma je dužina registra pomaka. Primitivni polinom stepena n je nesvodljivi polinom koji je delilac, ali nije delilac xd+1 za sve d koji su delioci od 2n-1.

Općenito, ne postoji jednostavan način za generiranje primitivnih polinoma datog stepena po modulu 2. Najlakši način je da nasumično odaberete polinom i provjerite da li je primitivan. Nije lako - i pomalo kao da se proveri da li je slučajno odabrani broj prost - ali mnogi matematički softverski paketi to mogu da urade.

Neki, ali sigurno ne svi, polinomi različitih stupnjeva su primitivni po modulu 2. Na primjer, oznaka (32, 7, 5, 3, 2, 1, 0) znači da je sljedeći polinom primitivan po modulu 2:

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

Ovo se lako može generalizirati na LFSR sa maksimalnim periodom. Prvi broj je dužina LFSR-a. Posljednji broj je uvijek 0 i može se izostaviti. Svi brojevi osim 0 određuju sekvencu tapkanja, koja se računa od lijevog ruba registra pomaka. To jest, članovi polinoma sa nižim stepenom odgovaraju pozicijama bliže desnoj ivici registra.

Nastavljajući primjer, pisanje (32, 7, 5, 3, 2, 1, 0) znači da se za dati 32-bitni pomakni registar, novi bit generira XOR-om trideset drugog, sedmog, petog, trećeg, drugog , i prvi bitovi rezultirajući LFSR će imati maksimalnu dužinu, kružeći kroz 232-1 vrijednosti prije iteracije.

Za izgradnju stream šifri, sekvence na registrima pomaka se vrlo često koriste. Povratni pomakni registar sastoji se od dva dijela: registra pomaka i povratne funkcije, kao što je prikazano na slici. 87. Sam registar pomaka je niz bitova, čiji broj određuje dužinu registra. Dakle, ako je n bitova uključeno u registar, onda kažu da je n-bitni pomakni registar. Svaki put kada se dohvati bit, svi bitovi registra pomaka se pomjeraju udesno za jednu poziciju, obično prema bitovima s najmanjim značajem. Period registra pomaka je dužina rezultujuće sekvence prije nego što se počne ponavljati.

Rice. 87.

Bilo koja matematička funkcija koja izvodi operaciju nad bitovima može djelovati kao povratna informacija. Najjednostavniji tip registra pomaka povratne sprege je linearni pomakni registar povratne sprege (LFSR). U LFSR, povratna informacija je jednostavno operacija sabiranja po modulu 2 (XOR) na nekim bitovima registra; lista ovih bitova se naziva sekvenca odvajanja, ili točaka podizanja, kao što je prikazano na sl. 88. Ponekad se takav obrazac naziva Fibonačijeva konfiguracija. Zbog jednostavnosti sekvence povratne sprege, prilično razvijena matematička teorija može se koristiti za analizu LFSR. U svakom slučaju, kvalitet proizvedenog SRP-a ocjenjuje se posebnim skupom testova.

Rice. 88.

LFSR se zapisuju u obliku polinoma. U ovom slučaju, stepen prvog elementa polinoma ukazuje na broj bitova u registru pomeranja, a eksponencijalni eksponenti preostalih članova polinoma pokazuju koje će tačke preuzimanja biti korišćene. Tako, na primjer, pisanje x 4 + x + 1 znači da će se koristiti registar od četiri elementa za koji će bitovi bi i b 0 učestvovati u formiranju povratne sprege (slika 89).

Rice. 89.4

Razmotrite rad registra prikazanog na sl. 89. Inicijalizirajte ga, na primjer, vrijednošću 0101 (početna inicijalizacija se može izvršiti bilo kojim nizom bitova, osim nizom od samo nula, jer će u ovom slučaju povratna informacija uvijek formirati vrijednost nula i registar će ne proizvodi očekivani PSP). Dakle, u registru postoji pomak za jednu poziciju udesno. Najmanji bitni bit, jednak 1, izbacuje se iz registra i formira prvi bit PRS-a. Oni bitovi koji su bili na pozicijama b i b 0 prije pomaka se dodaju po modulu 2 i formiraju novi

visoki dio registra. Ilustrativan primjer rada razmatranog LFSR-a prikazan je na sl. 90.

Rice. 90.

Kao što se može vidjeti sa sl. 90, popunjavanje registra će proći kroz težinu od 15 od 16 mogućih stanja (prethodno smo utvrdili da se šesnaesto stanje, kada je LFSR 0000, ne može uzeti u obzir). Nakon toga, punjenje registra ponovo će biti jednako početnoj vrijednosti 0101, a generiranje bitova će se početi ponavljati. Izlazni niz registra će biti niz najmanjih bitova (do horizontalne linije na slici 90): 101011110001001. Veličina sekvence bita prije nego što se ponovi naziva se period. Da bi se osigurao maksimalni period određenog LFSR-a (tj. da bi registar prošao kroz sva moguća unutrašnja stanja), polinom koji određuje rad registra mora biti primitivan po modulu 2. Kao i kod velikih prostih brojeva, ne postoji način da se generirati takve polinome. Može se samo uzeti polinom i provjeriti da li je nesvodiv po modulu 2 ili ne. U opštem slučaju, primitivni polinom stepena n je takav nesvodljivi polinom koji je delilac x 2"+1, ali nije delilac xd +1 za sve d koji su delioci 2"-1. B. Schneier daje tablicu nekih polinoma, koji su nesvodljivi po modulu 2.

Sumirajući saznanja dobijena kao rezultat razmatranja primjera rada LFSR-a (slika 90), možemo reći da n-bitni LFSR može biti u jednom od 2”-1 internih stanja. Teoretski, takav registar može generirati pseudo-slučajnu sekvencu s periodom od 2 n -1 bita. Takvi registri se nazivaju LFSR registri sa maksimalnim periodom. Rezultirajući izlaz naziva se t-sekvenca.

Najjednostavnija vrsta povratne funkcije je linearna funkcija, kao što je modulo 2 suma sadržaja određenih bitova. Takav registar se zove Linear Feedback Shift Register (skraćeno LFSR). U opštem slučaju, linearna povratna funkcija je data formulom . Evo c k= 1 ako k th bit se koristi u povratnoj funkciji, i c k= 0 inače. Simbol Å označava sabiranje po modulu 2 (isključivo ILI).

Na primjer, razmotrite LFSR sa funkcijom povratne sprege (vidi sliku).

Ako je početno stanje registra 1111, tada će u narednim ciklusima poprimiti sljedeće nizove stanja: …

Izlazni niz se formira od najmanje značajne (krajnje desne) cifre registra. To će izgledati ovako: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Može se vidjeti da je generirani niz bitova u potpunosti određen početnim stanjem registra i povratnom funkcijom. Pošto je broj mogućih stanja registra konačan (jednak je 2 L), tada će se, prije ili kasnije, sekvenca ključeva početi ponavljati. Maksimalna dužina dijela ključnog niza koji se ne ponavlja naziva se period. T. Period ovisi o povratnoj funkciji. Maksimalni mogući period je T max=2 L-1 (registar preuzima sva moguća stanja osim 0000...0). Poziva se izlazna sekvenca LFSR-a sa maksimalnim periodom M-sekvenca.

Da biste saznali pod kojim uslovima će LFSR imati maksimalni period, funkcije povratne sprege odgovaraju karakterističnom polinomu. Dakle, registar dat gore kao primjer odgovara polinomu . Teorijska analiza pokazuje da će LFSR imati maksimalan period ako i samo ako je polinom P(x) je primitivno. Ispod su neki primitivni polinomi koji se preporučuju za praktičnu upotrebu. Tabela pokazuje stupnjeve varijable x u polinomu. Na primjer, unos (31, 3) odgovara polinomu .

LFSR su prvobitno dizajnirani da se implementiraju u hardver kao skup digitalnih kola. Softverske implementacije LFSR-a su obično sporije od hardverskih implementacija. Za povećanje performansi, korisno je pohraniti stanje registra kao cijeli broj L- broj bita, čiji pojedinačni bitovi odgovaraju binarnim znamenkama registra. Zatim se operacije po bitovima (pomak, maskiranje, itd.) koriste za pristup pojedinačnim bitovima.

Registar pomaka povratne sprege sastoji se od dva dijela: registra pomaka i povratne funkcije.

Slika 19. Registar pomaka povratne sprege.

Općenito, pomični registar je niz nekih elemenata prstena ili polja. Najčešće korišteni bit registri pomaka. Dužina takvog registra je izražena kao broj bitova. Svaki put kada se dohvati bit, svi bitovi u registru se pomiču udesno za jednu poziciju. Novi najznačajniji bit izračunava se kao funkcija svih ostalih bitova u registru. Izlaz je obično najmanji bitni bit. Period registra pomaka je dužina izlazne sekvence prije nego što se počne ponavljati.

Najjednostavniji tip registra pomaka je linearni pomakni registar povratne sprege (LFSR ili LRS). Povratna informacija je jednostavna XOR operacija na nekim bitovima registra. Lista ovih bitova je definirana karakteristični polinom i pozvao tapnite sekvencu. Ponekad se ova šema naziva Fibonačijeva konfiguracija.

Fig.20. LFOS Fibonačijeve konfiguracije.

U softverskoj implementaciji LFSR-a koristi se modificirana shema: za generiranje novog značajnog bita, umjesto korištenja bitova tap sekvence, XOR operacija se izvodi na svakom od njegovih bita sa izlazom generatora, zamjenjujući stari dio sekvence tapkanja. Ova modifikacija se ponekad naziva Galois konfiguracija.

Fig.21. RLOS Galois konfiguracije.

n-bit LFSR može biti u jednom od 2 n– 1 unutrašnje stanje. To znači da, teoretski, takav registar može generirati pseudoslučajni niz s periodom od 2 n– 1 bit (dopuna nulama je potpuno beskorisna). Prolazak svih 2 n– 1 interno stanje moguće samo uz određene sekvence dodira. Takvi registri se nazivaju LFSR sa maksimalnim periodom. Da bi se osigurao maksimalni period LFSR-a, potrebno je da njegov karakteristični polinom bude primitivno modulo 2. Stepen polinoma je dužina registra pomaka. Polinom primitivnog stepena n- tako je nesvodivo polinom koji je djelitelj, ali nije djelitelj x d+1 za sve d, koji su djelitelji od 2 n– 1. (Kada se govori o polinomima, termin prost broj zamijenjen terminom nesvodljivi polinom). Karakteristični polinom LFSR-a prikazan je na slikama:

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

je primitivan po modulu 2. Period takvog registra će biti maksimalan, kruži kroz sve 2 32 - 1 vrijednosti dok se ne ponove. Najčešće se koriste istanjeni polinomi, tj. koji imaju samo neke koeficijente. najpopularnijih trinoma.

Važan parametar generatora zasnovanog na LFSR je linearna složenost. Definiše se kao dužina n najkraći LFSR koji može simulirati izlaz generatora. Linearna složenost je važna jer sa jednostavnim Berlenkamp-Massey algoritam moguće je ponovo kreirati takav LFSR provjerom samo 2 n gama bitovi. Sa definicijom željenog LFSR-a, šifra toka je zapravo razbijena.

Pored LFSR-a, koriste se i registri pomaka sa nelinearnom povratnom spregom, povratnom spregom za prijenos itd.

Brojni generatori su razvijeni na bazi teoretskog pristupa (Blum-Micali generatori, RSA, BBS, kompresijski, aditivni generatori, itd.).

Matematička podrška za sintezu strujnih kriptografskih algoritama razvijena je potpunije i detaljnije u poređenju sa blok kriptografskim algoritmima. Međutim, za kreiranje stream šifri često se koriste algoritmi blok šifriranja u OFB ili CFB načinima.