Posuvný registr lineární zpětné vazby. Teorie provozu Lineární posuvný registr

Posuvný registr zpětné vazby sestává ze dvou částí: posuvného registru a funkce zpětné vazby.

Obr. 19. Posuvný registr se zpětnou vazbou.

Posunový registr je obecně posloupností některých prvků prstence nebo pole. Nejčastěji se používá bit posuvné registry. Délka takového registru je vyjádřena počtem bitů. Pokaždé, když se bit načte, všechny bity registru se posunou o jednu pozici doprava. Nový nejvýznamnější bit se vypočítá jako funkce všech ostatních bitů registru. Výstup je obvykle nejméně významný bit. Perioda posuvného registru je délka výstupní sekvence, než se začne opakovat.

Nejjednodušší typ posuvných registrů je lineární zpětnovazební posuvný registr (RSLOS nebo LRS). Zpětná vazba je jednoduchá operace XOR u některých bitů registru. Seznam těchto bitů je definován charakteristický polynom a zavolal sled ohybů... Někdy se tomu říká konfigurace Fibonacci.

Obr. Konfigurace RLOS Fibonacci.

V softwarové implementaci RSLOS se používá upravené schéma: ke generování nového významného bitu se místo použití bitů sekvence klepnutí provede operace XOR na každém jejím bitu s výstupem generátoru, který nahradí starý bit sekvence klepnutí. Tato modifikace se někdy nazývá galoisova konfigurace.

Obr. Konfigurace RSLOS Galois.

n-bit RSLOS může být v jednom ze 2 n - 1 vnitřní stav. To znamená, že teoreticky může takový registr generovat pseudonáhodnou sekvenci s periodou 2 n - 1 bit (polstrování nulami je zcela zbytečné). Předat všechny 2 n - 1 vnitřní stav je možný pouze u určitých sekvencí odboček. Takové registry se nazývají RSLOS s maximální periodou. Pro zajištění maximální periody RSLOS je nutné, aby jeho charakteristický polynom byl primitivní modulo 2. Stupeň polynomu je délka posuvného registru. Primitivní polynom stupně n - je to tak neredukovatelné polynom, který je dělitelem, ale ne dělitelem xD + 1 pro všechny dto jsou dělitelé 2 n - 1. (Při diskusi o polynomech termín prvočíslo se nahrazuje výrazem neredukovatelný polynom). Charakteristický polynom uvedený na obrázcích RLOS:

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

je primitivní modulo 2. Perioda takového registru bude maximální a bude cyklovat všemi 2 32 - 1 hodnotami, dokud se neopakují. Nejčastěji se používají ztenčené polynomy, tj. které mají jen některé koeficienty. nejoblíbenější jsou trinomials.

Důležitým parametrem generátoru založeného na RSLOS je lineární složitost... Je definována jako délka n nejkratší RLOS, který dokáže simulovat výstup generátoru. Lineární složitost je důležitá, protože s jednoduchou algoritmus Berlenkamp-Massey takový RSLOS můžete znovu vytvořit zaškrtnutím pouze 2 n gama bity. S definicí požadovaného RSLOS je proudová šifra skutečně rozbitá.

dešifrování - p i \u003d D (k i, c i), jak ukazuje obr. 7.21.

Obr. 7.21.

Streamové šifry jsou rychlejší než blokové šifry. Hardwarová implementace proudové šifry je také jednodušší. Když potřebujeme šifrovat binární toky a přenášet je konstantní rychlostí, nejlepší volba - použít proudovou šifru. Šifry streamů jsou bezpečnější proti poškození bitů během přenosu.

V moderních šifrách proudu každý r - bitové slovo v původním textovém proudu je šifrováno pomocí r -bitové slovo v klíčovém proudu pro vytvoření shody r -bitové slovo v proudu šifrovaného textu.

Obr. 7.22.

Jednorázová podložka je dokonalá šifra. On je perfektní. Neexistuje žádná metoda, která by poskytla protivníkovi schopnost rozpoznat klíč nebo statistiku šifrovacího textu a původního textu. Mezi původním a šifrovým textem neexistuje žádný vztah. Jinými slovy, ciphertext je skutečný náhodný proud bitů, i když získáte nějaké vzorky původního textu. Eve nemůže prolomit šifru, pokud nevyzkouší všechny možné proudy náhodných klíčů, které by byly 2 n, pokud je velikost původního textu n-bitová. Existuje však problém. Vysílač a přijímač musí navázat spojení pokaždé, když si chtějí vyměnit informace, aby mohli sdílet jednorázovou klávesnici. Musí se tak či onak dohodnout na náhodném klíči. Tato dokonalá a dokonalá šifra je tedy velmi obtížná.

Příklad 7.17

Jak vypadá šifrovací text při použití šifry jednorázového pad v každém z následujících případů?

a. Původní text se skládá z n nul.

b. Původní text se skládá z n jednotek.

v. Původní text se skládá ze střídání nul a jedniček.

d. Původní text je náhodný řetězec bitů.

Rozhodnutí

a. Protože pak se tok šifrovaného textu bude shodovat s tokem klíčů. Pokud je klíč náhodný, je šifrovací text také náhodný. Části původního textu nejsou v ciphertextu zachovány.

b. Protože kde je výplň, ciphertext stream je výplň keystream. Pokud je klíčový proud náhodný, pak je šifrový text také náhodný, fragmenty původního textu se do šifrovacího textu neuloží.

c. V tomto případě je každý bit v proudu šifrovacího textu stejný jako v klíčovém proudu nebo v jeho doplňku. Výsledek je tedy také náhodný, pokud je klíčový proud náhodný.

d. V tomto případě je ciphertext jasně náhodný, protože operace EXKLUZIVNÍ NEBO dvou náhodných bitů má za následek náhodný bitový tok.

Posuvný registr zpětné vazby

Jedno vylepšení jednorázové podložky - (FSR - Feedback Shift Register). FSR lze implementovat buď v software, nebo v hardwaru, ale pro zjednodušení se podíváme na implementaci hardwaru. Posuvný registr zpětné vazby skládá se z posuvný registr a funkce zpětné vazbyjak je znázorněno na obr. 7.23.

Obr. 7.23.

Posuvný registr je posloupnost m buněk od b 0 do b m-1, kde je každá buňka navržena pro uložení jednoho bitu. Buňky jsou považovány za n-bitové slovo, nazývané na začátku „počáteční hodnota“ nebo zdroj... Kdykoli je třeba bit vyslat (například na signál v určitou dobu), je každý bit posunut o jednu buňku doprava. To znamená, že hodnota každé buňky je přiřazena pravé sousední buňce a přebírá hodnotu levé buňky. Buňka zcela vpravo b 0 je považována za výstup a poskytuje výstupní hodnotu (k i). Buňka zcela vlevo, b m-1, získá svou hodnotu podle hodnoty informací o funkci zpětné vazby. Označíme výstup funkce informacemi zpětné vazby b m. Funkce zpětné vazby určuje, jaké hodnoty mají buňky k výpočtu b m. Zpětnovazební posuvný registr může být lineární nebo nelineární.

