Overfør tilbagemeldingsskiftregister

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 13. marts 2013; checks kræver 23 redigeringer .

Skifteregister med carry shift register ( FCSR ) er et shift register af bitord , en aritmetisk analog til et lineært feedback skifteregister , adskiller sig fra det ved tilstedeværelsen af et carry register. Det bruges til at generere pseudo-tilfældige bitsekvenser og blev også brugt til at oprette F-FCSR- strømchifferet .

Historie

I 1994 blev skiftregistret med carry feedback opfundet af Goresky og Klapper Ecuyer L'og)Coutureengelsk(Couture,ZamanogMarsagliaafuafhængigt, samt engelsk L'Ecuyer ). Desuden ønskede Clapper og Goresky at bruge det til krypteringsanalyse af summeringsgeneratoren. På den anden side sigtede Marsaglia, Zaman, Couture, L'Ecuer efter at finde en god tilfældig talgenerator til at løse problemer, såsom at bruge quasi-Monte Carlo-metoden . [en]

Beskrivelse

FCSR har et skifteregister, en feedbackfunktion og et bæreregister. Længden af skifteregisteret er antallet af bits. Når en bit skal udtrækkes, forskydes alle bits i skifteregisteret én position til højre. [2]

I stedet for at XORinge alle bits i tapsekvensen, tilføjes disse bit til hinanden og til indholdet af bæreregisteret. Resultatet bliver et nyt beat. Resultatet divideret med bliver det nye indhold i carry-registret. [3] $mod$ $2$ $2$

$m$ — værdien af 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 tilstand i registret

$m^{\prime }$ — ny værdi af transportregistret

Eksempel

Overvej et eksempel på et 3-bit register med tryk i første og anden position. Lad dens begyndelsesværdi være , og det indledende indhold af bæreregisteret være lig med . Udgangen vil være den yderste højre bit af skifteregisteret . Yderligere tilstande i registret er vist i tabellen nedenfor: $\venstre[0,\;0,\;1\højre]$ $[0]$

Trinnummer	skifteregister	Medbring register
0	$\venstre[0,\;0,\;1\højre]$	0
en	$\venstre[1,\;0,\;0\højre]$	0
2	$\venstre[0,\;1,\;0\højre]$	0
3	$\venstre[1,\;0,\;1\højre]$	0
fire	$\venstre[1,\;1,\;0\højre]$	0
5	$\venstre[1,\;1,\;1\højre]$	0
6	$\venstre[0,\;1,\;1\højre]$	en
7	$\venstre[1,\;0,\;1\højre]$	en
otte	$\venstre[0,\;1,\;0\højre]$	en
9	$\venstre[0,\;0,\;1\højre]$	en
ti	$\venstre[0,\;0,\;0\højre]$	en
elleve	$\venstre[1,\;0,\;0\højre]$	0

Den endelige interne tilstand (inklusive indholdet af bæreregisteret) er den samme som den anden interne tilstand. Fra dette øjeblik gentages sekvensen cyklisk med en periode lig med . Det er også værd at nævne, at bæreregistret ikke er en smule , men et tal. Dens størrelse skal være mindst , hvor er antallet af grene. I eksemplet er der kun tre grene, så bæreregisteret er en-bit. Hvis der var fire grene, ville bæreregisteret bestå af to bit og kunne antage værdierne eller . [3] $ti$ $\log _{2}t$ $t$ $0.1.2$ $3$

Egenskaber

I modsætning til LFSR er der en forsinkelse for FCSR, før den går ind i den cykliske tilstand, det vil sige, den begynder at generere en cyklisk gentagelsessekvens. Afhængigt af den valgte starttilstand er 4 forskellige tilfælde mulige: [3]

Starttilstanden kan være en del af den maksimale periode.
Starttilstanden kan gå over til den maksimale periodesekvens efter en vis indledende forsinkelse.
Starttilstanden kan efter en indledende forsinkelse generere en sekvens af nuller.
Starttilstanden kan efter en indledende forsinkelse frembringe en sekvens af enere.

Empirisk kan du kontrollere, hvordan en bestemt begyndelsestilstand ender. Skal køre FCSR i et stykke tid. (Hvis er den oprindelige mængde hukommelse og er antallet af grene, så er cyklusser tilstrækkelige.) Hvis outputstrømmen degenererer til en uendelig sekvens af nuller og ener pr. bit, hvor er længden af FCSR, så bør denne starttilstand ikke blive brugt. [3] $m$ $t$ ${~\log _{2}t}+{~\log _{2}m}+1$ $n$ $n$

Det er også værd at bemærke, at et sæt FCSR -baserede generatornøgler vil være svage, da FCSR'ens begyndelsestilstand svarer til strømchifferens nøgle. [3]

Den maksimale FCSR-periode er, hvor er et helt tal for forbindelsen. Dette tal definerer grene og er defineret som: $q-1$ $q$

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

$q$ - skal være et primtal, hvor 2 er en primitiv rod . [3] [1]

Forbindelse med LFSR

Ligesom LFSR-analyse er baseret på tilføjelse af primitive mod 2-polynomier, er FCSR-analyse baseret på tilføjelse af tal, kaldet 2-adic . I en verden af 2-adiske numre er der analoger til alt. På samme måde som lineær kompleksitet er defineret, kan 2-adisk kompleksitet også defineres. Der er også en 2-adic-analog til Berlekamp-Massey-algoritmen . Det betyder, at antallet af mulige stream-cifre er mindst fordoblet. Alt, hvad der kan gøres med LFSR, kan gøres med FCSR. [3]

Implementeringsmuligheder

Galois-konfiguration

