Carry Feedback Shift Register

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2013. március 13-án áttekintett verziótól ; az ellenőrzések 23 szerkesztést igényelnek .

A Shift regiszter átviteli regiszterrel ( FCSR ) bitszavak shift regisztere, a lineáris visszacsatolásos shift regiszter aritmetikai analógja , amelytől hordozóregiszter jelenlétében különbözik. Pszeudo-véletlen bitsorozatok generálására használják , és az F-FCSR adatfolyam titkosításának létrehozására is használták .

Történelem

1994 - ben Goresky és () Coutureangol(Couture,ZamanésMarsagliafüggetlenülegymástólvalamint,Klapper angol L' Ecuyer) találta fel a átviteli visszajelzéssel ellátott műszakregisztert . Sőt, Clapper és Goresky az összegző generátor kriptoanalízisére akarta használni . Másrészt Marsaglia, Zaman, Couture, L'Ecuer arra törekedett, hogy találjanak egy jó véletlenszám-generátort olyan problémák megoldására, mint például a kvázi-Monte Carlo módszer alkalmazása . [egy]

Leírás

Az FCSR rendelkezik egy eltolási regiszterrel, egy visszacsatolási funkcióval és egy átviteli regiszterrel. Az eltolási regiszter hossza a bitek száma. Ha egy bitet ki kell húzni, a shift regiszter összes bitje egy pozícióval jobbra tolódik. [2]

Ahelyett, hogy a leágazási szekvencia összes bitjét XOR-e végezné, ezek a bitek hozzáadódnak egymáshoz és a hordozóregiszter tartalmához. Az eredmény egy új ütem lesz. Az eredmény osztva lesz a hordozóregiszter új tartalma. [3] $mod$ $2$ $2$

$m$ — a hordozónyilvántartás értéke

\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}})$ — a nyilvántartás új állapota

$m^{\prime }$ — a hordozónyilvántartás új értéke

Példa

Tekintsünk egy példát egy 3 bites regiszterre, ahol az első és a második pozícióban leágazások találhatók. Legyen a kezdeti értéke , a hordozóregiszter kezdeti tartalma pedig egyenlő . A kimenet a shift regiszter jobb szélső bitje lesz . A nyilvántartás további állapotai az alábbi táblázatban láthatók: $\left[0,\;0,\;1\jobbra]$ $[0]$

Lépésszám	műszakregiszter	Hordozható nyilvántartás
0	$\left[0,\;0,\;1\jobbra]$	0
egy	$\left[1,\;0,\;0\jobbra]$	0
2	$\left[0,\;1,\;0\jobbra]$	0
3	$\left[1,\;0,\;1\jobbra]$	0
négy	$\left[1,\;1,\;0\jobbra]$	0
5	$\left[1,\;1,\;1\jobbra]$	0
6	$\left[0,\;1,\;1\jobbra]$	egy
7	$\left[1,\;0,\;1\jobbra]$	egy
nyolc	$\left[0,\;1,\;0\jobbra]$	egy
9	$\left[0,\;0,\;1\jobbra]$	egy
tíz	$\left[0,\;0,\;0\jobbra]$	egy
tizenegy	$\left[1,\;0,\;0\jobbra]$	0

A végső belső állapot (beleértve a hordozóregiszter tartalmát is) megegyezik a második belső állapottal. Ettől a pillanattól kezdve a sorozat ciklikusan ismétlődik a -val egyenlő periódussal . Azt is érdemes megemlíteni, hogy a hordozóregiszter nem egy bit , hanem egy szám. Mérete legalább , ahol az ágak száma. A példában csak három ág van, tehát a hordozóregiszter egybites. Ha négy ág lenne, akkor a hordozóregiszter két bitből állna, és felvehetné a vagy az értékeket . [3] $tíz$ $\log _{2}t$ $t$ $0.1.2$ $3$

Tulajdonságok

Ellentétben az LFSR -rel, az FCSR-nek késleltetése van, mielőtt ciklikus módba lép, vagyis elkezdi a ciklikus ismétlődő sorozat generálását. A választott kezdeti állapottól függően 4 különböző eset lehetséges: [3]

