Spremični register z linearno povratno informacijo. Primer linearnega premičnega registra s povratnimi informacijami

Za izgradnjo tokovnih šifer se zelo pogosto uporabljajo zaporedja v premičnih registrih. Pomikalni register s povratnimi informacijami je sestavljen iz dveh delov: premičnega registra in povratne funkcije, kot je prikazano na sl. 87. Sam pomični register je zaporedje bitov, katerih število določa dolžino registra. Torej, če je v registru vključenih n bitov, potem pravijo, da je n-bitni premični register. Vsakič, ko se pridobi bit, se vsi bit premičnega registra premaknejo v desno za en položaj, običajno proti najmanj pomembnim bitom. Obdobje premičnega registra je dolžina nastalega zaporedja, preden se začne ponavljati.

riž. 87.

Vsaka matematična funkcija, ki izvaja operacijo na bitih, lahko deluje kot povratna informacija. Najpreprostejša vrsta premičnega registra s povratnimi informacijami je linearni premični register s povratnimi informacijami (LFSR). V LFSR je povratna informacija preprosto operacija seštevanja po modulu 2 (XOR) na nekaterih bitih registra; seznam teh bitov se imenuje zaporedje pip ali prevzemnih točk, kot je prikazano na sl. 88. Včasih se tak vzorec imenuje Fibonaccijeva konfiguracija. Zaradi preprostosti zaporedja povratnih informacij je mogoče za analizo LFSR uporabiti dokaj razvito matematično teorijo. Kakovost izdelanega SRP-ja se v vsakem primeru ocenjuje s posebnim sklopom testov.

riž. 88.

LFSR so zapisani v obliki polinomov. V tem primeru stopnja prvega elementa polinoma označuje število bitov v premičnem registru, eksponentni eksponenti preostalih članov polinoma pa kažejo, katere točke prevzema bodo uporabljene. Tako na primer zapis x 4 + x + 1 pomeni, da bo uporabljen register štirih elementov, za katere bosta bita bi in b 0 sodelovala pri oblikovanju povratne informacije (slika 89).

riž. 89.4

Razmislite o delovanju registra, prikazanem na sl. 89. Inicializirajte ga na primer z vrednostjo 0101 (začetno inicializacijo lahko izvede katero koli zaporedje bitov, razen zaporedja samo nič, saj bo v tem primeru povratna informacija vedno tvorila vrednost nič in register bo ne ustvari pričakovanega PSP). Torej, v registru je premik v desno za eno pozicijo. Najmanjši bit, enak 1, se iztisne iz registra in tvori prvi bit PRS. Tisti biti, ki so bili na položajih b in b 0 pred premikom, se dodajo po modulu 2 in tvorijo novo

visoki del registra. Ilustrativen primer delovanja obravnavanega LFSR je prikazan na sl. 90.

riž. 90.

Kot je razvidno iz sl. 90 bo izpolnjevanje registra šlo skozi težo 15 od 16 možnih stanj (prej smo ugotovili, da šestnajstega stanja, ko je LFSR 0000, ni mogoče upoštevati). Po tem bo polnjenje registra spet enako začetni vrednosti 0101, generiranje bitnega zaporedja pa se bo začelo ponavljati. Izhodno zaporedje registra bo niz najmanj pomembnih bitov (do vodoravne črte na sliki 90): 101011110001001. Velikost bitnega zaporedja, preden se ponovi, se imenuje točka. Za zagotovitev največje dobe določenega LFSR (tj., da register gre skozi vsa možna notranja stanja), mora biti polinom, ki določa delovanje registra, primitiven po modulu 2. Tako kot pri velikih praštevilih ni načina, da bi ustvariti takšne polinome. Vzamemo lahko samo polinom in preverimo, ali je nereducibilen po modulu 2 ali ne. V splošnem primeru je primitivni polinom stopnje n tak nereducibilen polinom, ki je delilec x 2 "+1, vendar ni delilec xd +1 za vse d, ki so delitelji 2 "-1. B. Schneier ponuja tabelo nekaterih polinomov, ki so nereducljivi po modulu 2.

Če povzamemo znanje, pridobljeno kot rezultat obravnave primera delovanja LFSR (slika 90), lahko rečemo, da je n-bitni LFSR lahko v enem od notranjih stanj 2”-1. Teoretično lahko tak register generira psevdonaključno zaporedje s periodo 2 n -1 bitov. Takšni registri se imenujejo registri LFSR z največjo dobo. Nastali izhod se imenuje t-zaporedje.

Ministrstvo za izobraževanje in znanost

RUSKA DRŽAVNA SOCIALNA UNIVERZA

FAKULTETA ZA INFORMACIJSKE TEHNOLOGIJE

ODDELEK ZA VARSTVO INFORMACIJ

Kriptografske metode in sredstva za zagotavljanje informacijske varnosti

Tečajno delo

"R premični registri z linearnimi povratnimi informacijami kot generatorji psevdo naključnih števil"

Dokončano:

Študent 3. letnika

Skupina KZOI-D-3

Larionov I.P.

Preverjeno:

Izr. Baranova E.K.

Moskva 2011
VSEBINA

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

Teoretične osnove dela…………………………………………4
1. Splošne informacije o premičnih registrih povratnih informacij …………..4
  1. O tokovnih šifrah, ki temeljijo na RgCsLOS………………….………10
  2. O linearni kompleksnosti ustvarjenega psevdonaključnega zaporedja PgCsLOS……………………………………………….……12
  3. O korelacijski neodvisnosti generiranega zaporedja psevdonaključnih števil PrCsLOS………..….13
  4. O drugih metodah odpiranja ustvarjenega zaporedja psevdonaključnih števil RgCsLOS……………………………………..14
Programska implementacija RgCsLOS kot generatorja psevdo-naključnih sekvenc….…………………………….15
1. Splošna shema algoritma………………………………………………...15
2. Opis programskih modulov in vmesnika.……………….16
3. Uporabniški priročnik…………………………………………20

Zaključek ………………………………………………………………22

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

Priloga A ….………………………………………………………..24

UVOD

Namen tega dela je razviti programsko aplikacijo, ki implementira delovanje generatorja psevdo naključnih števil na podlagi premičnih registrov s povratnimi informacijami. Razvoj te aplikacije z grafičnim vmesnikom poteka v jeziku C++ za operacijski sistem Windows.

