Registru de schimbare liniar cu feedback

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 5 octombrie 2016; verificările necesită 44 de modificări .

Registrul de deplasare cu feedback liniar ( LFSR ) este un registru de deplasare al de biți , în care valoarea bitului de intrare (de alunecare) este egală cu o funcție booleană liniară din valorile biților rămași ai registrului înainte de deplasare. Poate fi organizat atât prin software cât și hardware. Este folosit pentru a genera secvențe de biți pseudo-aleatorie , care este folosit, în special, în criptografie [1] . Un registru de deplasare cu feedback de transport și un registru de deplasare cu feedback generalizat funcționează pe un principiu similar .

Descriere

În registrul de deplasare cu feedback liniar (RSLOS) există două părți (module):

registrul de deplasare real;
un circuit de feedback (sau subrutină) care calculează valoarea bitului inserat.

Registrul constă din celule de memorie funcționale (biți ai unuia sau mai multor cuvinte mașină), fiecare dintre ele stochează starea curentă (valoarea) unui bit. Numărul de celule se numește lungimea registrului. Biții (celulele) sunt de obicei numerotați cu numere , conținutul celei de-a -lea celulă este notat cu . Valoarea noului bit este determinată înainte de deplasarea biților în registru și numai după ce deplasarea este scrisă în celulă , iar următorul bit generat este extras din celulă. $L$ $i = 0,\;1,\;\puncte,\;L-1$ $i$ $S_{(L-1)-i}$ $S_L$ $0$ $L-1$

Funcția de feedback pentru LFSR este o funcție booleană liniară a valorilor tuturor sau a unor biți ai registrului. Funcția înmulțește biții de registru cu coeficienți , unde . Numărul de coeficienți este același cu numărul de biți de registru . Coeficienții iau valorile , iar ultimul coeficient este egal cu , deoarece LFSR este dat de polinomul caracteristic de grad . Adunarea Modulo 2 (operația „XOR”, notată în formule prin simbolul „ ”) sau inversarea sa logică „ XNOR ” sunt funcții booleene liniare și sunt cel mai des folosite în astfel de registre [2] . În acest caz, biții care sunt variabile ale funcției de feedback se numesc taps , iar registrul însuși se numește configurația Fibonacci [3] . $c_{i}$ $i = 1, \; 2,\; \puncte,\; L$ $L$ $c_{i}$ $\{ 0, \; unu \}$ $c_L$ $c_L = 1$ $L$ $\oplus$

Controlul registrului în implementările hardware se realizează prin aplicarea unui impuls de deplasare (altfel numit ceas sau impuls de ceas ) tuturor celulelor. Gestionarea registrelor în implementările software se realizează prin executarea unei bucle . La fiecare iterație a buclei, se calculează funcția de feedback și se realizează o schimbare de biți în cuvânt.

Cum funcționează

În timpul fiecărui ciclu de ceas , registrul de deplasare cu feedback liniar efectuează următoarele operații:

se citește bitul situat în celulă ; acest bit este următorul bit din secvența de ieșire; $L-1$
funcția de feedback calculează o nouă valoare pentru celulă folosind valorile curente ale celulelor; $0$
conţinutul fiecărei celule este mutat în celula următoare , unde ; $i$ $i+1$ $i = 0,\;1,\;\puncte,\;L-2$
celula este scrisă pe bitul calculat anterior de funcția de feedback. $0$

Dacă funcția de feedback realizează operația logică „ XOR ” (SAU exclusiv), valorile biților (celulelor) pot fi calculate folosind următoarele formule [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} )$

Proprietăți

Periodicitate

Perioada registrului de deplasare este lungimea minimă a secvenței rezultate înainte de a începe să se repete. Lungimea LFSR are stări inițiale care definesc valorile biților din celule. Dintre acestea , stările sunt diferite de zero, deci secvența generată are o perioadă de . Perioada secvenței generate este maximă și egală cu , dacă polinomul de feedback (sau polinomul caracteristic) peste câmp este primitiv . Pentru a face acest lucru, este necesar (dar nu suficient) să îndepliniți următoarele 2 condiții: $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)$

