Registar pomaka s linearnom povratnom spregom. Registar linearnog pomaka s povratnom spregom Primjer registra linearnog pomaka

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 registra pomaka se pomiču udesno za jednu poziciju, obično prema najmanjim bitovima. 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 znanja 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.

Ministarstvo obrazovanja i znanosti

RUSKO DRŽAVNO DRUŠTVENO SVEUČILIŠTE

FAKULTET INFORMACIJSKIH TEHNOLOGIJA

ODSJEK ZA ZAŠTITU INFORMACIJA

Kriptografske metode i sredstva osiguranja informacijske sigurnosti

Tečajni rad

„R registri pomaka s linearnom povratnom spregom kao generatori pseudoslučajnih brojeva"

Završeno:

student 3. godine

KZOI-D-3 grupa

Larionov I.P.

Provjereno:

Izv. prof. Baranova E.K.

Moskva 2011
SADRŽAJ

Uvod ……………………………..…………………………………….3

1. Teorijske osnove rada…………………………………………4
   1. Opće informacije o registrima pomaka s povratnom spregom …………..4
      1. O stream šiframa temeljenim na RgCsLOS………………….………10
      2. O linearnoj složenosti generiranog pseudoslučajnog niza PgCsLOS……………………………………………….……12
      3. O korelacijskoj neovisnosti generiranog niza pseudoslučajnih brojeva PrCsLOS………..….13
      4. O ostalim metodama otvaranja generiranog niza pseudoslučajnih brojeva RgCsLOS……………………………………..14
2. Softverska implementacija RgCsLOS-a kao generatora pseudo-slučajnih sekvenci….…………………………….15
   1. Generalizirana shema algoritma………………………………………………...15
   2. Opis softverskih modula i sučelja………………….16
   3. Priručnik za upotrebu……………………………………………20

Zaključak ………………………………………………………………22

Bibliografija………………………………………………….....23

Dodatak A ….………………………………………………………..24

UVOD

Svrha ovog rada je razvoj softverske aplikacije koja implementira rad generatora pseudoslučajnih brojeva na temelju pomačnih registra s povratnom spregom. Razvoj ove aplikacije s grafičkim sučeljem odvija se na jeziku C++ za Windows OS.

S razvojem kriptografije u 20. stoljeću, kriptografi su se suočili sa zadatkom stvaranja uređaja i strojeva za šifriranje koji bi mogli brzo i pouzdano šifrirati i dešifrirati poruke. Sustavi simetrične enkripcije, već otvoreni u to vrijeme, ispunjavali su ovaj zahtjev, ali njihova slaba točka bila je snažna ovisnost o ključu i njegovoj tajnosti. Najprikladnija klasa šifri koje bi se mogle koristiti u tu svrhu su šifre za igru. Problem je nastao u generiranju gama koje se nije moglo detektirati kada je poruka dešifrirana. Teoretski, to je bilo moguće ako je svaki put gama bila nasumična i mijenjala se tijekom vremena. Međutim, kada se koristi gama koja se potpuno nasumično mijenja, bilo bi teško osigurati pouzdano šifriranje-dešifriranje poruke. Kriptografi su preuzeli zadatak rješavanja ovog problema, čija je svrha bila pronaći algoritam koji implementira generiranje slučajnog raspona prema određenom pravilu, takav slijed bi trebao sadržavati nule i jedinice na “navodno” slučajnim pozicijama, a broj jedinica i nula trebao bi biti približno isti. Ovaj nasumični niz naziva sepseudo-slučajnibudući da je generiran prema određenom pravilu, a ne nasumično.

Rješenje je ubrzo pronađeno. Proučavanje svojstava registra pomaka omogućilo je utvrđivanje da su registri pomaka s povratnom spregom sposobni generirati pseudoslučajne sekvence koje su zbog svoje unutarnje strukture dovoljno otporne na dekodiranje.

1.Teorijske osnove rada