Lineární zpětná vazba Shift Register (LFSR)... Předpokládejme, že b m je lineární funkce b 0, b 1, ... ..., b m-1, pro kterou

Posuvný registr lineární zpětné vazby pracuje s binárními číslicemi, takže násobení a sčítání jsou v poli GF (2), takže hodnota C i je buď 1 nebo 0, ale C 0 musí být 1, aby byly získány informace zpětné vazby. Operace přidání je EXKLUZIVNÍ NEBO operace. Jinými slovy,

Příklad 7.18

Vytvořme lineární zpětnovazební posuvný registr s 5 buňkami, ve kterých.

Rozhodnutí

Pokud C i \u003d 0, b i nehraje při výpočtu b m roli, znamená to, že b i není spojeno s funkcí zpětné informace. Pokud c i \u003d 1, b i je zahrnuto do výpočtu b m. V tomto příkladu jsou c 1 a c 3 nuly, což znamená, že máme pouze tři spojení. Obrázek 7.24 ukazuje obvod lineárního zpětnovazebního posuvného registru.

Obr. 7.24.

Příklad 7.19

Vytvořme lineární zpětnovazební posuvný registr se 4 buňkami, ve kterých ... Zobrazit hodnotu registru po 20 operace (směny) pokud je počáteční hodnota (0001) 2.

Rozhodnutí

Obrázek 7.25 ukazuje návrh a použití lineárního posuvného registru uzavřené smyčky pro šifrování.

Obr. 7.25.

Tabulka 7.6. ukazuje hodnotu klíčového streamu. Pro každý přechod se vypočítá první hodnota b 4 a poté se každý bit posune o jednu buňku doprava.

Tabulka 7.6.

současná hodnota	b 4	b 3	b 2	b 1	b 0	k i
Počáteční 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

Upozorňujeme, že proud klíčů je 1000100110101111 1001 ……. Na první pohled to vypadá jako náhodná sekvence, ale když se podíváme na velký počet transakcí (posunů), vidíme, že sekvence jsou periodické. Toto opakování 15 bitů je uvedeno níže.

Klíč streamu se generuje pomocí lineárního zpětnovazebního posuvného registru pseudonáhodná sekvence, ve kterém se opakují sekvence délky N. Tok je periodický. Závisí to na obvodu generátoru a počátečních informacích a nesmí překročit 2 m - 1. Každý obvod generuje m-bitové sekvence od všech nul po všechny. Pokud se však počáteční sekvence skládá pouze z nul, výsledek je k ničemu - původní text by byl proudem všech nul. Proto je taková počáteční sekvence vyloučena.

Ministerstvo školství a vědy

RUSKÁ STÁTNÍ SOCIÁLNÍ UNIVERZITA

FAKULTA INFORMAČNÍ TECHNOLOGIE

ODDĚLENÍ OCHRANY INFORMACÍ

Kryptografické metody a nástroje informační bezpečnost

Kurz práce

„R. lineární zpětnovazební posuvné registry jako generátory pseudonáhodných čísel "

Dokončeno:

student 3. ročníku

skupina KZOI-D-3

Larionov I.P.

Kontrolovány:

doc. Baranova E.K.

Moskva 2011
OBSAH

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

Teoretické základy práce…………………………………………4
1. Obecné informace o posuvných registrech se zpětnou vazbou ... ... ... ... ..4
  1. O šifrách streamů založených na РгСсЛОС …………………. ……… 10
  2. O lineární složitosti generované pseudonáhodné sekvence РгСсЛОС …………………………………. …… 12
  3. Na korelační nezávislosti generované sekvence pseudonáhodných čísel РгСсЛОС ……… ..… .13
  4. O jiných metodách otevírání generované sekvence pseudonáhodných čísel РгСсЛОС …………………………………… ..14
Softwarová implementace РгСсЛОС jako generátoru pseudonáhodné sekvence….…………………………….15
1. Zobecněné schéma algoritmu ………………………………… ... 15
2. Popis programových modulů a rozhraní. ……………… .16
3. Uživatelská příručka ……………………………………… ... 20

Závěr ………………………………………………………………22

Bibliografie………………………………………………….....23

Příloha A ….………………………………………………………..24

ÚVOD

Účelem této práce je vyvinout softwarovou aplikaci, která implementuje provoz generátoru pseudonáhodných čísel na posuvných registrech se zpětnou vazbou. Rozvoj této aplikace s grafickým rozhraním se provádí v jazyceC ++ pro Windows.

S rozvojem kryptografie ve dvacátém století čelili kryptografové výzvě vytvářet šifrovací zařízení a stroje, které by mohly rychle a spolehlivě šifrovat a dešifrovat zprávy. Tento požadavek splňovaly symetrické šifrovací systémy, které již byly v té době otevřené, ale jejich slabou stránkou byla silná závislost na klíči a jeho utajení. Nejpohodlnější třídou šifer, kterou lze pro tento účel použít, jsou šifry gama. Nastal problém s generováním gama, které nemohlo být detekováno při dešifrování zprávy. Teoreticky to bylo možné, pokud bylo gama pokaždé náhodné a v průběhu času se měnilo. Při použití zcela náhodně se měnícího gamutu by však bylo obtížné zajistit spolehlivé šifrování a dešifrování zprávy. Cryptographers řešili tento problém, jehož cílem bylo najít algoritmus, který implementuje generování náhodného gama podle určitého pravidla, taková sekvence by měla obsahovat nuly a jednotky v „údajně“ náhodných pozicích a počet jednotek a nul by měl být přibližně stejný. Taková náhodná sekvence byla volánapseudonáhodné,protože to bylo generováno podle určitého pravidla, a ne náhodně.

Řešení bylo brzy nalezeno. Studium vlastností posuvných registrů umožnilo stanovit, že posuvné registry se zpětnou vazbou jsou díky své vnitřní struktuře schopné generovat pseudonáhodné sekvence, které jsou dostatečně odolné vůči dešifrování.

1. Teoretické základy práce

1.1 Obecné informace o posuvných registrech lineární zpětné vazby

Sekvence posuvných registrů se používají jak v kryptografii, tak v teorii kódování. Jejich teorie je dobře vyvinutá, šifry proudů založené na posuvných registrech byly dlouho před příchodem elektroniky tahounem vojenské kryptografie.

Posuvný registr se zpětnou vazbou (dále jen РгСсОС) se skládá ze dvou částí: posuvného registru a funkce zpětné vazby. Posuvný registr je sekvence bitů. Je určen počet bitůdélka posuvného registruje-li délka n bitů, je volán registrn-bitový posuvný registr... Kdykoli je třeba bit extrahovat, posunou se všechny bity posuvného registru doprava o 1 pozici. Nový bit zcela vlevo je funkcí všech ostatních bitů v registru. Výstup posuvného registru je jeden, obvykle nejméně významný, bit.Období registru směn je délka výsledné sekvence před začátkem jejího opakování.

