Linjä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 5 oktober 2016; kontroller kräver 44 redigeringar .

Linjärt återkopplingsskiftregister ( LFSR ) är ett skiftregister av bitord där värdet på den ingående (glidande) biten är lika med en linjär boolesk funktion från värdena för de återstående bitarna i registret före skiftet. Det kan organiseras av både mjukvara och hårdvara. Den används för att generera pseudo-slumpmässiga bitsekvenser , som används i synnerhet i kryptografi [1] . Ett skiftregister med bäråterkoppling och ett skiftregister med generaliserad återkoppling fungerar enligt en liknande princip .

Beskrivning

I skiftregistret med linjär återkoppling (RSLOS) finns två delar (moduler):

det faktiska skiftregistret;
en återkopplingskrets (eller subrutin) som beräknar värdet på den infogade biten.

Registret består av funktionella minnesceller (bitar av ett eller flera maskinord), som var och en lagrar det aktuella tillståndet (värdet) för en bit. Antalet celler kallas registrets längd. Bitar (celler) är vanligtvis numrerade med siffror , innehållet i den -e cellen betecknas med . Värdet på den nya biten bestäms före bitskiftet i registret och först efter att skiftet har skrivits till cellen , och nästa genererade bit extraheras från cellen. $L$ $i = 0,\;1,\;\prickar,\;L-1$ $i$ $S_{(L-1)-i}$ $S_L$ $0$ $L-1$

Återkopplingsfunktionen för LFSR är en linjär boolesk funktion av värdena för alla eller några bitar i registret. Funktionen multiplicerar registerbitarna med koefficienterna , där . Antalet koefficienter är detsamma som antalet registerbitar . Koefficienterna tar värdena och den sista koefficienten är lika med , eftersom LFSR ges av det karakteristiska polynomet av grad . Modulo 2-addition (”XOR”-operationen, betecknad i formler med symbolen “ ”) eller dess logiska inversion “ XNOR ” är linjära booleska funktioner och används oftast i sådana register [2] . I det här fallet kallas bitarna som är variabler för återkopplingsfunktionen taps , och själva registret kallas för Fibonacci- konfigurationen [3] . $c_{i}$ $i = 1, \; 2,\; \prickar,\; L$ $L$ $c_{i}$ $\{ 0, \; ett \}$ $c_L$ $c_L = 1$ $L$ $\ plus$

Registerstyrning i hårdvaruimplementationer utförs genom att applicera en skiftpuls (annars kallad klocka eller klockpuls ) till alla celler. Registerhantering i programimplementationer utförs genom att exekvera en loop . Vid varje iteration av slingan beräknas återkopplingsfunktionen och en bitförskjutning i ordet utförs.

Hur det fungerar

Under varje klockcykel utför det linjära återkopplingsskiftregistret följande operationer:

biten som finns i cellen läses ; denna bit är nästa bit i utgångssekvensen; $L-1$
återkopplingsfunktionen beräknar ett nytt värde för cellen med hjälp av de aktuella värdena för cellerna; $0$
innehållet i varje cell flyttas till nästa cell , där ; $i$ $i+1$ $i = 0,\;1,\;\prickar,\;L-2$
cellen skrivs till biten som tidigare beräknats av återkopplingsfunktionen. $0$

Om återkopplingsfunktionen utför den logiska operationen " XOR " (exklusiv ELLER), kan värdena för bitarna (cellerna) beräknas med hjälp av följande 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} )$

Egenskaper

Periodicitet

Perioden för skiftregistret är den minsta längden av den resulterande sekvensen innan den börjar upprepas. Längden LFSR har initiala tillstånd som definierar värdena för bitarna i cellerna. Av dessa är tillstånden icke-noll, så den genererade sekvensen har en period på . Perioden för den genererade sekvensen är maximal och lika med , om återkopplingspolynomet (eller karakteristiskt polynom) över fältet är primitivt . För att göra detta är det nödvändigt (men inte tillräckligt) att uppfylla följande två villkor: $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)$

ett jämnt antal kranar;
tappnummer, taget alla tillsammans, och inte i par, är coprime .

Antalet av alla möjliga primitiva polynom är , där är Euler-funktionen [5] . Registret som ges av ett sådant polynom kallas det maximala periodskiftregistret (eller pseudoslumpsekvensgeneratorn ), och de genererade sekvenserna kallas maximala periodsekvenser (eller M-sekvenser ) [4] [6] . $\tfrac{\phi(2^L-1)}{L}$ $\phi$

