Príklad posuvného registra s lineárnou spätnou väzbou. Posuvné registre s lineárnou spätnou väzbou. Bunkové automaty a posuvné registre s nelineárnou spätnou väzbou

dešifrovanie - p i = D (ki, c i), ako je znázornené ryža. 7.21.

Ryža. 7.21.

Streamové šifry sú rýchlejšie ako blokové šifry. Jednoduchšia je aj hardvérová implementácia prúdovej šifry. Keď potrebujeme zašifrovať binárne toky a preniesť ich konštantnou rýchlosťou, najlepšou voľbou je použiť prúdovú šifru. Prúdové šifry sú bezpečnejšie proti poškodeniu bitov počas prenosu.

V moderných prúdových šifrách každá r -bitové slovo v pôvodnom textovom prúde je zašifrované pomocou r -bitové slovo v kľúčovom prúde na vytvorenie zhody r -bitové slovo v prúde šifrovaného textu.

Ryža. 7.22.

Jednorazová podložka je dokonalá šifra. On je perfektný. Neexistuje metóda, ktorá by dala protivníkovi schopnosť rozpoznať kľúč alebo štatistiku šifrovaného textu a pôvodného textu. Medzi originálom a šifrovým textom nie je žiadny vzťah. Inými slovami, šifrový text je skutočný náhodný prúd bitov, aj keď získate nejaké vzorky pôvodného textu. Eva nemôže prelomiť šifru, pokiaľ nevyskúša všetky možné náhodné kľúče, čo by bolo 2 n, ak by veľkosť pôvodného textu bola n bitov. S tým je však problém. Vysielač a prijímač musia vytvoriť spojenie vždy, keď si chcú vymieňať informácie, aby mohli zdieľať jednorazovú klávesnicu. Musia sa tak či onak dohodnúť na náhodnom kľúči. Takže táto dokonalá a dokonalá šifra je veľmi ťažko realizovateľná.

Príklad 7.17

Ako vyzerá šifrový text pri použití jednorazovej blokovej šifry v každom z nasledujúcich prípadov?

a. Pôvodný text pozostáva z n núl.

b. Pôvodný text pozostáva z n jednotiek.

v. Pôvodný text pozostáva zo striedajúcich sa núl a jednotiek.

d) Pôvodný text je náhodný reťazec bitov.

Riešenie

a. Pokiaľ ide o potom sa tok šifrovaného textu bude zhodovať s tokom kľúčov. Ak je kľúč náhodný, je náhodný aj šifrový text. Časti pôvodného textu sa v šifrovanom texte nezachovajú.

b. Pokiaľ ide o kde je výplň, tok šifrovaného textu je výplň kľúčového prúdu. Ak je kľúčový prúd náhodný, potom je náhodný aj šifrový text, fragmenty pôvodného textu sa v šifrovanom texte neuložia.

c. V tomto prípade je každý bit v prúde šifrovaného textu buď rovnaký ako v prúde kľúčov, alebo je jeho doplnkom. Preto je výsledok tiež náhodný, ak je tok kľúčov náhodný.

d. V tomto prípade je šifrový text jasne náhodný, pretože operácia EXCLUSIVE OR dvoch náhodných bitov vedie k náhodnému bitovému toku.

Posuvný register spätnej väzby

Jedno vylepšenie jednorazovej podložky - (FSR - Feedback Shift Register). FSR môže byť implementované buď softvérovo alebo hardvérovo, ale kvôli jednoduchosti budeme uvažovať o hardvérovej implementácii. Posuvný register spätnej väzby zahŕňa funkcie posuvného registra a spätnej väzby ako je uvedené v ryža. 7.23.

Ryža. 7.23.

Posuvný register je sekvencia m buniek od b 0 do b m-1, kde každá bunka je navrhnutá na uloženie jedného bitu. Bunky sa považujú za n-bitové slovo, ktoré sa na začiatku nazýva „hodnota semena“, resp Zdroj... Kedykoľvek je potrebné vyslať bit (napríklad pri signáli v konkrétnom čase), každý bit sa posunie o jednu bunku doprava. To znamená, že hodnota každej bunky je priradená k pravej susednej bunke a preberá hodnotu ľavej bunky. Bunka úplne vpravo b 0 sa považuje za výstup a dáva výstupnú hodnotu (ki). Bunka úplne vľavo, b m-1, získa svoju hodnotu podľa hodnoty informácie o funkcii spätnej väzby. Výstup funkcie označujeme spätnoväzbovou informáciou b m. Funkcia spätnej väzby určuje, aké hodnoty majú bunky, aby bolo možné vypočítať b m. Posuvný register spätnoväzbových informácií môže byť lineárny alebo nelineárny.

Posunový register s lineárnou spätnou väzbou (LFSR)... Predpokladajme, že b m je lineárna funkcia b 0, b 1, ... ..., b m-1, pre ktorú

Posuvný register s lineárnou spätnou väzbou pracuje s binárnymi číslicami, takže násobenie a sčítanie sú v poli GF (2), takže hodnota C i je buď 1 alebo 0, ale C 0 musí byť 1, aby sa dostali informácie o spätnej väzbe. Operácia pridania je VÝLUČNÁ ALEBO operácia. Inými slovami,

Príklad 7.18

Zostavme lineárny spätnoväzbový posuvný register s 5 bunkami, v ktorých.

Riešenie

Ak C i = 0, b i nehrá úlohu pri výpočte b m, potom to znamená, že b i nie je spojené s funkciou spätnej väzby. Ak c i = 1, b i je zahrnuté do výpočtu b m. V tomto príklade sú c 1 a c 3 nuly, čo znamená, že máme len tri spojenia. Obrázok 7.24 znázorňuje obvod posuvného registra s lineárnou spätnou väzbou.

Ryža. 7.24.

Príklad 7.19

Zostrojme lineárny spätnoväzbový posuvný register so 4 bunkami, v ktorých ... Zobraziť hodnotu registra po 20 operácie (zmeny), ak je počiatočná hodnota (0001) 2.

Riešenie

Obrázok 7.25 ukazuje obvod a použitie lineárneho posuvného registra s uzavretou slučkou na šifrovanie.

Ryža. 7.25.