Obrázek Zpětná vazba Shift Register

Shift registry našel použití velmi rychle v proudových šiferách, protože byly snadno implementovány pomocí digitálního hardwaru. V roce 1965 vyvinul Ernst Selmer, hlavní kryptograf norské vlády, teorii sekvencí posuvných registrů. Solomon Golomb, matematik NSA, napsal knihu popisující některé jeho výsledky a Selmerovy výsledky. Nejjednodušší forma zpětnovazebního posuvného registru jeposuvný registr lineární zpětné vazby (posuvný registr lineární zpětné vazby, dále LFSR nebo РгСсЛОС) ... Zpětná vazba takových registrů je jednoduše XOR (modulo two addition) některých bitů registru, seznam těchto bitů se nazývá sekvence klepnutí. Tento registr se někdy nazývá konfigurace Fibbonacci. Vzhledem k jednoduchosti posloupnosti zpětné vazby lze pro analýzu PrCcVOC použít poměrně dobře propracovanou matematickou teorii. Analýzou výsledných výstupních sekvencí můžete ověřit, že jsou tyto sekvence dostatečně náhodné, aby byly bezpečné. PrCcLOC je nejčastěji používaný posuvný registr v kryptografii.

Kreslení PrCsLOS Fibbonacci

Obecně platí, že n -bit PgCsLOC může být v jednom zN \u003d 2 n -1 vnitřní stavy. To znamená, že teoreticky může takový registr generovat pseudonáhodnou sekvenci s periodou T \u003d 2n -1 bity. (Počet vnitřních stavů a \u200b\u200bobdobí jsou stejnéN \u003d T max \u003d 2 n -1, protože naplnění PrCcLOC nulami způsobí, že posuvný registr vytvoří nekonečnou sekvenci nul, což je naprosto zbytečné). Pouze pro určité sekvence odboček PrCcLOC projde všemi 2n -1 interní stavy, takové PrCsLOC jsouPrCcLOC s maximální periodou... Výsledný výsledek se nazýváM-sekvence.

Příklad ... Na obrázku níže je znázorněn 4bitový PrCcLOC klepnutý z prvního a čtvrtého bitu. Pokud je inicializován s hodnotou 1111, pak před opakováním bude registr předpokládat následující interní stavy:

Číslo směnného času (interní stav)	Stav registrace	Výstupní bit
Číslo směnného času (interní stav)		Výstupní bit
Počáteční hodnota














15 (návrat do původního stavu)
16 (opakovat stavy)

Výstupní sekvence bude řetězec nejméně významných bitů: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 s periodou T \u003d 15, celkový počet možné vnitřní stavy (kromě nuly),N \u003d 2 4 -1 \u003d 16-1 \u003d 15 \u003d T max proto je výstupní sekvenceM -sekvence.

Aby konkrétní PrCcLOC měl maximální periodu, musí být polynom vytvořený z větvové sekvence a konstanty 1 primitivní modulo 2. Polynom je reprezentován jako součet stupňů, například polynom stupněn vypadá takto:

anxn + a n-1 x n-1 +… + a 1 x 1 + a 0 x 0 \u003d anxn + a n-1 x n-1 +… + a 1 x + a 0, kde a i \u003d (0, 1) pro i \u003d 1… n, axi - označuje číslici.

Stupeň polynomu je délka posuvného registru. Primitivní polynom stupně n je neredukovatelný polynom, který dělí x2n - 1 +1, ale ne dělitel xd +1 pro všechny d dělitele 2n -jeden. Odpovídající matematickou teorii lze nalézt v.

Obecně neexistuje lehká cesta generovat primitivní polynomy daného stupně modulo 2. Nejjednodušší způsob je náhodný výběr polynomu a kontrola jeho primitivnosti. To není snadné a je to něco jako kontrola, zda je náhodně vybrané číslo jednoduché - ale mnoho matematických softwarových balíčků dokáže tento problém vyřešit.

Některé, ale určitě ne všechny polynomy různých stupňů, primitivní mod 2, jsou uvedeny níže. Například záznam

(32, 7, 5, 3, 2, 1, 0) znamená, že následující polynom je primitivní modulo 2: x32 + x 7 + x 5 + x 3 + x 2 + x + 1.

To lze snadno zobecnit pro PrCCLOC s maximální periodou. První číslo je délka PrCCLOC. Poslední číslo je vždy 0 a lze jej vynechat. Všechna čísla, kromě 0, určují sekvenci prstů počítanou od levého okraje posuvného registru. To znamená, že členové polynomu s nižším stupněm odpovídají pozicím blíže k pravému okraji registru.

Pokračování příkladu, zápis (32, 7, 5, 3, 2, 1, 0) znamená, že pro odebraný 32bitový posuvný registr je nový bit, nový bit generován XORing třicetisekundový, sedmý, pátý, třetí, druhý a první bit. , výsledný PrCcLOC bude mít maximální délku, cyklicky přes 232 -1 hodnot.

Obrázek 4 32bitový PrCcLOC s maximální délkou

Zvážit programový kód PrCcLOC, ve kterém je větvová sekvence charakterizována polynomem (32, 7, 5, 3, 2, 1, 0). V jazyce C to vypadá takto:

int LFSR () (

statický nepodepsaný dlouhý ShiftRegister \u003d 1;

/ * Všechno kromě 0. * /

ShiftRegister \u003d (((((ShiftRegister \u003e\u003e 31)

^ (ShiftRegister \u003e\u003e 6)

^ (ShiftRegister \u003e\u003e 4)

^ (ShiftRegister \u003e\u003e 2)

^ (ShiftRegister \u003e\u003e 1)

^ ShiftRegister))

A 0x00000001)

<<31)

| (ShiftRegister \u003e\u003e 1);

vrátit ShiftRegister & 0 x 00000001;)

Pokud je posuvný registr delší než počítačové slovo, kód se stává složitějším, ale ne moc. V aplikaciB je uvedena tabulka některých primitivních polynomů modulo 2, budeme ji v budoucnu používat k identifikaci některých vlastností těchto polynomů, stejně jako v softwarové implementaci k definování sekvence odklonu.

Vezměte prosím na vědomí, že všechny prvky tabulky mají lichý počet koeficientů. Taková dlouhá tabulka je k dispozici pro další práci s PrCcLOC, protože PrCcLOC se často používá pro kryptografii s proudovými šifry a v generátorech pseudonáhodných čísel. V našem případě můžete použít polynomy s nejvyšším stupněm nejvýše sedmi.

Pokud je p (x) primitivní, pak je primitivní a xn p (1 / x), takže každý prvek tabulky ve skutečnosti definuje dva primitivní polynomy. Například pokud (a, b, 0) je primitivní, pak (a, a-b, 0) je také primitivní. Pokud je to primitivní (a, b, c, d, 0), pak je to také primitivní (a, a-d, a-c, a-b, 0). Matematicky:

