Registar pomaka za povratne informacije ( FSR ) sastoji se iz dva dela: pomični registar I povratne funkcije .
Pomakni registar (Greška: referentni izvor nije pronađen) je niz bitova. Kada treba dohvatiti bit, svi bitovi registra pomaka se pomiču udesno za 1 poziciju. Novi krajnji lijevi bit je vrijednost povratne funkcije od preostalih bitova registra. Period Registar pomaka je dužina rezultujuće sekvence prije nego što se počne ponavljati.
Najjednostavniji tip registra pomaka je linearni pomakni registar sa povratnom spregom (LFSR
–
lijevo
Povratne informacije
Shift
Registrirajte se)
(Greška: referentni izvor nije pronađen). Povratna informacija je jednostavno XOR od nekih p bitova 
registar, lista ovih bitova se zove tapnite sekvencu.
n-bit LFSR može biti u jednom od 2 n -1 unutrašnja stanja. To znači da, teoretski, takav registar može generirati pseudo-slučajni niz s tačkom 2 n -1 bits Broj internih stanja i period su jednaki jer će popunjavanje registra nulama dovesti do toga da proizvede beskonačan niz nula, što je apsolutno beskorisno. Samo sa određenim sekvencama tapkanja, LFSR će ciklirati kroz sve 2 n -1 unutrašnja stanja. Ovi LFSR se nazivaju LFSRsa maksimalnim periodom.
Da bi određeni LFSR imao maksimalan period, polinom formiran od tap sekvence i konstante 1 mora biti primitivan po modulu 2 .
Izračunavanje primitivnosti polinoma je prilično složen matematički problem. Zbog toga postoje gotove tabele koje prikazuju brojeve sekvenci slavina koje obezbeđuju maksimalni period generatora. Na primjer, za 32-bitni pomakni registar možete pronaći sljedeći unos: (32,7,5,3,2,1,0) . To znači da da biste generirali novi bit, trebate zbrojiti trideset drugi, sedmi, peti, treći, drugi i prvi bit koristeći XOR funkciju.
Kod za takav LFSR u C++ bi bio ovakav:
// Bilo koja vrijednost osim nule
ShiftRegister = ((((ShiftRegister >> 31)
^ (ShiftRegister >> 6)
^ (ShiftRegistar >> 4)
^ (ShiftRegister >> 2)
^ (ShiftRegister >> 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (ShiftRegister >> 1);
return ShiftRegister & 0x00000001;
Softverske implementacije LFSR-a su prilično spore i rade brže ako su napisane u asemblerskom jeziku umjesto C. Jedno rješenje je korištenje 16 LFSR-ova paralelno (ili 32 u zavisnosti od dužine riječi u specifičnoj arhitekturi računala). Ova šema koristi niz riječi čija je veličina jednaka dužini LFSR-a, a svaka jedinica riječi u nizu se odnosi na vlastiti LFSR. Pod uslovom da se koriste isti redni brojevi slavina, ovo može obezbediti primetno povećanje performansi.
WITH 
Krug povratne sprege se također može modificirati. U tom slučaju generator neće imati veću kriptografsku snagu, ali će ga biti lakše implementirati u softver. Umjesto korištenja krajnjeg lijevog bita tap sekvence za generiranje novog krajnjeg lijevog bita, on vrši XOR svaki bit tap sekvence sa izlazom generatora i zamjenjuje ga rezultatom ove akcije, tada rezultat generatora postaje novi krajnji lijevi bit (Greška: referentni izvor nije pronađen).
Ova modifikacija se zove Galois konfiguracija. U C-u to izgleda ovako:
statički nepotpisani dugi ShiftRegister = 1;
void seed_LFSR (nepotpisano dugo seme)
ShiftRegister = sjeme;
int Galua_LFSR (void)
if (ShiftRegister & 0x00000001) (
ShiftRegister = (ShiftRegister ^ maska >> 1) | 0x8000000;
ShiftRegister >>= 1;
Prednost je što se svi XOR-ovi izvode u jednoj operaciji. Ovo kolo također može biti paralelno.
Sami LFSR-ovi su dobri generatori pseudo-slučajnih sekvenci, ali imaju neka nepoželjna svojstva koja nisu slučajna. Uzastopni bitovi su linearni, što ih čini beskorisnim za šifriranje. Za LFSR dužine n unutrašnje stanje predstavlja prethodno n izlazni bitovi generatora. Čak i ako se obrazac povratne informacije čuva u tajnosti, može se odrediti pomoću 2 n izlazne bitove generatora pomoću posebnih algoritama. Osim toga, veliki slučajni brojevi generirani korištenjem uzastopnih bitova ovog niza su visoko korelirani i za neke vrste aplikacija nisu slučajni. Uprkos tome, LFSR-ovi se često koriste za kreiranje algoritama za šifrovanje. U tu svrhu se koristi više LFSR-ova, obično s različitim dužinama i rednim brojevima slavina. Ključ je početno stanje registara. Svaki put kada je potreban novi bit, svi registri se pomjeraju. Ova operacija se zove clocking. Izlazni bit je funkcija, po mogućnosti nelinearna, nekih LFSR bitova. Ova funkcija se zove kombinovanje, i generator u cjelini – kombinovani generator. Mnogi od ovih generatora su još uvijek sigurni.
dešifrovanje - p i = D (k i, c i), kao što je prikazano na sl. 7.21.
Rice. 7.21.
Stream šifre su brže od blok šifri. Hardverska implementacija stream šifre je također jednostavnija. Kada moramo šifrirati binarne tokove i prenositi ih konstantnom brzinom, najbolji izbor je korištenje stream šifre. Stream šifre imaju veću zaštitu od oštećenja bitova tokom prenosa.
U modernoj stream šifri, svaki r -bitna riječ u toku običnog teksta je šifrirana pomoću r -bitna riječ u ključnom toku za kreiranje odgovarajuće r -bitna riječ u toku šifriranog teksta.
Rice. 7.22.
Jednokratni blok je savršena šifra. On je savršen. Ne postoji metoda koja bi omogućila protivniku da prepozna ključ ili statistiku šifriranog i otvorenog teksta. Ne postoji odnos između originala i šifrovanog teksta. Drugim riječima, šifrirani tekst je pravi slučajni tok bitova, čak i ako se dobiju neki uzorci originalnog teksta. Eva ne može razbiti šifru osim ako ne isproba sve moguće nasumične tokove ključeva, što bi bilo 2n da je veličina otvorenog teksta n-bita. Međutim, s tim postoji problem. Da bi predajnik i prijemnik dijelili jednokratni blok ključeva, moraju uspostaviti vezu svaki put kada žele razmijeniti informacije. Moraju se nekako dogovoriti oko slučajnog ključa. Tako da je ovu savršenu i idealnu šifru vrlo teško implementirati.
Primjer 7.17
Kakav je oblik šifriranog teksta kada se koristi jednokratna šifra u svakom od sljedećih slučajeva?
A. Izvorni tekst se sastoji od n nula.
b. Izvorni tekst se sastoji od n jedinica.
V. Izvorni tekst se sastoji od naizmjeničnih nula i jedinica.
d. Izvorni tekst je nasumični niz bitova.
Rješenje
a. Zbog 
, tada će tok šifriranog teksta odgovarati toku ključa. Ako je ključ nasumičan, šifrirani tekst je također slučajan. Dijelovi originalnog teksta nisu pohranjeni u šifriranom tekstu.
b. Zbog 
, gdje je dopuna toka šifriranog teksta je dopuna toka ključa. Ako je tok ključeva nasumičan, onda je i šifrirani tekst također nasumičan; dijelovi originalnog teksta nisu pohranjeni u šifriranom tekstu.
c. U ovom slučaju, svaki bit u toku šifriranog teksta je ili isti kao u toku ključa ili njegov komplementar. Stoga je rezultat također slučajan ako je tok ključeva nasumičan.
d. U ovom slučaju, šifrirani tekst je očigledno nasumičan jer izvođenje XOR operacije na dva nasumična bita rezultira slučajnim nizom bitova.
Registar pomaka povratne sprege
Jedno poboljšanje u odnosu na jednokratni pad je (FSR - Feedback Shift Register). FSR se može implementirati u softver ili hardver, ali radi jednostavnosti razmotrićemo hardversku implementaciju. Registar pomaka povratne sprege obuhvata registra pomaka i funkcija povratne sprege, kao što je prikazano na sl. 7.23.
Rice. 7.23.
Pomakni registar je niz od m ćelija od b 0 do b m-1, gdje je svaka ćelija dizajnirana da pohrani jedan bit. Ćelije se tretiraju kao n-bitna riječ, koja se na početku naziva "seed value" ili izvor. Kad god treba biti izlaz (na primjer, iz signala u određeno vrijeme), svaki bit se pomiče za jednu ćeliju udesno. To znači da je vrijednost svake ćelije dodijeljena desnoj susjednoj ćeliji i uzima vrijednost lijeve ćelije. Krajnja desna ćelija b 0 smatra se izlaznom i daje izlaznu vrijednost (k i ). Krajnja lijeva ćelija, b m-1, dobiva svoju vrijednost prema vrijednosti informacija o funkciji povratne sprege. Izlaz funkcije označavamo povratnom informacijom b m . Funkcija povratnih informacija određuje koje vrijednosti ćelije imaju za izračunavanje b m . Pomični registar povratne informacije može biti linearan ili nelinearan.
Registar pomaka s linearnom povratnom spregom (LFSR). Pretpostavimo da je b m linearna funkcija b 0, b 1,…..., b m-1, za koju
Registar linearne povratne sprege radi na binarnim znamenkama, tako da su množenje i sabiranje u GF(2) polju, tako da je vrijednost C i ili 1 ili 0, ali C 0 mora biti 1 da bi se dobila povratna informacija na izlazu. Operacija sabiranja je operacija ISKLJUČIVO ILI. Drugim riječima,
Primjer 7.18
Izgradimo linearni pomakni registar povratne sprege sa 5 ćelija, u kojem .
Rješenje
Ako je C i = 0, b i ne igra ulogu u izračunavanju b m, onda to znači da b i nije pridružen funkciji povratne informacije. Ako je c i = 1, b i je uključen u izračunavanje b m. U ovom primjeru, c 1 i c 3 su nule, što znači da imamo samo tri veze. Na slici 7.24 prikazano je kolo linearnog registra pomaka povratne sprege.
Rice. 7.24.
Primjer 7.19
Izgradimo linearni pomakni registar povratne sprege sa 4 ćelije, u kojima 
. Prikaži vrijednost registra nakon 20 operacije (smjene), ako je originalna vrijednost (0001) 2 .
Rješenje
Slika 7.25 prikazuje dizajn i upotrebu linearnog registra pomaka zatvorene petlje za šifriranje.
Rice. 7.25.
Tabela 7.6. prikazuje vrijednost ključnog toka. Za svaki prijelaz izračunava se prva vrijednost b 4, a zatim se svaki bit pomjera za jednu ćeliju udesno.
| sadašnja vrijednost | b 4 | b 3 | b 2 | b 1 | b 0 | k i |
|---|---|---|---|---|---|---|
| Početna vrijednost | 1 | 0 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 1 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 0 | 1 | 1 | 0 |
| 8 | 1 | 0 | 1 | 0 | 1 | 1 |
| 9 | 1 | 1 | 0 | 1 | 0 | 1 |
| 10 | 1 | 1 | 1 | 0 | 1 | 0 |
| 11 | 1 | 1 | 1 | 1 | 0 | 1 |
| 12 | 0 | 1 | 1 | 1 | 1 | 0 |
| 13 | 0 | 0 | 1 | 1 | 1 | 1 |
| 14 | 0 | 0 | 0 | 1 | 1 | 1 |
| 15 | 1 | 0 | 0 | 0 | 1 | 1 |
| 16 | 0 | 1 | 0 | 0 | 0 | 1 |
| 17 | 0 | 0 | 1 | 0 | 0 | 0 |
| 18 | 1 | 0 | 0 | 1 | 0 | 0 |
| 19 | 1 | 1 | 0 | 0 | 1 | 0 |
| 20 | 1 | 1 | 1 | 0 | 0 | 1 |
Imajte na umu da je tok ključeva 1000100110101111 1001……. Na prvi pogled izgleda kao slučajni niz, ali ako pogledamo veliki broj transakcija (smjena), možemo vidjeti da su nizovi periodični. Ovo ponavljanje od 15 bitova je prikazano ispod.
Ključ toka se generira korištenjem registra pomaka s linearnom povratnom spregom pseudoslučajni niz, u kojem se ponavljaju nizovi dužine N. Protok je periodičan. Zavisi od kruga generatora i početnih informacija i ne može biti više od 2 m – 1. Svaki sklop generiše m-bitne sekvence u rasponu od onih koje sadrže sve nule do onih koje sadrže sve jedinice. Međutim, ako je početni niz sve nule, rezultat je beskorisan - originalni tekst bi bio tok svih nula. Stoga je takav početni niz isključen.
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.
Pomakni registar zatvorene petlje (u daljem tekstu RGSSOC) sastoji se od dva dijela: registra pomaka i funkcije povratne sprege. Pomakni registar je niz bitova. Određuje se broj bitova dužina registra pomaka, ako je dužina n bitova, tada se poziva registar n-bitni pomakni registar. Kad god treba dohvatiti bit, svi bitovi registra pomaka se pomiču 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 rezultirajućeg niza prije nego što započne njegovo ponavljanje.
Slika 1. Registar pomaka povratne sprege
Shift registri su brzo našli upotrebu u stream šiframa jer su se lako implementirali pomoću digitalnog hardvera. Godine 1965, Ernst Selmer, glavni kriptograf norveške vlade, razvio je teoriju sekvence registra pomaka. Solomon Golomb, NSA matematičar, napisao je knjigu u kojoj je predstavio neke od njegovih i Selmerovih rezultata. Najjednostavniji tip registra pomaka povratne sprege je linearni pomakni registar povratne sprege (LFSR). Povratna informacija takvih registara je jednostavno XOR (modulo dva zbrajanja) nekih bitova registra, lista ovih bitova koja 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 PrCsVOC. Analizom rezultirajućih izlaznih sekvenci, možete provjeriti da li su sekvence dovoljno nasumične da budu sigurne. RGCCLOS se koristi češće od ostalih pomaka u kriptografiji.
Slika 2. PrCsLOS Fibonači
Općenito, n-bit PrCsLOS može biti u jednom od N=2 n -1 internih stanja. To znači da teoretski takav registar može generirati pseudo-slučajnu sekvencu s periodom od T=2 n -1 bita. (Broj unutrašnjih stanja i period su jednaki N=T max =2 n -1, jer će popunjavanje PrCsLOS nulama uzrokovati da registar pomaka proizvede beskonačan niz nula, što je apsolutno beskorisno). Samo za određene sekvence grana PrCsLOS će ciklički proći kroz sva 2 n -1 unutrašnja stanja, takvi PrCsLOS su RgSsLOS sa maksimalnim periodom. Rezultirajući rezultat se zove M-sekvenca.
Primjer . Na slici ispod prikazan je 4-bitni PrCCLOS sa prvim i četvrtim bitom. Ako je inicijaliziran vrijednošću 1111, tada će prije ponavljanja registar poprimiti sljedeća interna stanja:
 Broj smjene sata (interno stanje) |
Status registracije |
Izlazni bit |
|||
|
Početna vrijednost |
|||||
|
15 (povratak u početno stanje) |
|||||
|
16 (ponavljajuća stanja) |
Izlazni niz će biti niz najmanjih bitova: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 sa periodom T=15, ukupan broj mogućih unutrašnjih stanja (osim nule), N=2 4 -1=16-1= 15=T max , dakle, izlazna sekvenca je M-sekvenca.
Da bi određeni PrCsLOS imao maksimalan period, polinom formiran od tap sekvence i konstante 1 mora biti primitivan po modulu 2. Polinom je predstavljen kao zbir stepena, na primjer, polinom stepena n je predstavljen na sljedeći način :
a n x n +a n-1 x n-1 + … +a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 + … +a 1 x+a 0 , gdje a i =(0,1) za i=1…n, a x i - označava cifru.
Stepen polinoma je dužina registra pomaka. Primitivni polinom stepena n je nesvodljivi polinom koji je delilac x 2n?1 +1, ali nije delilac x d +1 za sve d koji su delilac od 2 n -1. Odgovarajuća matematička teorija se može naći u.
Uopšteno govoreći, ne postoji jednostavan način da se generišu primitivni polinomi datog stepena po modulu 2. Najlakši način je da nasumično odaberete polinom i proverite da li je primitivan. Ovo nije lako i pomalo liči na provjeru da li je slučajno odabrani broj prost - ali mnogi matematički softverski paketi mogu riješiti ovaj problem.
Neki, ali sigurno ne svi, polinomi različitih stupnjeva koji su primitivni po modulu 2 su dati u nastavku. Na primjer, snimite
(32, 7, 5, 3, 2, 1, 0) znači da je sljedeći polinom primitivan po modulu 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.
Ovo se lako može generalizirati na PrCsVOC sa maksimalnim periodom. Prvi broj je dužina PrCsLOS. Posljednji broj je uvijek 0 i može se izostaviti. Svi brojevi osim 0 određuju sekvencu tapkanja, koja se računa od lijeve ivice registra pomaka. To jest, članovi polinoma sa nižim stepenima odgovaraju pozicijama bliže desnoj ivici registra.
Nastavljajući s primjerom, 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, drugi i prvi bitovi, rezultirajući PrCsLOS će imati maksimalnu dužinu, kruži kroz 2 32 -1 vrijednosti prije ponavljanja.
Slika 4. 32-bitni PrCCLOS sa maksimalnom dužinom
Razmotrimo programski kod PrCsLOS, u kojem se tap sekvenca karakteriše polinomom (32, 7, 5, 3, 2, 1, 0). U C-u to izgleda ovako:
statički nepotpisani dugi ShiftRegister = 1;
/* Sve osim 0. */
ShiftRegister = ((((ShiftRegister >> 31)
^(ShiftRegister >> 6)
^(ShiftRegister >> 4)
^(ShiftRegister >> 2)
^(ShiftRegister >> 1)
^ShiftRegister))
| (ShiftRegister >> 1);
vrati ShiftRegister & 0x00000001;)
Ako je pomični registar duži od kompjuterske riječi, kod postaje složeniji, ali ne mnogo. Dodatak B sadrži tabelu nekih primitivnih polinoma po modulu 2; koristićemo je u budućnosti za identifikaciju nekih svojstava ovih polinoma, kao i u softverskoj implementaciji za specifikaciju tap sekvence.
Imajte na umu da svi elementi tabele imaju neparan broj koeficijenata. Ova dugačka tabela je obezbeđena za dalji rad sa RgCsLOC, pošto se RgCsLOC često koristi za kriptografiju sa stream šiframa i u generatorima pseudoslučajnih brojeva. U našem slučaju možemo koristiti polinome sa najvišim stepenom ne većim od sedam.
Ako je p(x) primitivan, onda je x n p(1/x) primitivan, tako da svaki element tabele zapravo definira dva primitivna polinoma. Na primjer, ako je (a, b, 0) primitivan, onda je (a, a-b, 0) također primitivan. Ako je (a, b, c, d, 0) primitivan, onda je (a, a-d, a-c, a-b, 0) također primitivan. matematički:
ako je x a +x b +1 primitivno, onda je x a +x a-b +1 primitivno,
ako je x a +x b +x c +x d +1 primitivno, tada je x a +x a-d +x a-c +x a-b +1 primitivno. Primitivni trinomi najbrže se implementiraju u softveru, jer da biste generirali novi bit trebate XOR samo dva bita registra pomaka (nulti član se ne uzima u obzir, tj. x 0 = 1, pogledajte primjer iznad). Zaista, svi polinomi povratne sprege dati u tabeli su rijetki, odnosno imaju malo koeficijenata. Oskudnost je uvijek izvor slabosti, što je ponekad dovoljno da razbije algoritam. Za kriptografske algoritme mnogo je bolje koristiti guste primitivne polinome, one sa mnogo koeficijenata. Korištenjem gustih polinoma, posebno kao dijela ključa, može se koristiti mnogo kraći PrCsLOS.
Generiranje gustih primitivnih polinoma po modulu 2 nije lako. Generalno, da biste generisali primitivne polinome stepena k, morate znati faktorizaciju broja 2 k -1.
Sami po sebi, PrCsLOS su dobri generatori pseudo-slučajnih sekvenci, ali imaju neka nepoželjna neslučajna (deterministička) svojstva. Uzastopni bitovi su linearni, što ih čini beskorisnim za šifriranje. Za PrCcLOS dužine n, interno stanje je prethodnih n izlaznih bitova generatora. Čak i ako se povratno kolo drži u tajnosti, može se odrediti iz 2n izlaznih bita oscilatora koristeći visoko efikasan Berlekamp-Massey algoritam.
Osim toga, veliki slučajni brojevi generirani korištenjem uzastopnih bitova ovog niza su u velikoj korelaciji i, za neke vrste aplikacija, uopće nisu slučajni. Uprkos tome, RgCCLOS se često koristi za kreiranje algoritama za šifrovanje kao komponente sistema i algoritama za šifrovanje.
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). Pomakni registar 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 treba dohvatiti bit, svi bitovi pomaknog registra su pomaknuti 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 registrima 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 sekvence registra pomaka. Solomon Golomb, NSA matematičar, napisao je knjigu u kojoj je predstavio neke 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 registra, lista ovih bitova koja se zove 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 sekvence dovoljno nasumične da bi bile sigurne. LFSR-ovi su najčešće korišteni registri pomaka u kriptografiji.
Rice. 1.2.2.
Na sl. Slika 1.2.3 prikazuje 4-bitni LFSR sa odvodima od prvog i četvrtog bita. 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 unutrašnjih stanja i period su 2n-1 jer će popunjavanje LFSR-a nulama uzrokovati da registar pomaka proizvede beskonačan niz nula, što je apsolutno beskorisno.) Samo za određene tap sekvence će LFSR ciklirati kroz sve 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.
Uopšteno govoreći, ne postoji jednostavan način da se generišu primitivni polinomi datog stepena po modulu 2. Najlakši način je da nasumično odaberete polinom i proverite da li je primitivan. Ovo nije lako – i pomalo liči na provjeru da li je slučajni broj prost – ali mnogi matematički softverski paketi mogu riješiti ovaj problem.
Neki, ali sigurno ne svi, polinomi različitih stupnjeva su primitivni po modulu 2. Na primjer, pisanje (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 maksimalnog perioda. 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 lijeve ivice registra pomaka. To jest, članovi polinoma sa nižim stepenima odgovaraju pozicijama bliže desnoj ivici registra.
Nastavljajući s primjerom, 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, drugi i prvi bitovi rezultirajući LFSR će imati maksimalnu dužinu, kruži kroz 232-1 vrijednosti prije ponavljanja.
Linear Feedback Shift Register (LFSR) je mehanizam za kreiranje pseudo-slučajnog niza binarnih bitova. Registar (slika 1) se sastoji od određenog broja ćelija koje su uspostavljene inicijalizacijskim vektorom (najčešće tajnim ključem). Rad registra je određen prisustvom ili odsustvom komunikacije od svakog bita do povratne sprege. Slavine registra povratnih informacija nisu fiksne, ali su dio ključa. U sljedećem koraku, sadržaj ćelija registra se pomiče za jednu poziciju udesno, a jedan bit koji je ostao slobodan kao rezultat XOR operacije stavlja se u krajnju lijevu ćeliju.
Rice. 1. Registar pomaka s linearnom povratnom spregom
Za postizanje maksimalnog gama perioda šifre, broj bitova m bira se pomakni registar da bude jednak jednom od Mersenneovih prostih brojeva (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203...), a unutrašnje veze registra moraju biti odabrane prema nesvodljivim primitivnim polinomima najvišeg stepena m. U ovom slučaju, gama period šifre može dostići (2 m-1).
LFSR je brz i lak za implementaciju u softveru i hardveru. Uz pravilan izbor bitova povratne sprege, generirane sekvence imaju dobra statistička svojstva. LFSR se koristi kao osnovni element za izgradnju visoko sigurnih sistema.
Registarska kaskada je skup LFSR-ova povezanih na takav način da ponašanje jednog LFSR-a zavisi od ponašanja prethodnog LFSR-a u kaskadi. Ovo "ovisno" ponašanje je tipično dizajnirano za kontrolu brojača pomaka sljedećeg LFSR-a od strane prvog LFSR-a.
Na primer, registar se pomera za jedan korak ako je vrednost prethodnog registra 1, a ako je vrednost 0, onda se registar pomera za dva koraka ili na neki drugi način. Veliki broj ovakvih kombinacija omogućava vrlo visoku sigurnost.
Najsigurnije sekvence proizvodi generator skupljanja zasnovan na jednostavnoj interakciji između rezultata dva LFSR registra. Bitovi jednog rezultata određuju da li će se odgovarajući bitovi drugog rezultata koristiti kao dio kompletnog "ključa toka". Generator kompresije je jednostavan, skalabilan i ima dobra zaštitna svojstva. Njegov nedostatak je što brzina generiranja "ključa toka" neće biti konstantna osim ako se ne preduzmu neke mjere opreza.
Fibonačijev metod sa kašnjenjima Jedan od široko korištenih Fibonačijevih generatora baziran je na sljedećoj iterativnoj formuli:
Gdje Yk- realni brojevi iz raspona
Rice. 2. Round-robin enkripcija
DES izlazni način povratne sprege može se koristiti za generiranje pseudoslučajnih brojeva, slično onome kako se koristi za šifriranje toka. Izlaz svake faze šifriranja je 64-bitna vrijednost, od kojih se samo najvažniji j bitovi vraćaju za šifriranje. 64-bitni izlazi su niz pseudoslučajnih brojeva sa dobrim statističkim svojstvima.
Generator pseudoslučajnih brojeva, opisan u ANSI X9.17 standardu, jedan je od najsigurnijih generatora pseudoslučajnih brojeva. Aplikacije koje koriste ovu tehnologiju uključuju finansijsku sigurnost i PGP aplikacije.
ANSI X9.17 generator se sastoji od sledećih delova (slika 3):
1. Ulaz: Generatorom upravljaju dva pseudo-slučajna ulaza. Prvi ulaz je 64-bitni prikaz trenutnog datuma i vremena ( DT i), koji se mijenjaju svaki put kada se broj kreira. Drugi ulaz je 64-bitno sjeme, koje je inicijalizirano na neku proizvoljnu vrijednost i modificirano tokom generiranja niza pseudoslučajnih brojeva ( V i).
2. Tasteri: Generator koristi tri trostruka DES modula sa dva ključa K1, K2. Sva tri koriste isti 56-bitni par ključeva, koji se mora čuvati u tajnosti i koristiti samo za generiranje pseudo-slučajnog broja.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K1, K2 |
| DT i |
| V i |
| R i |
| V i+1 |
3. Izlaz: Izlaz se sastoji od 64-bitnog pseudo-slučajnog broja R i i 64-bitne vrijednosti koja će se koristiti kao seme prilikom kreiranja sljedećeg broja ( V i +1) .
Rice. 3. ANSI X9.17 generator pseudoslučajnih brojeva
