Uvod u osnove suvremenih šifri sa simetričnim ključem. Pomakni registri s linearnom povratnom spregom kao generatori pseudoslučajnih brojeva. Pomakni registri s linearnom povratnom spregom c

U pomaknom registru s linearnom povratnom spregom razlikuju se dva dijela (modula): sam pomakni registar i sklop (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 duljina registra. Bitovi (ćelije) se obično numeriraju 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 obično se izvodi prije pomaka registra, a tek nakon pomaka se vrijednost izračunatog bita stavlja u ćeliju.

Period registra pomaka je minimalna duljina rezultirajućeg niza prije nego što se počne ponavljati. Budući da registar bitnih ćelija ima samo različita stanja različita od nule, tada, u načelu, razdoblje registra ne može prijeći ovaj broj. Ako je razdoblje registra jednako ovom broju, tada se takav registar naziva registar maksimalnog razdoblja.

Za LFSR, funkcija povratne sprege je linearna Booleova funkcija stanja svih ili nekih bitova registra. Na primjer, zbroj po modulu dva ili njegov logički inverz linearna je Booleova 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 povratne funkcije zavojima.

Kontrola registra u hardverskim implementacijama izvodi se primjenom impulsa pomaka (inače tzv sat ili sinkronizirani puls) na sve ćelije, u softveru - izvođenjem programskog ciklusa, uključujući izračun funkcije povratne sprege i pomaka bita u riječi.

Tijekom 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 nazivaju se zavojima, kao i odgovarajuće ćelije registra, dajući vrijednosti argumenata povratne funkcije.

Linearna složenost

Linearna složenost binarnog niza jedna je od najvažnijih karakteristika LFSR operacije. Uvedemo sljedeću notaciju:

Linearna složenost beskonačnog binarnog niza naziva se broj, koji je definiran na sljedeći način:

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

Svojstva linearne složenosti

Neka i biti binarni nizovi. Zatim:

Korelacijska neovisnost

Kako bi dobili visoku linearnu složenost, kriptografi pokušavaju nelinearno kombinirati rezultate višestrukih izlaznih sekvenci. U ovom slučaju postoji opasnost 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 na temelju takve ranjivosti zove se korelacijske autopsije. Thomas Siegenthaler je pokazao da je moguće točno definirati korelacijske neovisnosti te da postoji kompromis između korelacijske neovisnosti i linearne složenosti.

Glavna ideja iza ovog hacka je pronaći neku korelaciju između izlaza generatora i izlaza jednog od njegovih sastavnih dijelova. Zatim, promatranjem izlaznog slijeda, može se dobiti informacija o ovom međuizlazu. Koristeći ove informacije i druge korelacije, moguće je prikupiti podatke o drugim međuizlazima dok se generator ne hakira.

Korelacijski napadi ili varijacije kao što su napadi brze korelacije uspješno su korišteni protiv mnogih generatora toka ključa koji se temelje na linearnom povratnom registru pomaka, koji uključuju kompromis između računske složenosti i učinkovitosti.

Primjer

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

Budući da se unutarnje stanje na sedmom koraku vratilo u prvobitno stanje, počevši od sljedećeg koraka, doći će do ponavljanja. Drugim riječima, pokazalo se da je period niza jednak 7, što se dogodilo zbog primitivnosti polinoma.

Algoritmi za generiranje primitivnih polinoma

Spremni stolovi

Izračunavanje primitivnosti polinoma prilično je složen matematički problem. Stoga postoje gotove tablice koje navode brojeve sekvenci slavina koje osiguravaju maksimalno razdoblje generatora. Na primjer, za 32-bitni pomakni registar postoji slijed . To znači da je za generiranje novog bita potrebno zbrojiti 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čno neoznačeno dugo 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 prilično su spore i rade brže ako su napisane na asembleru, a ne u C. Jedno rješenje je korištenje 16 RLLS-a paralelno (ili 32, ovisno o duljini riječi u arhitekturi određenog računala). U takvoj shemi koristi se niz riječi čija je veličina jednaka duljini LFSR-a, a svaki bit riječi niza odnosi se na svoj LFSR. Pod uvjetom da se koriste isti redni brojevi slavina, to može dati primjetan porast performansi. [potreban je uzorak koda] (Vidi: bitslice).

Galois konfiguracija

Galoisova konfiguracija linearnog povratnog registra pomaka

Shema povratnih informacija također se 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 s izlazom generatora i zamijenite ga rezultatom ove radnje, 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 Fibonaccijeva konfiguracija navedena prva i Galoisova konfiguracija koja je ovdje dana daju iste sekvence (duljine 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 Fibonaccijevoj 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 usporedbi s Fibonaccijevom konfiguracijom

Primjeri generatora

stop-go generatori

Stop-and-Go naizmjenični generator

Ovaj oscilator koristi izlaz jednog LFSR-a za kontrolu taktne frekvencije drugog LFSR-a. Izlaz sata RSLOS-2 kontrolira se izlazom RSLOS-1, tako da RSLOS-2 može promijeniti svoje stanje u trenutku t samo ako je izlaz RSDOS-1 u trenutku t-1 bio jednak jedan. Ali ova shema 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 duljina. 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 zbroj RSLOS-2 i RSLOS-3. Ovaj generator ima veliki period i veliku linearnu složenost. Njegovi su autori također pokazali metodu za korelacijsko otvaranje RLOS-1, ali to ne oslabi generator u velikoj mjeri.

Gollmannova kaskada

Gollmannova kaskada

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 je izlaz generatora. Ako je duljina svih LFSR-ova jednaka i jednaka n, tada je linearna složenost sustava od k LFSR-a .

Ova ideja je jednostavna i može se koristiti za generiranje sekvenci s velikim periodima, velikom linearnom složenošću i dobrim statističkim svojstvima. Ali, nažalost, podložni su otvaranju, nazvanom "zaključavanje" (lock-in). Za veću stabilnost, preporuča se koristiti k najmanje 15. Štoviš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 registara pomaka. U teoriji, pri korištenju većeg broja pomačnih registara raste složenost šifre, što je i učinjeno 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 polovice, tada generator proizvodi jedinicu. Ako je broj nula na izlazima veći od polovice, tada generator proizvodi nulu. Da bi usporedba broja nula i jedinica bila moguća, broj registara pomaka mora biti neparan. Duljine svih registara moraju biti relativno prosti, a polinomi povratne sprege moraju biti primitivni kako bi period generiranog niza bio maksimalan.

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

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

gdje su , , duljine prvog, drugog i trećeg registra pomaka.

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

Druge vrste

Samorazrjeđivanje

Samoopadajući generatori nazivaju se generatori koji kontroliraju vlastitu frekvenciju. Predložene su dvije vrste takvih generatora. Prvi se sastoji od linearnog povratnog registra pomaka i nekog sklopa koji taktira ovaj registar ovisno o tome koje su izlazne vrijednosti registra pomaka. Ako je LFSR izlaz jednak jedan, tada se registar taktira d puta. Ako je izlaz nula, tada se registar taktira k puta. Drugi ima gotovo isti dizajn, ali donekle 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 s više brzina s unutarnjim umnoškom

Ovaj generator koristi dva registra pomaka s linearnom povratnom spregom s različitim taktnim frekvencijama: LFSR-1 i LFSR-2. Frekvencija sata RLOS-2 d puta je veća od frekvencije RLLS-1. Pojedinačni bitovi ovih registara kombiniraju se s operacijom AND. Izlazi operacije AND su zatim XOR. Izlazni slijed je uzet iz ovog XOR bloka. Opet, ovaj generator nije savršen (Nije preživio otvaranje linearne konzistencije. Ako je - duljina LFSR-1, - duljina LFSR-2, a d je omjer taktnih frekvencija, tada je unutarnje stanje generator se može dobiti iz izlaznog niza duljine ), ali ima visoku linearnu složenost i izvrsne statističke performanse.

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

Povratni pomakni registar sastoji se od dva dijela: registra pomaka i povratne funkcije (slika 1.2.1). Registar pomaka je niz bitova. (Broj bitova je određen duljinom registra pomaka. Ako je duljina n bitova, tada se registar naziva n-bitni pomakni registar.) Kad god treba izdvojiti bit, svi bitovi pomaknog registra su pomaknut udesno za 1 poziciju. Novi krajnji lijevi bit funkcija je svih ostalih bitova u registru. Izlaz registra pomaka je jedan, obično najmanje značajan, bit. Period registra pomaka je duljina rezultirajućeg niza prije nego što se počne ponavljati.

Riža. 1.2.1.

Kriptografi su voljeli stream šifre temeljene na registru pomaka: bilo ih je lako implementirati s digitalnim hardverom. 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 je iznio neke od njegovih i Selmerovih rezultata.

Najjednostavniji tip registra pomaka s povratnom spregom je linearni pomakni registar povratne sprege ili LFSR (slika 1.2.2). Povratna informacija je jednostavno XOR nekih bitova u registru, popis tih bitova naziva se tap sekvenca. Ponekad se takav registar naziva Fibonaccijeva konfiguracija. Zbog jednostavnosti sekvence povratne sprege, prilično napredna matematička teorija može se koristiti za analizu LFSR-a. Kriptografi vole analizirati sekvence, uvjeravajući se da su ti nizovi dovoljno nasumični da bi bili sigurni. LFSR se češće koriste u kriptografiji od ostalih pomaka.

Riža. 1.2.2.

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

Riža. 1.2.3. 4

Izlazni niz bit će 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 unutarnjih 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 s određenim sekvencama tap-a, LFSR će ciklirati kroz sva 2n-1 interna stanja, takvi LFSR-ovi su LFSR-ovi s maksimalnim razdobljem. Rezultirajući rezultat naziva se M-sekvencija.

Da bi određeni LFSR imao maksimalnu period, polinom formiran od tap sekvence i konstante 1 mora biti primitivan po modulu 2. Stupanj polinoma je duljina registra pomaka. Primitivni polinom stupnja n je nesvodljivi polinom koji je djelitelj, ali nije djelitelj xd+1 za sve d koji su djelitelji od 2n-1.

Općenito, ne postoji jednostavan način za generiranje primitivnih polinoma zadanog stupnja po modulu 2. Najlakši način je nasumično odabrati polinom i provjeriti je li primitivan. Nije lako - i pomalo poput provjere je li nasumično odabrani broj prost - ali mnogi matematički softverski paketi to mogu učiniti.

Neki, ali sigurno ne svi, polinomi različitih stupnjeva primitivni su 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

To se lako može generalizirati na LFSR s maksimalnim razdobljem. Prvi broj je duljina LFSR-a. Posljednji broj je uvijek 0 i može se izostaviti. Svi brojevi osim 0 određuju slijed dodira, računajući od lijevog ruba registra pomaka. To jest, članovi polinoma s nižim stupnjem odgovaraju pozicijama bliže desnom rubu 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 , a prvi bitovi rezultirajući LFSR imat će maksimalnu duljinu, proći kroz 232-1 vrijednosti prije iteracije.

Za izgradnju stream šifri vrlo se često koriste sekvence na registrima pomaka. Povratni pomakni registar sastoji se od dva dijela: registra pomaka i povratne funkcije, kao što je prikazano na sl. 87. Sam registar pomaka je niz bitova, čiji broj određuje duljinu 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 u registru pomaka se pomiču udesno za jednu poziciju, obično na niži red. Period registra pomaka je duljina rezultirajućeg niza prije nego što se počne ponavljati.

Riža. 87.

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

Riža. 88.

LFSR su zapisani u obliku polinoma. U ovom slučaju, stupanj prvog elementa polinoma označava broj bitova u registru pomaka, a eksponencijalni eksponenti preostalih članova polinoma pokazuju koje će se točke preuzimanja koristiti. Tako npr. pisanje x 4 + x + 1 znači da će se koristiti registar od četiri elementa za koji će bitovi bi i b 0 sudjelovati u formiranju povratne veze (slika 89).

Riža. 89.4

Razmotrimo rad registra prikazanog na sl. 89. Inicijalizirajte ga, na primjer, vrijednošću 0101 (početnu inicijalizaciju može izvesti bilo koji niz bitova, osim niza od samo nula, budući da će u tom slučaju povratna informacija uvijek formirati vrijednost nula i registar će ne proizvodi očekivani PSP). Dakle, u registru postoji pomak udesno za jednu poziciju. Najmanji bitni bit, jednak 1, izbacuje se iz registra i čini prvi bit PRS-a. Oni bitovi koji su bili na pozicijama b i b 0 prije pomaka dodaju se po modulu 2 i formiraju novi

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

Riža. 90.

Kao što se može vidjeti iz sl. 90, popunjavanje registra proći će 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 ponovno će biti jednako početnoj vrijednosti 0101, a generiranje bitnog niza će se početi ponavljati. Izlazni slijed registra bit će niz najmanjih bitova (do vodoravne crte na slici 90): 101011110001001. Veličina sekvence bita prije nego što se ponovi naziva se periodom. Kako bi se osiguralo maksimalno razdoblje određenog LFSR-a (tj. da bi registar prošao kroz sva moguća unutarnja 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 uzeti samo polinom i provjeriti je li on nesvodiv po modulu 2 ili ne. U općem slučaju, primitivni polinom stupnja n je takav nesvodljivi polinom koji je djelitelj x 2 "+1, ali nije djelitelj xd +1 za sve d koji su djelitelji 2 "-1. B. Schneier daje tablicu nekih polinoma, koji su nesvodljivi po modulu 2.

Rezimirajući saznanja dobivena 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 unutarnjih stanja. Teoretski, takav registar može generirati pseudo-slučajni niz s periodom od 2 n -1 bita. Takvi se registri nazivaju LFSR registri s maksimalnim razdobljem. Rezultirajući izlaz naziva se t-slijed.

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

Na primjer, razmotrite LFSR s povratnom funkcijom (vidi sliku).

Ako je početno stanje registra 1111, tada će u sljedećim ciklusima poprimiti sljedeći niz stanja: …

Izlazni niz se formira od najmanje značajne (krajnje desne) znamenke 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 slijed bitova u potpunosti određen početnim stanjem registra i povratnom funkcijom. Budući da je broj mogućih stanja registra konačan (jednak je 2 L), tada će se prije ili kasnije ključna sekvenca početi ponavljati. Maksimalna duljina dijela ključnog niza koji se ne ponavlja naziva se periodom. T. Razdoblje ovisi o povratnoj funkciji. Maksimalno moguće razdoblje je T max=2 L-1 (registar preuzima sva moguća stanja osim 0000...0). Poziva se izlazna sekvenca LFSR-a s maksimalnom periodom M-sekvencija.

Kako bi saznali uvjete pod kojima će LFSR imati maksimalan period, funkcije povratne sprege odgovaraju karakterističnom polinomu. Dakle, gore navedeni registar kao primjer odgovara polinomu . Teorijska analiza pokazuje da će LFSR imati maksimalan period ako i samo ako je polinom P(x) je primitivni. U nastavku su neki primitivni polinomi koji se preporučuju za praktičnu upotrebu. Tablica prikazuje stupnjeve varijable x u polinomu. Na primjer, unos (31, 3) odgovara polinomu .

LFSR su izvorno dizajnirani za implementaciju u hardver kao skup digitalnih sklopova. Softverske implementacije LFSR-a obično su 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 za pristup pojedinačnim bitovima koriste operacije po bitovima (pomak, maskiranje, itd.).

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

Slika 19. Registar pomaka povratne sprege.

Općenito, pomakni registar je slijed nekih elemenata prstena ili polja. Najčešće korišteni malo registri pomaka. Duljina takvog registra izražava se 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 duljina izlaznog niza 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. Popis ovih bitova je definiran karakteristični polinom i nazvao slijed dodira. Ponekad se ova shema naziva Fibonaccijeva konfiguracija.

sl.20. LFOS Fibonaccijeve 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 bitova s ​​izlazom generatora, zamjenjujući stari dio slijeda slavina. Ova se modifikacija ponekad naziva Galois konfiguracija.

sl.21. RLOS Galoisove konfiguracije.

n-bit LFSR može biti u jednom od 2 n– 1 unutarnja stanja. 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 interna stanja moguća samo uz određene sekvence slavina. Takvi se registri nazivaju LFSR s maksimalnim razdobljem. Da bi se osigurao maksimalni period LFSR-a, potrebno je da njegov karakteristični polinom bude primitivni modulo 2. Stupanj polinoma je duljina registra pomaka. Polinom primitivnog stupnja n- takav je nesvodiv polinom koji je djelitelj, ali nije djelitelj x d+1 za sve d, koji su djelitelji od 2 n– 1. (Kad se govori o polinomima, termin glavni broj zamijenjen terminom nesvodljivi polinom). Karakteristični polinom LFSR-a prikazan na slikama:

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

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

Važan parametar generatora na temelju LFSR je linearna složenost. Definira se kao duljina n najkraći LFSR koji može simulirati izlaz generatora. Linearna složenost je važna jer s jednostavnim Berlenkamp-Massey algoritam moguće je ponovno stvoriti takav LFSR provjerom samo 2 n gama bitovi. S definicijom željenog LFSR-a, stream šifra je zapravo razbijena.

Osim LFSR-a koriste se i pomačni registri s nelinearnom povratnom spregom, prijenosnom povratnom spregom itd.

Na temelju teorijsko-teorijskog pristupa razvijen je niz generatora (Blum-Micali generatori, RSA, BBS, kompresijski, aditivni generatori itd.).

Matematička podrška za sintezu stream kriptografskih algoritama razvijena je potpunije i detaljnije u usporedbi s blokovskim kriptografskim algoritmima. Međutim, za stvaranje stream šifri često se koriste algoritmi blok šifriranja u OFB ili CFB načinima.