Linjär komplexitet

Den linjära komplexiteten för en oändlig binär sekvens är talet, som definieras enligt följande: $S=(S_0,\;S_1,\;S_2,\;\prickar)$ $L(S)$

if är en nollsekvens, då ; $S=(0,\;0,\;0,\;\prickar)$ $L(S)=0$
om det inte finns någon LFSR som genererar , då ; $S$ $L(S) = \infty$
annars lika med längden på den kortaste LFSR som genererar . $L(S)$ $S$

Den linjära komplexiteten för en finit binär sekvens är ett tal lika med längden på den kortaste LFSR som genererar denna sekvens. $S_n=(S_0,\;S_1,\;\prickar,\;S_n)$ $L(S_n)$

Den linjära komplexiteten hos ett linjärt återkopplingsskiftregister indikerar hur nära den genererade sekvensen är slumpmässig . En effektiv algoritm för att bestämma den linjära komplexiteten för en finit binär sekvens är Berlekamp-Massey-algoritmen .

Korrelationsoberoende

I ett försök att erhålla en hög linjär komplexitet hos den genererade sekvensen kombinerar kryptografer icke-linjärt utsignalerna från flera skiftregister. I det här fallet kan en eller flera utgångssekvenser (eller till och med utgångar från individuella LFSR) kopplas samman med en gemensam ström och öppnas av en kryptoanalytiker . Ett hack baserat på en sådan sårbarhet kallas en korrelationsattack . Huvudidén med ett sådant hack är att hitta en viss korrelation mellan utsignalen från generatorn och utsignalerna från dess beståndsdelar. Sedan kan man, genom att observera utgångssekvensen, få information om dessa mellanutgångar och därmed hacka generatorn. Thomas Siegenthaler har visat att det är möjligt att definiera korrelationsoberoende exakt, och att det finns en avvägning mellan korrelationsoberoende och linjär komplexitet [7] .

Programvaruimplementering

Mjukvaruimplementationer av RSLOS är ganska långsamma och fungerar snabbare om de är skrivna i assembler . En av lösningarna är parallell användning av 16 RSLOS (eller 32, beroende på ordlängden i datorarkitekturen). I ett sådant schema används en array av ord, vars storlek är lika med längden på skiftregistret, och varje bit av ordet hänvisar till sin egen LFSR. Eftersom samma antal uttagssekvenser används kan detta ge en märkbar vinst i generatorns prestanda [3] .

Fibonacci-konfiguration

Överväg ett 32-bitars skiftregister. Det finns en flyktsekvens för det . Detta betyder att för att generera en ny bit är det nödvändigt att summera de 31:a, 30:e, 29:e, 27:e, 25:e och 0:e bitarna med hjälp av XOR- operationen. Den resulterande LFSR har en maximal period . Koden för ett sådant register i C är följande: $\vänster(32,\;31,\;30,\;28,\;26,\;1\höger)$ $2^{32}-1$