je-li x primitivnía + x b +1, pak je to primitivní a xa + x a-b +1,

je-li x primitivnía + x b + x c + x d +1, pak je to primitivní a xa + x a-d + x a-c + x a-b +1. Primitivní trinomialy se nejrychleji implementují do softwaru, protože ke generování nového bitu je třeba XORovat pouze dva bity posuvného registru (nulový člen se nebere v úvahu, tj. X0 \u003d 1, viz příklad výše). Ve skutečnosti jsou všechny polynomy zpětné vazby zobrazené v tabulce řídké, to znamená, že mají málo koeficientů. Řídkost je vždy zdrojem slabosti, což někdy stačí k prolomení algoritmu. Pro kryptografické algoritmy je mnohem lepší použít husté primitivní polynomy, ty s mnoha koeficienty. Použitím hustých polynomů, zejména jako součást klíče, lze použít mnohem kratší PsCLOC.

Generování hustých primitivních polynomů mod 2 není snadné. Obecně platí, že ke generování primitivních polynomů stupně k potřebujete znát faktorizaci čísla 2k -1.

Samy o sobě jsou PrCcLOC dobré generátory pseudonáhodných sekvencí, ale mají některé nežádoucí nenáhodné (deterministické) vlastnosti. Následné bity jsou lineární, takže jsou pro šifrování zbytečné. Pro PrCcLOC délky n je vnitřní stav předchozích n výstupních bitů generátoru. I když je schéma zpětné vazby utajeno, lze jej určit z 2n výstupních bitů generátoru pomocí vysoce účinného algoritmu Berlekamp-Massey.

Kromě toho velká náhodná čísla generovaná pomocí po sobě jdoucích bitů této sekvence jsou vysoce korelována a pro některé typy aplikací nejsou náhodná vůbec. Navzdory tomu se PgCsLOC často používají k vytváření šifrovacích algoritmů jako komponent šifrovacích systémů a algoritmů.

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

Základní přístup k návrhu generátoru streamu klíčů založeného na PrCsLOS je jednoduchý. Nejprve se vezme jeden nebo více PrCCLOC, obvykle s různými délkami a různými polynomy zpětné vazby. (Pokud jsou délky coprime a všechny zpětnovazební polynomy jsou primitivní, pak bude mít generovaný generátor maximální délku.) Klíčem je počáteční stav registrů PrCCLOC. Pokaždé, když je potřeba nový bit, posuňte registry PrCCLOC o jeden bit (někdy se tomu říká taktování). Výstupní bit je funkcí, nejlépe nelineární, některých bitů v registrech PrCCLOC. Tato funkce se nazývá kombinující funkce a celý generátor se nazývá kombinující generátor. (Pokud je výstupní bit funkcí jediného PrCcLOC, pak se generátor nazývá generátor filtru.) Hodně z teorie pro tento druh zařízení vyvinuli Selmer a Neal Zierler. Lze zavést řadu komplikací. Některé generátory používají různé taktovací frekvence pro různé PgCLOC, někdy frekvence jednoho generátoru závisí na výstupu jiného. Jedná se o všechny elektronické verze nápadů na šifrovací stroje, které se objevily před druhou světovou válkou a které se nazývají řízené generátory. taktovací frekvence (generátory řízené hodinami ). Ovládání hodin může být dopředné, kde výstup jednoho PrCcLOC řídí hodiny jiného PrCcLOC, nebo uzavřená smyčka, kde výstup jednoho PrCcLOC ovládá jeho vlastní hodiny. I když jsou všechny tyto generátory citlivé, alespoň teoreticky, na vnořené útoky a pravděpodobnou korelaci, mnoho z nich je stále bezpečných.

Ian Cassells, bývalý vedoucí katedry čisté matematiky v Cambridge a kryptoanalytik v Bletchly Parku, řekl, že „kryptografie je směsicí matematiky a zmatku a bez zmatku lze matematiku použít proti vám.“ Myslel to v šifrech proudu, aby to zajistil maximální délka a další vlastnosti, určité matematické struktury, jako je PrCcLOC, jsou zapotřebí, ale je třeba zavést nějaký složitý nelineární nepořádek, aby někdo zabránil získání obsahu registru a porušení algoritmu. Tato rada platí také pro blokové algoritmy.

Většina skutečných streamovacích šifer je založena na PrCCLOC. Dokonce i v raných dobách elektroniky nebylo jejich budování obtížné. Posuvný registr není nic jiného než pole bitů a posloupnost zpětné vazby je sada bran XOR. I při použití VLSI poskytuje proudová šifra založená na RgCsLOS značné zabezpečení prostřednictvím několika logických bran. Problém PrCsLOC je, že jejich softwarová implementace je velmi neefektivní. Musíte se vyhnout řídkým zpětnovazebním polynomům - usnadňují úniky korelace - a husté zpětnovazebné polynomy jsou neúčinné.

Toto odvětví kryptografie rychle roste a je pod dohledem vládyNSA ... Většina vývojů je klasifikována - mnoho dnes používaných vojenských šifrovacích systémů je založeno na RgClCS. Většina počítačů Cray (Cray 1, Cray X-MP, Cray Y-MP) má velmi podivnou instrukci, běžně označovanou jako „počet obyvatel“. Počítá počet jednotek v registru a lze jej použít jak k efektivnímu výpočtu Hammingovy vzdálenosti mezi dvěma binárními slovy, tak k implementaci vektorizované verze PrCCLOC. Tato instrukce je považována za kanonickou instrukci NSA a je povinná téměř ve všech smlouvách týkajících se počítačů.

Na druhé straně bylo prolomeno překvapivě velké množství zdánlivě složitých generátorů posuvných registrů. A samozřejmě počet takových generátorů napadených vojenskými kryptanalytickými institucemi, jako je NSA, je ještě větší.

1.3 O lineární složitosti generované sekvence pseudonáhodných čísel PrCcLOC

Streamové šifry se často analyzují snadněji než blokové šifry. Například lineární složitost nebo lineární interval je důležitým parametrem používaným k analýze generátorů založených na PrCsLOC. Je definována jako délka n nejkratší PgCVOC, která může simulovat výstup generátoru. Jakákoli sekvence generovaná strojem s konečným stavem přes konečné pole má konečnou lineární složitost. Lineární složitost je důležitá, protože s jednoduchým algoritmem zvaným Berlekamp-Masseyho algoritmus je možné určit tento PrCCLOC zkoumáním pouze 2 n bitů klíčového proudu. Znovu vytvořením požadovaného PrCCLOC rozbijete proudovou šifru.