Galois-konfigurationen består af:

n -bit hovedregister , med nogle faste haner $M=(m_{0},\cdots,{m_{{n-1}}})$ $d_{0},\cdots ,d_{{n-1}}$
n-1 - bit bæreregister $C=(c_{0},\cdots ,c_{{n-2}})$

På tidspunktet t ændres tilstanden som følger: $(M,C)$

1. , for alle , med og og hvor repræsenterer feedback-bitten. $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 opdateres: , for alle og , for alle . [4] [5] $m_{i}\leftarrow {x_{i}}mod2$ $i\in [0\prikker n-1]$ $c_{i}\leftarrow {x_{i}}div2$ $i\in [0\prikker n-2]$

Fibonacci-konfiguration

Fibonacci-konfigurationen består af:

n - bit hovedregister $M=(m_{0},\cdots,{m_{{n-1}}})$
haner er tilknyttet et bæreregister bestående af bits, hvor Hamming-vægten for $(d_{0},\cdots ,d_{{n-1}})$ $c$ $w_{H}(d)$ $w_{H}(d)$ $d=(1+|q|)/2$

Staten ændrer sig som følger: $(M,c)$

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

2. opdateringstilstand: , . [4] [5] $M\venstrepil (m_{1},\dots,m_{{n-1}},xmod2)$ $c\venstrepil xdiv2$

Mulige use cases i generatorer

Interleaved stop-and-go generatorer

Hovedartikel: Stop-go-generator

Den bruger tre skifteregistre af forskellig længde. Her styrer Register-1 klokfrekvensen for 2. og 3. register, det vil sige, Register-2 ændrer sin tilstand, når output fra Register-1 er lig med én, og Register-3 - når output fra Register-1 er lig med nul. [3]

Disse registre bruger FCSR'er i stedet for nogle LFSR'er, og XOR-operationen kan erstattes med en carry-add.

Stop-go generator FCSR : Register-1, Register-2, Register-3 er FCSR. Den samlende funktion er XOR.
Stop-go generator FCSR/LFSR: Register-1 - FCSR; Register-2, Register-3 - LFSR. Den samlende funktion er tilføjelse med bære.
Stop-go generator FCSR/LFSR: Register-1 - LFSR; Register-2, Register-3 - FCSR. Den samlende funktion er XOR. [3]

Kaskadegeneratorer

Hovedartikel: Gollmann Cascade

Dette kredsløb er en forbedret version af stop-go generatoren. Den består af en sekvens af registre, hvor clocking af hver af dem styres af det foregående register. Hvis udgangen af Register-1 på det tidspunkt er 1, klokkes register-2. Hvis outputtet af Register-2 på tidspunktet er 1, bliver Register-3 klokket, og så videre. Udgangen af det sidste register er udgangen af generatoren. [3]

Der er to måder at bruge FCSR i kaskadeoscillatorer:

FCSR Cascade. Gollmann Cascade med FCSR i stedet for LFSR.
Kaskade FCSR/LFSR. Gollmann-kaskade med oscillatorer, der ændrer LFSR til FCSR og omvendt. [3]

Kombinerede generatorer

Disse generatorer bruger et variabelt antal FCSR'er og/eller LFSR'er og en række funktioner, der kombinerer registre. XOR-operationen ødelægger FCSR'ens algebraiske egenskaber, så det giver mening at bruge denne operation til at kombinere dem. [3]

FCSR paritetsgenerator. Alle registre er FCSR og joinfunktionen er XOR.
LFSR/FCSR paritetsgenerator. Der anvendes en blanding af LFSR og FCSR, og kombinationsfunktionen er XOR.
Tærskelgenerator FCSR. Alle registre er FCSR, og den samlende funktion er majorisering.
Tærskelgenerator LFSR/FCSR. Der anvendes en blanding af LFSR og FCSR, og den samlende funktion er majorisering.
Summeringsgenerator FCSR. Alle registre er FCSR, og joinfunktionen tilføjes med carry.
Summeringsgenerator LFSR/FCSR. Der anvendes en blanding af LFSR og FCSR, og joinfunktionen er carry-add. [3]

Ansøgning

Skifteregistre med carry-feedback kan tjene som grundlag for at skabe forskellige generatorer (hvoraf nogle er beskrevet ovenfor), samt forskellige stream-cifre.

F-FCSR

Hovedartikel: F-FCSR .

F-FCSR er en familie af strømcifre baseret på brugen af et carry feedback shift register (FCSR) med et lineært outputfilter. Idéen til chifferen blev foreslået af Terry Berger, François Arnault og Cédric Larade. F-FCSR blev indsendt til eSTREAM- konkurrencen , blev inkluderet på listen over vindere af konkurrencen i april 2008, men senere blev en kryptografisk svaghed afsløret, og i september 2008 blev F-FCSR afnoteret fra eSTREAM.

Se også

Noter

↑ 1 2 A. Klapper En undersøgelse af feedback med bæreskiftregistre (downlink)
↑ A. Klapper og M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, i Journal of Cryptology vol. 10, s. 111-147 , 1997, [1] (utilgængeligt link)
↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 B. Schneier, 2013 .
↑ 1 2 A. Klapper og M. Goresky, Fibonacci og Galois Repræsentationer af feedback med Carry Shift Registers , 2004, [2] Arkiveret 23. september 2015 på Wayback Machine
↑ 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier og Benjamin Pousse, A new approach for FCSRs , [3] Arkiveret 2. juni 2018 på Wayback Machine

Litteratur

Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildetekster i C-sprog. - Triumf, 2013. - 816 s. - ISBN 978-5-89392-527-2 .