un număr par de robinete;
Numerele de tip tap, luate împreună și nu în perechi, sunt coprime .

Numărul tuturor polinoamelor primitive posibile este , unde este funcția Euler [5] . Registrul dat de un astfel de polinom se numește registru de deplasare maximă a perioadei (sau generator de secvențe pseudoaleatoare ), iar secvențele generate sunt numite secvențe de perioadă maximă (sau M-secvențe ) [4] [6] . $\tfrac{\phi(2^L-1)}{L}$ $\phi$

Complexitate liniară

Complexitatea liniară a unei secvențe binare infinite este numărul, care este definit după cum urmează: $S=(S_0,\;S_1,\;S_2,\;\puncte)$ $L(S)$

dacă este o secvență zero, atunci ; $S=(0,\;0,\;0,\;\puncte)$ $L(S)=0$
dacă nu există LFSR care să genereze , atunci ; $S$ $L(S) = \infty$
în caz contrar egal cu lungimea celui mai scurt LFSR care generează . $L(S)$ $S$

Complexitatea liniară a unei secvențe binare finite este un număr egal cu lungimea celei mai scurte LFSR care generează această secvență. $S_n=(S_0,\;S_1,\;\dots,\;S_n)$ $L(S_n)$

Complexitatea liniară a unui registru de deplasare cu feedback liniar indică cât de apropiată este secvența generată de aleatoriu . Un algoritm eficient pentru determinarea complexității liniare a unei secvențe binare finite este algoritmul Berlekamp-Massey .

Independența corelației

În încercarea de a obține o complexitate liniară ridicată a secvenței generate, criptografii combină neliniar ieșirile mai multor registre de deplasare. În acest caz, una sau mai multe secvențe de ieșire (sau chiar ieșiri ale LFSR-urilor individuale) pot fi conectate printr-un flux comun și deschise de un criptoanalist . Un hack bazat pe o astfel de vulnerabilitate se numește atac de corelare . Ideea principală a unui astfel de hack este de a găsi o corelație între ieșirea generatorului și ieșirile părților sale componente. Apoi, observând secvența de ieșire, se pot obține informații despre aceste ieșiri intermediare și, astfel, pot pirata generatorul. Thomas Siegenthaler a arătat că este posibil să se definească exact independența corelației și că există un compromis între independența corelației și complexitatea liniară [7] .

Implementarea software

Implementările software ale RSLOS sunt destul de lente și funcționează mai rapid dacă sunt scrise în asamblator . Una dintre soluții este utilizarea paralelă a 16 RSLOS (sau 32, în funcție de lungimea cuvântului din arhitectura computerului). Într-o astfel de schemă, este utilizată o matrice de cuvinte, a căror dimensiune este egală cu lungimea registrului de deplasare, iar fiecare bit al cuvântului se referă la propriul său LFSR. Deoarece se utilizează același număr de secvențe de tape, acest lucru poate oferi un câștig vizibil în performanța generatorului [3] .

Configurația Fibonacci

Luați în considerare un registru de deplasare pe 32 de biți. Există o secvență de evadare pentru el . Aceasta înseamnă că pentru a genera un nou bit, este necesar să se însumeze biții 31, 30, 29, 27, 25 și 0 folosind operația XOR . LFSR rezultat are o perioadă maximă . Codul pentru un astfel de registru în C este următorul: $\left(32,\;31,\;30,\;28,\;26,\;1\right)$ $2^{ 32 }-1$

int LFSR_Fibonacci ( vod ) { static nesemnat lung S = 0x00000001 ; S = (((( S >> 31 ) ^ ( S >> 30 ) ^ ( S >> 29 ) ^ ( S >> 27 ) ^ ( S >> 25 ) ^ S ) & 0x00000001 ) << 31 ) | ( S >> 1 ); returnează S & 0x00000001 ; }

Configurație Galois