Tuto myšlenku lze rozšířit z polí na kroužky a na případy, kdy je výstupní sekvence považována za čísla v lichém charakteristickém poli. Další expanze vede k zavedení konceptu profilu lineární složitosti, který definuje lineární složitost posloupnosti, jak se prodlužuje. Existují také koncepty sférické a kvadratické složitosti. V každém případě nezapomeňte, že vysoká lineární složitost nemusí nutně zaručovat bezpečnost generátoru, ale nízká lineární složitost naznačuje nedostatečnou bezpečnost generátoru.

1.4 Na korelační nezávislosti generované sekvence pseudonáhodných čísel PrCcVOC

Kryptografové se snaží získat vysokou lineární složitost nelineárním spojením výsledků některých výstupních sekvencí. Nebezpečí zde spočívá v tom, že jednu nebo více interních výstupních sekvencí - často jen výstupy jednotlivých PrCsLOC - lze spojit běžným proudem klíčů a otevřít pomocí lineární algebry. Toto se často označuje jako korelační útok nebo útok rozděl a panuj. Thomas Siegenthaler ukázal, že nezávislost korelace lze přesně určit a že existuje kompromis mezi nezávislostí korelace a lineární složitostí.

Hlavní myšlenkou útoku na korelaci je detekovat určitou korelaci mezi výstupem generátoru a výstupem jedné z jeho základních částí. Poté pozorováním výstupní sekvence lze získat informace o tomto mezilehlém výstupu. Pomocí těchto informací a dalších korelací je možné sbírat data na dalších mezilehlých výstupech, dokud nebude generátor hacknut.

Korelační útoky a jejich variace, jako jsou rychlé korelační útoky, byly úspěšně použity proti mnoha generátorům klíčových toků založených na PgCLOC, což nabízí kompromis mezi výpočetní složitostí a efektivitou.

1.5 O dalších metodách otevírání generované sekvence pseudonáhodných čísel PrCcLOC

Existují i \u200b\u200bjiné způsoby, jak zaútočit na generátory klíčových proudů. Test lineární konzistence se pokusí pomocí maticové techniky najít nějakou podmnožinu šifrovacího klíče. Existuje také „útok typu„ setkat se ve střední konzistenci “. Algoritmus lineárního syndromu je založen na schopnosti napsat fragment výstupní sekvence ve formě lineární rovnice. Existuje nejlepší aproximační útok afflne a útok odvozené sekvence. Na proudové šifry lze také použít metody diferenciální a lineární kryptoanalýzy.

2. Popis softwarové implementace РгСсЛОС jako generátoru pseudonáhodné sekvence

2.1 Zobecněné schéma algoritmu

2.2 Popis softwarových modulů a rozhraní

Obrázek 3 níže zobrazuje okno programu.

Obrázek Rozhraní programu

Nabídka má následující funkce:

Soubor-\u003e Uložit zprávu

Tato funkce vytvoří soubor se zprávou, který zaznamenává počáteční stav PrCcLOC, odbočovací sekvenci, období přijaté pseudonáhodné bitové sekvence, samotnou sekvenci a tabulku stavů. Pokud byl soubor úspěšně uložen, zobrazí se zpráva o úspěšném uložení (obrázek 4). Doporučená přípona souboru zprávy *.txt.

Obrázek

Soubor-\u003e Konec

Tato funkce zajišťuje zavření aplikace.

Nastavit sekvenci větví

Tato funkce vytváří sekvenci klepnutí čtením hodnot z buněk, které uživatel zaškrtl na obrazovce. Poté uživatele upozorní na vytvoření sekvence odklonu (obrázek 5). Sekvence klepnutí určuje, ze kterých klopných obvodů zpětné vazby posuvného registru bude jítXOR k vytvoření offsetového bitu. Ve výchozím nastavení je zpětná vazba od prvního spouštěče vždy přítomna, při absenci dalších spojení bude proveden posun vlevo s permutací nejméně významného bitu do polohy nejvýznamnějšího.

Obrázek

Nastavte počáteční hodnotu

Tato funkce čte uživatelem zadanou hodnotu počátečního registru z oknaUpravit 1 a zkontroluje zadanou hodnotu podle zadaných podmínek: zadaný řádek není prázdný (obrázek 6), zadaný řádek má délku osm (8bit \u003d 1 bajt, obrázek 7), zadaný řádek obsahuje pouze nuly a / nebo jedničky (obrázek 8), zadaný řádek je nenulový (Obrázek 9). Jinak se zobrazí chybové zprávy, uživatel je musí opravit a znovu stisknout tlačítko. Pokud je kontrola úspěšná, zapíše se počáteční hodnota do stavové tabulky v řádku „Počáteční“ a bude vydáno oznámení (obrázek 10).

Obrázek

Posuňte registr

Tato funkce emuluje činnost posuvného registru. Postupně provádějící 256 posunů, každý posun tvoří výstupní bit pseudonáhodné sekvence a nový stav registru. Jakmile je stav registru roven počátečnímu, je v poli vypočítána a zobrazena periodaMemo 1 přijal pseudonáhodnou sekvenci.

Nápověda-\u003e O programu

Tato funkce se zobrazí stručný popis programy a pokyny (Obrázek 11).

Obrázek

Nápověda-\u003e O autorovi

Tato funkce zobrazuje informace o autorovi programu (obrázek 12).

Obrázek

2.3 Uživatelská příručka

Nejprve nastavte počáteční stav registru. Musí obsahovat osm binárních znaků. Jinak se zobrazí chybová zpráva a budete muset opravit zadanou hodnotu. Stiskněte položku nabídky „Nastavit počáteční hodnotu“.
Poté zaškrtněte políčka v zaškrtávacích polích zpětných vazeb registrů (sekvence větví). Stiskněte položku nabídky „Nastavit sekvenci větví“.
Poté klikněte na položku nabídky „Shift case“. Než to uděláte, ujistěte se, že jste dokončili kroky 1 a 2, jinak dojde k chybě softwaru.
Po obdržení výsledků je můžete uložit kliknutím na položku nabídky „Soubor-\u003e Uložit zprávu“. Než to uděláte, ujistěte se, že jste dokončili kroky 1-3, jinak dojde k chybě softwaru.
Nápovědu získáte kliknutím na položky nabídky „Soubor-\u003e O aplikaci“, „Soubor-\u003e O autorovi“.
Chcete-li vidět fungování registru s dalšími hodnotami sekvence odboček a počátečním stavem registru, opakujte kroky v krocích 1-3 v pořadí a zadejte další parametry.

ZÁVĚR

V tomto článku jsme považovali PgCCLOC za generátory pseudonáhodných čísel. Program může sloužit jako vizuální demonstrace principů činnosti posuvných registrů se zapnutou lineární zpětnou vazbouXOR ... Lze jej použít ke studiu principu vytváření pseudonáhodné posloupnosti bitů, vztahu mezi počáteční hodnotou registru a hodnotou pseudonáhodné posloupnosti, stahovací posloupnosti a periody. Výsledný pseudonáhodný gamut lze použít v jiném softwarová aplikace (například softwarová implementace gama šifry).

