Bär feedback skiftregister

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 mars 2013; kontroller kräver 23 redigeringar .

Skiftregister med överföringsskiftregister ( FCSR ) är ett skiftregister av , en aritmetisk analog till ett linjärt återkopplingsskiftregister , som skiljer sig från det genom närvaron av ett överföringsregister. Den används för att generera pseudo-slumpmässiga bitsekvenser och användes också för att skapa F-FCSR- strömchifferet .

Historik

1994 uppfanns skiftregistret med bärfeedback av Goresky och Ecuyer L'och)Coutureengelsk(Couture,ZamanochMarsagliaavoberoendeKlapper, samt engelska L'Ecuyer ). Dessutom ville Clapper och Goresky använda den för kryptoanalys av summeringsgeneratorn. Å andra sidan siktade Marsaglia, Zaman, Couture, L'Ecuer på att hitta en bra slumptalsgenerator för att lösa problem som att använda quasi-Monte Carlo-metoden . [ett]

Beskrivning

FCSR har ett skiftregister, en återkopplingsfunktion och ett överföringsregister . Längden på skiftregistret är antalet bitar. När en bit behöver extraheras skiftas alla bitar i skiftregistret åt höger med en position. [2]

Istället för att XORera alla bitar i tappsekvensen, adderas dessa bitar till varandra och till innehållet i bärregistret. Resultatet blir ett nytt beat. Resultatet dividerat med blir det nya innehållet i bärregistret. [3] $mod$ $2$ $2$

$m$ — Värdet på transportregistret

\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}})$ — ny tillstånd i registret

$m^{\prime }$ — Nytt värde på överföringsregistret

Exempel

Betrakta ett exempel på ett 3-bitars register med uttag i första och andra positionen. Låt dess initiala värde vara och det initiala innehållet i bärregistret vara lika med . Utsignalen kommer att vara biten längst till höger i skiftregistret . Ytterligare tillstånd i registret visas i tabellen nedan: $\vänster[0,\;0,\;1\höger]$ $[0]$

Stegnummer	skift register	Bär register
0	$\vänster[0,\;0,\;1\höger]$	0
ett	$\vänster[1,\;0,\;0\höger]$	0
2	$\vänster[0,\;1,\;0\höger]$	0
3	$\vänster[1,\;0,\;1\höger]$	0
fyra	$\vänster[1,\;1,\;0\höger]$	0
5	$\vänster[1,\;1,\;1\höger]$	0
6	$\vänster[0,\;1,\;1\höger]$	ett
7	$\vänster[1,\;0,\;1\höger]$	ett
åtta	$\vänster[0,\;1,\;0\höger]$	ett
9	$\vänster[0,\;0,\;1\höger]$	ett
tio	$\vänster[0,\;0,\;0\höger]$	ett
elva	$\vänster[1,\;0,\;0\höger]$	0

Det slutliga interna tillståndet (inklusive innehållet i överföringsregistret) är detsamma som det andra interna tillståndet. Från och med detta ögonblick upprepas sekvensen cykliskt med en period lika med . Det är också värt att nämna att bärregistret inte är en bit , utan ett nummer. Dess storlek måste vara minst , där är antalet grenar. I exemplet finns det bara tre grenar, så bärregistret är enbit. Om det fanns fyra grenar skulle bärregistret bestå av två bitar och skulle kunna ta på sig värdena eller . [3] $tio$ $\log _{2}t$ $t$ $0.1.2$ $3$

Egenskaper

Till skillnad från LFSR finns det en fördröjning för FCSR innan den går in i den cykliska moden, det vill säga den börjar generera en cyklisk upprepad sekvens. Beroende på det valda initiala tillståndet är 4 olika fall möjliga: [3]

Det ursprungliga tillståndet kan vara en del av den maximala perioden.
Det initiala tillståndet kan övergå till den maximala periodsekvensen efter en viss initial fördröjning.
Det initiala tillståndet kan, efter en initial fördröjning, generera en sekvens av nollor.
Det initiala tillståndet kan, efter en initial fördröjning, producera en sekvens av ettor.

Empiriskt kan du kontrollera hur ett visst initialtillstånd slutar. Måste köra FCSR ett tag. (Om är den initiala mängden minne och är antalet grenar, då är cykler tillräckliga.) Om utgångsströmmen urartar till en oändlig sekvens av nollor och ettor per bit, var är längden på FCSR, bör detta initiala tillstånd inte användas. [3] $m$ $t$ ${~\log _{2}t}+{~\log _{2}m}+1$ $n$ $n$

Det är också värt att notera att en uppsättning FCSR-baserade generatornycklar kommer att vara svaga, eftersom det initiala tillståndet för FCSR motsvarar nyckeln för strömchifferet. [3]

Den maximala FCSR-perioden är, där är ett heltal för anslutningen. Detta nummer definierar grenar och definieras som: $q-1$ $q$

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

$q$ - måste vara ett primtal där 2 är en primitiv rot . [3] [1]

Anslutning till LFSR

Precis som LFSR-analys är baserad på tillägg av primitiva mod 2-polynom, baseras FCSR-analys på tillägg av tal, kallade 2-adic . I en värld av 2-adiska nummer finns det analoger för allt. På samma sätt som linjär komplexitet definieras, kan 2-adisk komplexitet också definieras. Det finns också en 2-adisk analog för Berlekamp-Massey-algoritmen . Det betyder att antalet möjliga strömchiffer åtminstone har fördubblats. Allt som kan göras med LFSR kan göras med FCSR. [3]

Implementeringsalternativ

Galois-konfiguration