A kezdeti állapot a maximális időtartam része lehet.
A kezdeti állapot némi kezdeti késleltetés után átválthat a maximális periódussorozatba.
A kezdeti állapot egy kezdeti késleltetés után nullák sorozatát generálhatja.
A kezdeti állapot egy kezdeti késleltetés után egyesek sorozatát hozhatja létre.

Empirikusan ellenőrizheti, hogyan végződik egy adott kezdeti állapot. Egy darabig futnia kell az FCSR-nek. (Ha a kezdeti memória mennyisége és az elágazások száma, akkor a ciklusok elegendőek.) Ha a kimeneti adatfolyam bitenként nullák és egyesek végtelen sorozatává degenerálódik , ahol az FCSR hossza, akkor ez a kezdeti állapot nem használva lenni. [3] $m$ $t$ ${~\log _{2}t}+{~\log _{2}m}+1$ $n$ $n$

Azt is érdemes megjegyezni, hogy az FCSR-alapú generátorkulcsok egy készlete gyenge lesz, mivel az FCSR kezdeti állapota megfelel az adatfolyam titkosító kulcsának. [3]

A maximális FCSR periódus ,ahol a kapcsolat egész száma. Ez a szám határozza meg az ágakat, és a következőképpen definiálható: $q-1$ $q$

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

$q$ - olyan prímszámnak kell lennie, amelyre a 2 primitív gyök . [3] [1]

Csatlakozás az LFSR -hez

Ahogy az LFSR elemzés primitív mod 2 polinomok összeadásán alapul, az FCSR analízis a számok összeadásán, az úgynevezett 2-adic . A 2-adikus számok világában mindenre van analóg. Ugyanúgy, ahogy a lineáris komplexitás definiálható, a 2-adikus komplexitás is definiálható. A Berlekamp-Massey algoritmusnak van egy 2-adikus analógja is . Ez azt jelenti, hogy a lehetséges adatfolyam-rejtjelek száma legalább megduplázódott. Bármi, amit meg lehet tenni az LFSR-rel, megtehető az FCSR-rel. [3]

Megvalósítási lehetőségek

Galois konfiguráció

A Galois konfiguráció a következőkből áll:

n bites főregiszter , néhány rögzített leágazással $M=(m_{0},\cdots ,{m_{{n-1}}})$ $d_{0},\cdots ,d_{{n-1}}$
n-1 - bithordozó regiszter $C=(c_{0},\cdots ,c_{{n-2}})$

A t időpontban az állapot a következőképpen változik: $(M,C)$

1. , for all , with és ahol a visszacsatoló bitet jelenti. $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. Az állapot frissült: , for all és , for all . [4] [5] $m_{i}\leftarrow {x_{i}}mod2$ $i\in [0\pont n-1]$ $c_{i}\leftarrow {x_{i}}div2$ $i\in [0\pont n-2]$

Fibonacci konfiguráció

A Fibonacci konfiguráció a következőkből áll:

n - bites főregiszter $M=(m_{0},\cdots ,{m_{{n-1}}})$
A csapok egy bitekből álló hordozóregiszterhez vannak társítva , ahol a Hamming - súly $(d_{0},\cdots ,d_{{n-1}})$ $c$ $w_{H}(d)$ $w_{H}(d)$ $d=(1+|q|)/2$

Az állapot a következőképpen változik: $(M,c)$

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

2. frissítés állapota: , . [4] [5] $M\leftarrow (m_{1},\dots ,m_{{n-1}},xmod2)$ $c\leftarrow xdiv2$

Lehetséges használati esetek generátorokban

Interleaved stop-and-go generátorok

Fő cikk: Stop-go generátor

Három különböző hosszúságú műszakregisztert használ. Itt az 1. regiszter vezérli a 2. és 3. regiszter órafrekvenciáját, vagyis a 2. regiszter megváltoztatja állapotát, ha az 1. regiszter kimenete eggyel egyenlő, a 3. regiszter pedig, ha az 1. regiszter kimenete egyenlő nullával. [3]

Ezek a regiszterek FCSR-t használnak egyes LFSR-ek helyett, és az XOR művelet helyettesíthető egy átviteli hozzáadással.