Z razvojem kriptografije v 20. stoletju so se kriptografi soočili z nalogo izdelave šifrirnih naprav in strojev, ki bi lahko hitro in zanesljivo šifrirali in dešifrirali sporočila. Simetrični šifrirni sistemi, ki so bili takrat že odprti, so izpolnjevali to zahtevo, vendar je bila njihova šibka točka močna odvisnost od ključa in njegove tajnosti. Najprimernejši razred šifr, ki bi jih lahko uporabili v ta namen, so igralne šifre. Težava je nastala pri ustvarjanju gama, ki je ni bilo mogoče zaznati, ko je bilo sporočilo dešifrirano. Teoretično je bilo to mogoče, če bi bila gama vsakič naključna in se sčasoma spreminjala. Vendar pa bi bilo pri uporabi popolnoma naključne spreminjajoče se game težko zagotoviti zanesljivo šifriranje-dešifriranje sporočila. Kriptografi so prevzeli nalogo reševanja tega problema, katerega namen je bil najti algoritem, ki izvaja generiranje naključnega razpona po določenem pravilu, tako zaporedje naj vsebuje ničle in enote na "domnevno" naključnih pozicijah, število enic in nič mora biti približno enako. To naključno zaporedje se imenujepsevdo-naključnosaj je bil ustvarjen po določenem pravilu in ne naključno.

Rešitev je bila kmalu najdena. Študija lastnosti premičnih registrov je omogočila ugotovitev, da so premični registri s povratnimi informacijami sposobni generirati psevdonaključna zaporedja, ki so zaradi svoje notranje strukture dovolj odporna na dekodiranje.

1.Teoretični temelji dela

1.1 Splošne informacije o premičnih registrih z linearno povratno informacijo

Zaporedja premičnih registrov se uporabljajo tako v kriptografiji kot v teoriji kodiranja. Njihova teorija je dobro razvita, tokovne šifre, ki temeljijo na premičnem registru, so bile delovni konj vojaške kriptografije že dolgo pred pojavom elektronike.

Pomikalni register s povratnimi informacijami (v nadaljevanju PgCsOS) je sestavljen iz dveh delov: premičnega registra in povratne funkcije.Spremični register je zaporedje bitov. Število bitov je določenodolžina premičnega registra, če je dolžina n bitov, se register pokličen-bitni premični register. Kadar koli je treba ekstrahirati bit, se vsi bit premičnega registra premaknejo v desno za 1 položaj. Novi skrajni levi bit je funkcija vseh drugih bitov v registru. Izhod premičnega registra je en, običajno najmanj pomemben bit.Obdobje menjalnega registraje dolžina nastalega zaporedja, preden se začne ponavljati.

Slika premični register povratne informacije

Premikalni registri so hitro našli uporabo v tokovnih šifrah, saj so bili enostavno implementirani z uporabo digitalne strojne opreme. Leta 1965 je Ernst Selmer, glavni kriptograf norveške vlade, razvil teorijo zaporedja premičnega registra. Solomon Golomb, matematik NSA, je napisal knjigo, v kateri je opisal nekatere njegove rezultate in rezultate Selmerja. Najpreprostejša vrsta premičnega registra s povratnimi informacijami jepremični register linearne povratne informacije ( premični register linearne povratne informacije, v nadaljevanju LFSR ali RgCsLOS) . Povratna informacija takih registrov je preprosto XOR (seštevanje po modulu dveh) nekaterih bitov registra, seznam teh bitov se imenuje zaporedje odpiranja. Včasih se tak register imenuje Fibonaccijeva konfiguracija. Zaradi preprostosti zaporedja povratnih informacij je mogoče za analizo PgCsLOC uporabiti precej razvito matematično teorijo. Z analizo nastalih izhodnih zaporedij lahko preverite, ali so ta zaporedja dovolj naključna, da so varna. Spremični registri se v kriptografiji uporabljajo pogosteje kot drugi premični registri.

Slika PgCsLOS Fibonacci

Na splošno je n -bit PrCsLOS je lahko v enem od N=2n -1 notranja stanja. To pomeni, da lahko teoretično tak register ustvari psevdonaključno zaporedje s periodo T=2 n -1 bit. (Število notranjih stanj in obdobje sta enaka N=Tmax=2n -1, ker polnjenje PrCsLOC z ničlami povzroči, da premični register izpiše neskončno zaporedje ničel, kar je popolnoma neuporabno). Samo z določenimi zaporedji dotikov bo PrCsLOS ciklično šel skozi vsa 2 n -1 notranjih stanj, kot so RgCsLOSRgSsLOS z največjo dobo. Nastali rezultat se imenujeM-zaporedje.

Primer . Spodnja slika prikazuje 4-bitni PrCsLOS s pipo iz prvega in četrtega bita. Če je inicializiran z vrednostjo 1111, bo pred ponovitvijo registra prevzel naslednja notranja stanja:

Preklopna številka (notranje stanje)	Status registracije	izhodni bit
Preklopna številka (notranje stanje)		izhodni bit
Začetna vrednost














15 (vrnitev v začetno stanje)
16 (ponavljajoča se stanja)

Izhodno zaporedje bo niz najmanj pomembnih bitov: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 s obdobjem T=15, skupno število možnih notranjih stanj (razen nič), N=2 4 -1=16-1=15= Tmax , zato je izhodno zaporedje M - zaporedje.

Da bi imel določen PgCsLOS največjo dobo, mora biti polinom, sestavljen iz zaporedja pip in konstante 1, primitiven po modulu 2. Polinom je predstavljen kot vsota potenk, na primer polinom stopnje n izgleda takole:

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 , kjer je a i =(0, 1 ) za i=1…n, axi – označuje bit .

Stopnja polinoma je dolžina premičnega registra. Primitivni polinom stopnje n je nereducibilen polinom, ki je delilec x 2n−1 +1, vendar ni delilec x d +1 za vse d, ki so delitelji 2 n -ena. Ustrezno matematično teorijo lahko najdete v .

Na splošno ni enostavnega načina za generiranje primitivnih polinomov dane stopnje po modulu 2. Najlažji način je, da naključno izberete polinom in preverite, ali je primitiven. To ni enostavno in je nekako podobno preverjanju, ali naključno izbrano število ni pra - vendar lahko to težavo rešijo številni matematični programski paketi.

Spodaj so podani nekateri, a zagotovo ne vsi polinomi različnih stopenj, primitivnih modulov 2. Na primer vnos

(32, 7, 5, 3, 2, 1, 0) pomeni, da je naslednji polinom primitiven po modulu 2: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