Tabuľka 7.6. zobrazuje hodnotu prúdu kľúčov. Pre každý prechod sa vypočíta prvá hodnota b4 a potom sa každý bit posunie o jednu bunku doprava.

Tabuľka 7.6.

súčasná hodnota	b 4	b 3	b 2	b 1	b 0	k i
Pôvodná hodnota	1	0	0	0	1
1	0	1	0	0	0	1
2	0	0	1	0	0	0
3	1	0	0	1	0	0
4	1	1	0	0	1	0
5	0	1	1	0	0	1
6	1	0	1	1	0	0
7	0	1	0	1	1	0
8	1	0	1	0	1	1
9	1	1	0	1	0	1
10	1	1	1	0	1	0
11	1	1	1	1	0	1
12	0	1	1	1	1	0
13	0	0	1	1	1	1
14	0	0	0	1	1	1
15	1	0	0	0	1	1
16	0	1	0	0	0	1
17	0	0	1	0	0	0
18	1	0	0	1	0	0
19	1	1	0	0	1	0
20	1	1	1	0	0	1

Všimnite si, že tok kľúčov je 1000100110101111 1001 ……. Na prvý pohľad to vyzerá ako náhodná sekvencia, no ak sa pozrieme na veľké množstvo transakcií (shiftov), ​​môžeme vidieť, že sekvencie sú periodické. Toto opakovanie 15 bitov je zobrazené nižšie.

Kľúč toku sa generuje pomocou posuvného registra s lineárnou spätnou väzbou pseudonáhodná sekvencia, v ktorých sa opakujú postupnosti dĺžky N. Prietok je periodický. Závisí od obvodu generátora a počiatočných informácií a nemôže byť väčšia ako 2 m - 1. Každý obvod generuje m-bitové sekvencie od všetkých núl po všetky jednotky. Ak však počiatočná sekvencia pozostáva iba z núl, výsledok je zbytočný — pôvodný text by bol prúdom všetkých núl. Preto je takáto počiatočná sekvencia vylúčená.

Ministerstvo školstva a vedy

RUSKÁ ŠTÁTNA SOCIÁLNA UNIVERZITA

FAKULTA INFORMAČNÝCH TECHNOLÓGIÍ

ODDELENIE OCHRANY INFORMÁCIÍ

Kryptografické metódy a prostriedky na zaistenie informačnej bezpečnosti

Práca na kurze

"R Posuvné registre s lineárnou spätnou väzbou ako generátory pseudonáhodných čísel "

Dokončené:

študent 3. ročníka

skupina KZOI-D-3

Larionov I.P.

Skontrolované:

Doc. Baranová E.K.

Moskva 2011
OBSAH

Úvod ……………………………..…………………………………….3

1. Teoretické základy práce…………………………………………4
   1. Všeobecné informácie o posuvných registroch s uzavretou slučkou ... ... ... ... ..4
      1. O prúdových šifrách založených na РгСсЛОС …………………. ……… 10
      2. O lineárnej zložitosti vygenerovanej pseudonáhodnej sekvencie РгСсЛОС …………………………………. …… 12
      3. O korelačnej nezávislosti vygenerovanej postupnosti pseudonáhodných čísel РгСсЛОС ……… ..… .13
      4. O ďalších spôsoboch otvárania vygenerovanej postupnosti pseudonáhodných čísel РгСсЛОС …………………………………… ..14
2. Softvérová implementácia РгСсЛОС ako generátor pseudonáhodných sekvencií….…………………………….15
   1. Zovšeobecnená schéma algoritmu ………………………………… ... 15
   2. Popis programových modulov a rozhrania ……………… .16
   3. Návod na použitie ………………………………… ... 20

Záver ………………………………………………………………22

Bibliografia………………………………………………….....23

Príloha A ….………………………………………………………..24

ÚVOD

Cieľom tejto práce je vyvinúť softvérovú aplikáciu, ktorá implementuje činnosť generátora pseudonáhodných čísel na posuvných registroch so spätnou väzbou. Vývoj tejto aplikácie s grafickým rozhraním prebieha v jazyku C ++ pre Windows.

S rozvojom kryptografie v dvadsiatom storočí čelili kryptografi výzve vytvoriť šifrovacie zariadenia a stroje, ktoré by dokázali rýchlo a spoľahlivo šifrovať a dešifrovať správy. Túto požiadavku spĺňali už vtedy otvorené symetrické šifrovacie systémy, no ich slabou stránkou bola silná závislosť na kľúči a jeho utajení. Najvhodnejšou triedou šifier, ktoré možno na tento účel použiť, sú gama šifry. Vyskytol sa problém s generovaním gama, ktoré nebolo možné zistiť pri dešifrovaní správy. Teoreticky to bolo možné, ak by bola gama zakaždým náhodná a časom sa menila. Pri použití úplne náhodne sa meniaceho gamutu by však bolo ťažké poskytnúť spoľahlivé šifrovanie-dešifrovanie správy. Tento problém riešili kryptografi, ktorých cieľom bolo nájsť algoritmus, ktorý implementuje generovanie náhodnej gama podľa určitého pravidla, takáto sekvencia by mala obsahovať nuly a jednotky na „vraj“ náhodných pozíciách a počet jednotiek a núl by mala byť približne rovnaká. Táto náhodná sekvencia bola pomenovanápseudonáhodný,pretože bol generovaný podľa určitého pravidla a nie náhodne.

Čoskoro sa našlo riešenie. Štúdium vlastností posuvných registrov umožnilo zistiť, že posuvné registre so spätnou väzbou sú schopné vďaka svojej vnútornej štruktúre generovať pseudonáhodné sekvencie, ktoré sú dostatočne odolné voči dešifrovaniu.

1.Teoretické základy práce

1.1 Všeobecné informácie o posuvných registroch s lineárnou spätnou väzbou

Sekvencie posuvných registrov sa používajú v kryptografii aj v teórii kódovania. Ich teória je dobre rozvinutá, prúdové šifry založené na posuvných registroch boli ťahúňom vojenskej kryptografie dávno pred príchodom elektroniky.