V tuto chvíli se tyto registry nepoužívají jako nezávislé generátory pseudonáhodných čísel, ale jsou součástí složitějších zařízení. Byli to však oni, kdo otevřel nové směry v matematice (hledání primitivních polynomů v konečných polích, matematické metody rozbíjení generátorů pseudonáhodných čísel). Bez znalosti principů fungování generátorů založených na PrCCLOS je nemožné pochopit provoz složitějších zařízení. Díky své jednoduché hardwarové implementaci jsou široce používány v technologii. Studie РгСсОС vedla ke vzniku nových šifer - blokových a streamových - založených na těchto typech registrů (šmyková permutační šifra,DES atd.; EDS, hash funkce).

Obecně platí, že výzkum v této oblasti vážně tlačil na vývoj kryptografie a kryptoanalytiky, počítačů a zařízení a také umožnil implementovat řadu dalších užitečné funkce (například kódy pro opravu cyklu).

BIBLIOGRAFIE

Schneier Bruce. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C. - M.: Triumph, 2002
A.V. Babash Kryptografické a automaticko-teoretické aspekty moderní informační bezpečnosti. Svazek 1 - M.: Vyd. Centrum EAOI, 2009 .-- 414 s.
E.S. Selmer. Monografie: „Lineární rekurze v konečném poli“. Bergen University, Norsko, 1966.
N. Zierler a J. Brillhart. „On primitive trinomials modulo 2“, Information and Control journal, vydání 13, č. 6. prosince 1968, str. 541-544.
K.Kh. Meyer a W.L.Tuchman. „Pseudonáhodné kódy lze rozluštit,“ časopis Electronic Design, č. 23. listopadu 1972.
J.L. Massey. "Zobecnění posuvných registrů a dekódování kódu Bose-Chowdhury-Hawkingham",Transakce IEEE na teorii informací, v. IT -15, č ... 1. ledna 1969, s. 122-127.
S.U. Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (dotisk Aigean Park Press, 1982).

Příloha A

Tabulka některých primitivních polynomů 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 počátečního stavu (IS)

kontrola správného vstupu

Vydání chybové zprávy

Instalace sekvence větví

Zápis IS do tabulky stavů

Zaznamenat i -tý stav registru a výstupní bit do stavové tabulky

IS \u003d\u003d Aktuální stav

Ukládání výsledků

Výstup pseudonáhodné sekvence

Výstup

Běh

Ano

V posuvném registru s lineární zpětnou vazbou se rozlišují dvě části (moduly): samotný posuvný registr a obvody (nebo podprogramy), které vypočítávají hodnotu vloženého bitu. Registr se skládá z funkčních buněk (nebo bitů strojového slova nebo několika slov), z nichž každá ukládá aktuální stav jednoho bitu. Počet buněk se nazývá délka registru. Bity (buňky) jsou obvykle očíslovány čísly, z nichž každé je schopné bit uložit, a vypočítaný bit je vložen do buňky a z buňky je extrahován další vygenerovaný bit, který je vytlačen. Výpočet bitu, který má být vložen, se obvykle provádí před posunem registru a až po posunutí se do buňky vloží hodnota vypočítaného bitu.

Perioda posuvného registru je minimální délka přijaté sekvence před začátkem jejího opakování. Jelikož registr bitových buněk má pouze různé nenulové stavy, potom v zásadě nemůže doba registru překročit toto číslo. Pokud se doba registrace rovná tomuto číslu, pak se takový registr nazývá registr maximální doby.

U RSLOS je funkce zpětné vazby lineární booleovská funkce ze stavů všech nebo některých bitů registru. Například součet modulo two nebo jeho logická inverze je lineární logická funkce (operace XOR, označená jako ve vzorcích) a v takových registrech se nejčastěji používá.

V tomto případě se obvykle nazývají ty bity, které jsou proměnnými funkce zpětné vazby kohoutky.

Registr je řízen v hardwarových implementacích použitím posuvného impulzu (jinak nazývaného hodiny nebo synchronizační impuls) do všech buněk, v buňkách programu - podle programový cyklus, včetně výpočtu zpětnovazební funkce a bitového posunu ve slově.

Během každého časového kroku se provádějí následující operace:

Registr posunutí lineární zpětné vazby

Logická operace XOR (exkluzivní OR) je tedy brána jako funkce zpětné vazby, tj .:

Vlastnosti primitivních polynomů

Vlastnosti

Vlastnosti sekvence vydané RSLOS úzce souvisí s vlastnostmi přidruženého polynomu. Nenulové koeficienty se nazývají kohoutkystejně jako odpovídající buňky registru dodávající hodnoty argumentů do funkce zpětné vazby.

Lineární složitost

Lineární složitost binární sekvence je jednou z nejdůležitějších charakteristik provozu RSLOS. Pojďme si představit následující notaci:

Definice

Lineární složitost nekonečné binární sekvence nazývá číslo, které je definováno takto:

Lineární složitost konečné binární sekvence se nazývá číslo, které se rovná délce nejkratší RLOS, která generuje sekvenci, která má jako první členy.

Vlastnosti lineární složitosti

Dovolit a být binární sekvence. Pak:

Korelační nezávislost

K dosažení vysoké lineární složitosti se kryptografové snaží nelineárně kombinovat výsledky více výstupních sekvencí. V tomto případě existuje nebezpečí, že jeden nebo několik výstupních sekvencí (často i výstupy jednotlivých RFLOS) lze spojit společným proudem klíčů a otevřít pomocí lineární algebry. Hackování založené na takové zranitelnosti se nazývá korelační pitva... Thomas Sigenthaler ukázal, že nezávislost korelace lze přesně definovat a že existuje kompromis mezi nezávislostí korelace a lineární složitostí.

Hlavní myšlenkou tohoto hacku je najít určitou korelaci mezi výstupem generátoru a výstupem jedné z jeho částí. Poté pozorováním výstupní sekvence můžete získat informace o tomto mezilehlém kolíku. Pomocí těchto informací a dalších korelací je možné sbírat data o dalších přechodných závěrech, dokud nebude generátor hacknut.

Korelační útoky nebo variace, jako jsou rychlé korelační útoky, byly úspěšně použity proti mnoha generátorům klíčových toků založených na lineárním zpětnovazebním posuvném registru, které zahrnují kompromis mezi výpočetní složitostí a efektivitou.

Příklad

Pro RSLOS s přidruženým polynomem má vygenerovaná sekvence tvar. Předpokládejme, že sekvence je zapsána do registru před zahájením procesu, pak bude doba generovaného bitového toku 7 s následující sekvencí:

Číslo kroku	stav	Vygenerovaný bit
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Jelikož se vnitřní stav v sedmém kroku vrátil do svého původního stavu, bude se od dalšího kroku opakovat. Jinými slovy, období posloupnosti se ukázalo být 7, což se stalo kvůli primitivitě polynomu.