Stop-go generátor FCSR: Register-1, Register-2, Register-3 az FCSR. Az egyesítő függvény az XOR.
Stop-go generátor FCSR/LFSR: Register-1 - FCSR; Register-2, Register-3 - LFSR. Az egyesítő funkció a szállítással való kiegészítés.
Stop-go generátor FCSR/LFSR: Register-1 - LFSR; Register-2, Register-3 - FCSR. Az egyesítő függvény az XOR. [3]

Kaszkádgenerátorok

Főcikk : Gollmann Cascade

Ez az áramkör a stop-go generátor továbbfejlesztett változata. Regiszterek sorozatából áll, amelyek mindegyikének órajelét az előző regiszter vezérli. Ha az 1. regiszter kimenete pillanatnyilag 1, akkor a 2. regiszter órajele. Ha a 2. regiszter kimenete pillanatnyilag 1, akkor a 3. regiszter órajele van, és így tovább. Az utolsó regiszter kimenete a generátor kimenete. [3]

Kétféleképpen használhatjuk az FCSR-t lépcsőzetes oszcillátorokban:

FCSR Cascade. Gollmann Cascade FCSR-rel LFSR helyett.
Kaszkád FCSR/LFSR. Gollmann kaszkád az LFSR-t FCSR-re cserélő oszcillátorokkal és fordítva. [3]

Kombinált generátorok

Ezek a generátorok változó számú FCSR-t és/vagy LFSR-t, valamint számos, regisztereket kombináló függvényt használnak. Az XOR művelet megsemmisíti az FCSR algebrai tulajdonságait, ezért célszerű ezt a műveletet használni ezek kombinálására. [3]

FCSR paritásgenerátor. Minden regiszter FCSR, a csatlakozási funkció pedig XOR.
LFSR/FCSR paritásgenerátor. Az LFSR és az FCSR keverékét használják, a kombináló függvény pedig az XOR.
FCSR küszöbgenerátor. Minden regiszter FCSR, az egyesítő funkció pedig a majorizáció.
LFSR/FCSR küszöbgenerátor. Az LFSR és az FCSR keverékét használják, és az egyesítő funkció a majorizáció.
FCSR összegző generátor. Minden regiszter FCSR, és a join funkció add with carry.
LFSR/FCSR összegző generátor. Az LFSR és az FCSR keveréke használatos, és az összekapcsolás függvény a carry-add. [3]

Alkalmazás

A átviteli visszacsatolású Shift regiszterek alapul szolgálhatnak különféle generátorok (amelyek közül néhányat fentebb leírtunk), valamint különféle adatfolyam titkosítások létrehozásához.

F-FCSR

Fő cikk: F-FCSR .

Az F-FCSR egy adatfolyam-rejtjel-család, amely egy átviteli visszacsatolási eltolási regiszter (FCSR) használatán alapul, lineáris kimeneti szűrővel. A rejtjelezés ötletét Terry Berger, François Arnault és Cédric Larade javasolta. Az F-FCSR-t beküldték az eSTREAM versenyre , 2008 áprilisában felkerült a verseny nyerteseinek listájára, de később kiderült egy kriptográfiai gyengeség, és 2008 szeptemberében az F-FCSR kikerült az eSTREAM-ból.

Lásd még

Jegyzetek

↑ 1 2 A. Klapper A Carry Shift regiszterekkel kapcsolatos visszajelzések felmérése (lefelé irányuló kapcsolat)
↑ A. Klapper és M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, Journal of Cryptology vol. 10, pp. 111-147 , 1997, [1] (elérhetetlen link)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 B. Schneier, 2013 .
↑ 1 2 A. Klapper és M. Goresky, Fibonacci and Galois Representations of Feedback with Carry Shift Registers , 2004, [2] Archivált : 2015. szeptember 23. a Wayback Machine -nél
↑ 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier és Benjamin Pousse, Új megközelítés az FCSR -ekhez , [3] Archivált : 2018. június 2. a Wayback Machine -nél

Irodalom

Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forrásszövegek C nyelven. - Triumph, 2013. - 816 p. - ISBN 978-5-89392-527-2 .