Carry Feedback Shift Register

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. března 2013; kontroly vyžadují 23 úprav .

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 .

Historie

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]

Popis

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] $mod$ $2$ $2$

$m$ — hodnota registru přenosu

\sigma ={q_{1}}{a_{k-1}}+\cdots +{q_{k}}{a_{0}}+m

{a_{k}}={\sigma }{mod}{2}

{m^{\prime }}=[{\sigma }/2]

$({a_{k}},\cdots ,{a_{1}})$ — nový stav registru

$m^{\prime}$ — nová hodnota registru přenosu

Příklad

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: $\left[0,\;0,\;1\right]$ $[0]$

Číslo kroku	posuvný registr	Nosit registr
0	$\left[0,\;0,\;1\right]$	0
jeden	$\left[1,\;0,\;0\right]$	0
2	$\left[0,\;1,\;0\right]$	0
3	$\left[1,\;0,\;1\right]$	0
čtyři	$\left[1,\;1,\;0\right]$	0
5	$\left[1,\;1,\;1\right]$	0
6	$\left[0,\;1,\;1\right]$	jeden
7	$\left[1,\;0,\;1\right]$	jeden
osm	$\left[0,\;1,\;0\right]$	jeden
9	$\left[0,\;0,\;1\right]$	jeden
deset	$\left[0,\;0,\;0\right]$	jeden
jedenáct	$\left[1,\;0,\;0\right]$	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] $deset$ $\log _{2}t$ $t$ $0.1.2$ $3$

Vlastnosti

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]

Počáteční stav může být součástí maximální doby.
Počáteční stav může po určité počáteční prodlevě přejít na sekvenci maximální periody.
Počáteční stav může po počátečním zpoždění generovat sekvenci nul.
Počáteční stav může po počátečním zpoždění vytvořit sekvenci jedniček.

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] $m$ $t$ ${~\log _{2}t}+{~\log _{2}m}+1$ $n$ $n$

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: $q-1$ $q$

$q={2q_{1}}+{{2^{2}}q_{2}}+{{2^{3}}q_{3}}+\cdots +{{2^{n}}q_{ n}}-1$

$q$ - musí být prvočíslo, pro které je 2 primitivní kořen . [3] [1]

Spojení s LFSR

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]

Možnosti implementace

Konfigurace Galois

Konfigurace Galois se skládá z:

n -bitový hlavní registr , s některými pevnými odbočkami $M=(m_{0},\cdots ,{m_{{n-1}}})$ $d_{0},\cdots ,d_{{n-1}}$
n-1 - bitový přenosový registr $C=(c_{0},\cdots,c_{{n-2}})$

V čase t se stav změní následovně: $(M,C)$

1. , pro všechny , s a a kde představuje bit zpětné vazby. $x_{i}=m_{{i+1}}+{c_{i}}{d_{i}}+{m_{0}}{d_{i}}$ $0\leq i<n$ $m_{{n}}=0$ $c_{{n-1}}=0$ $m_{0}$

2. Stav je aktualizován: , pro všechny a , pro všechny . [4] [5] $m_{i}\leftarrow {x_{i}}mod2$ $i\in [0\teček n-1]$ $c_{i}\leftarrow {x_{i}}div2$ $i\in [0\tečky n-2]$

Konfigurace Fibonacci

Konfigurace Fibonacci se skládá z:

n - bitový hlavní registr $M=(m_{0},\cdots ,{m_{{n-1}}})$
kohoutky jsou spojeny s přenosovým registrem sestávajícím z bitů, kde je Hammingova váha pro $(d_{0},\cdots ,d_{{n-1}})$ $C$ $w_{H} (d)$ $w_{H} (d)$ $d=(1+|q|)/2$

Stav se mění takto: $(M,c)$

1 .; $x=c+\součet _{{i=0}}^{{n-1}}{{m_{i}}{d_{{n-1-i}}}}$

2. stav aktualizace: , . [4] [5] $M\leftarrow (m_{1},\tečky ,m_{{n-1}},xmod2)$ $c\leftarrow xdiv2$

Možné případy použití v generátorech

Prokládané generátory stop-and-go

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.

Generátor zastavení FCSR: Registr-1, Registr-2, Registr-3 je FCSR. Sjednocující funkcí je XOR.
Generátor stop-go FCSR/LFSR: Registr-1 - FCSR; Registr-2, Registr-3 - LFSR. Sjednocující funkcí je přidávání s nošením.
Generátor zastavení FCSR/LFSR: Registr-1 - LFSR; Registr-2, Registr-3 - FCSR. Sjednocující funkcí je XOR. [3]

Kaskádové generátory

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:

Kaskáda FCSR. Gollmann Cascade s FCSR místo LFSR.
Kaskádový FCSR/LFSR. Gollmannova kaskáda s oscilátory měnícími LFSR na FCSR a naopak. [3]

Kombinované generátory

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]

Generátor parity FCSR. Všechny registry jsou FCSR a funkce spojení je XOR.
Generátor parity LFSR/FCSR. Používá se směs LFSR a FCSR a kombinační funkce je XOR.
Generátor prahů FCSR. Všechny registry jsou FCSR a sjednocující funkcí je majorizace.
Generátor prahů LFSR/FCSR. Používá se směs LFSR a FCSR a sjednocující funkcí je majorizace.
Součtový generátor FCSR. Všechny registry jsou FCSR a funkce spojení je add with carry.
Součtový generátor LFSR/FCSR. Používá se směs LFSR a FCSR a funkce spojení je carry-add. [3]

Aplikace

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.

F-FCSR

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.

Viz také

Poznámky

↑ 1 2 A. Klapper Přehled zpětné vazby s Carry Shift Registers (downlink)
↑ A. Klapper a M. Goresky, Feedback Shift Registers, 2-Adic Span a Combiners With Memory, v Journal of Cryptology sv. 10, str. 111-147 , 1997, [1] (nepřístupný odkaz)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 B. Schneier, 2013 .
↑ 1 2 A. Klapper a M. Goresky, Fibonacci a Galois Representations of Feedback with Carry Shift Registers , 2004, [2] Archivováno 23. září 2015 na Wayback Machine
↑ 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier a Benjamin Pousse, Nový přístup pro FCSR , [3] Archivováno 2. června 2018 na Wayback Machine

Literatura

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojové texty v jazyce C. - Triumf, 2013. - 816 s. - ISBN 978-5-89392-527-2 .