Galois-konfigurationen består av:

n -bitars huvudregister , med några fasta kranar $M=(m_{0},\cdots ,{m_{{n-1}}})$ $d_{0},\cdots ,d_{{n-1}}$
n-1 - bitars överföringsregister $C=(c_{0},\cdots ,c_{{n-2}})$

Vid tidpunkten t ändras tillståndet enligt följande: $(M,C)$

1. , för alla , med och och där representerar återkopplingsbiten. $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. Status uppdateras: , för alla och , för alla . [4] [5] $m_{i}\leftarrow {x_{i}}mod2$ $i\i [0\prickar n-1]$ $c_{i}\leftarrow {x_{i}}div2$ $i\i [0\prickar n-2]$

Fibonacci-konfiguration

Fibonacci-konfigurationen består av:

n - bit huvudregister $M=(m_{0},\cdots ,{m_{{n-1}}})$
tappar är förknippade med ett bärregister bestående av bitar, där Hammingvikten för $(d_{0},\cdots ,d_{{n-1}})$ $c$ $w_{H}(d)$ $w_{H}(d)$ $d=(1+|q|)/2$

Staten ändras enligt följande: $(M,c)$

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

2. uppdateringstillstånd: , . [4] [5] $M\vänsterpil (m_{1},\dots,m_{{n-1}},xmod2)$ $c\vänsterpil xdiv2$

Möjliga användningsfall i generatorer

Interfolierade stop-and-go-generatorer

Huvudartikel: Stop-go-generator

Den använder tre skiftregister av olika längd. Här styr Register-1 klockfrekvensen för det andra och 3:e registret, det vill säga Register-2 ändrar sitt tillstånd när utsignalen från Register-1 är lika med ett, och Register-3 - när utsignalen från Register-1 är lika med noll. [3]

Dessa register använder FCSRs istället för vissa LFSRs, och XOR-operationen kan ersättas med en carry add.

Stop-go generator FCSR: Register-1, Register-2, Register-3 är FCSR. Den sammanhållande funktionen är XOR.
Stop-go generator FCSR/LFSR: Register-1 - FCSR; Register-2, Register-3 - LFSR. Den sammanhållande funktionen är tillägg med bär.
Stop-go generator FCSR/LFSR: Register-1 - LFSR; Register-2, Register-3 - FCSR. Den sammanhållande funktionen är XOR. [3]

Kaskadgeneratorer

Huvudartikel: Gollmann Cascade

Denna krets är en förbättrad version av stop-go-generatorn. Den består av en sekvens av register, vars klockning styrs av det föregående registret. Om utsignalen från Register-1 vid tidpunkten är 1, klockas Register-2. Om utsignalen från Register-2 vid tidpunkten är 1, klockas Register-3, och så vidare. Utsignalen från det sista registret är utsignalen från generatorn. [3]

Det finns två sätt att använda FCSR i kaskadkopplade oscillatorer:

FCSR Cascade. Gollmann Cascade med FCSR istället för LFSR.
Kaskad FCSR/LFSR. Gollmann-kaskad med oscillatorer som ändrar LFSR till FCSR och vice versa. [3]

Kombinerade generatorer

Dessa generatorer använder ett variabelt antal FCSR:er och/eller LFSR:er och en mängd olika funktioner som kombinerar register. XOR-operationen förstör de algebraiska egenskaperna hos FCSR, så det är vettigt att använda den här operationen för att kombinera dem. [3]

FCSR paritetsgenerator. Alla register är FCSR och joinfunktionen är XOR.
LFSR/FCSR paritetsgenerator. En blandning av LFSR och FCSR används, och kombinationsfunktionen är XOR.
Tröskelgenerator FCSR. Alla register är FCSR, och den sammanhållande funktionen är majorisering.
Tröskelgenerator LFSR/FCSR. En blandning av LFSR och FCSR används, och den sammanhållande funktionen är majorisering.
Summeringsgenerator FCSR. Alla register är FCSR, och join-funktionen läggs till med carry.
Summeringsgenerator LFSR/FCSR. En blandning av LFSR och FCSR används, och joinfunktionen är carry-add. [3]

Applikation

Skiftregister med bärfeedback kan tjäna som bas för att skapa olika generatorer (av vilka några beskrivs ovan), såväl som olika strömchiffer.

F-FCSR

Huvudartikel: F-FCSR .

F-FCSR är en familj av strömchiffer baserad på användningen av ett överföringsåterkopplingsskiftregister (FCSR) med ett linjärt utgångsfilter. Idén till chiffret föreslogs av Terry Berger, François Arnault och Cédric Larade. F-FCSR skickades till eSTREAM- tävlingen , ingick i listan över vinnare av tävlingen i april 2008, men senare avslöjades en kryptografisk svaghet och i september 2008 avnoterades F-FCSR från eSTREAM.

Se även

Anteckningar

↑ 1 2 A. Klapper En undersökning av feedback med bärskiftregister (nedlänk)
↑ A. Klapper och M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, i Journal of Cryptology vol. 10, sid. 111-147 , 1997, [1] (otillgänglig länk)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 B. Schneier, 2013 .
↑ 1 2 A. Klapper och M. Goresky, Fibonacci och Galois Representations of Feedback with Carry Shift Registers , 2004, [2] Arkiverad 23 september 2015 på Wayback Machine
↑ 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier och Benjamin Pousse, A new approach for FCSRs , [3] Arkiverad 2 juni 2018 på Wayback Machine

Litteratur

Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källtexter i C-språk. - Triumph, 2013. - 816 sid. - ISBN 978-5-89392-527-2 .