Ca și în configurația Fibonacci, circuitul de feedback este un set de operații XOR ale biților de tip tap cu ieșirea generatorului, dar ordinea biților din registru este inversată: al-lea bit este intrarea și al -lea bit . este ieșirea . Rezultatul adunării este scris în celula următoare, iar noul bit de ieșire este scris în -th. Astfel, dacă bitul generat este egal cu zero, atunci toți biții din celule sunt deplasați la dreapta fără modificări, dacă bitul generat este egal cu unu, atunci biții de atingere își schimbă valoarea la opus și toți biții sunt deplasați La dreapta. Atât configurația Fibonacci, cât și configurația Galois de aceeași lungime generează aceleași secvențe, dar deplasate în timp una de alta (în acest caz, stările interne ale registrelor pot diferi) [8] . $L-1$ $0$ $L-1$

Acest generator nu are o putere criptografică mai mare , dar oferă un câștig de performanță: toate operațiunile XOR prin paralelizare pot fi efectuate într-o operație, și nu succesiv una după alta, ca în configurația Fibonacci. Această schemă va oferi, de asemenea, un câștig în implementarea hardware.

Codul pentru un registru cu deplasare pe 32 de biți în C este următorul:

int LFSR_Galois ( vod ) { // pentru polinomul 0x80000057, inversat 0xea000001 static fără semn lung S = 0x00000001 ; dacă ( S & 0x00000001 ) { S = (( S ^ 0x80000057 ) >> 1 ) | 0x80000000 ; returnează 1 ;} else { S >>= 1 ; returnează 0 ;} }

Este de remarcat faptul că o buclă cu un număr fix de apeluri de funcții LFSR_Galoisîn configurația Galois este de aproximativ 2 ori mai rapidă decât o funcție LFSR_Fibonacciîn configurația Fibonacci ( compilatorul MS VS 2010 pe Intel Core i5 ).

Un exemplu de secvență generată

Configurația Fibonacci

Fie LFSR dat de polinomul caracteristic . Aceasta înseamnă că biții de atingere vor fi al 2-lea și al 0-lea, iar unitatea din formula polinomială înseamnă că al 0-lea bit este intrarea. Funcția de feedback are forma . Să presupunem că starea inițială a registrului de deplasare a fost secvența . Alte stări ale registrului sunt prezentate în tabelul de mai jos: $x^{3}+x+1$ $S_j=S_{j-1}\oplus S_{j-3}$ $\left[0,\;0,\;1\right]$

Numărul pasului	Stat	Bit generat
0	$\left[0,\;0,\;1\right]$	unu
unu	$\left[1,\;0,\;0\right]$	0
2	$\left[1,\;1,\;0\right]$	0
3	$\left[1,\;1,\;1\right]$	unu
patru	$\left[0,\;1,\;1\right]$	unu
5	$\left[1,\;0,\;1\right]$	unu
6	$\left[0,\;1,\;0\right]$	0
7	$\left[0,\;0,\;1\right]$	unu

Deoarece starea internă la pasul al șaptelea a revenit la starea inițială, atunci, începând cu pasul următor, biții se vor repeta. Adică, secvența generată este următoarea: (ordinea biților din secvență corespunde cu ordinea în care au fost generați de LFSR). Astfel, perioada șirului este 7, adică valoarea maximă posibilă, ceea ce s-a întâmplat din cauza primitivității polinomului dat. $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$

Configurație Galois

Să luăm același polinom caracteristic, adică , . Doar primul bit este adăugat la bitul de ieșire. Starea inițială este aceeași. Alte state ale registrului: $c_3=c_1=1$ $c_2=0$

Numărul pasului	Stat	Bit generat
0	$\left[0,\;0,\;1\right]$	unu
unu	$\left[1,\;0,\;1\right]$	unu
2	$\left[1,\;1,\;1\right]$	unu
3	$\left[1,\;1,\;0\right]$	0
patru	$\left[0,\;1,\;1\right]$	unu
5	$\left[1,\;0,\;0\right]$	0
6	$\left[0,\;1,\;0\right]$	0
7	$\left[0,\;0,\;1\right]$	unu

Starea internă a registrului la al șaptelea pas a revenit la starea inițială, prin urmare, perioada sa este, de asemenea, egală cu 7. Spre deosebire de configurația Fibonacci, stările interne ale registrului s-au dovedit a fi diferite, dar succesiunea generată este aceeași , deplasat doar cu 4 cicluri : (ordinea biților din secvență corespunde ordinii generării lor de LFSR). $\left[1,\;1,\;1,\;0,\;1,\;0,\;0,\;1,\;...\right]$

Reprezentarea matricială a LFSR

secțiunea articolului în limba engleză

Generarea de polinoame primitive

Calcularea unui polinom primitiv pe un câmp este o problemă matematică destul de complicată: pentru a genera un polinom de grad primitiv, trebuie să cunoașteți factorii numărului . Este mai ușor să alegeți la întâmplare un polinom și să îl testați pentru primitivitate [3] . O altă metodă este de a folosi tabele gata făcute care listează numărul de secvențe de tape care oferă perioada maximă a generatorului. Mai jos este un tabel de polinoame primitive pe câmp pentru registrele de deplasare cu o perioadă maximă de până la 19 biți [5] . Este demn de luat în considerare faptul că un generator de orice lungime dată poate avea mai mult de un polinom primitiv în funcție de proprietățile lor . O listă completă pentru registrele cu lungimea de 4 până la 32 de biți poate fi găsită aici . ${\mathrm {GF}}(2)$ $k$ $2^{k}-1$ ${\mathrm {GF}}(2)$

biți, $n$	Polinom primitiv	Perioadă, $2^{n}-1$	Numărul de polinoame primitive
2	$x^{2}+x+1$	3	unu
3	$x^3+x^2+1$	7	2
patru	$x^4+x^3+1$	cincisprezece	2
5	$x^{5}+x^{3}+1$	31	6
6	$x^{6}+x^{5}+1$	63	6
7	$x^{ 7 }+x^{ 6 }+1$	127	optsprezece
opt	$x^{8}+x^{6}+x^{5}+x^{4}+1$	255	16
9	$x^{9}+x^{5}+1$	511	48
zece	$x^{10}+x^{7}+1$	1023	60
unsprezece	$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
paisprezece	$x^{14}+x^{13}+x^{12}+x^{2}+1$	16383	756
cincisprezece	$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
optsprezece	$x^{18}+x^{11}+1$	262143	7776
19	$x^{19}+x^{18}+x^{17}+x^{14}+1$	524287	27594
20 - 168	[unu]
2 - 786, 1024, 2048, 4096	[2]

Avantaje și dezavantaje

Beneficii

performanță ridicată a algoritmilor criptografici creați pe baza LFSR (de exemplu , stream ciphers );
utilizarea doar a celor mai simple operații pe biți de adunare și înmulțire, implementate în hardware în aproape toate dispozitivele de calcul;
proprietăți criptografice bune (LFSR-urile pot genera secvențe de perioade lungi cu proprietăți statistice bune);
datorită structurii lor, LFSR-urile sunt ușor de analizat folosind metode algebrice.

Dezavantaje

Una dintre principalele probleme ale LFSR este că implementarea software-ului lor este extrem de ineficientă: polinoamele rare cu feedback trebuie evitate, deoarece duc la o piratare mai ușoară prin atac de corelație , iar polinoamele dense sunt foarte lente de calculat. Prin urmare, o implementare software a unui astfel de generator nu este mai rapidă decât o implementare DES .
Liniaritatea secvenței la ieșirea registrului face posibilă determinarea unică a polinomului de feedback pe biți seriali folosind algoritmul Berlekamp-Massey sau algoritmul Euclid [3] [4] . $C(x)$ $2L$
Ușurința relativă a analizei prin metode algebrice nu numai că facilitează dezvoltarea, dar crește și șansele de rupere a unui generator bazat pe LFSR.

Modalități de îmbunătățire a puterii criptografice a secvențelor generate

Generatoare cu mai multe registre cu deplasare

Acest tip de generator constă din mai multe registre de deplasare cu feedback linear care generează, respectiv, biți . În continuare, biții generați sunt convertiți de o funcție booleană . Trebuie remarcat faptul că pentru generatoarele de acest tip, lungimile registrului , , sunt relativ prime între ele. $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,\;\puncte,\;M$

Perioada acestui generator este , unde este numărul total de celule. Prin urmare, utilizarea mai multor LFSR-uri mărește perioada secvenței generate în comparație cu un singur registru, ceea ce crește puterea criptografică a generatorului. De asemenea, crește complexitatea liniară sau lungimea celui mai scurt registru corespunzător unui generator dat. Un astfel de registru este găsit folosind algoritmul Berlekamp-Massey folosind secvența generată. În cel mai bun caz, lungimea sa este proporțională cu perioada secvenței generate [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$

Generatoare cu transformări neliniare

Schema bloc a unui astfel de generator nu este diferită de diagrama generatorului anterior. Principala diferență este că dispozitivul de transformare este dat de o funcție booleană neliniară . Ca o astfel de funcție, de exemplu, se ia polinomul Zhegalkin (conform teoremei Zhegalkin , orice funcție booleană poate fi reprezentată în mod unic de polinomul Zhegalkin). $f(x_1, x_2, \dots, x_M)$

Un generator neliniar poate fi implementat și pe un registru de deplasare cu feedback neliniar . Poate da variante de secvențe ale perioadei maxime , care este mai mult decât cea a LFSR [5] . $2^{2^{L-1}-L}$

Puterea criptografică a acestui generator este crescută datorită neliniarității funcției utilizate. Determinarea stării registrelor din secvența de biți generată este o problemă matematică complexă, deoarece nu se cunoaște un algoritm care să restabilească stările inițiale.

Această metodă este utilizată, de exemplu, în generatorul Geff și în generatorul generalizat Geff, totuși, astfel de generatoare pot fi piratate prin analiza de corelație [7] .

Oscilatoare cu timpi diferite ale registrului de deplasare

Generator stop-and-go

Generatorul Stop-and-Go ( ing. Stop-and-Go , Both-Piper ) folosește ieșirea lui LFSR-1 pentru a controla frecvența de ceas a LFSR-2, astfel încât LFSR-2 își schimbă starea la un moment dat. numai dacă ieșirea lui LFSR-1 la momentul respectiv era egală cu unu. Această schemă nu a rezistat deschiderii de corelație [3] . $t_{i}$ $t_{i-1}$

Pentru a crește puterea criptografică, a fost propus un generator stop-go intercalat . Utilizează trei registre de deplasare de lungimi diferite. Aici LFOS-1 controlează frecvența de ceas a registrului 2 și 3, adică LFSR-2 își schimbă starea când ieșirea LFSR-1 este egală cu unu și LFSR-3 - când ieșirea LFSR-1 este egală cu zero. Ieșirea generatorului este operarea modulo două dintre ieșirile RLOS-2 și RLLS-3. Acest generator are o perioadă mare și o complexitate liniară mare. Există o metodă de deschidere a corelației RLOS-1, dar aceasta nu slăbește foarte mult proprietățile criptografice ale generatorului.

O schemă de sincronizare mai complicată este utilizată într-un generator stop-and-go cu două sensuri , care utilizează 2 registre de deplasare de aceeași lungime. Dacă ieșirea lui LFSR-1 la un anumit moment de timp este egală cu zero și la un moment dat este egală cu unu, atunci LFSR-2 nu este tactat în acest moment . Dacă ieșirea lui LFSR-2 în momentul de timp este egală cu zero, iar în momentul de timp este egală cu unu și dacă acest registru este tactat în momentul de timp , atunci în același moment LFSR-1 este nu cronometrat. Complexitatea liniară a acestui circuit este aproximativ egală cu perioada secvenței generate. $t_{i-1}$ $t_{i-2}$ $t_{i}$ $t_{i-1}$ $t_{i-2}$ $t_{i}$

Generator autodecimant

Oscilatoarele autodecimate își controlează propria frecvență . Există două tipuri de astfel de generatoare. Primul a fost propus de Rainer Rüppel . Este alcătuit dintr-un registru de deplasare și un circuit de feedback liniar care ceasează registrul în funcție de modul în care iese registrul de deplasare. Dacă ieșirea LFSR este egală cu unu, atunci registrul este tactat cu o frecvență, iar dacă ieșirea este zero, atunci cu alta. Al doilea tip a fost propus de Bill Chambers și Dieter Kollman . Circuitul de feedback nu primește semnalul de ieșire în sine, ci rezultatul funcționării XOR a anumitor biți LFSR.

Există, de asemenea , generatoare de micșorare și auto - contracție . Sunt destul de noi și nu toate proprietățile lor sunt bine studiate. Primul folosește două LFSR. Dacă un impuls de ceas este aplicat generatorului și ieșirea lui RLOS-1 este una, atunci ieșirea generatorului va fi ieșirea lui RLLS-2. În caz contrar, atunci când se aplică un impuls de ceas, ambii biți sunt resetati și ceasul pornește de la capăt. În al doilea generator, în loc să se verifice ieșirile a două registre pentru 0 sau 1, se verifică 2 biți ai unui registru.

Generatorul decimat poate fi piratat dacă polinoamele de feedback sunt decimate. În plus, rata sa de generare nu este constantă. Un generator cu autodecimare are nevoie de aproximativ 2 ori mai puțină memorie decât primul, dar funcționează de 2 ori mai lent [7] .

Oscilator multirate cu produs interior

Acest generator folosește două registre de deplasare RSLOS-1 și RSLOS-2. Frecvența de ceas a RSLOS-2 este de câteva ori mai mare decât cea a RSLOS-1. Anumiți biți ai acestor registre sunt înmulțiți între ei folosind operația AND . Rezultatele înmulțirilor sunt adăugate prin operația XOR și se obține secvența de ieșire. Acest generator are o complexitate liniară mare și are proprietăți statistice bune. Cu toate acestea, starea sa poate fi determinată din secvența de ieșire a lungimii , unde și sunt lungimile LFSR-1 și, respectiv, LFSR-2 și este raportul frecvențelor lor de ceas. $d$ $L_1 + L_2 + \log_2{d}$ $L_{1}$ $L_{2}$ $d$

Cascada Gollmann

Acest circuit este o versiune îmbunătățită a generatorului stop-go. Este alcătuit dintr-o secvență de LFSR-uri, a căror sincronizare este controlată de LFSR-ul anterior. Dacă ieșirea lui LFSR-1 în momentul de față este 1, atunci LFSR-2 este tactat. Dacă ieșirea lui LFSR-2 în momentul de față este 1, atunci LFSR-3 este tactat și așa mai departe. Ieșirea ultimului LFSR este ieșirea generatorului. Dacă lungimea tuturor LFSR-urilor este aceeași și egală cu , atunci perioada sistemului LFSR este , iar complexitatea liniară este [7] . $t_{i}$ $t_{i}$ $L$ $M$ $(2^L - 1)^M$ $L(S) = L(2^L - 1)^{M-1}$

Această idee este simplă și poate fi folosită pentru a genera secvențe cu perioade uriașe, complexități liniare mari și proprietăți statistice bune. Dar, din păcate, sunt susceptibili la un atac numit lock - in , când un criptoanalist , restabilind mai întâi secvența de intrare a ultimului registru din cascadă, rupe întreaga cascadă, registru cu registru. Pe măsură ce numărul de registre crește, secvența generată se apropie aleatoriu , deci este mai bine să folosiți mai multe LFSR de lungime mică decât mai puține LFSR lungi. $M$

Generatori majoritari

Generatorul majoritar (sau prag ) constă dintr-un număr mare de registre de deplasare, ale căror ieșiri merg către dispozitivul specificat de funcția de majorare, de exemplu, elementul majoritar . Particularitatea acestui generator este că fiecare dintre registrele de deplasare are propriul bit de ceas , , care sunt variabilele funcției majoritare. De exemplu, pentru trei registre, o astfel de funcție are forma . Sunt deplasate numai acele registre ai căror biți de ceas sunt egali cu valoarea , adică deplasarea registrelor are loc pe majoritatea valorilor acestor biți: 0 sau 1. $a_{i}$ $i=1,\;2,\;\puncte,\;M$ $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ $b(t)$

Astfel, obținem un generator cu un număr variabil de LFSR. Complexitatea sa liniară este , unde este lungimea --lea registru [7] . Dezavantajele unui astfel de generator sunt posibilitatea de enumerare directă și deschidere a corelației (fiecare bit de ieșire oferă câteva informații despre starea registrului de deplasare, mai exact - 0,189 biți). $L(S) = \sum\limits_{i,j=1}^M L_iL_j$ $L_i$ $i$

Generatoare similare sunt utilizate în algoritmii de criptare A5 (A5/1, A5/2).

Aplicație

Registrele de deplasare cu feedback liniar pot fi implementate în hardware, permițându-le să fie utilizate pentru generarea rapidă a secvenței pseudo-aleatoare , cum ar fi spectrul de răspândire a secvenței directe sau generarea de semnal de zgomot [9] .

Utilizare în criptografie

Registrele de deplasare cu feedback liniar au fost folosite de mult timp ca generatoare de secvențe pseudo-aleatoare pentru cifrurile de flux (în special în criptografia militară ). Cu toate acestea, LFSR este o schemă liniară și, în unele cazuri, poate fi piratată cu ușurință. De exemplu, un criptoanalist poate intercepta o porțiune a textului cifrat și o poate folosi, folosind algoritmul Berlekamp-Massey menționat mai sus , pentru a reconstrui un LFSR de dimensiune minimă care imită LFSR original. Apoi, textul interceptat poate fi introdus în registrul primit și decriptat. Metodele pentru creșterea puterii criptografice a cifrurilor de flux bazate pe LFSR sunt prezentate mai sus .

Registrul de deplasare a feedback-ului liniar este baza pentru cifrurile de flux, cum ar fi A5/1 și A5/2, utilizate în standardul GSM și cifrul E0 utilizat în Bluetooth . Cifrul A5/2 a fost spart, iar cifrurile A5/1 și E0 sunt serios defecte [10] [11] .

Registrul de deplasare cu feedback liniar este strâns legat de generatorul liniar congruențial [12] .

Utilizați ca contoare

Frecvența secvenței LFSR generată vă permite să o utilizați ca divizor de ceas sau contor [13] . Un contor bazat pe un astfel de oscilator are un circuit de feedback simplificat, spre deosebire de contoarele convenționale binare sau coduri Gray și, prin urmare, poate funcționa la viteze mari de ceas. Cu toate acestea, trebuie să vă asigurați că un astfel de contor nu intră niciodată în starea zero.

Testarea dispozitivelor digitale

Spre deosebire de un contor convențional, LFSR nu trece de la o stare la alta în ordinea numărării binare, ceea ce îi permite să fie folosit pentru a genera un semnal de test atunci când sunt detectate erori în circuitele logice [6] .

De asemenea, registrele de deplasare cu feedback liniar sunt utilizate în autotestul încorporat [ ( autotest încorporat , BIST ) pentru analiza semnăturii (detecția erorii de biți) în circuitele logice. Astfel de sisteme sunt utilizate datorită numărului limitat de ieșiri de microcircuit (nu toate valorile intermediare ale biților pot fi aplicate la ieșire). Sistemul BIST este format din 3 blocuri: un generator de secvențe de testare și un analizor de semnături, care sunt construite pe baza LFSR, și un controler de testare. Registrul de deplasare din analizor „comprimă” rezultatul circuitului pentru secvența de testare într-o semnătură și continuă să funcționeze până când toți biții săi, cu excepția lui 0, devin egali cu zero, adică cu starea . Alături de LFSR, există un numărător binar care numără numărul de cicluri de la sfârșitul compresiei reacției de testare. Dacă starea inițială a registrului corespundea semnăturii de referință (semnătura unui circuit fără erori), atunci citirea contorului corespunde numărului bitului eronat [14] [15] . $\left[1,\;0,\;0,\;...,\;0\right]$

Deoarece LFSR efectuează compresie cu pierderi, este probabil ca într-o schemă cu erori semnătura rezultată să fie egală cu cea de referință. Acest lucru poate fi evitat prin utilizarea unui analizor de semnături cu intrări multiple.

Scrambling

Registrele de deplasare cu feedback liniar sunt utilizate în codificare pentru a produce un flux digital cu proprietăți ale secvenței aleatorii . O secvență LFSR pseudo-aleatorie de lungime maximă este adăugată modulo 2 la fluxul de biți transmis, iar secvența este generată la aceeași rată ca și transmisia de date. Unele sisteme și tehnologii care folosesc codificarea sunt:

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.

Vezi și

Note

↑ B. Sklyar, 2007 .
↑ Registrele de schimbare a feedback-ului linear în dispozitivele Virtex . Consultat la 19 noiembrie 2014. Arhivat din original pe 2 noiembrie 2013. (nedefinit)
↑ 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 .
↑ Registre cu deplasare eficiente, contoare LFSR și generatoare lungi de secvențe pseudo-aleatorie . Consultat la 18 noiembrie 2014. Arhivat din original la 25 ianuarie 2021. (nedefinit)
↑ B. Harrington, 2008 .
↑ O. Dyachenko .
↑ V. Vargauzin, 1999 .

Literatură

Schneier B. Criptografia aplicată. Protocoale, algoritmi, texte sursă în limbaj C. - Triumf, 2013. - 816 p. - ISBN 978-5-89392-527-2 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Securitatea informației : manual - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Larin A. L. Fundamentele electronicii digitale - M .: MIPT , 2008. - 314 p. — ISBN 978-5-7417-0228-4
Sklyar B. Comunicare digitală. Fundamente teoretice și aplicare practică. - Williams, 2007. - 1104 p. - ISBN 978-5-8459-0497-3 .
Kobzarev Yu. B. Radar modern. - Ripol Classic, 2013. - 708 p. — ISBN 978-5-4584-7357-6 .
Fomichev V. M. Matematică discretă și criptologie : Curs de cursuri / ed. N. D. Podufalov - M . : Dialog-MEPhI , 2013. - 397 p. — ISBN 978-5-86404-185-7
Beker H. , Piper F. Cipher systems: the protection of communications (engleză) - Londra : Northwood Books , 1982. - 427 p. — ISBN 978-0-7198-2611-5
Sizonenko AB Sursă digitală de zgomot multicanal bazată pe registrul de deplasare recurent . - Revista Special Equipment and Communications Nr. 3, 2012. Copie de arhivădin 29 noiembrie 2014 laWayback Machine
Barklan E. , Biham E. , Keller N. Criptanaliză instantanee doar cu text cifrat a comunicațiilor criptate GSM . - Jurnalul de criptologie Nr. 21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Criptanaliză instantanee doar cu text cifrat a comunicațiilor criptate GSM . - Crypto No. 3621, 2005. (link inaccesibil)
Eastlake D. , Schiller J. , Crocker S. Randomness requirements for security . — 2005.
Harrington B. Obțineți un impuls de la BIST . — 2008. (link inaccesibil)
Dyachenko O. N. Analiză compactă asupra câmpului GF(3).
Vargauzin V. Principiile televiziunii digitale ale standardului ATSC. - Revista Tele-Sputnik nr. 9 (47), 1999.

Link -uri

Referință LFSR . Teoria și implementarea LFSR, secvențe de lungime maximă și tabele complete de secvențe de atingere pentru lungimi de la 7 la 16 milioane (3 la 24 de biți) și tabele parțiale pentru lungimi de până la 4 miliarde (25 la 32 de biți) (link indisponibil) Arhivat la 1 octombrie 2018 .
Recomandarea Uniunii Internaționale de Telecomunicații O.151 . august 1992
Rutina de generare a numerelor pseudo-aleatoare Arhivată 25 decembrie 2008 la Wayback Machine
[3 ]
Explicație simplă a LFSR-urilor pentru ingineri
Termenii de feedback
O implementare a unui generator de numere pseudoaleatoare, sigur din punct de vedere criptografic
Metode și sarcini de protecție a informațiilor criptografice (link inaccesibil)