Lineært 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 5. oktober 2016; checks kræver 44 redigeringer .

Lineært feedback- skiftregister ( LFSR ) er et skifteregister af bitord , værdien af input (glidende) bit er lig med en lineær boolsk funktion fra værdierne af de resterende bits i registeret før skiftet. Det kan organiseres af både software og hardware. Det bruges til at generere pseudo-tilfældige bitsekvenser , som især bruges i kryptografi [1] . Et skiftregister med bærefeedback fungerer efter et lignende princip. generaliseret feedback-skiftregister .

Beskrivelse

I skifteregisteret med lineær feedback (RSLOS) er der to dele (moduler):

det egentlige skifteregister;
et feedback-kredsløb (eller subrutine), der beregner værdien af den indsatte bit.

Registeret består af funktionelle hukommelsesceller (bits af et eller flere maskinord), som hver lagrer den aktuelle tilstand (værdi) af en bit. Antallet af celler kaldes registrets længde. Bits (celler) er normalt nummereret med tal , indholdet af den -th celle er angivet med . Værdien af den nye bit bestemmes før bitforskydningen i registeret og først efter at skiftet er skrevet til cellen , og den næste genererede bit ekstraheres fra cellen. $L$ $i = 0,\;1,\;\prikker,\;L-1$ $jeg$ $S_{(L-1)-i}$ $S_L$ $0$ $L-1$

Feedbackfunktionen for LFSR er en lineær boolesk funktion af værdierne af alle eller nogle bits af registeret. Funktionen multiplicerer registerbittene med koefficienterne , hvor . Antallet af koefficienter er det samme som antallet af registerbits . Koefficienterne tager værdierne , og den sidste koefficient er lig med, da LFSR er givet af det karakteristiske gradpolynomium . Modulo 2-addition (“XOR”-operationen, angivet i formler med symbolet “ ”) eller dens logiske inversion “ XNOR ” er lineære booleske funktioner og bruges oftest i sådanne registre [2] . I dette tilfælde kaldes de bits, der er variable i feedbackfunktionen, taps , og selve registeret kaldes Fibonacci- konfigurationen [3] . $c_{i}$ $i = 1, \; 2,\; \prikker,\; L$ $L$ $c_{i}$ $\{ 0, \; en \}$ $c_L$ $c_L = 1$ $L$ $\plus$

Registerkontrol i hardwareimplementeringer udføres ved at påføre en skiftimpuls (ellers kaldet en clock eller clock puls ) til alle celler. Registerstyring i softwareimplementeringer udføres ved at udføre en loop . Ved hver iteration af sløjfen beregnes feedbackfunktionen, og der udføres et bitskifte i ordet.

Sådan virker det

Under hver clock-cyklus udfører det lineære feedback-skifteregister følgende operationer:

den bit, der er placeret i cellen, læses ; denne bit er den næste bit i outputsekvensen; $L-1$
feedbackfunktionen beregner en ny værdi for cellen ved hjælp af de aktuelle værdier af cellerne; $0$
indholdet af hver celle flyttes til næste celle , hvor ; $jeg$ $i+1$ $i = 0,\;1,\;\prikker,\;L-2$
cellen skrives til den bit, der tidligere er beregnet af feedbackfunktionen. $0$

Hvis feedbackfunktionen udfører den logiske operation " XOR " (eksklusiv ELLER), kan værdierne af bits (celler) beregnes ved hjælp af følgende formler [4] :

$S_L=(c_1*S_{L-1})\oplus(c_2*S_{L-2})\oplus\dots\oplus(c_L*S_{0})$

$S_{L+1}=(c_1*S_{L})\oplus(c_2*S_{L-1})\oplus\dots\oplus(c_L*S_{1})$ $...$ $S_{L+j-1}=(c_1*S_{L+j-2})\oplus(c_2*S_{L+j-3})\oplus\dots\oplus(c_L*S_{j-1} )$

Egenskaber

Periodicitet

