Posuvný registr s přenosovým posuvným registrem ( FCSR je posuvný registr bitových slov, aritmetický analog posuvného registru s lineární zpětnou vazbou , liší se od něj přítomností přenosového registru. Používá se ke generování pseudonáhodných bitových sekvencí a byl také použit k vytvoření proudové šifry F-FCSR .
V roce 1994 vynalezli posuvný registr s přenosovou zpětnou vazbou Goresky a Klapper Ecuyer L'a)Coutureanglicky(Couture,ZamanaMarsaglianezávislejako, stejně anglicky L'Ecuyer ). Clapper a Goresky jej navíc chtěli použít pro kryptoanalýzu sumačního generátoru. Na druhé straně, Marsaglia, Zaman, Couture, L'Ecuer se snažily najít dobrý generátor náhodných čísel pro řešení problémů, jako je použití kvazi-Monte Carlo metody . [jeden]
FCSR má posuvný registr, zpětnovazební funkci a přenosový registr. Délka posuvného registru je počet bitů. Když je potřeba extrahovat bit, všechny bity posuvného registru se posunou doprava o jednu pozici. [2]
Namísto XORingu všech bitů v odbočovací sekvenci se tyto bity přidávají k sobě navzájem ak obsahu přenosového registru. Výsledkem je nový rytmus. Výsledek děleno se stává novým obsahem nosného registru. [3]
— hodnota registru přenosu
— nový stav registru
— nová hodnota registru přenosu
Uvažujme příklad 3bitového registru s odbočkami na první a druhé pozici. Nechť je jeho počáteční hodnota a počáteční obsah registru carry se rovná . Výstupem bude bit zcela vpravo posuvného registru . Další stavy registru jsou uvedeny v tabulce níže:
Číslo kroku | posuvný registr | Nosit registr |
---|---|---|
0 | 0 | |
jeden | 0 | |
2 | 0 | |
3 | 0 | |
čtyři | 0 | |
5 | 0 | |
6 | jeden | |
7 | jeden | |
osm | jeden | |
9 | jeden | |
deset | jeden | |
jedenáct | 0 |
Konečný vnitřní stav (včetně obsahu nosného registru) je stejný jako druhý vnitřní stav. Od tohoto okamžiku se sekvence cyklicky opakuje s periodou rovnou . Za zmínku také stojí, že nosný registr není bit , ale číslo. Jeho velikost musí být alespoň , kde je počet větví. V příkladu jsou pouze tři větve, takže přenosový registr je jednobitový. Pokud by existovaly čtyři větve, pak by se přenosový registr skládal ze dvou bitů a mohl by nabývat hodnot nebo . [3]
Na rozdíl od LFSR existuje zpoždění pro FCSR, než vstoupí do cyklického režimu, to znamená, že začne generovat cyklickou opakující se sekvenci. V závislosti na zvoleném počátečním stavu jsou možné 4 různé případy: [3]
Empiricky můžete zkontrolovat, jak konkrétní počáteční stav končí. Je potřeba na chvíli spustit FCSR. (Pokud je počáteční množství paměti a počet větví, pak jsou cykly dostatečné.) Pokud výstupní proud degeneruje do nekonečné sekvence nul a jedniček na bit, kde je délka FCSR, pak by tento počáteční stav neměl být použit. [3]
Rovněž stojí za zmínku, že sada klíčů generátoru založených na FCSR bude slabá, protože počáteční stav FCSR odpovídá klíči proudové šifry. [3]
Maximální perioda FCSR je, kde je celé číslo spojení. Toto číslo definuje pobočky a je definováno jako:
- musí být prvočíslo, pro které je 2 primitivní kořen . [3] [1]
Stejně jako je analýza LFSR založena na sčítání primitivních polynomů mod 2, je analýza FCSR založena na sčítání čísel, nazývaných 2-adic . Ve světě 2-adických čísel existují analogy pro všechno. Stejným způsobem, jako je definována lineární složitost , lze také definovat 2-adickou složitost. Existuje také 2-adický analog pro algoritmus Berlekamp-Massey . To znamená, že počet možných proudových šifer se minimálně zdvojnásobil. Cokoli, co lze udělat s LFSR, lze udělat s FCSR. [3]
Konfigurace Galois se skládá z:
V čase t se stav změní následovně:
1. , pro všechny , s a a kde představuje bit zpětné vazby.
2. Stav je aktualizován: , pro všechny a , pro všechny . [4] [5]
Konfigurace Fibonacci se skládá z:
Stav se mění takto:
1 .;
2. stav aktualizace: , . [4] [5]
Hlavní článek: Stop-go generátor
Využívá tři posuvné registry různých délek. Registr-1 zde řídí hodinovou frekvenci 2. a 3. registru, to znamená, že registr-2 mění svůj stav, když je výstup registru-1 roven jedné, a registr-3 - když je výstup registru-1 rovna nule. [3]
Tyto registry používají FCSR místo některých LFSR a operace XOR může být nahrazena carry add.
Hlavní článek: Gollmann Cascade
Tento obvod je vylepšenou verzí stop-go generátoru. Skládá se z posloupnosti registrů, přičemž taktování každého z nich je řízeno předchozím registrem. Pokud je výstup registru-1 v daném čase 1, pak je registr-2 taktován. Je-li výstup registru-2 v čase 1, pak je taktován registr-3 a tak dále. Výstupem posledního registru je výstup generátoru. [3]
Existují dva způsoby použití FCSR v kaskádových oscilátorech:
Tyto generátory používají proměnný počet FCSR a/nebo LFSR a řadu funkcí, které kombinují registry. Operace XOR ničí algebraické vlastnosti FCSR, takže má smysl používat tuto operaci k jejich kombinaci. [3]
Posuvné registry s přenosovou zpětnou vazbou mohou sloužit jako základ pro vytváření různých generátorů (některé z nich jsou popsány výše), a také různých proudových šifer.
Hlavní článek: F-FCSR .
F-FCSR je rodina proudových šifer založených na použití posuvného registru se zpětnou vazbou (FCSR) s lineárním výstupním filtrem. Nápad na šifru navrhli Terry Berger, François Arnault a Cédric Larade. F-FCSR byl přihlášen do soutěže eSTREAM , byl zařazen do seznamu vítězů soutěže v dubnu 2008, ale později byla odhalena kryptografická slabina a v září 2008 byl F-FCSR z eSTREAM odstraněn.