Algoritmy pro generování primitivních polynomů

Připravené stoly

Výpočet primitivnosti polynomu je poměrně obtížný matematický problém. Proto existují hotové tabulky, které udávají počet sekvencí klepnutí, které poskytují maximální dobu generátoru. Například existuje posloupnost pro 32bitový posuvný registr. To znamená, že 31., 30., 29., 29., 27., 25. a 0. bit musí být XORed, aby se vygeneroval nový bit. Kód takového RSLOS v jazyce C je následující:

Int LFSR (void) (static unsigned long S \u003d 1; S \u003d (((((S \u003e\u003e 31) ^ (S \u003e\u003e 30) ^ (S \u003e\u003e 29) ^ (S \u003e\u003e 27) ^ (S \u003e\u003e 25) ^ S) a 1)<< 31 ) | (S>\u003e 1); návrat S & 1; )

Softwarové implementace generátorů RSLOS jsou poměrně pomalé a fungují rychleji, pokud jsou psány v assembleru a ne v C. Jedním z řešení je použití 16 RSLOS paralelně (nebo 32, v závislosti na délce slova v architektuře konkrétního počítače). V takovém schématu se používá pole slov, jejichž velikost se rovná délce RSLOS a každý bit slova v poli odkazuje na svůj vlastní RSLOS. Za předpokladu, že jsou použita stejná pořadová čísla prstů, může to poskytnout významné zvýšení výkonu. [je nutný příklad kódu] (Viz: bitslice).

Galoisova konfigurace

Galoisova konfigurace lineárního zpětnovazebního posuvného registru

Lze také upravit smyčku zpětné vazby. V tomto případě generátor nebude mít větší kryptografickou sílu, ale bude snazší jej implementovat do softwaru. Namísto použití bitů sekvence prstů ke generování nového bitu nejvíce vlevo je každý bit F-sekvence XORed a nahrazen výstupem generátoru, pak se výsledek generátoru stane novým bitem nejvíce vlevo. V jazyce C to vypadá takto:

Int LFSR (void) (static unsigned long Q \u003d 1; Q \u003d (Q \u003e\u003e 1) ^ (Q & 1? 0x80000057: 0); return Q & 1;)

Výplatou je, že všechny XOR jsou prováděny v jedné operaci.

je možné dokázat, že konfigurace Fibonacci uvedená v první a zde uvedená konfigurace Galois dává stejné sekvence (délka 2 32 −1), ale fáze se od sebe posunula
smyčka pevného počtu volání LFSR v konfiguraci Galois je asi dvakrát rychlejší než v konfiguraci Fibonacci (kompilátor MS VS 2010 na Intel Core i5)
všimněte si, že v konfiguraci Galois je pořadí bitů ve zpětnovazebním slově obráceno ve srovnání s konfigurací Fibonacci

Příklady generátorů

Stop-and-go generátory

Stop-and-go střídavý generátor

Tento generátor používá výstup jednoho RSLOS k řízení taktovací frekvence druhého RSLOS. Hodinový výstup RSLOS-2 je řízen výstupem RSLOS-1, takže RSLOS-2 může změnit svůj stav v čase t, pouze pokud byl výstup RSLOS-1 v čase t-1 roven jedné. Toto schéma však neodolalo zúčtování korelací.

Proto byl na základě stejné myšlenky navržen vylepšený generátor. Říká se mu střídavý generátor typu stop-and-go. Používá tři RFLO různých délek. RSLOS-2 je taktován, když je výstup RSLOS-1 roven jedné, a RSLOS-3, když je výstup RSLOS-1 nulový. Výstup generátoru je součet modulo 2 u RSLOS-2 a RSLOS-3. Tento generátor má dlouhou dobu a velkou lineární složitost. Jeho autoři také ukázali metodu otevření korelace RSLOS-1, což však generátor příliš neoslabí.

Gollmannova kaskáda

Stupeň Gollmann je zesílená verze generátoru stop-and-go. Skládá se ze sekvence RSLOS, jejichž taktování je řízeno předchozím RSLOS. Pokud je výstup RSLOS-1 v čase t 1, pak je RSLOS-2 taktován. Pokud je výstup RSLOS-2 v čase t 1, pak je RSLOS-3 taktován atd. Posledním výstupem RFLOS je výstup generátoru. Pokud je délka všech RFLOS stejná a rovná se n, pak se rovná lineární složitost systému k LLS.

Tato myšlenka je jednoduchá a lze ji použít ke generování sekvencí s velkými periodami, velkou lineární složitostí a dobrými statistickými vlastnostmi. Bohužel jsou však citliví na útok zvaný lock-in. Pro větší trvanlivost se doporučuje použít k alespoň 15. Navíc je lepší použít více krátkých RFLOS než méně dlouhých RFLO.

Generátor prahových hodnot

Tento generátor se pokouší obejít bezpečnostní problémy předchozích generátorů pomocí variabilního počtu posuvných registrů. Teoreticky, když se používá větší počet posuvných registrů, zvyšuje se složitost šifry, což bylo provedeno v tomto generátoru.

Tento generátor se skládá z velkého počtu posuvných registrů, jejichž výstupy směřují do funkce majorizace. Pokud je počet jednotek na výstupech registru větší než polovina, generátor vydá jeden. Pokud je počet nul na výstupech více než polovina, generátor vydá nulu. Aby bylo možné porovnat počet nul a jedniček, musí být počet posuvných registrů lichý. Délky všech registrů musí být relativně jednoduché a polynomy zpětné vazby musí být primitivní, aby období generované sekvence bylo maximální.

V případě tří posuvných registrů může být generátor reprezentován jako:

Tento generátor je podobný generátoru Geff, kromě toho, že generátor prahových hodnot má lineárnější složitost. Jeho lineární složitost je:

kde ,, jsou délky prvního, druhého a třetího posuvného registru.

Jeho nevýhodou je, že každý výstupní bit poskytuje určité informace o stavu posuvného registru. Přesněji 0,189 bitů. Proto tento generátor nemusí odolat korelačnímu útoku.

Jiné typy

Samovolné ředění

Self-decimating generators are those that control their own frequency. Byly navrženy dva typy těchto generátorů. První se skládá z lineárního zpětnovazebního posuvného registru a některých obvodů, které blokují tento registr, v závislosti na tom, jaké jsou výstupní hodnoty posuvného registru. Pokud je výstup RSLOS roven jednomu, pak je registr taktován dkrát. Pokud je výstup nulový, pak je registr taktován k krát. Druhý má téměř stejný design, ale mírně upravený: v hodinovém obvodu vstup jako kontrola 0 nebo 1 nepřijímá samotný výstupní signál, ale XOR určitých bitů posuvného registru s lineární zpětnou vazbou. Bohužel tento druh generátoru není bezpečný.

Vícerychlostní generátor s interním produktem

Tento generátor používá dva lineární zpětnovazební posuvné registry s různými hodinovými frekvencemi: RSLOS-1 a RSLOS-2. Frekvence hodin RSLOS-2 je dkrát vyšší než frekvence RSLOS-1. Jednotlivé bity těchto registrů jsou ANDed společně. Poté se na výstupech operace AND provede XOR. Výstupní sekvence je odstraněna z tohoto bloku XOR. Tento generátor opět není bezchybný (Nevydržel otevření lineární konzistence. Pokud je délka RSLOS-1, je délka RSLOS-2 a d je poměr hodinové frekvence, pak vnitřní stav generátoru lze získat z výstupní sekvence délky), ale má vysokou lineární složitost a vynikající statistický výkon.

Definice

Posuvný registr lineární zpětné vazby se skládá ze dvou částí: samotného posuvného registru a funkce zpětné vazby. Registr se skládá z bitů, jeho délka je počet těchto bitů. Když se má bit načíst, všechny bity v registru se posunou o jednu pozici doprava. Nový bit zcela vlevo je určen funkcí zbývajících bitů. Z registru vychází jeden, obvykle nejméně významný bit. Perioda posuvného registru je délka přijaté sekvence před začátkem jejího opakování.

Pro RSLOS je funkcí zpětné vazby součet modulo 2 (xor) některých volaných bitů registru kohoutky.

Posuvný registr zpětné vazby lineární délky se skládá z očíslovaných buněk, z nichž každá je schopná uložit bit a má jeden vstup a jeden výstup, stejně jako hodinový signál, který řídí posun dat. Během každé časové jednotky se provádějí následující operace:

Registr posunutí lineární zpětné vazby

Logická operace XOR (exkluzivní OR) je tedy brána jako funkce zpětné vazby, tj .:

Vlastnosti

Vlastnosti generované sekvence RSLOS úzce souvisí s vlastnostmi přidružený polynom přes pole. Nenulové koeficienty se nazývají kohoutkystejně jako odpovídající buňky registru dodávající hodnoty argumentů do funkce zpětné vazby.

Periodicita

Protože existují různé nenulové stavy registru, období sekvence generované RSLOS pro jakýkoli nenulový počáteční stav nepřekročí. V tomto případě období závisí na přidruženém polynomu:

Vlastnosti primitivních polynomů

Lineární složitost

Lineární složitost binární sekvence je jednou z nejdůležitějších charakteristik provozu RSLOS. Pojďme si představit následující notaci:

Definice

Lineární složitost nekonečná binární sekvence je číslo, které je definováno následovně:

Lineární složitost konečná binární sekvence je číslo, které se rovná délce nejkratší RLOS, která generuje sekvenci, která má jako první členy.

Vlastnosti lineární složitosti

Dovolit a být binární sekvence. Pak:

Korelační nezávislost

K dosažení vysoké lineární složitosti se kryptografové snaží nelineárně kombinovat výsledky více výstupních sekvencí. V tomto případě existuje nebezpečí, že jeden nebo několik výstupních sekvencí (často i výstupy jednotlivých RFLOS) lze spojit společným proudem klíčů a otevřít pomocí lineární algebry. Hackování založené na takové zranitelnosti se nazývá korelační pitva... Thomas Sigenthaler ukázal, že nezávislost korelace lze přesně definovat a že existuje kompromis mezi nezávislostí korelace a lineární složitostí.

Poznámka

Příklad

Číslo kroku	stav	Vygenerovaný bit
0		-
1		1
2		0
3		0
4		1
5		1
6		1
7		0

Algoritmy pro generování primitivních polynomů

Připravené stoly

Galoisova konfigurace

Galoisova konfigurace lineárního zpětnovazebního posuvného registru

Int LFSR (void) (static unsigned long Q \u003d 1; Q \u003d (Q \u003e\u003e 1) ^ (Q & 1? 0x80000057: 0); return Q & 1;)

Výplatou je, že všechny XOR jsou prováděny v jedné operaci.

Poznámky:

je možné dokázat, že konfigurace Fibonacci daná první a zde uvedená konfigurace Galois dávají stejné sekvence (délka 2³²-1), ale mimo fázi jedna od druhé
smyčka pevného počtu volání LFSR v konfiguraci Galois je asi dvakrát rychlejší než v konfiguraci Fibonacci (kompilátor MS VS 2010 na Intel Core i5)
všimněte si, že v konfiguraci Galois je pořadí bitů ve zpětnovazebním slově obráceno ve srovnání s konfigurací Fibonacci

Příklady generátorů na RSLOS

Stop-and-go generátory

Stop-and-go střídavý generátor

Gollmannova kaskáda

Stupeň Gollmann je zesílená verze generátoru stop-and-go. Skládá se ze sekvence RSLOS, jejichž taktování je řízeno předchozím RSLOS. Pokud je výstup RSLOS-1 v čase t 1, pak je RSLOS-2 taktován. Pokud je výstup RSLOS-2 v čase t 1, pak je RSLOS-2 taktován atd. Posledním výstupem RFLOS je výstup generátoru. Pokud je délka všech RFLOS stejná a rovná se n, pak se lineární složitost systému k LLS rovná

Tato myšlenka je jednoduchá a lze ji použít ke generování sekvencí s velkými periodami, velkými lineárními složitostmi a dobrými statistickými vlastnostmi. Bohužel jsou však citliví na útok zvaný lock-in. Pro větší trvanlivost se doporučuje použít k alespoň 15. Navíc je lepší použít více krátkých RFLOS než méně dlouhých RFLO.

Generátor prahových hodnot

V případě tří posuvných registrů může být generátor reprezentován jako:

Tento generátor je podobný generátoru Geff, kromě toho, že generátor prahových hodnot má lineárnější složitost. Jeho lineární složitost je:

Kde ,, - délky prvního, druhého a třetího posuvného registru.

Jeho nevýhodou je, že každý výstupní bit poskytuje určité informace a stav posuvného registru. Přesněji 0,189 bitů. Proto tento generátor nemusí odolat korelačnímu útoku.

Jiné typy generátorů

Pojďme je stručně popsat

Posuvný registr zpětné vazby

Vlastnosti primitivních polynomů

Vlastnosti

Lineární složitost

Korelační nezávislost

Příklad

Algoritmy pro generování primitivních polynomů

Připravené stoly

Galoisova konfigurace

Příklady generátorů

Stop-and-go generátory

Gollmannova kaskáda

Generátor prahových hodnot

Jiné typy

Samovolné ředění

Vícerychlostní generátor s interním produktem

Definice

Vlastnosti

Periodicita

Vlastnosti primitivních polynomů

Lineární složitost

Korelační nezávislost

Příklad

Algoritmy pro generování primitivních polynomů

Připravené stoly

Galoisova konfigurace

Příklady generátorů na RSLOS

Stop-and-go generátory

Gollmannova kaskáda

Generátor prahových hodnot

Jiné typy generátorů

Samostřikovací generátory