Skifteregisterets periode er minimumlængden af den resulterende sekvens, før den begynder at gentages. Længden LFSR har begyndelsestilstande, der definerer værdierne af bits i cellerne. Af disse er tilstandene ikke-nul, så den genererede sekvens har en periode på . Perioden for den genererede sekvens er maksimal og lig med , hvis feedbackpolynomiet (eller karakteristisk polynomium) over feltet er primitivt . For at gøre dette er det nødvendigt (men ikke tilstrækkeligt) at opfylde følgende 2 betingelser: $L$ $2^{{L}}$ $2^{L}-1$ $T\leq2^{L}-1$ $2^{L}-1$ $C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+\dots +c_{1}x+1$ ${\mathrm {GF}}(2)$

et lige antal tryk;
tryknumre, taget alle sammen og ikke i par, er coprime .

Antallet af alle mulige primitive polynomier er , hvor er Euler-funktionen [5] . Registeret givet af et sådant polynomium kaldes det maksimale periodeskiftregister (eller pseudo-tilfældige sekvensgenerator ), og de genererede sekvenser kaldes maksimale periodesekvenser (eller M-sekvenser ) [4] [6] . $\tfrac{\phi(2^L-1)}{L}$ $\phi$

Lineær kompleksitet

Den lineære kompleksitet af en uendelig binær sekvens er tallet, som er defineret som følger: $S=(S_0,\;S_1,\;S_2,\;\prikker)$ $L(S)$

hvis er en nul-sekvens, så ; $S=(0,\;0,\;0,\;\prikker)$ $L(S)=0$
hvis der ikke er nogen LFSR, der genererer , så ; $S$ $L(S) = \infty$
ellers lig med længden af den korteste LFSR, der genererer . $L(S)$ $S$

Den lineære kompleksitet af en endelig binær sekvens er et tal svarende til længden af den korteste LFSR, der genererer denne sekvens. $S_n=(S_0,\;S_1,\;\prikker,\;S_n)$ $L(S_n)$

Den lineære kompleksitet af et lineært feedback-skiftregister angiver, hvor tæt den genererede sekvens er på tilfældig . En effektiv algoritme til at bestemme den lineære kompleksitet af en endelig binær sekvens er Berlekamp-Massey-algoritmen .

Korrelationsuafhængighed