Posuvný register so spätnou väzbou (ďalej len РгСсОС) pozostáva z dvoch častí: posuvného registra a funkcie spätnej väzby.Posuvný register je sekvencia bitov. Počet bitov je určenýdĺžka posuvného registra, ak je dĺžka n bitov, potom sa volá registern-bitový posuvný register... Kedykoľvek je potrebné získať bit, všetky bity posuvného registra sa posunú doprava o 1 pozíciu. Nový bit úplne vľavo je funkciou všetkých ostatných bitov registra. Výstupom posuvného registra je jeden, zvyčajne najmenej významný bit.Obdobie posunového registraje dĺžka výslednej sekvencie pred začiatkom jej opakovania.

Obrázok Posunový register spätnej väzby

Posunové registre si našli cestu do prúdových šifier veľmi rýchlo, pretože sa dali jednoducho implementovať pomocou digitálneho hardvéru. V roku 1965 Ernst Selmer, hlavný kryptograf nórskej vlády, vyvinul teóriu sekvencií posuvných registrov. Solomon Golomb, matematik NSA, napísal knihu, v ktorej načrtol niektoré jeho výsledky a výsledky Selmera. Najjednoduchšia forma spätnoväzbového posuvného registra jeposuvný register s lineárnou spätnou väzbou ( posuvný register s lineárnou spätnou väzbou, ďalej len LFSR alebo РгСсЛОС) ... Spätná väzba takýchto registrov je jednoducho XOR (modulo two Adding) niektorých bitov registra, zoznam týchto bitov sa nazýva sekvencia klepnutia. Tento register sa niekedy nazýva Fibbonacciho konfigurácia. Vďaka jednoduchosti sekvencie spätnej väzby možno na analýzu PrCcVOC použiť pomerne dobre rozvinutú matematickú teóriu. Analýzou výsledných výstupných sekvencií môžete overiť, že tieto sekvencie sú dostatočne náhodné, aby boli bezpečné. PrCcLOC je najbežnejšie používaný posuvný register v kryptografii.

Kresba PrCsLOS Fibbonacci

Vo všeobecnosti n -bit PgCsLOC môže byť v jednom z N = 2 n -1 vnútorné stavy. To znamená, že teoreticky môže takýto register generovať pseudonáhodnú sekvenciu s periódou T = 2 n - 1 bit. (Počet vnútorných stavov a perióda sú rovnaké N = Tmax = 2 n -1, pretože vyplnenie PrCcLOC nulami spôsobí, že posuvný register vytvorí nekonečnú sekvenciu núl, čo je absolútne zbytočné). Len pri určitých odbočovacích sekvenciách bude PrCcLOC cyklicky prechádzať všetkými 2 n -1 vnútorné stavy, akými sú PrCsLOCPrCcLOC s maximálnou periódou... Výsledný výsledok je tzvM-sekvencia.

Príklad ... Obrázok nižšie ukazuje 4-bitový PrCcLOC odpočúvaný z prvého a štvrtého bitu. Ak je inicializovaný s hodnotou 1111, potom pred opakovaním nadobudne register nasledujúce vnútorné stavy:

Číslo posunu hodín (interný stav)	Registrovať štát				Výstupný bit
Pôvodná hodnota
15 (návrat do pôvodného stavu)
16 (opakované stavy)

Výstupná sekvencia bude reťazec najmenej významných bitov: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 s periódou T = 15, celkový počet možných vnútorných stavov (okrem nuly), N = 2 4-1 = 16-1 = 15 = T max teda výstupná postupnosť je M -následnosť.

Aby mal konkrétny PrCcLOC maximálnu periódu, polynóm vytvorený z postupnosti vetvenia a konštanta 1 musí byť primitívny modulo 2. Polynóm je reprezentovaný ako súčet stupňov, napríklad polynóm stupňov n vyzerá takto:

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, kde a i = (0, 1 ) pre i = 1 ... n, axi - označuje číslicu.

Stupeň polynómu je dĺžka posuvného registra. Primitívny polynóm stupňa n je ireducibilný polynóm, ktorý delí x 2n - 1 +1, ale nie deliteľom x d +1 pre všetkých d deliteľov 2 n -1. Príslušnú matematickú teóriu možno nájsť v.

Vo všeobecnosti neexistuje jednoduchý spôsob, ako generovať primitívne polynómy daného stupňa modulo 2. Najjednoduchší spôsob je vybrať polynóm náhodne a skontrolovať, či je primitívny. Nie je to jednoduché a je to niečo ako kontrola, či náhodne vybrané číslo nie je jednoduché – ale mnohé matematické softvérové ​​balíky dokážu tento problém vyriešiť.

Niektoré, ale určite nie všetky, polynómy rôznych stupňov, primitívny mod 2, sú uvedené nižšie. Napríklad vstup

(32, 7, 5, 3, 2, 1, 0) znamená, že nasledujúci polynóm je primitívny modulo 2: x 32 + x 7 + x 5 + x 3 + x 2 + x + 1.

Toto možno ľahko zovšeobecniť pre PrCCLOC s maximálnou periódou. Prvé číslo je dĺžka PrCcLOC. Posledné číslo je vždy 0 a možno ho vynechať. Všetky čísla, okrem 0, určujú poradie prstov, počítané od ľavého okraja posuvného registra. To znamená, že členy polynómu s nižším stupňom zodpovedajú pozíciám bližšie k pravému okraju registra.

Pokračujúc v príklade, zápis (32, 7, 5, 3, 2, 1, 0) znamená, že pre prevzatý 32-bitový posuvný register sa generuje nový bit, nový bit XORingom tridsiateho, siedmeho, piaty, tretí, druhý a prvý bit. , výsledný PrCcLOC bude mať maximálnu dĺžku, pričom bude cyklovať cez 2 32 -1 hodnoty.

Obrázok 4 32-bitový PrCcLOC s maximálnou dĺžkou

Uvažujme programový kód PgCsLOC, v ktorom je postupnosť vetvenia charakterizovaná polynómom (32, 7, 5, 3, 2, 1, 0). V jazyku C to vyzerá takto:

int LFSR () (

statický nepodpísaný dlhý ShiftRegister = 1;

/ * Všetko okrem 0. * /

ShiftRegister = (((((ShiftRegister >> 31)

^ (ShiftRegister >> 6)

^ (ShiftRegister >> 4)

^ (ShiftRegister >> 2)

^ (ShiftRegister >> 1)

^ ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1);

vrátiť ShiftRegister & 0 x 00000001;)

Ak je posuvný register dlhší ako počítačové slovo, kód sa stáva zložitejším, ale nie príliš. V aplikácii B vzhľadom na tabuľku niektorých primitívnych polynómov modulo 2 ju v budúcnosti použijeme na identifikáciu niektorých vlastností týchto polynómov, ako aj pri implementácii softvéru na definovanie postupnosti odklonu.

Treba poznamenať, že všetky prvky tabuľky majú nepárny počet koeficientov. Takáto dlhá tabuľka je určená na ďalšiu prácu s PrCcLOC, pretože PrCcLOC sa často používa na kryptografiu s prúdovými šiframi a v generátoroch pseudonáhodných čísel. V našom prípade môžete použiť polynómy s najvyšším stupňom najviac sedem.

Ak je p (x) primitívne, potom je primitívne a x n p (1 / x), takže každý prvok tabuľky v skutočnosti definuje dva primitívne polynómy. Napríklad, ak (a, b, 0) je primitívne, potom také je (a, a-b, 0). Ak je primitívna (a, b, c, d, 0), tak je aj primitívna (a, a-d, a-c, a-b, 0). Matematicky:

ak je x primitívne a + x b +1, potom je to primitívne a x a + x a-b +1,

ak je x primitívne a + x b + x c + x d +1, potom je to primitívne a x a + x a-d + x a-c + x a-b +1. Primitívne trojčlenky sú softvérovo implementované najrýchlejšie, keďže na vygenerovanie nového bitu je potrebné vykonať XOR len dva bity posuvného registra (nulový člen sa neberie do úvahy, t.j. x 0 = 1, pozri príklad vyššie). Všetky spätnoväzbové polynómy uvedené v tabuľke sú skutočne riedke, to znamená, že majú málo koeficientov. Zriedkavosť je vždy zdrojom slabosti, čo niekedy stačí na prelomenie algoritmu. Pre kryptografické algoritmy je oveľa lepšie použiť husté primitívne polynómy, tie s mnohými koeficientmi. Použitím hustých polynómov, najmä ako súčasti kľúča, možno použiť oveľa kratšie PsCLOC.

Generovanie hustých primitívnych polynómov mod 2 nie je jednoduché. Vo všeobecnosti, ak chcete generovať primitívne polynómy stupňa k, potrebujete poznať faktorizáciu čísla 2 k -1.

PrCcLOC sú samé o sebe dobrými generátormi pseudonáhodných sekvencií, ale majú niektoré nežiaduce nenáhodné (deterministické) vlastnosti. Po sebe idúce bity sú lineárne, vďaka čomu sú na šifrovanie nepoužiteľné. Pre PrCLOC dĺžky n je vnútorný stav predchádzajúcich n výstupných bitov generátora. Aj keď je schéma spätnej väzby utajená, možno ju určiť z 2n výstupných bitov generátora pomocou vysoko efektívneho Berlekamp-Masseyho algoritmu.

Okrem toho veľké náhodné čísla generované pomocou súvislých bitov tejto sekvencie sú vysoko korelované a pre niektoré typy aplikácií nie sú náhodné vôbec. Napriek tomu sa PgCsLOC často používajú na vytváranie šifrovacích algoritmov ako súčasti šifrovacích systémov a algoritmov.

1.2 O prúdových šifrách založených na РгСсЛОС

Základný prístup k návrhu generátora toku kľúčov založeného na RgCsLOC je jednoduchý. Najprv sa vezme jeden alebo viac PrCcLOC, zvyčajne s rôznymi dĺžkami a rôznymi polynómami spätnej väzby. (Ak sú dĺžky coprime a všetky spätnoväzbové polynómy sú primitívne, potom vygenerovaný generátor bude mať maximálnu dĺžku.) Kľúčom je počiatočný stav registrov PrCCLOC. Zakaždým, keď je potrebný nový bit, posuňte registre PrCCLOC o jeden bit (niekedy sa to nazýva taktovanie). Výstupný bit je funkcia, výhodne nelineárna, niektorých bitov v registroch PrCCLOC. Táto funkcia sa nazýva kombinačná funkcia a generátor ako celok sa nazýva kombinovaný generátor. (Ak je výstupný bit funkciou jedného PrCcLOC, potom sa generátor nazýva generátor filtra.) Veľkú časť teórie pre tento druh zariadenia vyvinuli Selmer a Neal Zierler. Môže sa vyskytnúť množstvo komplikácií. Niektoré generátory používajú inú hodinovú frekvenciu pre rôzne PgCLOC, niekedy frekvencia jedného generátora závisí od výstupu druhého. Toto sú všetky elektronické verzie myšlienok šifrovacích strojov, ktoré sa objavili pred druhou svetovou vojnou, ktoré sa nazývajú generátory riadené hodinami ( generátory riadené hodinami ). Riadenie hodín môže byť dopredné, kde výstup jedného PrCcLOC riadi hodiny druhého PrCcLOC, alebo uzavretá slučka, kde výstup jedného PrCcLOC riadi svoje vlastné hodiny. Zatiaľ čo všetky tieto generátory sú citlivé, aspoň teoreticky, na hniezdne útoky a pravdepodobnú koreláciu, mnohé z nich sú stále bezpečné.

Ian Cassells, bývalý vedúci Katedry čistej matematiky v Cambridge a kryptoanalytik v Bletchly Park, povedal, že „kryptografia je zmesou matematiky a zmätku a matematika môže byť použitá proti vám bez zmätku“. Myslel tým, že v prúdových šifrách sú na poskytnutie maximálnej dĺžky a iných vlastností potrebné určité matematické štruktúry, ako napríklad PrCCLOC, ale musí sa zaviesť nejaký zložitý nelineárny neporiadok, aby sa zabránilo niekomu získať obsah registra a prelomiť algoritmus. Táto rada platí aj pre blokové algoritmy.

Väčšina skutočných prúdových šifier je založená na PrCCLOC. Ani v začiatkoch elektroniky nebolo ich zostavenie náročné. Posuvný register nie je nič iné ako pole bitov a sekvencia spätnej väzby je súbor brán XOR. Aj pri použití VLSI poskytuje prúdová šifra založená na RgCsLOS značnú bezpečnosť pomocou niekoľkých logických brán. Problém PrCsLOC je v tom, že ich softvérová implementácia je veľmi neefektívna. Musíte sa vyhnúť riedkym spätnoväzbovým polynómom – uľahčujú korelačné prerušenia – a husté spätnoväzbové polynómy sú neúčinné.

Toto odvetvie kryptografie rýchlo rastie a je pod ostražitou vládnou kontrolou zvonku NSA ... Väčšina vývojov je klasifikovaná - mnohé z dnes používaných vojenských šifrovacích systémov sú založené na РгСсЛОС. V skutočnosti väčšina počítačov Cray (Cray 1, Cray X-MP, Cray Y-MP) má veľmi kurióznu inštrukciu, ktorá sa bežne označuje ako „počet populácie“. Počíta počet jednotiek v registri a dá sa použiť na efektívny výpočet Hammingovej vzdialenosti medzi dvoma binárnymi slovami a na implementáciu vektorizovanej verzie PrCCLOC. Táto inštrukcia sa považuje za kanonickú inštrukciu NSA a musí sa objaviť takmer vo všetkých zmluvách týkajúcich sa počítačov.

Na druhej strane sa podarilo prelomiť prekvapivo veľké množstvo zdanlivo zložitých generátorov posuvných registrov. A, samozrejme, počet takýchto generátorov hacknutých vojenskými kryptoanalytickými inštitúciami, ako je NSA, je ešte väčší.

1.3 O lineárnej zložitosti vygenerovanej sekvencie pseudonáhodných čísel PrCcLOC

Streamové šifry sa často analyzujú ľahšie ako blokové šifry. Napríklad lineárna zložitosť alebo lineárny interval je dôležitým parametrom používaným na analýzu generátorov založených na PrCsLOS. Je definovaná ako dĺžka n najkratšieho PgCVOC, ktorý dokáže simulovať výstup generátora. Akákoľvek sekvencia generovaná konečným automatom v konečnom poli má konečnú lineárnu zložitosť. Lineárna zložitosť je dôležitá, pretože pomocou jednoduchého algoritmu nazývaného Berlekamp-Masseyov algoritmus je možné tento PrCCLOC určiť skúmaním iba 2n bitov kľúčového toku. Opätovným vytvorením požadovaného PgCCLOC prelomíte prúdovú šifru.

Táto myšlienka môže byť rozšírená z polí na krúžky a na prípady, keď sa výstupná sekvencia považuje za čísla v nepárnom charakteristickom poli. Ďalšie rozšírenie vedie k zavedeniu konceptu lineárneho profilu zložitosti, ktorý definuje lineárnu zložitosť sekvencie pri jej predlžovaní. Existujú aj koncepty sférickej a kvadratickej zložitosti. V každom prípade si pamätajte, že vysoká lineárna zložitosť nemusí nevyhnutne zaručovať bezpečnosť generátora, ale nízka lineárna zložitosť naznačuje nedostatočnú bezpečnosť generátora.

1.4 O korelačnej nezávislosti vygenerovanej sekvencie pseudonáhodných čísel PrCcLOC

Kryptografi sa snažia získať vysokú lineárnu zložitosť nelineárnym kombinovaním výsledkov niektorých výstupných sekvencií. Nebezpečenstvo tu spočíva v tom, že jedna alebo viac interných výstupných sekvencií - často len výstupy jednotlivých PrCsLOC - môžu byť spojené spoločným kľúčovým prúdom a otvorené pomocou lineárnej algebry. Toto sa často označuje ako korelačný útok alebo útok typu rozdeľ a panuj. Thomas Siegenthaler ukázal, že korelačnú nezávislosť možno presne určiť a že existuje kompromis medzi korelačnou nezávislosťou a lineárnou zložitosťou.

Hlavnou myšlienkou korelačného útoku je zistiť určitú koreláciu medzi výstupom generátora a výstupom jednej z jeho častí. Potom pozorovaním výstupnej sekvencie možno získať informácie o tomto medzivýstupe. Pomocou týchto informácií a ďalších korelácií je možné zbierať údaje o ďalších medzivýstupoch, kým nie je generátor hacknutý.

Korelačné útoky a ich variácie, ako sú rýchle korelačné útoky, boli úspešne použité proti mnohým generátorom kľúčových prúdov založených na PgCLOC, ktoré ponúkajú kompromis medzi výpočtovou zložitosťou a efektívnosťou.

1.5 O ďalších spôsoboch otvárania vygenerovanej sekvencie pseudonáhodných čísel PrCcLOC

Existujú aj iné spôsoby, ako zaútočiť na generátory kľúčových prúdov. Test lineárnej konzistencie sa snaží nájsť nejakú podmnožinu šifrovacieho kľúča pomocou maticovej techniky. Existuje aj útok konzistencie stretnutia v strede. Algoritmus lineárneho syndrómu je založený na schopnosti zapísať fragment výstupnej sekvencie vo forme lineárnej rovnice. Existuje najlepší aflne aproximačný útok a odvodený sekvenčný útok. Na prúdové šifry možno použiť aj metódy diferenciálnej a lineárnej kryptoanalýzy.

2. Popis softvérovej implementácie РгСсЛОС ako generátora pseudonáhodných sekvencií

2.1 Zovšeobecnená schéma algoritmu

2.2 Popis softvérových modulov a rozhrania

Obrázok 3 nižšie zobrazuje okno programu.

Obrázok Rozhranie programu

Menu má nasledujúce funkcie:

• Súbor-> Uložiť správu

Táto funkcia vytvára súbor správ, ktorý zaznamenáva počiatočný stav PrCcLOC, sekvenciu odbočiek, periódu prijatej pseudonáhodnej sekvencie bitov, samotnú sekvenciu a tabuľku stavov. Ak bol súbor úspešne uložený, zobrazí sa hlásenie o úspešnom uložení (obrázok 4). Odporúčaná prípona súboru správy *. TXT.

Kreslenie

• Súbor-> Ukončiť

Táto funkcia zabezpečuje zatvorenie aplikácie.

• Nastavte poradie vetví

Táto funkcia generuje sekvenciu ťuknutia načítaním hodnôt z políčok, ktoré používateľ zaškrtol na obrazovke. Potom upozorní užívateľa na vytvorenie sekvencie odklonu (obrázok 5). Sekvencia stiahnutia určuje, z ktorých klopných obvodov spätných väzieb posuvného registra pôjde XOR aby sa vytvoril ofsetový bit. Štandardne je vždy prítomná spätná väzba z prvého spúšťača, pri absencii iných spojení sa vykoná posun doľava s permutáciou najmenej významného bitu na pozíciu najvýznamnejšieho.

Kreslenie

• Nastavte počiatočnú hodnotu

Táto funkcia načíta užívateľom zadanú počiatočnú hodnotu registra z okna Upraviť 1 a skontroluje zadanú hodnotu podľa zadaných podmienok: zadaný riadok nie je prázdny (obrázok 6), zadaný riadok má dĺžku osem (8bit = 1 bajt, obrázok 7), zadaný riadok obsahuje iba nuly a / alebo jedničky (obrázok 8), zadaný riadok je nenulový (obrázok 9). V opačnom prípade sa zobrazia chybové hlásenia, používateľ ich musí opraviť a znova stlačiť tlačidlo. Ak je kontrola úspešná, počiatočná hodnota sa zapíše do tabuľky stavov v riadku „Počiatočné“ a vydá sa upozornenie (obrázok 10).

Kreslenie

Kreslenie

Kreslenie

Kreslenie

Kreslenie

• Posuňte register

Táto funkcia emuluje činnosť posuvného registra. Postupne sa vykoná 256 posunov, pričom každý posun tvorí výstupný bit pseudonáhodnej sekvencie a nový stav registra. Hneď ako sa stav registra rovná počiatočnému, vypočíta sa obdobie a zobrazí sa v poli Memo 1 prijatá pseudonáhodná sekvencia.

• Pomocník-> O programe

Táto funkcia zobrazuje krátky popis programu a inštrukcie (obrázok 11).

Kreslenie

• Pomoc-> O autorovi

Táto funkcia zobrazuje informácie o autorovi programu (obrázok 12).

Kreslenie

2.3 Návod na použitie

1. Najprv nastavte počiatočný stav registra. Musí obsahovať osem binárnych znakov. V opačnom prípade sa zobrazí chybové hlásenie a zadanú hodnotu budete musieť opraviť. Stlačte položku ponuky „Nastaviť počiatočnú hodnotu“.
2. Potom začiarknite políčka v začiarkavacích políčkach spätnej väzby registra (sekvencia pobočiek). Stlačte bod menu „Nastaviť poradie vetví“.
3. Potom kliknite na položku ponuky „Shift case“. Pred vykonaním tohto kroku sa uistite, že ste dokončili kroky 1 a 2, inak dôjde k softvérovej chybe.
4. Po prijatí výsledkov ich môžete uložiť kliknutím na položku ponuky „Súbor-> Uložiť správu“. Pred vykonaním tohto kroku sa uistite, že ste dokončili kroky 1-3, inak sa vyskytne chyba softvéru.
5. Ak potrebujete pomoc, kliknite na položky ponuky „Súbor-> Informácie“, „Súbor-> O autorovi“.
6. Ak chcete vidieť činnosť registra s inými hodnotami sekvencie klepnutia a počiatočným stavom registra, zopakujte kroky v krokoch 1-3 v poradí a zadajte ďalšie parametre.

ZÁVER

V tomto článku sme považovali PgCCLOC za generátory pseudonáhodných čísel. Program môže slúžiť ako názorná ukážka princípov činnosti posuvných registrov so zapnutou lineárnou spätnou väzbou XOR ... Môže sa použiť na štúdium princípu vytvárania pseudonáhodnej postupnosti bitov, vzťahu medzi počiatočnou hodnotou registra a hodnotou pseudonáhodnej postupnosti, postupnosti stiahnutia a periódy. Výsledný pseudonáhodný gamut možno použiť v inej softvérovej aplikácii (napríklad softvérová implementácia gama šifry).

V súčasnosti sa tieto registre nepoužívajú ako nezávislé generátory pseudonáhodných čísel, ale sú súčasťou zložitejších zariadení. Boli to však oni, ktorí otvorili nové smery v matematike (hľadanie primitívnych polynómov v konečných poliach, matematické metódy lámania generátorov pseudonáhodných čísel). Bez znalosti princípov činnosti generátorov na báze PrCCLOS nie je možné pochopiť činnosť zložitejších zariadení. Vďaka svojej jednoduchej hardvérovej implementácii sú široko používané v technológii. Štúdium РгСсОС viedlo k vzniku nových šifier - blokových a prúdových - založených na týchto typoch registrov (posuvná permutačná šifra, DES atď.; EDS, hašovacie funkcie).

Vo všeobecnosti výskum v tejto oblasti vážne posunul vývoj kryptografie a kryptoanalytiky, počítačov a zariadení a umožnil implementovať množstvo ďalších užitočných funkcií (napríklad korekciu kódov cyklov).

BIBLIOGRAFIA

1. Schneier Bruce. Aplikovaná kryptografia. Protokoly, algoritmy, zdrojové texty v jazyku C. - M.: Triumf, 2002
2. A. V. Babash Kryptografické a automatovo-teoretické aspekty modernej informačnej bezpečnosti. Zväzok 1 - M .: Ed. Stredisko EAOI, 2009 .-- 414 s.
3. E.S. Selmer. Monografia: "Lineárna rekurzia v konečnom poli". Univerzita v Bergene, Nórsko, 1966.
4. N. Zierler a J. Brillhart. "O primitívnych trojčlenkách modulo 2", Information and Control journal, vydanie 13 č. 6. december 1968, s. 541-544.
5. K.Kh. Meyer a W. L. Tuchman. "Pseudonáhodné kódy sa dajú prelomiť," hovorí časopis Electronic Design, č. 23, november 1972.
6. J. L. Massey. "Zovšeobecnenie posuvných registrov a dekódovanie kódu Bose-Chowdhury-Hockingham", IEEE Transactions on Information Theory, v. IT -15, č ... 1, január 1969, s. 122-127.
7. S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (pretlačené Aigean Park Press, 1982).

Príloha A

Tabuľka niektorých primitívnych polynómov mod 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)

Vstup do počiatočného stavu (IS)

skontrolujte správnosť zadania

Vydanie chybového hlásenia

Inštalácia sekvencie vetiev

Zápis IS do tabuľky stavu

Záznam i -tý stav registra a výstupný bit do tabuľky stavov

IS == Aktuálny stav

Ukladajú sa výsledky

Výstup pseudonáhodnej sekvencie

Výkon

Beh

Áno

Áno

nie

Definícia

Posuvný register s lineárnou spätnou väzbou pozostáva z dvoch častí: skutočného posuvného registra a funkcie spätnej väzby. Register pozostáva z bitov, jeho dĺžka je počet týchto bitov. Keď sa má získať bit, všetky bity v registri sa posunú o jednu pozíciu doprava. Nový bit úplne vľavo je určený funkciou zostávajúcich bitov. Na výstupe registra je jeden, zvyčajne najmenej významný bit. Perioda posuvného registra - dĺžka prijatej sekvencie pred začiatkom jej opakovania.

Pre RSLOS je spätnou väzbou súčet modulo 2 (xor) niektorých bitov registra, tzv kohútiky.

Lineárny posuvný register so spätnou väzbou pozostáva z očíslovaných buniek, z ktorých každá je schopná uložiť bit a má jeden vstup a jeden výstup a hodinový signál, ktorý riadi posun údajov. Počas každej jednotky času sa vykonávajú tieto operácie:

Posunový register s lineárnou spätnou väzbou

Logická operácia XOR (exkluzívny OR) sa teda berie ako funkcia spätnej väzby, to znamená:

Vlastnosti

Vlastnosti vygenerovanej sekvencie RSLOS úzko súvisia s vlastnosťami asociovaný polynóm nad ihriskom. Jeho nenulové koeficienty sa nazývajú kohútiky ako aj príslušné bunky registra dodávajúce hodnoty argumentov do funkcie spätnej väzby.

Periodicita

Pretože existujú rôzne nenulové stavy registra, perióda sekvencie generovanej RSLOS pre žiadny nenulový počiatočný stav neprekročí. V tomto prípade obdobie závisí od súvisiaceho polynómu:

Vlastnosti primitívnych polynómov

Lineárna zložitosť

Lineárna zložitosť binárnej postupnosti je jednou z najdôležitejších charakteristík operácie RSLOS. Uveďme si nasledujúci zápis:

Definícia

Lineárna zložitosť nekonečná binárna postupnosť je číslo, ktoré je definované takto:

Lineárna zložitosť konečná binárna postupnosť je číslo, ktoré sa rovná dĺžke najkratšieho RLOS, čím sa vygeneruje postupnosť, ktorá má ako prvé členy.

Vlastnosti lineárnej zložitosti

Dovoliť a byť binárne postupnosti. potom:

Korelačná nezávislosť

Na získanie vysokej lineárnej zložitosti sa kryptografi pokúšajú nelineárne kombinovať výsledky viacerých výstupných sekvencií. V tomto prípade je nebezpečenstvo, že jednu alebo viacero výstupných sekvencií (často aj výstupy jednotlivých RFLOS) možno spojiť spoločným kľúčovým prúdom a otvoriť pomocou lineárnej algebry. Hackovanie založené na takejto zraniteľnosti sa nazýva korelačná pitva... Thomas Sigenthaler ukázal, že korelačná nezávislosť sa dá presne určiť a že existuje kompromis medzi korelačnou nezávislosťou a lineárnou zložitosťou.

Poznámka

Hlavnou myšlienkou tohto hacku je nájsť určitú koreláciu medzi výstupom generátora a výstupom jednej z jeho častí. Potom, pozorovaním výstupnej sekvencie, môžete získať informácie o tomto prostrednom kolíku. Pomocou týchto informácií a ďalších korelácií je možné zbierať údaje o iných medziľahlých záveroch, kým nie je generátor hacknutý.

Korelačné útoky alebo variácie, ako sú rýchle korelačné útoky, boli úspešne použité proti mnohým generátorom kľúčových prúdov založených na lineárnom spätnom registri, ako sú rýchle korelačné útoky, ktoré zahŕňajú kompromis medzi výpočtovou zložitosťou a efektívnosťou.

Príklad

Pre RSLOS s pridruženým polynómom má vygenerovaná sekvencia tvar. Predpokladajme, že pred spustením procesu je do registra zapísaná sekvencia, potom bude perióda generovaného bitového toku 7 s nasledujúcou sekvenciou:

Číslo kroku	Štát	Generovaný bit
0		-
1		1
2		0
3		0
4		1
5		1
6		1
7		0

Keďže sa vnútorný stav v siedmom kroku vrátil do pôvodného stavu, potom, počnúc ďalším krokom, dôjde k opakovaniu. Inými slovami, perióda postupnosti sa ukázala ako 7, čo sa stalo kvôli primitívnosti polynómu.

Algoritmy na generovanie primitívnych polynómov

Pripravené stoly

Výpočet primitívnosti polynómu je pomerne zložitý matematický problém. Preto existujú hotové tabuľky, ktoré uvádzajú čísla sekvencií vetiev, ktoré poskytujú maximálnu periódu generátora. Napríklad pre 32-bitový posuvný register existuje sekvencia. To znamená, že ak chcete vygenerovať nový bit, musíte XOR 31., 30., 29., 27., 25. a 0. bit. Kód pre takýto RSLOS v C je nasledujúci:

Int LFSR (neplatné) (statické bez znamienka dlhé S = 1; S = ((((S >> 31) ^ (S >> 30) ^ (S >> 29) ^ (S >> 27) ^ (S >> 25) ^ S) a 1)<< 31 ) | (S>> 1); návrat S & 1; )

Softvérové ​​implementácie generátorov RSLOS sú dosť pomalé a fungujú rýchlejšie, ak sú napísané v assembleri a nie v C. Jedným z riešení je použiť paralelne 16 RSLOS (alebo 32, v závislosti od dĺžky slova v architektúre konkrétneho počítača). V takejto schéme sa používa pole slov, ktorých veľkosť sa rovná dĺžke RSLOS a každý bit slova v poli odkazuje na svoj vlastný RSLOS. Za predpokladu, že sa použijú rovnaké poradové čísla prstov, môže dôjsť k výraznému zvýšeniu výkonu. [potrebujete príklad kódu] (Pozri: bitslice).

Konfigurácia Galois

Galoisova konfigurácia posuvného registra s lineárnou spätnou väzbou

Slučku spätnej väzby možno tiež upraviť. V tomto prípade generátor nebude mať väčšiu kryptografickú silu, ale bude jednoduchšie ho softvérovo implementovať. Namiesto použitia bitov sekvencie prstov na generovanie nového bitu najviac vľavo sa každý bit sekvencie F XORed a nahradí výstupom generátora, potom sa výsledkom generátora stane nový bit najviac vľavo. V jazyku C to vyzerá takto:

Int LFSR (neplatné) (statické bez znamienka dlhé Q = 1; Q = (Q >> 1) ^ (Q & 1? 0x80000057: 0); návrat Q & 1;)

Odmenou je, že všetky XOR sa vykonajú v jednej operácii.

Poznámky:

• je možné dokázať, že Fibonacciho konfigurácia daná prvou a tu uvedená Galoisova konfigurácia dávajú rovnaké sekvencie (dĺžka 2³²-1), ale mimo fázy jedna od druhej
• slučka pevného počtu hovorov LFSR v konfigurácii Galois je približne dvakrát rýchlejšia ako v konfigurácii Fibonacci (kompilátor MS VS 2010 na Intel Core i5)
• všimnite si, že v konfigurácii Galois je poradie bitov v slove spätnej väzby v porovnaní s konfiguráciou Fibonacciho obrátené

Príklady generátorov na RSLOS

Generátory stop-and-go

Striedavý generátor stop-and-go

Tento oscilátor využíva výstup jedného RSLOS na riadenie taktovacej frekvencie druhého RSLOS. Hodinový výstup RSLOS-2 je riadený výstupom RSLOS-1, takže RSLOS-2 môže zmeniť svoj stav v čase t iba vtedy, ak je výstup RSDOS-1 v čase t-1 rovný jednej. Táto schéma však korelačnému zúčtovaniu neodolala.

Preto bol navrhnutý vylepšený generátor založený na rovnakej myšlienke. Nazýva sa to striedavý generátor typu stop-and-go. Používa tri RFLO rôznych dĺžok. RSLOS-2 je taktovaný, keď je výstup RSLOS-1 rovný jednej, a RSLOS-3 je taktovaný, keď je výstup RSLOS-1 nula. Výstup generátora je súčet modulo 2 RSLOS-2 a RSLOS-3. Tento generátor má dlhú periódu a veľkú lineárnu zložitosť. Jeho autori tiež ukázali spôsob otvárania korelácie RSLOS-1, ale to veľmi neoslabuje generátor.

Gollmannova kaskáda

Gollmannova kaskáda

Stupeň Gollmann je zosilnená verzia generátora stop-and-go. Pozostáva zo sekvencie RSLOS, pričom taktovanie každého z nich riadi predchádzajúci RSLOS. Ak je výstup RSLOS-1 v čase t 1, potom je RSLOS-2 taktovaný. Ak je výstup RSLOS-2 v čase t 1, potom je RSLOS-2 taktovaný atď. Výstup posledného RSLOS je výstup generátora. Ak je dĺžka všetkých LFLOS rovnaká a rovná sa n, potom sa lineárna zložitosť systému k LFL rovná

Táto myšlienka je jednoduchá a možno ju použiť na generovanie sekvencií s obrovskými periódami, veľkou lineárnou zložitosťou a dobrými štatistickými vlastnosťami. Bohužiaľ sú citlivé na útok zvaný lock-in. Pre väčšiu odolnosť sa odporúča použiť k aspoň 15. Navyše je lepšie použiť viac krátkych RFLO ako menej dlhých RFLO.

Generátor prahov

Generátor prahov

Tento generátor sa pokúša obísť bezpečnostné problémy predchádzajúcich generátorov pomocou variabilného počtu posuvných registrov. Teoreticky pri použití väčšieho počtu posuvných registrov narastá zložitosť šifry, čo sa robilo v tomto generátore.

Tento generátor pozostáva z veľkého počtu posuvných registrov, ktorých výstupy sú privádzané do majorizačnej funkcie. Ak je počet jednotiek na výstupoch registrov viac ako polovica, potom generátor vydá jednu. Ak je počet núl na výstupoch väčší ako polovica, potom generátor vydá nulu. Aby bolo možné porovnávať počet núl a jednotiek, musí byť počet posuvných registrov nepárny. Dĺžky všetkých registrov musia byť relatívne jednoduché a spätnoväzbové polynómy musia byť primitívne, aby perióda vygenerovanej sekvencie bola maximálna.

V prípade troch posuvných registrov môže byť generátor reprezentovaný ako:

Tento generátor je podobný Geffovmu generátoru, až na to, že prahový generátor má lineárnejšiu zložitosť. Jeho lineárna zložitosť je:

Kde,, sú dĺžky prvého, druhého a tretieho posuvného registra.

Jeho nevýhodou je, že každý výstupný bit poskytuje nejakú informáciu a stav posuvného registra. Presnejšie 0,189 bitu. Preto tento generátor nemusí odolať korelačnému útoku.

Iné typy generátorov

Poďme si ich stručne popísať

Samodecimujúce generátory

Samodecimujúce generátory sú tie, ktoré riadia svoju vlastnú frekvenciu. Boli navrhnuté dva typy takýchto generátorov. Prvý pozostáva z posuvného registra s lineárnou spätnou väzbou a nejakého obvodu, ktorý tento register taktova, v závislosti od toho, aké sú výstupné hodnoty posuvného registra. Ak je výstup RSLOS rovný jednej, potom je register taktovaný d-krát. Ak je výstup nula, potom je register taktovaný k-krát. Druhý má takmer rovnaký dizajn, ale mierne upravený: v hodinovom obvode vstup ako kontrola 0 alebo 1 neprijíma samotný výstupný signál, ale XOR určitých bitov posuvného registra s lineárnou spätnou väzbou. Bohužiaľ, tento druh generátora nie je bezpečný.