Registar pomaka povratne veze ( FSR ) sastoji se od dva dijela: pomačni registar I povratne funkcije .
Registar posmaka (pogreška: referentni izvor nije pronađen) je niz bitova. Kada treba dohvatiti bit, svi bitovi registra posmaka pomiču se udesno za 1 poziciju. Novi krajnji lijevi bit je vrijednost funkcije povratne sprege iz preostalih bitova registra. Razdoblje Registar pomaka je duljina rezultirajuće sekvence prije nego što se počne ponavljati.
Najjednostavniji tip registra posmaka s povratnom spregom je linearni pomakni registar s povratnom spregom (LFSR
–
Lijevo
Povratne informacije
Shift
Registar)
(Pogreška: izvor reference nije pronađen). Povratna informacija je jednostavno XOR nekih p bitova 
registar, poziva se popis tih bitova slijed dodira.
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 točkom 2 n -1 komadići Broj internih stanja i period su jednaki jer će punjenje registra nulama proizvesti beskonačan niz nula, što je apsolutno beskorisno. Samo uz određene sekvence tapkanja, LFSR će kružiti kroz sve 2 n -1 unutarnja stanja. Ovi LFSR-ovi se nazivaju LFSRs maksimalnim razdobljem.
Kako bi određeni LFSR imao maksimalni period, polinom formiran od sekvence odvoda i konstante 1 mora biti primitivan modulo 2 .
Izračunavanje primitivnosti polinoma prilično je složen matematički problem. Stoga postoje gotove tablice koje prikazuju brojeve sekvenci slavina koje osiguravaju maksimalno razdoblje generatora. Na primjer, za 32-bitni registar posmaka možete pronaći sljedeći unos: (32,7,5,3,2,1,0) . To znači da za generiranje novog bita morate zbrojiti trideset drugi, sedmi, peti, treći, drugi i prvi bit pomoću funkcije XOR.
Kod za takav LFSR u C++ bi bio ovakav:
// Bilo koja vrijednost osim nule
ShiftRegister = ((((ShiftRegister >> 31)
^ (Registar pomaka >> 6)
^ (ShiftRegister >> 4)
^ (ShiftRegister >> 2)
^ (Registar pomaka >> 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (Registar pomaka >> 1);
vrati ShiftRegister & 0x00000001;
Softverske implementacije LFSR-a prilično su spore i rade brže ako su napisane u asemblerskom jeziku, a ne u C-u. Jedno je rješenje koristiti 16 LFSR-ova paralelno (ili 32 ovisno o duljini riječi u specifičnoj arhitekturi računala). Ova shema koristi niz riječi čija je veličina jednaka duljini LFSR-a, a svaka jedinica riječi u nizu odnosi se na vlastiti LFSR. Pod uvjetom da se koriste isti sekvencijski brojevi dodira, to može pružiti primjetan dobitak performansi.
S 
Povratni krug se također može modificirati. U tom slučaju generator neće imati veću kriptografsku snagu, ali će ga biti lakše programski implementirati. Umjesto da koristi krajnji lijevi bit niza dodira za generiranje novog krajnjeg lijevog bita, on izvodi XOR svaki bit niza dodira s izlazom generatora i zamjenjuje ga rezultatom ove radnje, tada rezultat generatora postaje novi krajnji lijevi bit (Pogreška: Izvor reference nije pronađen).
Ova izmjena se zove Galois konfiguracija. U C-u to izgleda ovako:
static unsigned long ShiftRegister = 1;
void seed_LFSR (nepotpisano dugo sjeme)
ShiftRegister = sjeme;
int Galua_LFSR (prazno)
if (ShiftRegister & 0x00000001) (
ShiftRegister = (ShiftRegister ^ maska >> 1) | 0x8000000;
ShiftRegister >>= 1;
Prednost je u tome što se svi XOR-ovi izvode u jednoj operaciji. Ovaj sklop se također može paralelizirati.
Sami LFSR-ovi su dobri generatori pseudoslučajnih sekvenci, ali imaju neka nepoželjna neslučajna svojstva. Uzastopni bitovi su linearni, što ih čini beskorisnim za enkripciju. Za duljine LFSR n unutarnje stanje predstavlja prethodno n izlazni bitovi generatora. Čak i ako se uzorak povratne informacije drži u tajnosti, može se odrediti pomoću 2 n izlazni bitovi generatora pomoću posebnih algoritama. Osim toga, veliki nasumični brojevi generirani korištenjem uzastopnih bitova ovog niza visoko su povezani i za neke vrste aplikacija nisu slučajni. Unatoč tome, LFSR-ovi se često koriste za stvaranje algoritama šifriranja. U tu se svrhu koristi višestruki LFSR, obično s različitim duljinama i sekvencijskim brojevima odvajanja. Ključ je početno stanje registara. Svaki put kada je potreban novi bit, svi registri se pomiču. Ova operacija se zove taktiranje. Izlazni bit je funkcija, po mogućnosti nelinearna, nekih LFSR bitova. Ova funkcija se zove kombinirajući, i generator u cjelini – kombinirajući generator. Mnogi od ovih generatora još uvijek su sigurni.
dešifriranje - p i = D (k i, c i), kao što je prikazano na sl. 7.21.
Riža. 7.21.
Stream šifre su brže od blok šifri. Hardverska implementacija tokovne šifre također je jednostavnija. Kada moramo šifrirati binarne tokove i prenositi ih konstantnom brzinom, najbolji izbor je koristiti šifru toka. Stream šifre imaju veću zaštitu od oštećenja bitova tijekom prijenosa.
U modernoj potočnoj šifri, svaki r -bitna riječ u toku običnog teksta šifrirana je pomoću r -bitna riječ u toku ključa za stvaranje odgovarajućeg r -bitna riječ u toku šifriranog teksta.
Riža. 7.22.
Jednokratni blok je savršena šifra. On je savrsen. Ne postoji metoda koja bi protivniku omogućila prepoznavanje ključa ili statistike šifriranog i otvorenog teksta. Ne postoji odnos između izvornika i šifriranog teksta. Drugim riječima, šifrirani tekst je pravi nasumični tok bitova, čak i ako se dobiju neki uzorci izvornog teksta. Eva ne može razbiti šifru osim ako ne isproba sve moguće nasumične nizove ključeva, što bi bilo 2n da je veličina otvorenog teksta n-bitova. Međutim, postoji problem s ovim. Kako bi odašiljač i prijamnik dijelili jednokratni blok ključeva, moraju uspostaviti vezu svaki put kada žele razmijeniti informacije. Moraju se nekako dogovoriti oko slučajnog ključa. Dakle, ovu savršenu i idealnu šifru je vrlo teško implementirati.
Primjer 7.17
Kakav je oblik šifre kada se koristi jednokratna šifra u svakom od sljedećih slučajeva?
A. Izvorni tekst sastoji se od n nula.
b. Izvorni tekst sastoji se od n jedinica.
V. Izvorni tekst sastoji se od izmjeničnih nula i jedinica.
d. Izvorni tekst je slučajni niz bitova.
Riješenje
a. Jer 
, tada će tok šifriranog teksta odgovarati toku ključa. Ako je ključ slučajan, šifrirani tekst je također slučajan. Dijelovi izvornog teksta nisu pohranjeni u šifriranom tekstu.
b. Jer 
, gdje je komplement toka šifriranog teksta je komplement toka ključa. Ako je tok ključeva slučajan, onda je šifrirani tekst također slučajan; dijelovi izvornog 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 komplement. Stoga je rezultat također slučajan ako je tok ključeva slučajan.
d. U ovom je slučaju šifrirani tekst očito slučajan jer izvođenje operacije XOR na dva slučajna bita rezultira slučajnim nizom bitova.
Registar pomaka povratne veze
Jedno poboljšanje jednokratne pločice je (FSR - Feedback Shift Register). FSR se može implementirati u softver ili hardver, ali radi jednostavnosti razmotrit ćemo hardversku implementaciju. Registar pomaka povratne veze sadrži registar pomaka i funkcije povratne sprege, kao što je prikazano na sl. 7.23.
Riža. 7.23.
Registar posmaka je niz od m ćelija od b 0 do b m-1, gdje je svaka ćelija dizajnirana za pohranu jednog bita. Ćelije se tretiraju kao n-bitna riječ, koja se na početku naziva "seed value" ili izvor. Kad god treba poslati bit (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 preuzima vrijednost lijeve ćelije. Krajnja desna ćelija b 0 smatra se izlazom i daje izlaznu vrijednost (k i ). Krajnja lijeva ćelija, b m-1, dobiva svoju vrijednost prema vrijednosti informacije o funkciji povratne sprege. Izlaz funkcije označavamo povratnom informacijom b m . Funkcija povratne informacije određuje koje vrijednosti ćelije moraju izračunati b m . Registar posmaka 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 posmaka s linearnom povratnom spregom radi na binarnim znamenkama, tako da su množenje i zbrajanje u GF(2) polju, tako da je vrijednost C i 1 ili 0, ali C 0 mora biti 1 da bi se dobila povratna informacija na izlazu. Operacija zbrajanja je operacija ISKLJUČIVO ILI. Drugim riječima,
Primjer 7.18
Izgradimo pomakni registar s linearnom povratnom spregom s 5 ćelija, u kojem .
Riješenje
Ako C i = 0, b i ne igra ulogu u izračunu b m, to znači da b i nije povezan s povratnom informacijskom funkcijom. Ako je c i = 1, b i je uključen u izračun b m. U ovom primjeru, c 1 i c 3 su nule, što znači da imamo samo tri veze. Na slici 7.24 prikazan je sklop posmačnog registra s linearnom povratnom spregom.
Riža. 7.24.
Primjer 7.19
Izgradimo pomakni registar s linearnom povratnom spregom s 4 ćelije, u kojem 
. Prikaži vrijednost registra nakon 20 operacije (smjene), ako je izvorna vrijednost (0001) 2 .
Riješenje
Slika 7.25 prikazuje dizajn i korištenje linearnog pomačnog registra zatvorene petlje za šifriranje.
Riža. 7.25.
Tablica 7.6. prikazuje vrijednost toka ključa. Za svaki prijelaz izračunava se prva vrijednost b 4, a zatim se svaki bit pomiče 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ča 1000100110101111 1001……. Na prvi pogled izgleda kao slučajni slijed, ali ako pogledamo veliki broj transakcija (smjena), vidimo da su slijedovi periodični. Ovo ponavljanje od 15 bita prikazano je u nastavku.
Ključ toka se generira pomoću registra pomaka s linearnom povratnom spregom pseudoslučajni niz, u kojima se nizovi duljine N ponavljaju. Protok je periodičan. Ovisi o krugu generatora i početnim informacijama i ne može biti veći od 2 m – 1. Svaki sklop generira 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 samo nula, rezultat je beskoristan - izvorni tekst bio bi tok svih nula. Stoga je takav početni niz isključen.
Nizovi registra pomaka koriste se iu kriptografiji i u teoriji kodiranja. Njihova je teorija dobro razvijena; tokovne šifre temeljene na registru pomaka bile su radna snaga vojne kriptografije davno prije pojave elektronike.
Pomakni registar zatvorene petlje (u daljnjem tekstu RGSSOC) sastoji se od dva dijela: pomakni registar i povratna funkcija. Pomakni registar je niz bitova. Određuje se broj bitova duljina registra posmaka, ako je duljina n bitova, tada se poziva registar n-bitni posmični registar. Kad god treba dohvatiti bit, svi bitovi registra posmaka pomiču se 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. Razdoblje registra pomaka je duljina rezultirajuće sekvence prije početka njenog ponavljanja.
Slika 1. Registar posmaka povratne veze
Registri pomaka brzo su našli upotrebu u šiframa toka jer su se lako implementirali pomoću digitalnog hardvera. Godine 1965. Ernst Selmer, glavni kriptograf norveške vlade, razvio je teoriju niza registra pomaka. Solomon Golomb, NSA matematičar, napisao je knjigu u kojoj predstavlja neke svoje i Selmerove rezultate. Najjednostavniji tip registra posmaka s povratnom spregom je registar posmaka s linearnom povratnom spregom (LFSR). Povratna informacija takvih registara jednostavno je XOR (zbrajanje po modulu dva) nekih bitova registra, popis tih bitova koji se naziva sekvenca odvajanja. Ponekad se takav registar naziva Fibbonaccijeva 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 potvrditi da su sekvence dovoljno nasumične da budu sigurne. RGCCLOS se u kriptografiji koristi češće od ostalih registara pomaka.
Slika 2. PrCsLOS Fibbonacci
Općenito, n-bitni PrCsLOS može biti u jednom od N=2 n -1 internih stanja. To znači da teoretski takav registar može generirati pseudoslučajni niz s periodom od T=2 n -1 bita. (Broj internih stanja i period jednaki su N=T max =2 n -1, jer će punjenje PrCsLOS nulama uzrokovati da registar posmaka proizvodi beskonačan niz nula, što je apsolutno beskorisno). Samo za određene sekvence grananja PrCsLOS će ciklički prolaziti kroz svih 2 n -1 internih stanja, takvi PrCsLOS su RgSsLOS s maksimalnim periodom. Dobiveni rezultat naziva se M-slijed.
Primjer . Donja slika prikazuje 4-bitni PrCCLOS s prvim i četvrtim bitovima koji su uključeni. Ako se inicijalizira s vrijednošću 1111, tada će prije ponavljanja registar poprimiti sljedeća interna stanja:
 Pomak broja sata (interno stanje) |
Status registracije |
Izlazni bit |
|||
|
Početna vrijednost |
|||||
|
15 (povratak u početno stanje) |
|||||
|
16 (ponovljena stanja) |
Izlazna sekvenca bit će niz najmanje značajnih bitova: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 s periodom T=15, ukupnim brojem mogućih internih stanja (osim nule), N=2 4 -1=16-1= 15=T max , dakle, izlazna sekvenca je M-sekvenca.
Da bi određeni PrCsLOS imao maksimalnu periodu, polinom formiran od niza odvoda i konstante 1 mora biti primitivan po modulu 2. Polinom je predstavljen kao zbroj potencija, na primjer, polinom stupnja n predstavljen je 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 ja =(0,1) za i=1…n, a x i - označava znamenku.
Stupanj polinoma je duljina registra posmaka. Primitivni polinom stupnja n je nesvodljivi polinom koji je djelitelj od x 2n?1 +1, ali nije djelitelj od x d +1 za sve d koji su djelitelji od 2 n -1. Odgovarajuća matematička teorija može se pronaći u.
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. To nije lako i pomalo je poput provjere je li nasumično 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 dati su 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.
To se može lako generalizirati na PrCsVOC s maksimalnim razdobljem. Prvi broj je duljina PrCsLOS. Zadnji broj je uvijek 0 i može se izostaviti. Svi brojevi osim 0 određuju slijed dodira, računajući od lijevog ruba registra posmaka. To jest, članovi polinoma s nižim stupnjevima odgovaraju pozicijama bliže desnom rubu registra.
Nastavljajući s primjerom, pisanje (32, 7, 5, 3, 2, 1, 0) znači da se za dati 32-bitni registar posmaka novi bit generira XOR-om tridesetdrugog, sedmog, petog, trećeg, drugi i prvi bitovi, rezultirajući PrCsLOS će imati maksimalnu duljinu, kružeći kroz 2 32 -1 vrijednosti prije ponavljanja.
Slika 4. 32-bitni PrCCLOS s maksimalnom duljinom
Razmotrimo programski kod PrCsLOS, u kojem je niz dodira karakteriziran polinomom (32, 7, 5, 3, 2, 1, 0). U C-u to izgleda ovako:
static unsigned long ShiftRegister = 1;
/* Sve osim 0. */
ShiftRegister = ((((ShiftRegister >> 31)
^(Registar pomaka >> 6)
^(Registar pomaka >> 4)
^(Registar pomaka >> 2)
^(Registar pomaka >> 1)
^ShiftRegister))
| (Registar pomaka >> 1);
vrati ShiftRegister & 0x00000001;)
Ako je registar posmaka duži od računalne riječi, kod postaje kompliciraniji, ali ne puno. Dodatak B sadrži tablicu nekih primitivnih polinoma po modulu 2; koristit ćemo je u budućnosti za identifikaciju nekih svojstava ovih polinoma, kao i u implementaciji softvera za određivanje sekvence dodira.
Imajte na umu da svi elementi tablice imaju neparan broj koeficijenata. Ova dugačka tablica predviđena je za daljnji rad s RgCsLOC-om, budući da se RgCsLOC često koristi za kriptografiju s tokovnim šiframa i u generatorima pseudoslučajnih brojeva. U našem slučaju možemo koristiti polinome s najvećim stupnjem od najviše sedam.
Ako je p(x) primitivan, onda je x n p(1/x) primitivan, pa svaki element tablice 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 primitivan, onda je x a +x a-b +1 primitivan,
ako je x a +x b +x c +x d +1 primitivan, onda je x a +x a-d +x a-c +x a-b +1 primitivan. Primitivne trinome najbrže je implementirati u softver, budući da za generiranje novog bita trebate izvršiti XOR samo dva bita registra posmaka (nulti član se ne uzima u obzir, tj. x 0 = 1, pogledajte gornji primjer). Doista, svi povratni polinomi navedeni u tablici su rijetki, odnosno imaju malo koeficijenata. Rijetkost je uvijek izvor slabosti, što je ponekad dovoljno da pokvari algoritam. Za kriptografske algoritme puno je bolje koristiti guste primitivne polinome, one s mnogo koeficijenata. Korištenjem gustih polinoma, posebno kao dijela ključa, može se koristiti puno kraći PrCsLOS.
Generiranje gustih primitivnih polinoma po modulu 2 nije lako. Općenito, da biste generirali primitivne polinome stupnja k, morate znati faktorizaciju broja 2 k -1.
Sami po sebi, PrCsLOS su dobri generatori pseudoslučajnih nizova, ali imaju neka nepoželjna neslučajna (deterministička) svojstva. Uzastopni bitovi su linearni, što ih čini beskorisnim za enkripciju. Za PrCcLOS duljine n, interno stanje je prethodnih n izlaznih bitova generatora. Čak i ako se povratni krug drži u tajnosti, može se odrediti iz 2n izlaznih bitova oscilatora pomoću visoko učinkovitog Berlekamp-Massey algoritma.
Osim toga, veliki nasumični brojevi generirani korištenjem uzastopnih bitova ovog niza visoko su povezani i, za neke vrste aplikacija, uopće nisu nasumični. Unatoč tome, RgCCLOS se često koriste za izradu algoritama šifriranja kao komponente sustava i algoritama šifriranja.
Nizovi registra pomaka koriste se iu kriptografiji i u teoriji kodiranja. Njihova je teorija dobro razvijena; tokovne šifre temeljene na registru pomaka bile su radna snaga vojne kriptografije davno prije pojave elektronike.
Registar posmaka povratne sprege sastoji se od dva dijela: registra posmaka i funkcije povratne sprege (slika 1.2.1). Pomakni registar je niz bitova. (Broj bitova određen je duljinom registra posmaka. Ako je duljina n bitova, tada se registar naziva n-bitnim registrom posmaka.) Kad god treba dohvatiti bit, svi bitovi registra posmaka pomaknuti su 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 duljina rezultirajuće sekvence prije nego što se počne ponavljati.
Riža. 1.2.1.
Kriptografima su se svidjele tokovne šifre temeljene na registrima pomaka: bilo ih je lako implementirati pomoću digitalnog hardvera. Samo ću se kratko dotaknuti matematičke teorije. Godine 1965. Ernst Selmer, glavni kriptograf norveške vlade, razvio je teoriju niza registra pomaka. Solomon Golomb, NSA matematičar, napisao je knjigu u kojoj predstavlja neke svoje i Selmerove rezultate.
Najjednostavniji tip registra posmaka s povratnom spregom je registar posmaka s linearnom povratnom spregom ili LFSR (slika 1.2.2). Povratna informacija je jednostavno XOR nekih bitova registra, popis tih bitova koji se naziva sekvenca dodira. Ponekad se takav registar naziva Fibbonaccijeva 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 sekvence dovoljno nasumične da budu sigurne. LFSR su najčešće korišteni registri pomaka u kriptografiji.
Riža. 1.2.2.
Na sl. Slika 1.2.3 prikazuje 4-bitni LFSR s odvojcima iz prvog i četvrtog bita. Ako se inicijalizira s vrijednošću 1111, tada će prije ponavljanja registar poprimiti sljedeća interna stanja:
Riža. 1.2.3. 4
Izlazna sekvenca bit će niz najmanje značajnih 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 pseudoslučajni niz s periodom od 2n-1 bita. (Broj internih stanja i period su 2n-1 jer će punjenje LFSR-a nulama uzrokovati da registar posmaka proizvede beskonačan niz nula, što je apsolutno beskorisno.) Samo za određene nizove dodira LFSR će kružiti kroz sve 2n- 1 unutarnja stanja, takvi LFSR-ovi su LFSR-ovi s maksimalnim razdobljem. Rezultirajući rezultat naziva se M-niz.
Kako bi određeni LFSR imao maksimalnu periodu, polinom formiran od niza odvoda i konstante 1 mora biti primitivan po modulu 2. Stupanj polinoma je duljina registra posmaka. Primitivni polinom stupnja n je nesvodljivi polinom koji je djelitelj, ali nije djelitelj od 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. Ovo nije jednostavno - i pomalo je poput provjere je li nasumični 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 može lako generalizirati na maksimalni period LFSR. Prvi broj je duljina LFSR-a. Zadnji broj je uvijek 0 i može se izostaviti. Svi brojevi osim 0 određuju slijed dodira, računajući od lijevog ruba registra posmaka. To jest, članovi polinoma s nižim stupnjevima odgovaraju pozicijama bliže desnom rubu registra.
Nastavljajući s primjerom, pisanje (32, 7, 5, 3, 2, 1, 0) znači da se za dati 32-bitni registar posmaka novi bit generira XOR-om tridesetdrugog, sedmog, petog, trećeg, drugi i prvi bit će rezultirajući LFSR imati maksimalnu duljinu, kružeći kroz 232-1 vrijednosti prije ponavljanja.
Registar pomaka s linearnom povratnom spregom (LFSR) mehanizam je za stvaranje pseudoslučajnog niza binarnih bitova. Registar (slika 1) sastoji se od niza ćelija koje se uspostavljaju inicijalizacijskim vektorom (najčešće tajnim ključem). Rad registra određen je prisutnošću ili odsutnošću komunikacije od svakog bita do povratne sprege. Odvojci registra povratnih informacija nisu fiksni, već su dio ključa. U sljedećem koraku sadržaj ćelija registra pomiče se za jednu poziciju udesno, a jedan bit koji ostane slobodan kao rezultat operacije XOR se postavlja u krajnju lijevu ćeliju.
Riža. 1. Pomakni registar s linearnom povratnom spregom
Da bi se postigla maksimalna šifra gama period, broj bitova m posmični registar odabran je tako da bude jednak jednom od Mersenneovih prostih brojeva (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203...), a unutarnje veze registra moraju biti odabrane prema nesvodljivim primitivnim polinomima najvišeg stupnja m. U tom slučaju, gama period šifre može doseći (2 m-1).
LFSR je brz i jednostavan za implementaciju u softver i hardver. S pravilnim izborom povratnih bitova, generirani nizovi imaju dobra statistička svojstva. LFSR se koristi kao osnovni element za izgradnju visoko sigurnih sustava.
Kaskada registara je skup LFSR-ova povezanih na takav način da ponašanje jednog LFSR-a ovisi o ponašanju prethodnog LFSR-a u kaskadi. Ovo "ovisno" ponašanje obično je osmišljeno za kontrolu brojača pomaka sljedećeg LFSR-a od strane prvog LFSR-a.
Primjerice, registar se pomiče za jedan korak ako je vrijednost prethodnog registra 1, a ako je vrijednost 0, tada se registar pomiče za dva koraka ili na neki drugi način. Velik broj takvih kombinacija omogućuje vrlo visoku sigurnost.
Najsigurnije nizove proizvodi generator koji se skuplja na temelju jednostavne interakcije između rezultata dvaju LFSR registara. Bitovi jednog rezultata određuju hoće li 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 ako se ne poduzmu neke mjere opreza.
Fibonaccijeva metoda s kašnjenjima Jedan od široko korištenih Fibonaccijevih generatora temelji se na sljedećoj iterativnoj formuli:
Gdje Y k- realni brojevi iz raspona
Riža. 2. Round-robin šifriranje
Način DES izlazne povratne informacije može se koristiti za generiranje pseudoslučajnih brojeva, slično kao što se koristi za enkripciju toka. Izlaz svakog stupnja enkripcije je 64-bitna vrijednost, od koje se samo najvažnijih j bitova vraća za enkripciju. 64-bitni izlazi su niz pseudo-nasumičnih brojeva s dobrim statističkim svojstvima.
Generator pseudo-slučajnih brojeva, opisan u standardu ANSI X9.17, jedan je od najsigurnijih generatora pseudo-slučajnih brojeva. Aplikacije koje koriste ovu tehnologiju uključuju financijsku sigurnost i PGP aplikacije.
Generator ANSI X9.17 sastoji se od sljedećih dijelova (slika 3):
1. Ulaz: Generatorom upravljaju dva pseudoslučajna ulaza. Prvi unos 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 se inicijalizira na neku proizvoljnu vrijednost i modificira tijekom generiranja niza pseudoslučajnih brojeva ( V i).
2. Tipke: Generator koristi tri trostruka DES modula s 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 početna vrijednost pri kreiranju sljedećeg broja ( V i +1) .
Riža. 3. ANSI X9.17 generator pseudoslučajnih brojeva