I et forsøg på at opnå en høj lineær kompleksitet af den genererede sekvens kombinerer kryptografer ikke-lineært output fra flere skifteregistre. I dette tilfælde kan en eller flere outputsekvenser (eller endda output fra individuelle LFSR'er) forbindes med en fælles strøm og åbnes af en kryptoanalytiker . Et hack baseret på en sådan sårbarhed kaldes et korrelationsangreb . Hovedideen med et sådant hack er at finde en vis sammenhæng mellem output fra generatoren og output fra dens komponentdele. Så kan man ved at observere udgangssekvensen få information om disse mellemudgange og dermed hacke generatoren. Thomas Siegenthaler har vist, at det er muligt at definere korrelationsuafhængighed præcist, og at der er en afvejning mellem korrelationsuafhængighed og lineær kompleksitet [7] .

Softwareimplementering

Softwareimplementeringer af RSLOS er ret langsomme og virker hurtigere, hvis de er skrevet i assembler . En af løsningerne er parallel brug af 16 RSLOS (eller 32, afhængig af ordlængden i computerarkitekturen). I et sådant skema bruges et array af ord, hvis størrelse er lig med længden af skifteregisteret, og hver bit af ordet refererer til sin egen LFSR. Da det samme antal tryksekvenser bruges, kan dette give en mærkbar gevinst i generatorens ydeevne [3] .

Fibonacci-konfiguration

Overvej et 32-bit skifteregister. Der er en flugtsekvens for det . Dette betyder, at for at generere en ny bit, er det nødvendigt at summere 31., 30., 29., 27., 25. og 0. bit ved hjælp af XOR- operationen. Den resulterende LFSR har en maksimal periode . Koden for et sådant register i C er som følger: $\venstre(32,\;31,\;30,\;28,\;26,\;1\højre)$ $2^{32}-1$

int LFSR_Fibonacci ( ugyldig ) { statisk lang S = 0x00000001 uden fortegn ; S = (((( S >> 31 ) ^ ( S >> 30 ) ^ ( S >> 29 ) ^ ( S >> 27 ) ^ ( S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | ( S >> 1 ); retur S & 0x00000001 ; }

Galois-konfiguration

Som i Fibonacci-konfigurationen er tilbagekoblingskredsløbet et sæt XOR-operationer af tap-bittene med output fra generatoren, men rækkefølgen af bits i registeret er omvendt: -th bit er input og -th bit er udgangen . Resultatet af tilføjelsen skrives til den næste celle, og den nye outputbit skrives til -th. Således, hvis den genererede bit er lig nul, så forskydes alle bit i cellerne til højre uden ændringer, hvis den genererede bit er lig med én, så ændrer tap-bittene deres værdi til det modsatte, og alle bits forskydes til højre. Både Fibonacci-konfigurationen og Galois -konfigurationen af samme længde genererer de samme sekvenser, men forskudt i tid fra hinanden (i dette tilfælde kan de interne tilstande af registrene være forskellige) [8] . $L-1$ $0$ $L-1$

Denne generator har ikke større kryptografisk styrke , men den giver en ydelsesforstærkning: alle XOR-operationer gennem parallelisering kan udføres i én operation og ikke sekventielt efter hinanden, som i Fibonacci-konfigurationen. Denne ordning vil også give en gevinst i hardwareimplementering.

Koden for et 32-bit skiftregister i C er som følger:

int LFSR_Galois ( ugyldig ) { // for polynomium 0x80000057, omvendt 0xea000001 statisk uden fortegn lang S = 0x00000001 ; if ( S & 0x00000001 ) { S = (( S ^ 0x80000057 ) >> 1 ) | 0x80000000 ; returner 1 ;} andet { S >>= 1 ; returner 0 ;} }

Det er værd at bemærke, at en løkke med et fast antal funktionskald LFSR_Galoisi Galois-konfigurationen er cirka 2 gange hurtigere end en funktion LFSR_Fibonaccii Fibonacci-konfigurationen ( MS VS 2010 compiler på Intel Core i5 ).

Et eksempel på en genereret sekvens

Fibonacci-konfiguration

Lad LFSR være givet ved det karakteristiske polynomium . Det betyder, at tap- bittene bliver 2. og 0., og enheden i polynomialformlen betyder, at 0. bit er input. Feedbackfunktionen har formen . Lad os sige, at den oprindelige tilstand af skifteregisteret var sekvensen . Yderligere tilstande i registret er vist i tabellen nedenfor: $x^{3}+x+1$ $S_j=S_{j-1}\oplus S_{j-3}$ $\venstre[0,\;0,\;1\højre]$

Trinnummer	Stat	Bit genereret
0	$\venstre[0,\;0,\;1\højre]$	en
en	$\venstre[1,\;0,\;0\højre]$	0
2	$\venstre[1,\;1,\;0\højre]$	0
3	$\venstre[1,\;1,\;1\højre]$	en
fire	$\venstre[0,\;1,\;1\højre]$	en
5	$\venstre[1,\;0,\;1\højre]$	en
6	$\venstre[0,\;1,\;0\højre]$	0
7	$\venstre[0,\;0,\;1\højre]$	en

Da den interne tilstand i det syvende trin vendte tilbage til sin oprindelige tilstand, vil bitsene blive gentaget fra næste trin. Det vil sige, at den genererede sekvens er som følger: (rækkefølgen af bits i sekvensen svarer til den rækkefølge, hvori de blev genereret af LFSR). Således er sekvensens periode 7, det vil sige den maksimalt mulige værdi, som skete på grund af primitiviteten af det givne polynomium. $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$

Galois-konfiguration

Lad os tage det samme karakteristiske polynomium, det vil sige . Kun 1. bit tilføjes til outputbit. Starttilstanden er den samme. Yderligere tilstande i registret: $c_3=c_1=1$ $c_2=0$

Trinnummer	Stat	Bit genereret
0	$\venstre[0,\;0,\;1\højre]$	en
en	$\venstre[1,\;0,\;1\højre]$	en
2	$\venstre[1,\;1,\;1\højre]$	en
3	$\venstre[1,\;1,\;0\højre]$	0
fire	$\venstre[0,\;1,\;1\højre]$	en
5	$\venstre[1,\;0,\;0\højre]$	0
6	$\venstre[0,\;1,\;0\højre]$	0
7	$\venstre[0,\;0,\;1\højre]$	en

Registerets interne tilstand i det syvende trin vendte tilbage til sin oprindelige tilstand, derfor er dets periode også lig med 7. I modsætning til Fibonacci-konfigurationen viste de interne tilstande af registeret sig at være forskellige, men den genererede sekvens er den samme , kun forskudt med 4 cyklusser : (rækkefølgen af bits i sekvensen svarer til rækkefølgen af deres generering af LFSR). $\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;...\right]$

Matrixrepræsentation af LFSR

afsnit af den engelske artikel

Generering af primitive polynomier

At beregne et primitivt polynomium over et felt er et ret kompliceret matematisk problem: for at generere et primitivt gradspolynomium skal du kende faktorerne for tallet . Det er nemmere at vælge et polynomium tilfældigt og teste det for primitivitet [3] . En anden metode er at bruge færdige tabeller, der viser antallet af tryksekvenser, der giver den maksimale periode for generatoren. Nedenfor er en tabel med primitive polynomier over feltet for skifteregistre med en maksimal periode på op til 19 bit [5] . Det er værd at overveje, at en generator af en given længde kan have mere end et primitivt polynomium i henhold til deres egenskaber . En komplet liste for registre på 4 til 32 bit lange kan findes her . ${\mathrm {GF}}(2)$ $k$ $2^{k}-1$ ${\mathrm {GF}}(2)$

stykker, $n$	Primitivt polynomium	Periode, $2^{n}-1$	Antal primitive polynomier
2	$x^{2}+x+1$	3	en
3	$x^3+x^2+1$	7	2
fire	$x^4+x^3+1$	femten	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{7}+x^{6}+1$	127	atten
otte	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	16
9	$x^{9}+x^{5}+1$	511	48
ti	$x^{10}+x^{7}+1$	1023	60
elleve	$x^{11}+x^{9}+1$	2047	176
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$	4095	144
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$	8191	630
fjorten	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
femten	$x^{15}+x^{14}+1$	32767	1800
16	$x^{16}+x^{14}+x^{13}+x^{11}+1$	65535	2048
17	$x^{17}+x^{14}+1$	131071	7710
atten	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20 - 168	[en]
2 - 786, 1024, 2048, 4096	[2]

Fordele og ulemper

Fordele

høj ydeevne af kryptografiske algoritmer oprettet på basis af LFSR (for eksempel stream ciphers );
brugen af kun de enkleste bitoperationer til addition og multiplikation, implementeret i hardware i næsten alle computerenheder;
gode kryptografiske egenskaber (LFSR'er kan generere lange periodesekvenser med gode statistiske egenskaber);
på grund af deres struktur analyseres LFSR'er let ved hjælp af algebraiske metoder.

Ulemper

Et af hovedproblemerne ved LFSR er, at deres softwareimplementering er ekstremt ineffektiv: sparsomme feedbackpolynomier skal undgås, da de fører til en lettere hacking ved korrelationsangreb , og tætte polynomier er meget langsomme at beregne. Derfor er en softwareimplementering af en sådan generator ikke hurtigere end en DES -implementering .
Lineariteten af sekvensen ved udgangen af registeret gør det muligt entydigt at bestemme feedbackpolynomiet over serielle bits ved hjælp af Berlekamp-Massey- algoritmen eller Euklid-algoritmen [3] [4] . $C(x)$ $2L$
Den relative lette analyse ved algebraiske metoder letter ikke kun udviklingen, men øger også chancerne for at bryde en generator baseret på LFSR.

Måder at forbedre den kryptografiske styrke af genererede sekvenser

Generatorer med flere skifteregistre

Denne type generator består af flere lineære feedback-skifteregistre, der genererer bit hhv. Dernæst konverteres de genererede bits af en boolsk funktion . Det skal bemærkes, at for generatorer af denne type er registerlængderne , , relativt prime i forhold til hinanden. $x_{1,i},\;x_{2,i},\;\dots,\;x_{M,i}$ $f(x_{1,i},\;x_{2,i},\;\prikker,\;x_{M,i})$ $L_i$ $i=1,\;2,\;\prikker,\;M$

Perioden for denne generator er , hvor er det samlede antal celler. Derfor øger brugen af flere LFSR'er perioden for den genererede sekvens sammenlignet med et enkelt register, hvilket øger generatorens kryptografiske styrke . Det øger også den lineære kompleksitet eller længden af det korteste register svarende til en given generator. Et sådant register findes ved hjælp af Berlekamp-Massey-algoritmen ved hjælp af den genererede sekvens. I bedste fald er dens længde i forhold til perioden for den genererede sekvens [4] . $T=(2^{L_1}-1)\cdot(2^{L_2}-1)\cdots(2^{L_M}-1)\lesssim2^L$ $L=\sum\limits_{i=1}^M L_i$

Generatorer med ikke-lineære transformationer

Blokdiagrammet for en sådan generator er ikke forskelligt fra diagrammet for den tidligere generator. Den største forskel er, at transformationsenheden er givet af en ikke-lineær boolesk funktion . Som sådan en funktion tages for eksempel Zhegalkin-polynomiet (ifølge Zhegalkin- sætningen kan enhver boolsk funktion være entydigt repræsenteret af Zhegalkin-polynomiet). $f(x_1, x_2, \prikker, x_M)$

En ikke-lineær generator kan også implementeres på et skifteregister med ikke-lineær feedback . Det kan give varianter af sekvenser af den maksimale periode , som er mere end den for LFSR [5] . $2^{2^{L-1}-L}$

Den kryptografiske styrke af denne generator øges på grund af den anvendte funktions ikke-linearitet. At bestemme registrenes tilstand ud fra den genererede bitsekvens er et komplekst matematisk problem, fordi der ikke kendes nogen algoritme, der gendanner de oprindelige tilstande.

Denne metode bruges for eksempel i Geff-generatoren og den generaliserede Geff-generator, dog kan sådanne generatorer hackes ved korrelationsanalyse [7] .

Oscillatorer med forskellige skifteregistertiminger

Stop-and-go generator

Stop-and-Go- generatoren ( eng. Stop-and-Go , Both-Piper ) bruger outputtet fra LFSR-1 til at styre LFSR-2's klokfrekvens , så LFSR-2 ændrer sin tilstand på et tidspunkt kun hvis udgangen af LFSR-1 på det tidspunkt var lig med én. Dette skema modstod ikke korrelationsåbningen [3] . $t_{i}$ $t_{i-1}$

For at øge kryptografisk styrke blev en interleaved stop-go generator foreslået . Den bruger tre skifteregistre af forskellig længde. Her styrer LFOS-1 klokfrekvensen for 2. og 3. register, dvs. LFSR-2 ændrer sin tilstand, når LFSR-1-udgangen er lig med en, og LFSR-3 - når LFSR-1-udgangen er lig nul. Udgangen af generatoren er driften af modulo to af udgangene på RLOS-2 og RLLS-3. Denne generator har en stor periode og en stor lineær kompleksitet. Der er en metode til korrelationsåbning af RLOS-1, men dette svækker ikke generatorens kryptografiske egenskaber.

Et mere kompliceret clocking-skema bruges i en to-vejs stop-and-go generator , som bruger 2 skifteregistre af samme længde. Hvis outputtet af LFSR-1 på et bestemt tidspunkt er lig med nul, og på et tidspunkt er det lig med én, så klokkes LFSR-2 ikke på tidspunktet . Hvis udgangen af LFSR-2 på tidspunktet for tiden er lig med nul, og på tidspunktet er den lig med én, og hvis dette register er clocket på tidspunktet , så er LFSR-1 i samme øjeblik ikke uret. Den lineære kompleksitet af dette kredsløb er omtrent lig med perioden for den genererede sekvens. $t_{i-1}$ $t_{i-2}$ $t_{i}$ $t_{i-1}$ $t_{i-2}$ $t_{i}$

Selvdecimerende generator

Selvdecimerede oscillatorer styrer deres egen frekvens . Der er to typer af sådanne generatorer. Den første blev foreslået af Rainer Rüppel . Det består af et skifteregister og et lineært feedbackkredsløb, der clocker registeret baseret på, hvordan skifteregisteret udsender. Hvis LFSR-udgangen er lig med én, klokkes registeret med én frekvens, og hvis udgangen er nul, så med en anden. Den anden type blev foreslået af Bill Chambers og Dieter Kollman . Feedbackkredsløbet modtager ikke selve udgangssignalet, men resultatet af XOR-driften af visse LFSR-bits.

Der er også krympende og selvkrympende generatorer . _ _ _ De er ret nye, og ikke alle deres egenskaber er velundersøgte. Den første bruger to LFSR'er. Hvis en clock-impuls påføres generatoren, og udgangen af RLOS-1 er én, så vil udgangen af generatoren være udgangen af RLLS-2. Ellers, når en urimpuls påføres, nulstilles begge bit, og uret starter forfra. I den anden generator, i stedet for at kontrollere udgangene fra to registre for 0 eller 1, kontrolleres 2 bits af et register.

Den decimerede generator kan hackes, hvis feedbackpolynomierne decimeres. Derudover er dens generationshastighed ikke konstant. En selvdecimerende generator har brug for omkring 2 gange mindre hukommelse end den første, men den arbejder 2 gange langsommere [7] .

Multirate oscillator med indre produkt

Denne generator bruger to skifteregistre RSLOS-1 og RSLOS-2. Klokkefrekvensen for RSLOS-2 er flere gange højere end for RSLOS-1. Visse bits af disse registre multipliceres med hinanden ved hjælp af OG- operationen . Resultaterne af multiplikationerne adderes ved XOR-operationen, og outputsekvensen opnås. Denne generator har en høj lineær kompleksitet og har gode statistiske egenskaber. Imidlertid kan dens tilstand bestemmes ud fra udgangssekvensen af længde , hvor og er længderne af henholdsvis LFSR-1 og LFSR-2, og er forholdet mellem deres klokfrekvenser. $d$ $L_1 + L_2 + \log_2{d}$ $L_{1}$ $L_{2}$ $d$

Gollmann Cascade

Dette kredsløb er en forbedret version af stop-go generatoren. Den består af en sekvens af LFSR'er, hvor timingen af hver styres af den foregående LFSR. Hvis udgangen af LFSR-1 på tidspunktet er 1, klokkes LFSR-2. Hvis outputtet af LFSR-2 på tidspunktet er 1, bliver LFSR-3 clocket, og så videre. Outputtet fra den sidste LFSR er outputtet fra generatoren. Hvis længden af alle LFSRs er den samme og lig med , så er perioden for LFSR-systemet , og den lineære kompleksitet er [7] . $t_{i}$ $t_{i}$ $L$ $M$ $(2^L - 1)^M$ $L(S) = L(2^L - 1)^{M-1}$

Denne idé er enkel og kan bruges til at generere sekvenser med store perioder, store lineære kompleksiteter og gode statistiske egenskaber. Men desværre er de modtagelige for et angreb kaldet lock - in , når en kryptoanalytiker , der først genopretter inputsekvensen for det sidste register i kaskaden, bryder hele kaskaden, register for register. Når antallet af registre stiger, nærmer den genererede sekvens sig tilfældig , så det er bedre at bruge flere LFSR'er med lille længde end færre lange LFSR'er. $M$

Flertalsgeneratorer

Majoritetsgenerator (eller tærskel ) består af et stort antal skifteregistre, hvis udgange går til den enhed, der er specificeret af majoriseringsfunktionen, for eksempel majoritetselementet . Det særlige ved denne generator er, at hvert af skifteregistrene har sin egen clockbit , , som er variablerne for majoritetsfunktionen. For tre registre har en sådan funktion f.eks. formen . Kun de registre forskydes, hvis clock-bits er lig med værdien , det vil sige, at forskydningen af registrene sker på størstedelen af værdierne af sådanne bits: 0 eller 1. $a_{i}$ $i=1,\;2,\;\prikker,\;M$ $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ $b(t)$

Således får vi en generator med et variabelt antal LFSR'er. Dens lineære kompleksitet er , hvor er længden af det -th register [7] . Ulemperne ved en sådan generator er muligheden for direkte opregning og korrelationsåbning (hver outputbit giver noget information om skifteregisterets tilstand, for at være præcis - 0,189 bit). $L(S) = \sum\grænser_{i,j=1}^M L_iL_j$ $L_i$ $jeg$

Lignende generatorer bruges i A5 - krypteringsalgoritmer (A5/1, A5/2).

Ansøgning

Lineære feedback-skiftregistre kan implementeres i hardware, hvilket gør det muligt at bruge dem til hurtig pseudo-tilfældig sekvensgenerering , såsom direkte sekvens spredt spektrum eller støjsignalgenerering [9] .

Brug i kryptografi

Lineære feedback-skifteregistre har længe været brugt som pseudo-tilfældige sekvensgeneratorer til strømchiffer (især i militær kryptografi ). LFSR er dog et lineært skema og kan i nogle tilfælde nemt hackes. For eksempel kan en kryptoanalytiker opsnappe en del af chifferteksten og bruge den ved at bruge den ovennævnte Berlekamp-Massey-algoritme til at rekonstruere en minimumsstørrelse LFSR, der efterligner den originale LFSR. Derefter kan den opsnappede tekst føres ind i det modtagne register og dekrypteres. Metoder til at øge den kryptografiske styrke af stream ciphers baseret på LFSR er givet ovenfor .

Det lineære feedback-skiftregister er grundlaget for stream-cifre som A5/1 og A5/2, der bruges i GSM -standarden, og E0 -chifferen , der bruges i Bluetooth . A5/2-cifferet er blevet brudt, og A5/1- og E0-cifferet er alvorligt fejlbehæftet [10] [11] .

Det lineære feedback-skiftregister er tæt forbundet med den lineære kongruentiale generator [12] .

Brug som tællere

Frekvensen af den genererede LFSR-sekvens giver dig mulighed for at bruge den som en urdeler eller tæller [13] . En tæller baseret på en sådan oscillator har et forenklet feedbackkredsløb, i modsætning til konventionelle binære eller grå kodetællere , og kan derfor fungere ved høje clockhastigheder. Du skal dog sørge for, at en sådan tæller aldrig går i nultilstand.

Test af digitale enheder

I modsætning til en konventionel tæller går LFSR ikke fra en tilstand til en anden i rækkefølgen af binær tælling, hvilket gør det muligt at bruge den til at generere et testsignal, når der detekteres fejl i logiske kredsløb [6] .

Ligeledes bruges lineære feedback-skiftregistre i indbygget selvtest ( indbygget selvtest , BIST ) til signaturanalyse (detektion af bitfejl) i logiske kredsløb. Sådanne systemer bruges på grund af det begrænsede antal mikrokredsløbsudgange (ikke alle mellemliggende bitværdier kan anvendes på udgangen). BIST-systemet består af 3 blokke: en testsekvensgenerator og en signaturanalysator, som er bygget på basis af LFSR, og en testcontroller. Skiftregisteret i analysatoren "komprimerer" resultatet af kredsløbet for testsekvensen til en signatur og fortsætter med at arbejde, indtil alle dets bit, bortset fra 0, bliver lig med nul, det vil sige tilstanden . Sammen med LFSR er der en binær tæller, der tæller antallet af cyklusser siden afslutningen af testreaktionskomprimeringen. Hvis registrets begyndelsestilstand svarede til referencesignaturen (signatur af et fejlfrit kredsløb), så svarer tælleraflæsningen til nummeret på den fejlagtige bit [14] [15] . $\venstre[1,\;0,\;0,\;...,\;0\højre]$

Da LFSR udfører komprimering med tab, er det sandsynligt, at i et skema med fejl vil den resulterende signatur være lig med referencen. Dette kan undgås ved at bruge en signaturanalysator med flere indgange.

Scrambling

Lineære feedback-skiftregistre bruges i scrambling for at producere en digital strøm med tilfældige sekvensegenskaber . En pseudo-tilfældig LFSR-sekvens med maksimal længde tilføjes modulo 2 til den transmitterede bitstrøm, og sekvensen genereres med samme hastighed som datatransmissionen. Nogle systemer og teknologier, der bruger scrambling er:

ATSC [16] ;
DAB ;
DVB-T ;
NICAM ;
CDMA ;
100BASE-T2 Fast Ethernet ;
1000BASE-T Gigabit Ethernet ;
PCI Express 3.0 ;
SATA ;
Serial Attached SCSI ;
USB 3.0 ;
IEEE 802.11a ;
Bluetooth L.E.

Se også

Noter

↑ B. Sklyar, 2007 .
↑ Lineære feedbackskifteregistre i Virtex-enheder . Hentet 19. november 2014. Arkiveret fra originalen 2. november 2013. (ubestemt)
↑ 1 2 3 4 5 B. Schneier, 2013 .
↑ 1 2 3 4 Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ 1 2 3 Yu.B. Kobzarev, 2013 .
↑ 1 2 Larin, 2008 .
↑ 1 2 3 4 5 Fomichev, 2003 .
↑ Beker, Piper, 1982 .
↑ A. Sizonenko, 2012 .
↑ E. Barklan, E. Biham, N. Keller, 2008 .
↑ Y. Lu, W. Meier, S. Vaudenay, 2005 .
↑ D. Eastlake, J. Schiller, S. Crocker, 2005 .
↑ Effektive skiftregistre, LFSR-tællere og lange pseudo-tilfældige sekvensgeneratorer . Hentet 18. november 2014. Arkiveret fra originalen 25. januar 2021. (ubestemt)
↑ B. Harrington, 2008 .
↑ O. Dyachenko .
↑ V. Vargauzin, 1999 .

Litteratur

Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildetekster i C-sprog. - Triumf, 2013. - 816 s. - ISBN 978-5-89392-527-2 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssikkerhed : lærebog - M .: MIPT , 2011. - 225 s. — ISBN 978-5-7417-0377-9
Larin A. L. Fundamentals of digital electronics - M .: MIPT , 2008. - 314 s. — ISBN 978-5-7417-0228-4
Sklyar B. Digital kommunikation. Teoretisk grundlag og praktisk anvendelse. - Williams, 2007. - 1104 s. - ISBN 978-5-8459-0497-3 .
Kobzarev Yu. B. Moderne radar. - Ripol Classic, 2013. - 708 s. — ISBN 978-5-4584-7357-6 .
Fomichev V. M. Diskret matematik og kryptologi : Forelæsningsforløb / red. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - 397 s. — ISBN 978-5-86404-185-7
Beker H. , Piper F. Cipher systems: the protection of communications (engelsk) - London : Northwood Books , 1982. - 427 s. — ISBN 978-0-7198-2611-5
Sizonenko AB Multikanal digital støjkilde baseret på tilbagevendende skifteregister . - Special Equipment and Communications Magazine nr. 3, 2012. Arkiveksemplardateret 29. november 2014 påWayback Machine
Barklan E. , Biham E. , Keller N. Øjeblikkelig krypteringstekst-kun kryptering af GSM-krypteret kommunikation . - Tidsskrift for kryptologi nr. 21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Øjeblikkelig krypteringstekst kun krypteringsanalyse af GSM-krypteret kommunikation . - Krypto nr. 3621, 2005. (utilgængeligt link)
Eastlake D. , Schiller J. , Crocker S. Tilfældighedskrav til sikkerhed . - 2005.
Harrington B. Få dit boost fra BIST . — 2008. (utilgængeligt link)
Dyachenko O. N. Kompakt analyse over feltet GF(3).
Vargauzin V. Principper for digitalt tv af ATSC-standarden. - Tele-Sputnik magasin nr. 9 (47), 1999.

Lineært tilbagemeldingsskiftregister

Beskrivelse

Sådan virker det

Egenskaber

Periodicitet

Lineær kompleksitet

Korrelationsuafhængighed

Softwareimplementering

Fibonacci-konfiguration

Galois-konfiguration

Et eksempel på en genereret sekvens

Fibonacci-konfiguration

Galois-konfiguration

Matrixrepræsentation af LFSR

Generering af primitive polynomier

Fordele og ulemper

Fordele

Ulemper

Måder at forbedre den kryptografiske styrke af genererede sekvenser

Generatorer med flere skifteregistre

Generatorer med ikke-lineære transformationer

Oscillatorer med forskellige skifteregistertiminger

Flertalsgeneratorer

Ansøgning

Brug i kryptografi

Brug som tællere

Test af digitale enheder

Scrambling

Se også

Noter

Litteratur

Links