int LFSR_Fibonacci ( ogiltig ) { statisk unsigned long S = 0x00000001 ; S = (((( S >> 31 ) ^ ( S >> 30 ) ^ ( S >> 29 ) ^ ( S >> 27 ) ^ ( S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | ( S >> 1 ); returnera S & 0x00000001 ; }

Galois-konfiguration

Som i Fibonacci-konfigurationen är återkopplingskretsen en uppsättning XOR-operationer av uttagsbitarna med utgången från generatorn, men ordningen på bitarna i registret är omvänd: den -th biten är ingången och den -th biten är utgången . Resultatet av tillägget skrivs till nästa cell, och den nya utgångsbiten skrivs till -th. Således, om den genererade biten är lika med noll, så skiftas alla bitar i cellerna till höger utan ändringar, om den genererade biten är lika med ett, så ändrar tappbitarna sitt värde till det motsatta, och alla bitar skiftas till höger. Både Fibonacci-konfigurationen och Galois -konfigurationen av samma längd genererar samma sekvenser, men förskjutna i tid från varandra (i detta fall kan registrens interna tillstånd skilja sig åt) [8] . $L-1$ $0$ $L-1$

Denna generator har inte större kryptografisk styrka , men den ger en prestandavinst: alla XOR-operationer genom parallellisering kan utföras i en operation, och inte sekventiellt efter varandra, som i Fibonacci-konfigurationen. Detta schema kommer också att ge en vinst i hårdvaruimplementering.

Koden för ett 32-bitars skiftregister i C är följande:

int LFSR_Galois ( ogiltig ) { // för polynom 0x80000057, reversed 0xea000001 static unsigned long S = 0x00000001 ; if ( S & 0x00000001 ) { S = (( S ^ 0x80000057 ) >> 1 ) | 0x80000000 ; returnera 1 ;} annat { S >>= 1 ; returnera 0 ;} }

Det är värt att notera att en slinga med ett fast antal funktionsanrop LFSR_Galoisi Galois-konfigurationen är ungefär 2 gånger snabbare än en funktion LFSR_Fibonaccii Fibonacci-konfigurationen ( MS VS 2010 kompilator på Intel Core i5 ).

Ett exempel på en genererad sekvens

Fibonacci-konfiguration

Låt LFSR ges av det karakteristiska polynomet . Detta betyder att tappbitarna blir 2:a och 0:e, och enheten i polynomformeln betyder att den 0:e biten är indata. Återkopplingsfunktionen har formen . Låt oss säga att det initiala tillståndet för skiftregistret var sekvensen . Ytterligare tillstånd i registret visas i tabellen nedan: $x^{3}+x+1$ $S_j=S_{j-1}\oplus S_{j-3}$ $\vänster[0,\;0,\;1\höger]$

Stegnummer	stat	Bit genererad
0	$\vänster[0,\;0,\;1\höger]$	ett
ett	$\vänster[1,\;0,\;0\höger]$	0
2	$\vänster[1,\;1,\;0\höger]$	0
3	$\vänster[1,\;1,\;1\höger]$	ett
fyra	$\vänster[0,\;1,\;1\höger]$	ett
5	$\vänster[1,\;0,\;1\höger]$	ett
6	$\vänster[0,\;1,\;0\höger]$	0
7	$\vänster[0,\;0,\;1\höger]$	ett

Eftersom det interna tillståndet i det sjunde steget återgick till sitt ursprungliga tillstånd, kommer bitarna att repeteras med början från nästa steg. Det vill säga, den genererade sekvensen är som följer: (ordningen på bitarna i sekvensen motsvarar den ordning i vilken de genererades av LFSR). Således är sekvensens period 7, det vill säga det maximala möjliga värdet, vilket hände på grund av det givna polynomets primitivitet . $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$

Galois-konfiguration

Låt oss ta samma karakteristiska polynom, det vill säga . Endast den 1:a biten läggs till utgångsbiten. Det ursprungliga tillståndet är detsamma. Ytterligare stater i registret: $c_3=c_1=1$ $c_2=0$

Stegnummer	stat	Bit genererad
0	$\vänster[0,\;0,\;1\höger]$	ett
ett	$\vänster[1,\;0,\;1\höger]$	ett
2	$\vänster[1,\;1,\;1\höger]$	ett
3	$\vänster[1,\;1,\;0\höger]$	0
fyra	$\vänster[0,\;1,\;1\höger]$	ett
5	$\vänster[1,\;0,\;0\höger]$	0
6	$\vänster[0,\;1,\;0\höger]$	0
7	$\vänster[0,\;0,\;1\höger]$	ett

Det interna tillståndet för registret i det sjunde steget återgick till sitt ursprungliga tillstånd, därför är dess period också lika med 7. Till skillnad från Fibonacci-konfigurationen visade sig de interna tillstånden i registret vara olika, men den genererade sekvensen är densamma , endast skiftad med 4 cykler : (ordningen på bitarna i sekvensen motsvarar ordningen för deras generering av LFSR). $\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;...\right]$

Matrisrepresentation av LFSR

avsnitt i den engelska artikeln

Generera primitiva polynom

Att beräkna ett primitivt polynom över ett fält är ett ganska komplicerat matematiskt problem: för att generera ett primitivt gradpolynom måste du känna till talets faktorer . Det är lättare att slumpmässigt välja ett polynom och testa det för primitivitet [3] . En annan metod är att använda färdiga tabeller som listar antalet uttagssekvenser som ger den maximala perioden för generatorn. Nedan finns en tabell med primitiva polynom över fältet för skiftregister med en maximal period på upp till 19 bitar [5] . Det är värt att tänka på att en generator av vilken längd som helst kan ha mer än ett primitivt polynom beroende på deras egenskaper . En komplett lista för register 4 till 32 bitar långa finns här . ${\mathrm {GF}}(2)$ $k$ $2^{k}-1$ ${\mathrm {GF}}(2)$

bitar, $n$	Primitivt polynom	Period, $2^{n}-1$	Antal primitiva polynom
2	$x^{2}+x+1$	3	ett
3	$x^3+x^2+1$	7	2
fyra	$x^4+x^3+1$	femton	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{7}+x^{6}+1$	127	arton
åtta	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	16
9	$x^{9}+x^{5}+1$	511	48
tio	$x^{10}+x^{7}+1$	1023	60
elva	$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
fjorton	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
femton	$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
arton	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20 - 168	[ett]
2 - 786, 1024, 2048, 4096	[2]

Fördelar och nackdelar

Fördelar

hög prestanda för kryptografiska algoritmer skapade på basis av LFSR (till exempel strömchiffer );
användningen av endast de enklaste bitoperationerna för addition och multiplikation, implementerade i hårdvara i nästan alla datorenheter;
bra kryptografiska egenskaper (LFSR kan generera långa periodsekvenser med bra statistiska egenskaper);
på grund av sin struktur kan LFSR lätt analyseras med algebraiska metoder.

Nackdelar

Ett av huvudproblemen med LFSR är att deras mjukvaruimplementering är extremt ineffektiv: glesa återkopplingspolynom måste undvikas, eftersom de leder till en lättare hackning genom korrelationsattack , och täta polynom är mycket långsamma att beräkna. Därför är en mjukvaruimplementering av en sådan generator inte snabbare än en DES- implementering .
Linjäriteten hos sekvensen vid registrets utgång gör det möjligt att unikt bestämma återkopplingspolynomet över seriella bitar med hjälp av Berlekamp-Massey- algoritmen eller Euklid-algoritmen [3] [4] . $C(x)$ $2L$
Den relativa lättheten att analysera med algebraiska metoder underlättar inte bara utvecklingen utan ökar också chanserna att bryta en generator baserad på LFSR.

Sätt att förbättra den kryptografiska styrkan hos genererade sekvenser

Generatorer med flera skiftregister

Denna typ av generator består av flera linjära återkopplingsskiftregister som genererar respektive bitar. Därefter konverteras de genererade bitarna av någon boolesk funktion . Det bör noteras att för generatorer av denna typ är registerlängderna , , relativt prime till varandra. $x_{1,i},\;x_{2,i},\;\dots,\;x_{M,i}$ $f(x_{1,i},\;x_{2,i},\;\dots,\;x_{M,i})$ $L_i$ $i=1,\;2,\;\prickar,\;M$

Perioden för denna generator är , där är det totala antalet celler. Därför ökar användningen av flera LFSR:er perioden för den genererade sekvensen jämfört med ett enda register, vilket ökar generatorns kryptografiska styrka . Det ökar också den linjära komplexiteten eller längden på det kortaste registret som motsvarar en given generator. Ett sådant register hittas med hjälp av Berlekamp-Massey-algoritmen med användning av den genererade sekvensen. I bästa fall står dess längd i proportion till perioden för den genererade sekvensen [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 icke-linjära transformationer

Blockschemat för en sådan generator skiljer sig inte från diagrammet för den tidigare generatorn. Den största skillnaden är att transformationsenheten ges av en icke-linjär boolesk funktion . Som en sådan funktion tas till exempel Zhegalkin-polynomet (enligt Zhegalkin -satsen kan vilken boolesk funktion som helst representeras unikt av Zhegalkin-polynomet). $f(x_1, x_2, \dots, x_M)$

En icke-linjär generator kan också implementeras på ett skiftregister med icke-linjär återkoppling . Det kan ge varianter av sekvenser av den maximala perioden , som är mer än den för LFSR [5] . $2^{2^{L-1}-L}$

Den kryptografiska styrkan hos denna generator ökar på grund av olinjäriteten hos den använda funktionen. Att bestämma tillståndet för registren från den genererade bitsekvensen är ett komplext matematiskt problem, eftersom ingen algoritm är känd som återställer de ursprungliga tillstånden.

Denna metod används till exempel i Geff-generatorn och den generaliserade Geff-generatorn, dock kan sådana generatorer hackas genom korrelationsanalys [7] .

Oscillatorer med olika skiftregistertider

Stopp-och-gå-generator

Stop-and-Go- generatorn ( eng. Stop-and-Go , Both-Piper ) använder utgången från LFSR-1 för att styra klockfrekvensen för LFSR-2, så att LFSR-2 ändrar sitt tillstånd någon gång i tiden endast om utsignalen från LFSR-1 vid den tiden var lika med ett. Detta schema motstod inte korrelationsöppningen [3] . $t_{i}$ $t_{i-1}$

För att öka den kryptografiska styrkan föreslogs en interfolierad stop-go-generator . Den använder tre skiftregister av olika längd. Här styr LFOS-1 klockfrekvensen för det andra och tredje registret, dvs LFSR-2 ändrar sitt tillstånd när LFSR-1-utgången är lika med ett, och LFSR-3 - när LFSR-1-utgången är lika med noll. Generatorns utgång är driften av modulo två av utgångarna på RLOS-2 och RLLS-3. Denna generator har en stor period och en stor linjär komplexitet. Det finns en metod för korrelationsöppning av RLOS-1, men detta försvagar inte generatorns kryptografiska egenskaper.

Ett mer komplicerat klockningsschema används i en tvåvägs stop-and-go-generator , som använder 2 skiftregister av samma längd. Om utsignalen från LFSR-1 vid en viss tidpunkt är lika med noll, och vid en tidpunkt är den lika med ett, så klockas inte LFSR-2 vid tidpunkten . Om utsignalen från LFSR-2 vid tidpunkten är lika med noll, och vid tidpunkten är den lika med ett, och om detta register klockas vid tidpunkten , då är LFSR-1 vid samma tidpunkt inte klockad. Den linjära komplexiteten för denna krets är ungefär lika med perioden för den genererade sekvensen. $t_{i-1}$ $t_{i-2}$ $t_{i}$ $t_{i-1}$ $t_{i-2}$ $t_{i}$

Självdecimerande generator

Självdecimerade oscillatorer styr sin egen frekvens . Det finns två typer av sådana generatorer. Den första föreslogs av Rainer Rüppel . Den består av ett skiftregister och en linjär återkopplingskrets som klockar registret baserat på hur skiftregistret matar ut. Om LFSR-utgången är lika med en, klockas registret med en frekvens, och om utgången är noll, då med en annan. Den andra typen föreslogs av Bill Chambers och Dieter Kollman . Återkopplingskretsen tar inte emot själva utsignalen, utan resultatet av XOR-operationen av vissa LFSR-bitar.

Det finns också krympande och självkrympande generatorer . _ _ _ De är ganska nya, och inte alla deras egenskaper är väl studerade. Den första använder två LFSR. Om en klockpuls appliceras på generatorn och utgången från RLOS-1 är en, kommer generatorns utgång att vara utgången från RLLS-2. Annars, när en klockpuls appliceras, återställs båda bitarna och klockan börjar om. I den andra generatorn, istället för att kontrollera utsignalerna från två register för 0 eller 1, kontrolleras 2 bitar av ett register.

Den decimerade generatorn kan hackas om återkopplingspolynomen decimeras. Dessutom är dess produktionshastighet inte konstant. En självdecimerande generator behöver ungefär 2 gånger mindre minne än den första, men den fungerar 2 gånger långsammare [7] .

Multirate oscillator med inre produkt

Denna generator använder två skiftregister RSLOS-1 och RSLOS-2. Klockfrekvensen för RSLOS-2 är flera gånger högre än för RSLOS-1. Vissa bitar av dessa register multipliceras med varandra med hjälp av OCH- operationen . Resultaten av multiplikationerna adderas av XOR-operationen och utmatningssekvensen erhålls. Denna generator har en hög linjär komplexitet och har goda statistiska egenskaper. Emellertid kan dess tillstånd bestämmas från utgångssekvensen för längd , där och är längderna av LFSR-1 respektive LFSR-2, och är förhållandet mellan deras klockfrekvenser. $d$ $L_1 + L_2 + \log_2{d}$ $L_{1}$ $L_{2}$ $d$

Gollmann Cascade

Denna krets är en förbättrad version av stop-go-generatorn. Den består av en sekvens av LFSR, vars timing styrs av föregående LFSR. Om utsignalen från LFSR-1 vid tidpunkten är 1, klockas LFSR-2. Om utsignalen från LFSR-2 vid tidpunkten är 1, klockas LFSR-3, och så vidare. Utsignalen från den sista LFSR är utsignalen från generatorn. Om längden på alla LFSRs är samma och lika med , då är perioden för LFSR-systemet , och den linjära komplexiteten är [7] . $t_{i}$ $t_{i}$ $L$ $M$ $(2^L - 1)^M$ $L(S) = L(2^L - 1)^{M-1}$

Denna idé är enkel och kan användas för att generera sekvenser med stora perioder, stora linjära komplexiteter och goda statistiska egenskaper. Men tyvärr är de mottagliga för en attack som kallas lock - in , när en kryptoanalytiker , som först återställer inmatningssekvensen för det sista registret i kaskaden, bryter hela kaskaden, register för register. När antalet register ökar, närmar sig den genererade sekvensen slumpmässigt , så det är bättre att använda fler LFSR med liten längd än färre långa LFSR. $M$

Majoritetsgeneratorer

Majoritetsgenerator (eller tröskel ) består av ett stort antal skiftregister, vars utgångar går till enheten som specificeras av majoriseringsfunktionen, till exempel majoritetselement . Det speciella med denna generator är att vart och ett av skiftregistren har sin egen klockbit , , som är variablerna för majoritetsfunktionen. Till exempel, för tre register har en sådan funktion formen . Endast de register skiftas vars klockbitar är lika med värdet , det vill säga skiftningen av registren sker på majoriteten av värdena för sådana bitar: 0 eller 1. $a_{i}$ $i=1,\;2,\;\prickar,\;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 ett variabelt antal LFSR. Dess linjära komplexitet är , där är längden på det -th registret [7] . Nackdelarna med en sådan generator är möjligheten till direkt uppräkning och korrelationsöppning (varje utgångsbit ger viss information om skiftregistrets tillstånd, för att vara exakt - 0,189 bitar). $L(S) = \sum\limits_{i,j=1}^M L_iL_j$ $L_i$ $i$

Liknande generatorer används i A5- krypteringsalgoritmer (A5/1, A5/2).

Applikation

Linjära återkopplingsskiftregister kan implementeras i hårdvara, vilket gör att de kan användas för snabb pseudo-slumpmässig sekvensgenerering , såsom direkt sekvensspridningsspektrum eller brussignalgenerering [ 9] .

Använd i kryptografi

Linjära återkopplingsskiftregister har länge använts som pseudo-slumpmässiga sekvensgeneratorer för strömchiffer (särskilt inom militär kryptografi ). LFSR är dock ett linjärt schema och kan i vissa fall lätt hackas. Till exempel kan en kryptoanalytiker fånga upp en del av chiffertexten och använda den, med den ovan nämnda Berlekamp-Massey-algoritmen, för att rekonstruera en minimistorlek LFSR som efterliknar den ursprungliga LFSR. Sedan kan den avlyssnade texten matas in i det mottagna registret och dekrypteras. Metoder för att öka den kryptografiska styrkan hos strömchiffer baserade på LFSR ges ovan .

Det linjära återkopplingsskiftregistret är grunden för strömchiffer som A5/1 och A5/2 som används i GSM- standarden och E0 chiffer som används i Bluetooth . A5/2-chifferet har brutits, och A5/1- och E0-chiffrorna är allvarligt felaktiga [10] [11] .

Skiftregistret för linjär återkoppling är nära relaterat till den linjära kongruentialgeneratorn [12] .

Använd som räknare

Frekvensen för den genererade LFSR-sekvensen låter dig använda den som en klockdelare eller räknare [13] . En räknare baserad på en sådan oscillator har en förenklad återkopplingskrets, till skillnad från konventionella binära eller grå kodräknare , och kan därför arbeta med höga klockhastigheter. Du måste dock se till att en sådan räknare aldrig går in i nolltillståndet.

Testa digitala enheter

Till skillnad från en konventionell räknare går LFSR inte från ett tillstånd till ett annat i ordningen för binär räkning, vilket gör att den kan användas för att generera en testsignal när fel upptäcks i logiska kretsar [6] .

Linjära återkopplingsskiftregister används också i inbyggt självtest ( inbyggt självtest , BIST ) för signaturanalys (bitfelsdetektering) i logiska kretsar. Sådana system används på grund av det begränsade antalet mikrokretsutgångar (inte alla mellanliggande bitvärden kan appliceras på utgången). BIST-systemet består av 3 block: en testsekvensgenerator och en signaturanalysator, som bygger på LFSR, och en testkontroller. Skiftregistret i analysatorn "komprimerar" resultatet av kretsen för testsekvensen till en signatur och fortsätter att arbeta tills alla dess bitar, förutom 0, blir lika med noll, det vill säga tillståndet . Tillsammans med LFSR finns det en binär räknare som räknar antalet cykler sedan slutet av testreaktionskomprimeringen. Om registrets initiala tillstånd motsvarade referenssignaturen (signaturen för en felfri krets), så motsvarar räknaravläsningen numret på den felaktiga biten [14] [15] . $\vänster[1,\;0,\;0,\;...,\;0\höger]$

Eftersom LFSR utför förlustkomprimering är det troligt att i ett schema med fel kommer den resulterande signaturen att vara lika med referensen. Detta kan undvikas genom att använda en signaturanalysator med flera ingångar.

Förvrängning

Linjära återkopplingsskiftregister används vid kryptering för att producera en digital ström med slumpmässiga sekvensegenskaper . En pseudoslumpmässig LFSR-sekvens med maximal längd adderas modulo 2 till den överförda bitströmmen, och sekvensen genereras i samma takt som dataöverföringen. Vissa system och tekniker som använder förvrängning är:

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 även

Anteckningar

↑ B. Sklyar, 2007 .
↑ Linjära återkopplingsförskjutningsregister i Virtex-enheter . Hämtad 19 november 2014. Arkiverad från originalet 2 november 2013. (obestämd)
↑ 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 .
↑ Effektiva skiftregister, LFSR-räknare och långa pseudo-slumpmässiga sekvensgeneratorer . Hämtad 18 november 2014. Arkiverad från originalet 25 januari 2021. (obestämd)
↑ B. Harrington, 2008 .
↑ O. Dyachenko .
↑ V. Vargauzin, 1999 .

Litteratur

Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källtexter i C-språk. - Triumph, 2013. - 816 sid. - ISBN 978-5-89392-527-2 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Informationssäkerhet : lärobok - M .: MIPT , 2011. - 225 sid. — ISBN 978-5-7417-0377-9
Larin A. L. Fundamentals of digital electronics - M .: MIPT , 2008. - 314 sid. — ISBN 978-5-7417-0228-4
Sklyar B. Digital kommunikation. Teoretiska grunder och praktisk tillämpning. - Williams, 2007. - 1104 sid. - ISBN 978-5-8459-0497-3 .
Kobzarev Yu. B. Modern radar. - Ripol Classic, 2013. - 708 sid. — ISBN 978-5-4584-7357-6 .
Fomichev V. M. Diskret matematik och kryptologi : Föreläsningskurs / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - 397 sid. — ISBN 978-5-86404-185-7
Beker H. , Piper F. Cipher systems: the protection of communications (engelska) - London : Northwood Books , 1982. - 427 sid. — ISBN 978-0-7198-2611-5
Sizonenko AB Flerkanalig digital bruskälla baserad på återkommande skiftregister . - Special Equipment and Communications Magazine nr 3, 2012. Arkivexemplardaterad 29 november 2014 påWayback Machine
Barklan E. , Biham E. , Keller N. Omedelbar krypteringsanalys av krypterad GSM-kommunikation . - Journal of cryptology nr 21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Krypteringsanalys av GSM-krypterad kommunikation med endast chiffertext . - Krypto nr 3621, 2005. (otillgänglig länk)
Eastlake D. , Schiller J. , Crocker S. Slumpmässighetskrav för säkerhet . — 2005.
Harrington B. Få din boost från BIST . — 2008. (otillgänglig länk)
Dyachenko O. N. Kompakt analys över fältet GF(3).
Vargauzin V. Principer för digital-tv enligt ATSC-standarden. - Tidningen Tele-Sputnik nr 9 (47), 1999.

Länkar

LFSR referens . LFSR-teori och implementering, maximala längdsekvenser och kompletta tappsekvenstabeller för längder från 7 till 16 miljoner (3 till 24 bitar), och deltabeller för längder upp till 4 miljarder (25 till 32 bitar) (otillgänglig länk) Arkiverad 1 oktober 2018 .
Internationella telekommunikationsförbundets rekommendation O.151 . augusti 1992
Rutin för generering av pseudoslumptal Arkiverad 25 december 2008 på Wayback Machine
[3 ]
Enkel förklaring av LFSRs för ingenjörer
Feedbackvillkor _
En implementering av en kryptografiskt säker krympande pseudoslumptalsgenerator
Metoder och uppgifter för skydd av kryptografiskt information (otillgänglig länk)