1.1 Opći podaci o pomačnim registrima s linearnom povratnom spregom

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 (u daljnjem tekstu PgCsOS) sastoji se od dva dijela: registra pomaka i povratne funkcije.Pomakni registar je niz bitova. Određuje se broj bitovaduljina registra pomaka, ako je duljina n bitova, tada se poziva registarn-bitni pomakni registar. Kad god treba izdvojiti bit, svi bitovi registra pomaka se pomiču 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.Razdoblje registra pomakaje duljina rezultirajućeg niza prije nego što se počne ponavljati.

Slika Registar pomaka povratne sprege

Registri s pomakom su brzo našli primjenu u stream šiframa, jer su se lako implementirali pomoću digitalnog hardvera. Godine 1965. Ernst Selmer, glavni kriptograf norveške vlade, razvio je teoriju slijeda registra pomaka. Solomon Golomb, NSA matematičar, napisao je knjigu u kojoj je iznio neke od njegovih i Selmerovih rezultata. Najjednostavniji tip registra pomaka jelinearni povratni pomakni registar ( linearni pomakni registar povratne sprege, u daljnjem tekstu LFSR ili RgCsLOS) . Povratna informacija takvih registara je jednostavno XOR (modulo dva zbrajanja) nekih bitova registra, popis tih bitova naziva se tap sekvenca. Ponekad se takav registar naziva Fibonaccijeva konfiguracija. Zbog jednostavnosti sekvence povratne sprege, za analizu PgCsLOC može se koristiti prilično razvijena matematička teorija. Analizom rezultirajućih izlaznih sekvenci možete provjeriti jesu li ti nizovi dovoljno nasumični da budu sigurni. Registri pomaka se koriste češće od ostalih pomačnih registara u kriptografiji.

Slika PgCsLOS Fibbonacci

Općenito, n -bit PrCsLOS može biti u jednom od N=2n -1 unutarnjih stanja. To znači da, teoretski, takav registar može generirati pseudoslučajni niz s periodom od T=2 n -1 bit. (Broj unutarnjih stanja i razdoblje su jednaki N=Tmax=2n -1 jer će punjenje PrCsLOC nulama uzrokovati da registar pomicanja ispusti beskonačan niz nula, što je apsolutno beskorisno). Samo s određenim sekvencama slavina PrCsLOS će ciklički proći kroz sva 2 n -1 unutarnjih stanja, kao što su RgCsLOSRgSsLOS s maksimalnim razdobljem. Rezultirajući rezultat se zoveM-sekvencija.

Primjer . Slika ispod prikazuje 4-bitni PrCsLOS s dodirom od prvog i četvrtog bita. Ako je inicijaliziran s vrijednošću 1111, tada će prije ponavljanja registar poprimiti sljedeća interna stanja:

Pomak kvačica (interno stanje)	Status registra				izlazni bit
Početna vrijednost
15 (povratak u početno stanje)
16 (ponavljajuća stanja)

Izlazni niz bit će niz najmanjih bitova: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 s periodom T=15, ukupan broj mogućih unutarnjih stanja (osim nule), N=2 4 -1=16-1=15= Tmax , dakle, izlazni slijed je M -slijed.

Da bi određeni PgCsLOS imao maksimalnu period, polinom formiran od tap sekvence i konstante 1 mora biti primitivan po modulu 2. Polinom je predstavljen kao zbroj potencija, na primjer, polinom stupnja n izgleda ovako:

anxn +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =anxn +a n-1 x n-1 +…+a 1 x+a 0 , gdje je a i =(0, 1 ) za i=1…n, axi – označava bit .

Stupanj polinoma je duljina registra pomaka. Primitivni polinom stupnja n je nesvodljivi polinom koji je djelitelj x 2n−1 +1, ali nije djelitelj x d +1 za sve d koji su djelitelji 2 n -jedan. Odgovarajuća matematička teorija može se nać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 donekle je poput provjere nije li slučajno odabrani broj prost - ali mnogi matematički softverski paketi mogu riješiti ovaj problem.