To je mogoče zlahka posplošiti na PrCcLOC z največjim obdobjem. Prva številka je dolžina PrCsLOS. Zadnja številka je vedno 0 in jo je mogoče izpustiti. Vse številke razen 0 določajo zaporedje dotikov, ki se šteje od levega roba premičnega registra. To pomeni, da izrazi polinoma z nižjo stopnjo ustrezajo položajem bližje desnemu robu registra.

Če nadaljujemo s primerom, pisanje (32, 7, 5, 3, 2, 1, 0) pomeni, da se za dani 32-bitni premični register nov bit generira z XOR 32., sedmega, petega, tretjega, drugega , in prvi biti , bo dobljeni RgCsLOS imel največjo dolžino, ki se giblje, dokler se ne ponovi po 2 32 -1 vrednosti.

Slika 4 32-bitni PrCsLOS z največjo dolžino

Razmislite o programski kodi PgCsLOS, v kateri je zaporedje pip označen s polinomom (32, 7, 5, 3, 2, 1, 0). V jeziku C izgleda takole:

int LFSR()(

statični nepodpisani dolgi ShiftRegister = 1;

/* Vse razen 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

vrni ShiftRegister & 0 x 00000001;)

Če je premični register daljši od računalniške besede, postane koda bolj zapletena, vendar ne veliko. V aplikaciji B podana je tabela nekaterih primitivnih polinomov po modulu 2, kasneje jo bomo uporabili za identifikacijo nekaterih lastnosti teh polinomov, pa tudi v programski implementaciji za nastavitev zaporedja topov.

Upoštevati je treba, da imajo vsi elementi tabele liho število koeficientov. Tako dolga tabela je predvidena za nadaljnje delo s PrCfLOC, saj se PrCfLOC pogosto uporablja za kriptografijo s tokovnimi šiframi in v generatorjih psevdonaključnih števil. V našem primeru lahko uporabimo polinome z najvišjo stopnjo največ sedem.

Če je p(x) primitiven, potem je tudi x n p(1/x), tako da vsak element tabele dejansko definira dva primitivna polinoma. Na primer, če je (a, b, 0) primitivno, potem je tudi (a, a-b, 0). Če je (a, b, c, d, 0) primitivno, potem je tudi (a, a-d, a-c, a-b, 0). matematično:

če je x primitiven a+xb +1, potem je primitivno in x a+x a-b+1,

če je x primitiven a + x b + x c + x d +1, potem je primitivno in x a + x a-d + x a-c + x a-b +1. Primitivne trinome je najhitreje implementirati programsko, saj morate za generiranje novega bita XOR samo dva bita premikalnega registra (ničelni člen se ne upošteva, t.j. x 0 =1, glej zgornji primer). Dejansko so vsi polinomi povratnih informacij, podani v tabeli, redki, torej imajo malo koeficientov. Redkost je vedno vir slabosti, kar je včasih dovolj za odpiranje algoritma. Za kriptografske algoritme je veliko bolje uporabiti goste primitivne polinome, tiste, ki imajo veliko koeficientov. Z uporabo gostih polinomov, zlasti kot del ključa, lahko uporabimo veliko krajši PrCcLOC.

Ustvarjanje gostih primitivnih polinomov po modulu 2 ni enostavno. V splošnem primeru, da ustvarimo primitivne polinome stopnje k, moramo poznati faktorizacijo števila 2 k-1.

PgCsLOS so sami po sebi dobri generatorji psevdonaključnih zaporedij, vendar imajo nekatere nezaželene nenaključne (deterministične) lastnosti. Zaporedni biti so linearni, zaradi česar so neuporabni za šifriranje. Za PgCsLOS dolžine n je notranje stanje prejšnjih n izhodnih bitov generatorja. Tudi če je shema povratne informacije skrivnost, jo je mogoče določiti iz 2n izhodnih bitov generatorja z uporabo visoko učinkovitega algoritma Berlekamp-Massey.

Poleg tega so velika naključna števila, ustvarjena z uporabo zaporednih bitov tega zaporedja, zelo povezana in za nekatere vrste aplikacij sploh niso naključna. Kljub temu se PrCsLOS pogosto uporablja za ustvarjanje šifrirnih algoritmov kot komponent sistemov in šifrirnih algoritmov.

1.2 O tokovnih šifrah, ki temeljijo na RgCsLOS

Osnovni pristop k oblikovanju generatorja ključnega toka, ki temelji na PrCsLOS, je preprost. Najprej se vzame en ali več PrCsLOS, običajno z različnimi dolžinami in različnimi povratnimi polinomi. (Če so dolžine enakovredne in so vsi polinomi povratne informacije primitivni, bo imel generirani generator največjo dolžino.) Ključ je začetno stanje registrov PrCcLOC. Vsakič, ko je potreben nov bit, malo premaknite registre PrCsLOS (včasih se imenuje taktiranje). Izhodni bit je funkcija, po možnosti nelinearna, nekaterih bitov registrov PrCsLOC. Ta funkcija se imenuje kombinirana funkcija, generator kot celota pa kombinacijski generator. (Če je izhodni bit funkcija enega samega PgCsLOS, se oscilator imenuje filtrirni oscilator.) Velik del teorije za tovrstnimi napravami sta razvila Selmer in Neal Zierler. Lahko uvedete številne zaplete. V nekaterih generatorjih se za različne PgCsLOS uporabljajo različne taktne frekvence, včasih je frekvenca enega generatorja odvisna od izhoda drugega. Vse to so elektronske različice idej za šifrirne stroje pred drugo svetovno vojno, imenovane oscilatorji, ki jih krmili uro ( generatorji s krmiljenjem ure ). Krmiljenje ure je lahko usmerjeno naprej, kjer izhod enega PgSsLOS nadzoruje takt drugega PgSsLOS, ali zaprto zanko, kjer izhod enega PgSsLOS nadzoruje svojo uro. Čeprav so vsi ti generatorji, vsaj teoretično, občutljivi na napade gnezdenja in verjetne korelacije, so mnogi od njih še vedno varni.

Ian Cassells, nekdanji predsednik čiste matematike v Cambridgeu in kriptoanalitik v Bletchly Parku, je dejal, da je "kriptografija mešanica matematike in zmede in brez zmede se lahko matematika uporabi proti tebi." Mislil je, da so v tokovnih šifrah določene matematične strukture, kot je PrCcLOC, potrebne za zagotavljanje največje dolžine in drugih lastnosti, vendar je treba uvesti nekaj zapletenega nelinearnega nereda, da se prepreči, da bi nekdo dobil vsebino registra in razpočil algoritem. Ta nasvet velja tudi za blokovne algoritme.

Večina resničnih tokovnih šifer temelji na PrCsLOS. Tudi v prvih dneh elektronike jih je bilo enostavno zgraditi. Pomični register ni nič drugega kot niz bitov, zaporedje povratnih informacij pa je niz vrat XOR. Tudi pri uporabi VLSI pretočna šifra, ki temelji na PrCsLOS, zagotavlja znatno varnost s pomočjo več logičnih vrat. Težava s PgCsLOS je, da je njihova implementacija programske opreme zelo neučinkovita. Izogibati se morate redkim povratnim polinomom – zaradi njih so korelacijski napadi lažji – in polinomi z gosto povratno informacijo so neučinkoviti.

Ta veja kriptografije hitro raste in je pod budnim vladnim nadzorom NSA . Večina razvoja je tajnih – številni vojaški sistemi šifriranja, ki se danes uporabljajo, temeljijo na PrCsLOS. Dejansko ima večina računalnikov Cray (Cray 1, Cray X-MP, Cray Y-MP) zelo zanimivo navodilo, ki se običajno imenuje "število prebivalstva". Šteje število 1 v registru in se lahko uporablja tako za učinkovito izračun Hammingove razdalje med dvema binarnima besedama kot za izvajanje vektorizirane različice PrCcLOC. To navodilo velja za kanonično navodilo NSA in se pojavlja v skoraj vseh računalniških pogodbah.

Po drugi strani pa je bilo vdrto presenetljivo veliko število navidez zapletenih generatorjev premičnih registrov. In seveda je število takšnih generatorjev, ki so jih vdrle vojaške kriptoanalitične institucije, kot je NSA, še večje.

1.3 O linearni kompleksnosti generiranega zaporedja psevdonaključnih števil PrCsLOS

Tokovne šifre je pogosto lažje razčleniti kot blokovne šifre. Na primer, pomemben parameter, ki se uporablja za analizo generatorjev, ki temeljijo na PgCsLOC, je linearna kompleksnost ali linearni interval. Definiran je kot dolžina n najkrajšega PrCsLOS, ki lahko simulira izhod generatorja. Vsako zaporedje, ki ga ustvari končni avtomat nad končnim poljem, ima končno linearno kompleksnost. Linearna kompleksnost je pomembna, ker lahko s preprostim algoritmom, imenovanim Berlekamp-Masseyjev algoritem, določimo ta PrCcLOC tako, da preučimo samo 2n bitov toka ključev. Če ponovno ustvarite želeni PrCsLOS, zlomite tokovno šifro.

To idejo je mogoče razširiti s polj na obroče in na primere, ko se izhodno zaporedje obravnava kot števila v polju z liho karakteristiko. Nadaljnja širitev vodi do uvedbe koncepta linearnega kompleksnega profila, ki določa linearno kompleksnost zaporedja, ko se podaljšuje. Obstajajo tudi koncepti sferične in kvadratne kompleksnosti. Vsekakor se je treba spomniti, da visoka linearna kompleksnost ne zagotavlja nujno varnosti generatorja, nizka linearna kompleksnost pa kaže na nezadostno varnost generatorja.

1.4 O korelacijski neodvisnosti generiranega zaporedja psevdonaključnih števil PrCsLOS

Kriptografi poskušajo doseči visoko linearno kompleksnost z združevanjem rezultatov nekaterih izhodnih zaporedij na nelinearen način. Nevarnost je, da je eno ali več notranjih izhodnih zaporedij – pogosto le izhode posameznih PrCsLOC – mogoče povezati s skupnim tokom ključev in jih odkriti z uporabo linearne algebre. Takšen obračun se pogosto imenuje korelacijski obračun ali obračun deli in obvladuj. Thomas Siegenthaler je pokazal, da je korelacijsko neodvisnost mogoče natančno definirati in da obstaja kompromis med korelacijsko neodvisnostjo in linearno kompleksnostjo.

Glavna ideja korelacijskega odpiranja je najti neko korelacijo med izhodom generatorja in izhodom ene od njegovih komponent. Nato lahko z opazovanjem izhodnega zaporedja dobimo informacije o tem vmesnem izhodu. S temi informacijami in drugimi korelacijami se lahko zbirajo drugi vmesni izhodi, dokler generator ne vdre.

Korelacijski napadi in njihove različice, kot so hitri korelacijski napadi, so bili uspešno uporabljeni proti številnim generatorjem tokov ključev, ki temeljijo na PgCsLOC, ki ponujajo kompromis med računsko kompleksnostjo in učinkovitostjo.

1.5 O drugih metodah odpiranja ustvarjenega zaporedja psevdonaključnih števil PgCsLOS

Obstajajo tudi drugi načini za prekinitev generatorjev toka ključev. Preizkus linearne doslednosti poskuša najti neko podmnožico šifrirnega ključa z uporabo matrične tehnike. Obstaja tudi napad na doslednost srečanja na sredini na pravilnost. Algoritem linearnega sindroma temelji na sposobnosti zapisovanja fragmenta izhodnega zaporedja kot linearne enačbe. Obstaja napad najboljšega afinskega približevanja in napad izpeljanega zaporedja. Metode diferencialne in linearne kriptoanalize se lahko uporabijo tudi za pretočne šifre.

2. Opis programske izvedbe PrCsLOS kot generatorja psevdo-naključnih sekvenc

2.1 Splošna shema algoritma

2.2 Opis programskih modulov in vmesnika

Slika 3 spodaj prikazuje okno programa.

Slika Programski vmesnik

Meni ima naslednje funkcije:

Datoteka->Shrani poročilo

Ta funkcija generira datoteko poročila, v katero se zapiše začetno stanje PrCsLOS, zaporedje pip, obdobje prejetega psevdonaključnega zaporedja bitov, samo zaporedje in tabela stanja. Če je bila datoteka uspešno shranjena, se prikaže sporočilo o uspešnem shranjevanju (slika 4). Priporočena razširitev datoteke za poročilo je *. txt.

Risanje

Datoteka->Izhod

Ta funkcija zagotavlja, da je aplikacija zaprta.

Nastavite ubežno zaporedje

Ta funkcija ustvari zaporedje dotikov z branjem vrednosti iz celic, ki jih je uporabnik označil na obrazcu zaslona. Po tem obvesti uporabnika o izdelavi zaporedja dotikov (slika 5). Zaporedje dotikov določa, kateri natikači premičnega registra bodo prejeli povratne informacije. XOR za oblikovanje offset bit. Privzeto je povratna informacija od prvega sprožilca vedno vklopljena, v odsotnosti drugih povezav se izvede premik v levo s spremembo najmanjšega bita na položaj najpomembnejšega.

Risanje

Nastavite začetno vrednost

Ta funkcija prebere začetno vrednost registra, ki jo je vnesel uporabnik iz okna Uredi 1 in preveri vneseno vrednost glede na podane pogoje: vneseni niz ni prazen (slika 6), vneseni niz ima dolžino osem (8bit=1bajt, slika 7), vneseni niz vsebuje samo ničle in/ali enot (slika 8), vneseni niz ni nič (slika 9). V nasprotnem primeru se prikažejo sporočila o napakah, ki jih mora uporabnik popraviti in znova pritisniti gumb. V primeru uspešnega preverjanja se začetna vrednost vpiše v tabelo stanja v vrstico "Začetno" in izdano obvestilo (slika 10).

Risanje

Izvedite premik registra

Ta funkcija posnema delovanje premičnega registra. Zaporedno naredi 256 premikov, vsak premik generira izhodni bit psevdo-naključnega zaporedja in novo stanje registra. Takoj, ko je stanje registra enako začetnemu, se obdobje izračuna in prikaže v polju beležka 1 je prejel psevdonaključno zaporedje.

Pomoč-> O

Ta funkcija prikazuje kratek opis programa in navodila (slika 11).

Risanje

Pomoč-> O avtorju

Ta funkcija prikazuje podatke o avtorju programa (slika 12).

Risanje

2.3 Uporabniški priročnik

Najprej nastavite začetno stanje registra. Vsebovati mora osem binarnih znakov. V nasprotnem primeru se prikaže sporočilo o napaki in vneseno vrednost boste morali popraviti. Pritisnite točko menija "Nastavi začetno vrednost".
Nato potrdite potrditvena polja za povratne informacije o registraciji (Tap Sequence). Pritisnite točko menija "Nastavi zaporedje dotikov".
Nato kliknite postavko menija "Registriraj Shift". Preden to storite, se prepričajte, da ste izvedli koraka 1 in 2, sicer bo prišlo do napake v programski opremi.
Ko prejmete rezultate, jih lahko shranite s klikom na točko menija "Datoteka->Shrani poročilo". Preden to storite, se prepričajte, da ste izvedli korake 1-3, sicer bo prišlo do napake v programski opremi.
Če želite dobiti pomoč, kliknite menijske elemente "Datoteka->Vizitka", "Datoteka->O avtorju".
Če želite videti delovanje registra z drugimi vrednostmi zaporedja dotikov in začetnim stanjem registra, zaporedno ponovite korake v korakih 1-3, pri čemer vnesete druge parametre.

ZAKLJUČEK

V tem prispevku so bili RgCsLOS obravnavani kot generatorji psevdo naključnih števil. Program lahko služi kot vizualna predstavitev principov delovanja premičnih registrov z vklopljeno linearno povratno informacijo XOR . Na njem lahko preučite princip oblikovanja psevdonaključnega zaporedja bitov, razmerje med začetno vrednostjo registra in vrednostjo psevdonaključnega zaporedja, zaporedjem odpiranja in piko. Nastala psevdonaključna gama se lahko uporabi v drugi programski aplikaciji (na primer v programski izvedbi gama šifre).

Do danes se ti registri ne uporabljajo kot neodvisni generatorji psevdo-naključnih števil, ampak so del bolj zapletenih naprav. Vendar so prav oni odprli nove smeri v matematiki (iskanje primitivnih polinomov v končnih poljih, matematične metode za razbijanje generatorjev psevdonaključnih števil). Brez poznavanja principov delovanja generatorjev na RgCsLOS je nemogoče razumeti delovanje kompleksnejših naprav. Zaradi enostavne izvedbe strojne opreme se široko uporabljajo v tehnologiji. Raziskave PrCsOS so privedle do pojava novih šifr - blokovnih in tokovnih - na podlagi teh vrst registrov (drsni permutacijski šifrir, DES itd.; EDS, hash funkcije).

Na splošno so raziskave na tem področju resno spodbudile razvoj kriptografije in kriptoanalitikov, računalnikov in naprav ter omogočile izvajanje številnih drugih uporabnih funkcij (na primer popravljanje cikličnih kod).

BIBLIOGRAFIJA

Schneier Bruce. Uporabna kriptografija. Protokoli, algoritmi, izvorna besedila v jeziku C. - M .: Triumf, 2002
Babash A.V. Kriptografski in avtomatsko-teoretični vidiki sodobne informacijske varnosti. Zvezek 1 - M .: Izd. Center EAOI, 2009. - 414 str.
E.S. Selmer. Monografija: "Linearna rekurzija v končnem polju". Univerza v Bergnu, Norveška, 1966.
N. Zierler in J. Brillhart. "On Primitive Trinomials Modulo 2", Journal of Information and Control, letnik 13, št. 6 december 1968, str. 541-544.
K.Kh. Meyer in W. L. Tuchman. "Psevdonaključne kode je mogoče razbiti", revija Electronic Design, št. 23. novembra 1972.
J. L. Massey. "Posplošitev premičnih registrov in dekodiranje kode Bose-Chowdhury-Hokvingham", IEEE Transactions on Information Theory, v. IT-15, n . 1. januar 1969, str. 122-127.
S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (ponatis pri Aigean Park Press, 1982).

Priloga A

Tabela nekaterih primitivnih polinomov 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)

Vnos začetnega stanja (IS)

potrditev vnosa

Izdaja sporočila o napaki

Nastavitev zaporedja dotikov

Zapis IP v tabeli stanja

Zapis i -th register stanja in izhodni bit v tabelo stanja

IS==Trenutno stanje

Shranjevanje rezultatov

Psevdo-naključni izhod zaporedja

Izhod

kosilo

V pomičnem registru z linearno povratno informacijo se razlikujeta dva dela (modula): sam pomični register in vezje (ali podprogram), ki izračuna vrednost vstavljenega bita. Register je sestavljen iz funkcijskih celic (ali bitov strojne besede ali več besed), od katerih vsaka shrani trenutno stanje enega bita. Število celic se imenuje dolžina registra. Biti (celice) so običajno oštevilčeni s številkami, od katerih je vsaka sposobna shraniti bit, izračunani bit pa se potisne v celico, naslednji generirani bit pa se izvleče iz celice. Izračun vstavljenega bita se običajno izvede pred premikom registra in šele po premiku se vrednost izračunanega bita postavi v celico.

Obdobje premičnega registra je najmanjša dolžina nastalega zaporedja, preden se začne ponavljati. Ker ima register bitnih celic samo različna stanja, ki niso nič, potem obdobje registra načeloma ne sme presegati tega števila. Če je obdobje registra enako tej številki, se tak register imenuje register največje dobe.

Za LFSR je povratna funkcija linearna logična funkcija stanj vseh ali nekaterih bitov registra. Na primer, vsota po modulu dva ali njen logični inverz je linearna logična funkcija (operacija XOR, označena kot v formulah) in se najpogosteje uporablja v takšnih registrih.

V tem primeru se običajno kličejo tisti biti, ki so spremenljivke povratne funkcije ovinki.

Nadzor registra v izvedbah strojne opreme se izvaja z uporabo impulza premika (sicer imenovan ura oz sinhronizacijski impulz) v vse celice, v programski opremi - z izvajanjem programskega cikla, vključno z izračunom povratne funkcije in bitnim premikom v besedi.

Med vsako uro se izvedejo naslednje operacije:

Tako se logična operacija XOR (izključno OR) vzame kot povratna funkcija, to je:

Lastnosti primitivnih polinomov

Lastnosti

Lastnosti zaporedja, ki ga ustvari LFSR, so tesno povezane z lastnostmi povezanega polinoma. Njegovi koeficienti, ki niso nič, se imenujejo ovinki, kot tudi ustrezne celice registra, ki zagotavljajo vrednosti argumentov povratne funkcije.

Linearna kompleksnost

Linearna kompleksnost binarnega zaporedja je ena najpomembnejših značilnosti delovanja LFSR. Naj uvedemo naslednji zapis:

Opredelitev

Linearna kompleksnost neskončnega binarnega zaporedja se imenuje število, ki je opredeljeno na naslednji način:

Linearna kompleksnost končnega binarnega zaporedja se imenuje število, ki je enako dolžini najkrajšega LFSR, ki generira zaporedje, ki ima kot prvi člen .

Lastnosti linearne kompleksnosti

Pustiti in biti binarna zaporedja. Nato:

Korelacijska neodvisnost

Da bi dosegli visoko linearno kompleksnost, kriptografi poskušajo nelinearno združiti rezultate več izhodnih zaporedij. V tem primeru je nevarnost, da se eno ali več izhodnih zaporedij (pogosto celo izhodi posameznih LFSR) lahko poveže s skupnim tokom ključev in odkrije z uporabo linearne algebre. Vdiranje, ki temelji na takšni ranljivosti, se imenuje korelacijsko obdukcijo. Thomas Siegenthaler je pokazal, da je korelacijsko neodvisnost mogoče natančno definirati in da obstaja kompromis med korelacijsko neodvisnostjo in linearno kompleksnostjo.

Glavna ideja tega vdora je najti neko korelacijo med izhodom generatorja in izhodom enega od njegovih sestavnih delov. Nato lahko z opazovanjem izhodnega zaporedja pridobimo informacije o tem vmesnem izhodu. S temi informacijami in drugimi korelacijami je mogoče zbrati podatke o drugih vmesnih izhodih, dokler generator ne vdre.

Korelacijski napadi ali variacije, kot so hitri korelacijski napadi, so bili uspešno uporabljeni proti številnim generatorjem tokov ključev, ki temeljijo na linearnem povratnem registru premikanja, ki vključujejo kompromis med računsko kompleksnostjo in učinkovitostjo.

Primer

Za LFSR s pripadajočim polinomom ima ustvarjeno zaporedje obliko . Recimo, da je pred začetkom procesa zaporedje vpisano v register, potem bo obdobje ustvarjenega bitnega toka enako 7 z naslednjim zaporedjem:

Številka koraka	Država	Bit ustvarjen
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Ker se je notranje stanje na sedmem koraku vrnilo v prvotno stanje, se bo od naslednjega koraka ponovilo. Z drugimi besedami, izkazalo se je, da je obdobje zaporedja enako 7, kar se je zgodilo zaradi primitivnosti polinoma.

Algoritmi za generiranje primitivnih polinomov

Pripravljene mize

Izračunavanje primitivnosti polinoma je precej zapleten matematični problem. Zato obstajajo že pripravljene tabele, ki navajajo število zaporedij pip, ki zagotavljajo maksimalno obdobje generatorja. Na primer, za 32-bitni premični register obstaja zaporedje . To pomeni, da je za generiranje novega bita potrebno sešteti 31., 30., 29., 27., 25. in 0. bite s funkcijo XOR. Koda za tak LFSR v jeziku C je naslednja:

Int LFSR (void ) ( statično nepodpisano dolgo S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); vrnitev S & 1 ; )

Programske izvedbe generatorjev RSLOS so precej počasne in delujejo hitreje, če so napisane v asemblerju in ne v C. Ena od rešitev je uporaba 16 RLLS vzporedno (ali 32, odvisno od dolžine besede v arhitekturi določenega računalnika). V takšni shemi se uporablja niz besed, katerih velikost je enaka dolžini LFSR, vsak bit besede matrike pa se nanaša na njegov LFSR. Pod pogojem, da se uporabljajo enake zaporedne številke pip, lahko to povzroči opazno povečanje zmogljivosti. [potrebujete vzorec kode] (Glej: bitslice).

Galois konfiguracija

Galoisova konfiguracija linearnega premičnega registra povratne informacije

Shemo povratnih informacij je mogoče tudi spremeniti. V tem primeru generator ne bo imel večje kriptografske moči, vendar ga bo lažje programsko implementirati. Namesto da bi uporabili bite zaporedja dotikov za generiranje novega skrajnega levega bita, XOR vsak bit zaporedja dotikov z izhodom generatorja in ga nadomestite z rezultatom tega dejanja, potem rezultat generatorja postane nov skrajni levi bit . V jeziku C izgleda takole:

Int LFSR (void) (statična nepodpisana dolga Q = 1; Q = (Q>> 1) ^ (Q& 1 ? 0x80000057 : 0) ; vrni Q & 1 ;)

Prednost je, da se vsi XOR izvajajo v eni operaciji.

je mogoče dokazati, da Fibonaccijeva konfiguracija, navedena prva, in Galoisova konfiguracija, podana tukaj, dajeta enaka zaporedja (dolžine 2 32 −1), vendar sta zamaknjeni v fazi drug od drugega
zanka fiksnega števila klicev funkcije LFSR v konfiguraciji Galois je približno dvakrat hitrejša kot v konfiguraciji Fibonacci (prevajalnik MS VS 2010 na Intel Core i5)
upoštevajte, da je v Galoisovi konfiguraciji vrstni red bitov v povratni besedi obrnjen v primerjavi s Fibonaccijevo konfiguracijo

Primeri generatorjev

stop-go generatorji

Izmenični generator Stop-and-Go

Ta oscilator uporablja izhod enega LFSR za nadzor taktne frekvence drugega LFSR. Izhod ure RSLOS-2 je nadzorovan z izhodom RSLOS-1, tako da lahko RSLOS-2 spremeni svoje stanje v času t le, če je bil izhod RSDOS-1 v času t-1 enak enoti. Toda ta shema se ni uprla odprtju korelacije.

Zato je bil predlagan izboljšan generator, ki temelji na isti ideji. Imenuje se prepleteni generator stop-and-go. Uporablja tri LFSR različnih dolžin. LFSR-2 je takt, ko je izhod LFSR-1 enak eni, in LFSR-3, ko je izhod LFSR-1 enak nič. Izhod generatorja je vsota modula 2 RSLOS-2 in RSLOS-3. Ta generator ima veliko obdobje in veliko linearno kompleksnost. Njegovi avtorji so pokazali tudi metodo za korelacijsko odpiranje RLOS-1, vendar to ne oslabi močno generatorja.

Gollmannova kaskada

Gollmann Cascade je izboljšana različica generatorja stop-go. Sestavljen je iz zaporedja LFSR, pri čemer je čas vsakega od njih nadzorovan s prejšnjim LFSR. Če je izhod LFSR-1 v času t 1, je LFSR-2 takt. Če je izhod LFSR-2 v času t 1, je LFSR-3 takt itd. Izhod zadnjega LFSR je izhod generatorja. Če je dolžina vseh LFSR enaka in je enaka n, je linearna kompleksnost sistema k LFSR .

Ta ideja je preprosta in se lahko uporablja za generiranje zaporedij z velikimi periodami, velikimi linearnimi kompleksnostmi in dobrimi statističnimi lastnostmi. Toda na žalost so dovzetni za odpiranje, ki se imenuje "zaklepanje" (zaklepanje). Za večjo stabilnost je priporočljivo uporabiti k vsaj 15. Poleg tega je bolje uporabiti krajši LFSR kot manj dolg LFSR.

generator praga

Ta generator poskuša zaobiti varnostne težave prejšnjih generatorjev z uporabo spremenljivega števila premičnih registrov. Teoretično se pri uporabi večjega števila premičnih registrov kompleksnost šifre poveča, kar je bilo storjeno v tem generatorju.

Ta generator je sestavljen iz velikega števila premičnih registrov, katerih izhodi se napajajo v majorizacijsko funkcijo. Če je število enot na izhodih registrov več kot polovico, potem generator proizvede enoto. Če je število ničel na izhodih več kot polovico, potem generator proizvede ničlo. Da bi bila primerjava števila nič in enic mogoča, mora biti število premičnih registrov liho. Dolžine vseh registrov morajo biti relativno preproste, polinomi povratne informacije pa morajo biti primitivni, tako da je obdobje generiranega zaporedja največje.

V primeru treh premičnih registrov je generator lahko predstavljen kot:

Ta generator je podoben generatorju Geff, le da ima generator praga bolj linearno kompleksnost. Njegova linearna kompleksnost je:

kjer so , , dolžine prvega, drugega in tretjega premičnega registra.

Njegova pomanjkljivost je, da vsak izhodni bit daje nekaj informacij o stanju premičnega registra. Natančneje 0,189 bitov. Zato se ta generator morda ne bo upiral odprtju korelacije.

Druge vrste

Samoredčenje

Samoupadajoči generatorji se imenujejo generatorji, ki nadzorujejo svojo frekvenco. Predlagani sta bili dve vrsti takšnih generatorjev. Prvi je sestavljen iz linearnega premičnega registra s povratnimi informacijami in nekega vezja, ki uri ta register, odvisno od tega, kakšne so izhodne vrednosti premičnega registra. Če je izhod LFSR enak eni, se register udri d-krat. Če je izhod nič, se register k-krat udri. Drugi ima skoraj enako zasnovo, vendar je nekoliko spremenjen: v taktnem vezju se kot preverjanje 0 ali 1 ne sprejema sam izhodni signal, temveč XOR določenih bitov premičnega registra z linearno povratno informacijo. Žal tovrstni generator ni varen.

Večstopenjski oscilator z notranjim produktom

Ta generator uporablja dva premična registra z linearno povratno informacijo z različnimi taktnimi frekvencami: LFSR-1 in LFSR-2. Urna frekvenca RLOS-2 je d-krat višja od frekvence RLLS-1. Posamezni biti teh registrov so združeni z operacijo IN. Izhodi operacije IN so nato razvrščeni XOR. Izhodno zaporedje je vzeto iz tega bloka XOR. Spet ta generator ni popoln (Ni preživel odprtja linearne konsistence. Če je - dolžina LFSR-1, - dolžina LFSR-2 in je d razmerje urnih frekvenc, potem je notranje stanje generator je mogoče dobiti iz izhodnega zaporedja dolžine), vendar ima visoko linearno kompleksnost in odlično statistično zmogljivost.

Povratni premični register je sestavljen iz dveh delov: premičnega registra in povratne funkcije.

Slika 19. Spremični register za povratne informacije.

Na splošno je premični register zaporedje nekaterih elementov obroča ali polja. Najpogosteje uporabljena bit premične registre. Dolžina takega registra je izražena kot število bitov. Vsakič, ko se pridobi bit, se vsi biti v registru premaknejo v desno za en položaj. Novi najpomembnejši bit se izračuna kot funkcija vseh drugih bitov v registru. Izhod je običajno najmanjši bit. Obdobje premičnega registra je dolžina izhodnega zaporedja, preden se začne ponavljati.

Najpreprostejši tip premičnih registrov je linearni pomični register (LFSR ali LRS). Povratne informacije so preprosta operacija XOR na nekaterih bitih registra. Seznam teh bitov je definiran karakteristični polinom in poklical zaporedje dotikov. Včasih se ta shema imenuje Fibonaccijeva konfiguracija.

sl.20. LFOS Fibonaccijeve konfiguracije.

V programski izvedbi LFSR se uporablja spremenjena shema: za generiranje novega pomembnega bita se namesto uporabe bitov zaporedja odpiranja na vsakem od njegovih bitov izvede operacija XOR z izhodom generatorja, ki nadomesti staro del zaporedja pip. Ta sprememba se včasih imenuje Galois konfiguracija.

sl.21. RLOS konfiguracije Galois.

n-bit LFSR je lahko v enem od 2 n– 1 notranja stanja. To pomeni, da lahko teoretično tak register generira psevdonaključno zaporedje s obdobjem 2 n– 1 bit (polnjenje z ničlami je popolnoma neuporabno). Prehod vseh 2 n– 1 notranja stanja možna samo z določenimi zaporedji dotikov. Takšni registri se imenujejo LFSR z največjo dobo. Za zagotovitev največje dobe LFSR je potrebno, da je njen karakteristični polinom primitivno po modulu 2. Stopnja polinoma je dolžina premičnega registra. Primitivni stopenjski polinom n- tako je nezmanjšljiv polinom, ki je delilec, vendar ni delilec x d+1 za vse d, ki so delitelji 2 n– 1. (Ko razpravljamo o polinomih, izraz praštevilo nadomesti z izrazom nereducibilni polinom). Značilni polinom LFSR, prikazan na slikah:

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

je primitiven po modulu 2. Obdobje takega registra bo največje in bo krožilo skozi vseh 2 32 - 1 vrednosti, dokler se ne ponovijo. Najpogosteje uporabljeni so stanjšani polinomi, t.j. ki imajo le nekaj koeficientov. najbolj priljubljeni trinomi.

Pomemben parameter generatorja, ki temelji na LFSR, je linearna kompleksnost. Opredeljena je kot dolžina n najkrajši LFSR, ki lahko simulira izhod generatorja. Linearna kompleksnost je pomembna, ker s preprostim Berlenkamp-Masseyjev algoritem takšen LFSR je mogoče ponovno ustvariti s preverjanjem samo 2 n gama biti. Z definicijo želenega LFSR je tokovna šifra dejansko pokvarjena.

Pomikalni register s povratnimi informacijami je sestavljen iz dveh delov: premičnega registra in povratne funkcije (slika 1.2.1). Spremični register je zaporedje bitov. (Število bitov je določeno z dolžino premičnega registra. Če je dolžina n bitov, se register imenuje n-bitni pomikalni register.) Kadar koli je treba izvleči bit, so vsi biti premičnega registra premaknjeno v desno za 1 položaj. Novi skrajni levi bit je funkcija vseh drugih bitov v registru. Izhod premičnega registra je en, običajno najmanj pomemben bit. Obdobje premičnega registra je dolžina nastalega zaporedja, preden se začne ponavljati.

riž. 1.2.1.

Kriptografom so bile všeč pretočne šifre, ki temeljijo na registru premika: enostavno jih je bilo implementirati z digitalno strojno opremo. Na kratko se bom dotaknil matematične teorije. Leta 1965 je Ernst Selmer, glavni kriptograf norveške vlade, razvil teorijo zaporedij premičnih registrov. Solomon Golomb, matematik NSA, je napisal knjigo, v kateri je opisal nekatere njegove in Selmerjeve rezultate.

Najenostavnejša vrsta premičnega registra s povratnimi informacijami je linearni premični register s povratnimi informacijami ali LFSR (slika 1.2.2). Povratne informacije so preprosto XOR nekaterih bitov v registru, seznam teh bitov se imenuje zaporedje dotika. Včasih se tak register imenuje Fibonaccijeva konfiguracija. Zaradi preprostosti zaporedja povratnih informacij se lahko za analizo LFSR uporabi precej napredna matematična teorija. Kriptografi radi analizirajo zaporedja in se prepričujejo, da so ta zaporedja dovolj naključna, da so varna. LFSR se v kriptografiji pogosteje uporabljajo kot drugi premični registri.

riž. 1.2.2.

Na sl. 1.2.3 prikazuje 4-bitni LFSR s pritiskom na prvi in četrti bit. Če je inicializiran z vrednostjo 1111, bo pred ponovitvijo registra prevzel naslednja notranja stanja:

riž. 1.2.3. 4

Izhodno zaporedje bo niz najmanj pomembnih bitov:

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

n-bitni LFSR je lahko v enem od 2n-1 notranjih stanj. To pomeni, da lahko teoretično tak register generira psevdonaključno zaporedje s periodo 2n-1 bitov. (Število notranjih stanj in obdobja sta 2n-1, ker bo polnitev LFSR z ničlami povzročila, da premični register izpiše neskončno zaporedje nič, kar je popolnoma neuporabno.) Samo z določenimi zaporedji dotikov bo LFSR krožil skozi vseh 2n-1 notranjih stanj, so takšni LFSR-ji LFSR z največjo dobo. Nastali rezultat se imenuje M-zaporedje.

Da bi imel določen LFSR največjo periodo, mora biti polinom, oblikovan iz zaporedja odpiranja in konstante 1, primitiven po modulu 2. Stopnja polinoma je dolžina premičnega registra. Primitivni polinom stopnje n je nereducibilen polinom, ki je delilec, vendar ni delilec xd+1 za vse d, ki so delitelji 2n-1.

Na splošno ni enostavnega načina za generiranje primitivnih polinomov dane stopnje po modulu 2. Najlažji način je, da naključno izberete polinom in preverite, ali je primitiven. To ni enostavno - in podobno kot preverjanje, ali je naključno izbrano število pra - vendar lahko to storijo številni programski paketi za matematiko.

Nekateri, a zagotovo ne vsi polinomi različnih stopenj so primitivni po modulu 2. Na primer, zapis (32, 7, 5, 3, 2, 1, 0) pomeni, da je naslednji polinom primitiven po modulu 2:

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

To je mogoče zlahka posplošiti na LFSR z največjo dobo. Prva številka je dolžina LFSR. Zadnja številka je vedno 0 in jo je mogoče izpustiti. Vse številke razen 0 določajo zaporedje dotikov, ki se šteje od levega roba premičnega registra. To pomeni, da izrazi polinoma z nižjo stopnjo ustrezajo položajem bližje desnemu robu registra.

Če nadaljujemo s primerom, pisanje (32, 7, 5, 3, 2, 1, 0) pomeni, da se za dani 32-bitni premični register nov bit generira z XOR 32., sedmega, petega, tretjega, drugega , in prvi biti bo dobljeni LFSR imel največjo dolžino, ki bo pred ponovitvijo cikliral skozi vrednosti 232-1.