Neki, ali zasigurno ne svi, polinomi različitih stupnjeva, primitivnih modula 2, navedeni su u nastavku. Na primjer, unos

(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 lako može generalizirati na PrCcLOC s maksimalnim razdobljem. Prvi broj je duljina PrCsLOS. 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 , i prvi bitovi, rezultirajući RgCsLOS imat će maksimalnu duljinu, ciklus će se ponavljati nakon 2 32 -1 vrijednosti.

Slika 4 32-bitni PrCsLOS s maksimalnom duljinom

Razmotrimo programski kod PgCsLOS, u kojem je slijed slavina karakteriziran polinomom (32, 7, 5, 3, 2, 1, 0). U jeziku C to izgleda ovako:

int LFSR()(

statički nepotpisani dugi ShiftRegister = 1;

/* Sve osim 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

vrati ShiftRegister & 0 x 00000001;)

Ako je pomakni registar duži od računalne riječi, kod postaje kompliciraniji, ali ne puno. U aplikaciji B data je tablica nekih primitivnih polinoma po modulu 2, koristit ćemo je u budućnosti za identifikaciju nekih svojstava ovih polinoma, kao i u softverskoj implementaciji za postavljanje tap sekvence.

Treba napomenuti da svi elementi tablice imaju neparan broj koeficijenata. Ovako duga tablica predviđena je za daljnji rad s PrCcLOC, budući da se PrCcLOC često koristi za kriptografiju s stream šiframa i u generatorima pseudoslučajnih brojeva. U našem slučaju možemo koristiti polinome s najvišim stupnjem ne više od sedam.

Ako je p(x) primitivan, onda je i x n p(1/x), tako da svaki element tablice zapravo definira dva primitivna polinoma. Na primjer, ako je (a, b, 0) primitivno, onda je i (a, a-b, 0). Ako je (a, b, c, d, 0) primitivan, onda je i (a, a-d, a-c, a-b, 0). Matematički:

ako je x primitivan a+xb +1, onda je primitivan i x a+x a-b+1,

ako je x primitivan a + x b + x c + x d +1, onda je primitivan i x a + x a-d + x a-c + x a-b +1. Primitivni trinomi najbrže se programski implementiraju, budući da za generiranje novog bita potrebno je XOR samo dva bita pomaknog registra (nulti član se ne uzima u obzir, tj. x 0 =1, vidi gornji primjer). Doista, svi polinomi povratne sprege dani u tablici su rijetki, odnosno imaju malo koeficijenata. Oskudnost je uvijek izvor slabosti, što je ponekad dovoljno za otvaranje algoritma. Za kriptografske algoritme puno je bolje koristiti guste primitivne polinome, one koji imaju mnogo koeficijenata. Korištenjem gustih polinoma, posebno kao dijela ključa, može se koristiti mnogo kraći PrCcLOC.

Generiranje gustih primitivnih polinoma po modulu 2 nije lako. U općem slučaju, da bi se generirali primitivni polinomi stupnja k, potrebno je znati faktorizaciju broja 2 k-1.

Sami po sebi, PgCsLOS su dobri generatori pseudo-slučajnih sekvenci, ali imaju neka nepoželjna neslučajna (deterministička) svojstva. Sekvencijalni bitovi su linearni, što ih čini beskorisnim za šifriranje. Za PgCsLOS duljine n, interno stanje je prethodnih n izlaznih bitova generatora. Čak i ako se shema povratne sprege drži u tajnosti, ona se može odrediti iz 2n izlaznih bitova generatora koristeći visoko učinkovit Berlekamp-Massey algoritam.

Osim toga, veliki slučajni brojevi generirani korištenjem uzastopnih bitova ovog niza su visoko povezani i, za neke vrste aplikacija, uopće nisu slučajni. Unatoč tome, PrCsLOS se često koriste za stvaranje algoritama za šifriranje kao komponente sustava i algoritama za šifriranje.

1.2. O stream šiframa temeljenim na RgCsLOS

Osnovni pristup projektiranju generatora ključnog toka baziranog na PrCsLOS je jednostavan. Prvo se uzima jedan ili više PrCsLOS, obično s različitim duljinama i različitim polinomima povratne sprege. (Ako su duljine međusobno proste i svi polinomi povratne sprege primitivni, tada će rezultirajući generator imati maksimalnu duljinu.) Ključ je početno stanje registara PrCcLOC. Svaki put kada je potreban novi bit, malo pomaknite registre PrCsLOS (ponekad se naziva taktiranje). Izlazni bit je funkcija, po mogućnosti nelinearna, nekih bitova PrCsLOC registara. Ova funkcija se naziva kombinirana funkcija, a generator u cjelini naziva se kombinacijski generator. (Ako je izlazni bit funkcija jednog PgCsLOS-a, tada se oscilator naziva filtarski oscilator.) Velik dio teorije iza ovih vrsta uređaja razvili su Selmer i Neal Zierler. Možete uvesti niz komplikacija. U nekim se generatorima koriste različite taktne frekvencije za različite PgCsLOS, ponekad frekvencija jednog generatora ovisi o izlazu drugog. Sve su to elektroničke verzije ideja šifriranih strojeva prije Drugog svjetskog rata zvanih oscilatori upravljani satom ( generatori upravljani satom ). Kontrola takta može biti usmjerena naprijed, gdje izlaz jednog PgSsLOS kontrolira brzinu takta drugog PgSsLOS, ili zatvorena petlja, gdje izlaz jednog PgSsLOS kontrolira vlastiti sat. Iako su svi ovi generatori osjetljivi, barem u teoriji, na napade gniježđenja i vjerojatne korelacije, mnogi od njih su još uvijek sigurni.

Ian Cassells, bivši predsjedavajući čiste matematike na Cambridgeu i kriptoanalitičar u Bletchly Parku, rekao je da je "kriptografija mješavina matematike i zbrke, i bez zabune, matematika se može koristiti protiv vas." Ono što je mislio je da su u stream šiframa određene matematičke strukture, kao što je PrCcLOC, potrebne za pružanje maksimalne duljine i drugih svojstava, ali se mora uvesti neki složeni nelinearni nered kako bi se spriječilo da netko dobije sadržaj registra i krene algoritam. Ovaj savjet vrijedi i za blok algoritme.

Većina pravih stream šifri temelji se na PrCsLOS. Čak iu ranim danima elektronike bilo ih je lako izgraditi. Pomakni registar nije ništa više od niza bitova, a slijed povratne sprege je skup XOR vrata. Čak i kada se koristi VLSI, stream šifra bazirana na PrCsLOS pruža značajnu sigurnost uz pomoć nekoliko logičkih vrata. Problem s PgCsLOS je što je njihova softverska implementacija vrlo neučinkovita. Morate izbjegavati rijetke polinome povratne sprege – oni olakšavaju korelacijske napade – a gusti polinomi povratne sprege su neučinkoviti.

Ova grana kriptografije brzo raste i pod budnom je državnom kontrolom NSA . Većina razvoja je tajna - mnogi vojni sustavi šifriranja koji se danas koriste temelje se na PrCsLOS-u. Doista, većina Cray računala (Cray 1, Cray X-MP, Cray Y-MP) ima vrlo zanimljivu uputu koja se obično naziva "broj stanovništva". Broji broj 1 u registru i može se koristiti i za učinkovito izračunavanje Hammingove udaljenosti između dvije binarne riječi i za implementaciju vektorizirane verzije PrCcLOS. Ova se uputa smatra kanonskom uputom NSA-e i pojavljuje se u gotovo svim računalnim ugovorima.

S druge strane, hakiran je iznenađujuće velik broj naizgled složenih generatora registra pomaka. I, naravno, broj takvih generatora hakiranih od strane vojnih kriptoanalitičkih institucija kao što je NSA još je veći.

1.3 O linearnoj složenosti generiranog niza pseudoslučajnih brojeva PrCsLOS

Stream šifre je često lakše raščlaniti nego blok šifre. Na primjer, važan parametar koji se koristi za analizu generatora temeljenih na PgCsLOC je linearna složenost ili linearni interval. Definira se kao duljina n najkraćeg PrCsLOS-a koji može simulirati izlaz generatora. Svaki niz koji generira konačni automat nad konačnim poljem ima konačnu linearnu složenost. Linearna složenost je važna jer se jednostavnim algoritmom zvanim Berlekamp-Massey algoritam može odrediti ovaj PrCcLOC ispitivanjem samo 2n bita toka ključeva. Ponovno kreiranjem željenog PrCsLOS-a razbijate šifru toka.

Ova se ideja može proširiti s polja na prstenove i na slučajeve gdje se izlazni niz tretira kao brojevi u polju neparne karakteristike. Daljnje proširenje dovodi do uvođenja koncepta linearnog profila složenosti, koji određuje linearnu složenost niza kako se produžuje. Također postoje koncepti sferne i kvadratne složenosti. U svakom slučaju, treba imati na umu da visoka linearna složenost ne jamči nužno sigurnost generatora, ali niska linearna složenost ukazuje na nedovoljnu sigurnost generatora.

1.4. O korelacijskoj neovisnosti generiranog niza pseudoslučajnih brojeva PrCsLOS

Kriptografi pokušavaju postići visoku linearnu složenost kombiniranjem rezultata nekih izlaznih sekvenci na nelinearan način. Ovdje postoji opasnost da jedan ili više internih izlaznih sekvenci - često samo izlazi pojedinačnih PrCsLOC - mogu biti povezani zajedničkim ključem i otkriveni korištenjem linearne algebre. Često se takav obračun naziva korelacijski obračun ili obračun zavadi pa vladaj. Thomas Siegenthaler je pokazao da se korelacijska neovisnost može precizno definirati i da postoji kompromis između korelacijske neovisnosti i linearne složenosti.

Glavna ideja otvaranja korelacije je pronaći neku korelaciju između izlaza generatora i izlaza jedne od njegovih komponenti. Zatim, promatrajući izlazni slijed, može se dobiti informacija o tom međuizlazu. Koristeći ove informacije i druge korelacije, mogu se prikupiti drugi međuizlazi dok se generator ne hakira.

Korelacijski napadi i njihove varijacije, kao što su napadi brze korelacije, uspješno su korišteni protiv mnogih generatora toka ključeva baziranih na PrCsLOC, nudeći kompromis između računske složenosti i učinkovitosti.

1.5. O drugim metodama otvaranja generiranog niza pseudoslučajnih brojeva PgCsLOS

Postoje i drugi načini za razbijanje generatora toka ključeva. Test linearne konzistentnosti pokušava pronaći neki podskup ključa za šifriranje koristeći tehniku ​​matrice. Postoji i napad na dosljednost susreta u sredini na ispravnost. Algoritam linearnog sindroma temelji se na sposobnosti zapisivanja fragmenta izlaznog niza kao linearne jednadžbe. Postoji napad najbolje afine aproksimacije i napad izvedene sekvence. Metode diferencijalne i linearne kriptoanalize također se mogu primijeniti na stream šifre.

2. Opis programske implementacije PrCsLOS-a kao generatora pseudo-slučajnih sekvenci

2.1 Generalizirana shema algoritma

2.2 Opis softverskih modula i sučelja

Slika 3 ispod prikazuje prozor programa.

Slika Programsko sučelje

Izbornik ima sljedeće funkcije:

• Datoteka->Spremi izvješće

Ova funkcija generira datoteku izvješća u koju se upisuje početno stanje PrCsLOS, tap slijed, period primljenog pseudo-slučajnog niza bitova, sam slijed i tablica stanja. Ako je datoteka uspješno spremljena, prikazuje se poruka o uspješnom spremanju (slika 4). Preporučena ekstenzija datoteke za izvješće je *. txt.

Crtanje

• Datoteka->Izlaz

Ova funkcija osigurava da je aplikacija zatvorena.

• Postavite izlazni slijed

Ova funkcija generira slijed dodira čitanjem vrijednosti iz ćelija koje je korisnik označio na obrascu zaslona. Nakon toga obavještava korisnika o kreiranju sekvence dodira (slika 5). Slijed dodira određuje koji će japanci registra pomaka dobiti povratnu informaciju. XOR za formiranje ofsetnog bita. Prema zadanim postavkama, povratna sprega s prvog okidača je uvijek uključena, u nedostatku drugih veza izvršit će se pomak ulijevo s promjenom najmanje značajnog bita na poziciju najznačajnijeg.

Crtanje

• Postavite početnu vrijednost

Ova funkcija čita početnu vrijednost registra koju je korisnik unio iz prozora Uredi 1 i provjerava unesenu vrijednost prema navedenim uvjetima: uneseni niz nije prazan (slika 6), uneseni niz ima duljinu osam (8bit=1bajt, slika 7), uneseni niz sadrži samo nule i/ili jedinice (slika 8), uneseni niz nije nula (slika 9). U suprotnom se prikazuju poruke o pogrešci, korisnik ih mora ispraviti i ponovno pritisnuti tipku. U slučaju uspješne provjere, početna vrijednost će biti upisana u tablicu stanja u retku "Inicijalno" i bit će izdana obavijest (slika 10.).

Crtanje

Crtanje

Crtanje

Crtanje

Crtanje

• Izvršite pomak registra

Ova funkcija oponaša rad registra pomaka. Slijedom čineći 256 pomaka, svaki pomak generira izlazni bit pseudo-slučajnog niza i novo stanje registra. Čim je stanje registra jednako početnom, razdoblje se izračunava i prikazuje u polju dopis 1 je primio pseudoslučajni niz.

• Pomoć-> O

Ova funkcija prikazuje kratak opis programa i upute (slika 11).

Crtanje

• Pomoć-> O autoru

Ova funkcija prikazuje podatke o autoru programa (slika 12).

Crtanje

2.3 Korisnički priručnik

1. Prvo postavite početno stanje registra. Mora sadržavati osam binarnih znakova. U suprotnom će se prikazati poruka o pogrešci i morat ćete ispraviti unesenu vrijednost. Pritisnite stavku izbornika "Postavi početnu vrijednost".
2. Zatim označite potvrdne okvire za povratne informacije o registraciji (Tap Sequence). Pritisnite stavku izbornika "Set Tap Sequence".
3. Zatim kliknite stavku izbornika "Registriraj Shift". Prije nego što to učinite, provjerite jeste li dovršili korake 1 i 2, inače će doći do softverske pogreške.
4. Nakon što primite rezultate, možete ih spremiti klikom na stavku izbornika "Datoteka->Spremi izvješće". Obavezno provjerite jeste li dovršili korake 1-3 prije nego što to učinite, inače će doći do softverske pogreške.
5. Da biste dobili pomoć, kliknite stavke izbornika "Datoteka->O", "Datoteka->O autoru".
6. Da biste vidjeli rad registra s drugim vrijednostima slijeda dodira i početnim stanjem registra, uzastopno ponovite korake u koracima 1-3, unoseći druge parametre.

ZAKLJUČAK

U ovom radu RgCsLOS su razmatrani kao generatori pseudoslučajnih brojeva. Program može poslužiti kao vizualna demonstracija principa rada pomačnih registara s uključenim linearnom povratnom spregom XOR . Na njemu možete proučavati princip formiranja pseudoslučajnog niza bitova, odnos između početne vrijednosti registra i vrijednosti pseudoslučajnog niza, tap sekvence i perioda. Rezultirajuća pseudo-slučajna gama može se koristiti u drugoj softverskoj aplikaciji (na primjer, softverska implementacija gama šifre).

Do danas se ovi registri ne koriste kao neovisni generatori pseudoslučajnih brojeva, već su dio složenijih uređaja. Međutim, upravo su oni otvorili nove smjerove u matematici (potraga za primitivnim polinomima u konačnim poljima, matematičke metode za razbijanje generatora pseudoslučajnih brojeva). Bez poznavanja principa rada generatora na RgCsLOS nemoguće je razumjeti rad složenijih uređaja. Zbog svoje jednostavne hardverske implementacije, široko se koriste u tehnologiji. Istraživanje PrCsOS-a dovelo je do pojave novih šifri - blok i stream - baziranih na ovim vrstama registara (sliding permutation cipher, DES itd.; EDS, hash funkcije).

Općenito, istraživanja u ovom području ozbiljno su potaknula razvoj kriptografije i kriptoanalitičara, računala i uređaja, a također su omogućila implementaciju niza drugih korisnih funkcija (primjerice, ispravljanje cikličkih kodova).

BIBLIOGRAFIJA

1. Schneier Bruce. Primijenjena kriptografija. Protokoli, algoritmi, izvorni tekstovi u C jeziku. - M .: Trijumf, 2002
2. Babash A.V. Kriptografski i automatsko-teorijski aspekti suvremene informacijske sigurnosti. Svezak 1 - M .: Izd. Centar EAOI, 2009. - 414 str.
3. E.S. Selmer. Monografija: "Linearna rekurzija u konačnom polju". Sveučilište u Bergenu, Norveška, 1966.
4. N. Zierler i J. Brillhart. "On Primitive Trinomials Modulo 2", Journal of Information and Control, Vol. 13 No. 6. prosinca 1968., str. 541-544.
5. K.Kh. Meyer i W. L. Tuchman. "Pseudo-slučajni kodovi mogu se razbiti", časopis Electronic Design, br. 23. studenog 1972.
6. J. L. Massey. "Generalizacija registara pomaka i dekodiranje koda Bose-Chowdhury-Hokvingham", IEEE Transakcije o teoriji informacija, v. IT-15, br . 1. siječnja 1969., str. 122-127.
7. S.U. Golomb. Sekvence registra pomaka, San Francisco, Zlatni dan, 1967. (pretisnuo Aigean Park Press, 1982.).

Dodatak A

Tablica nekih primitivnih polinoma po modulu 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Unos početnog stanja (IS)

validacija unosa

Izdavanje poruke o pogrešci

Postavljanje redoslijeda dodira

Snimanje IP-a u tablici stanja

Zapis i -ti registar stanja i izlazni bit u tablicu stanja

IS==Trenutno stanje

Spremanje rezultata

Izlaz pseudoslučajnog niza

Izlaz

lansirati

Da

Da

Ne

U registru pomaka 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 principu, 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 - izvršavanjem programskog ciklusa, uključujući izračun povratne funkcije i pomak 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:

Definicija

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 otkriti pomoću linearne algebre. Hakiranje na temelju takve ranjivosti zove se korelacijske autopsije. Thomas Siegenthaler je pokazao da se korelacijska neovisnost može precizno definirati i 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:

Broj koraka	država	Bit generiran
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

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); vrati 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

Galois 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 je malo izmijenjen: u krugu takta, kao provjera za 0 ili 1, ne prima se sam izlazni signal, već XOR određenih bitova pomaknog 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.

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 slavine. 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.

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). Pomakni registar 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 pomicanja 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-sekvenca.

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 ponavljanja.