O introducere în elementele de bază ale cifrurilor moderne cu cheie simetrică. Registru de deplasare cu feedback liniar ca generatoare de numere pseudo-aleatoare Registrul de deplasare cu feedback liniar c

Într-un registru de deplasare cu feedback liniar se disting două părți (module): registrul de deplasare însuși și circuite (sau subprograme) care calculează valoarea bitului inserat. Registrul constă din celule funcționale (sau biți ai unui cuvânt mașină sau mai multe cuvinte), fiecare dintre ele stochează starea curentă a unui bit. Numărul de celule se numește lungimea registrului. Biții (celulele) sunt de obicei numerotați cu numere, fiecare dintre acestea fiind capabil să stocheze un bit, iar bitul calculat este inserat în celulă, iar următorul bit generat este eliminat din celulă. Calculul bitului de inserat se realizează de obicei înainte de deplasarea registrului și numai după deplasare este plasată în celulă valoarea bitului calculat.

Perioada registrului de deplasare este lungimea minimă a secvenței primite înainte de începerea repetării acesteia. Deoarece un registru de celule de biți are doar stări diferite de zero, atunci, în principiu, perioada registrului nu poate depăși acest număr. Dacă perioada registrului este egală cu acest număr, atunci un astfel de registru se numește registrul perioadei maxime.

Pentru RSLOS, funcția de feedback este o funcție booleană liniară a stărilor tuturor sau a unora dintre biții de registru. De exemplu, suma modulo doi sau inversul său logic este o funcție booleană liniară (operație XOR, notată ca în formule) și este cel mai des folosită în astfel de registre.

În acest caz, acei biți care sunt variabile ale funcției de feedback sunt de obicei numiți robinete.

Controlul registrului în implementările hardware se realizează prin aplicarea unui impuls de deplasare (denumit altfel ceas sau puls de sincronizare) la toate celulele, în cele programate - prin executarea unui ciclu de program, care include calculul funcției de feedback și deplasarea biților în cuvânt.

În fiecare pas de timp, se efectuează următoarele operații:

Registru de schimbare linear cu feedback

Astfel, operația logică XOR (SAU exclusiv) este luată ca funcție de feedback, adică:

Proprietățile polinoamelor primitive

Proprietăți

Proprietățile secvenței emise de RSLOS sunt strâns legate de proprietățile polinomului asociat. Se numesc coeficienții săi diferit de zero robinete precum și celulele de registru corespunzătoare care furnizează valorile argumentelor funcției de feedback.

Complexitate liniară

Complexitatea liniară a unei secvențe binare este una dintre cele mai importante caracteristici ale funcționării RSLOS. Să introducem următoarea notație:

Complexitatea liniară a unei secvențe binare infinite numit un număr care este definit după cum urmează:

Complexitatea liniară a unei secvențe binare finite se numește un număr care este egal cu lungimea celui mai scurt RLOS, care generează o secvență care are ca primii membri.

Proprietăți de complexitate liniară

Fie și fie șiruri binare. Atunci:

Independența corelației

Pentru a obține o complexitate liniară ridicată, criptografii încearcă să combine rezultatele multiplelor secvențe de ieșire în mod neliniar. În acest caz, pericolul este ca una sau mai multe secvențe de ieșire (adesea chiar și ieșirile RFLOS individuale) să poată fi conectate printr-un flux de cheie comun și deschise folosind algebră liniară. Hackingul bazat pe o astfel de vulnerabilitate se numește autopsie de corelație... Thomas Sigenthaler a arătat că independența corelației poate fi determinată cu precizie și că există un compromis între independența corelației și complexitatea liniară.

Ideea principală a acestui hack este de a găsi o corelație între ieșirea generatorului și ieșirea uneia dintre părțile sale constitutive. Apoi, observând secvența de ieșire, puteți obține informații despre acest pin intermediar. Folosind aceste informații și alte corelații, este posibil să colectăm date despre alte inferențe intermediare până când generatorul este piratat.

Multe generatoare de chei bazate pe registru de schimbare a feedback-ului linear au folosit cu succes atacuri de corelare sau variații, cum ar fi atacurile de corelație rapide, care implică un compromis între complexitatea și eficiența computațională.

Exemplu

Pentru RSLOS cu un polinom asociat, secvența generată are forma. Să presupunem că o secvență este scrisă în registru înainte de a începe procesul, atunci perioada fluxului de biți generat va fi 7 cu următoarea secvență:

Deoarece starea interioară la pasul al șaptelea a revenit la inițial, atunci, începând de la pasul următor, va exista o repetare. Cu alte cuvinte, perioada secvenței s-a dovedit a fi 7, ceea ce s-a întâmplat datorită caracterului primitiv al polinomului.

Algoritmi pentru generarea de polinoame primitive

Mesele gata

Calcularea primitivității unui polinom este o problemă matematică destul de dificilă. Prin urmare, există tabele gata făcute care oferă numerele secvențelor de ramificație care oferă perioada maximă a generatorului. De exemplu, pentru un registru cu deplasare pe 32 de biți, există o secvență. Aceasta înseamnă că pentru a genera un nou bit, trebuie să XOR biții 31, 30, 29, 27, 25 și 0. Codul pentru un astfel de RSLOS în C este următorul:

Int LFSR (void) (static fără semn lung S = 1; S = ((((S >> 31) ^ (S >> 30) ^ (S >> 29) ^ (S >> 27) ^ (S >> 25) ^ S) și 1)<< 31 ) | (S>> 1); întoarcere S & 1; )

Implementările software ale generatoarelor RSLOS sunt destul de lente și funcționează mai rapid dacă sunt scrise în asamblator și nu în C. Una dintre soluții este să folosești 16 RSLOS în paralel (sau 32, în funcție de lungimea cuvântului din arhitectura unui anumit computer). Într-o astfel de schemă, este utilizată o matrice de cuvinte, a căror dimensiune este egală cu lungimea RSLOS, iar fiecare bit al cuvântului din matrice se referă la propriul RSLOS. Cu condiția ca aceleași numere de secvență ale degetelor să fie utilizate, pot exista câștiguri semnificative de performanță. [nevoie de un exemplu de cod] (Vezi: bitslice).

Configurația Galois

Configurația Galois a unui registru de deplasare cu feedback liniar

Bucla de feedback poate fi, de asemenea, modificată. În acest caz, generatorul nu va avea o putere criptografică mai mare, dar va fi mai ușor de implementat în software. În loc să folosiți biții Finger Sequence pentru a genera un nou bit din stânga, fiecare bit al F-Sequence este XOR și înlocuit cu ieșirea generatorului, apoi rezultatul generatorului devine noul bit din stânga. În limbajul C, arată astfel:

Int LFSR (void) (static fără semn lung Q = 1; Q = (Q >> 1) ^ (Q & 1? 0x80000057: 0); return Q & 1;)

Rezultatul este că toate XOR-urile sunt realizate într-o singură operațiune.

• se poate dovedi că configurația Fibonacci dată în prima și configurația Galois dată aici dau aceleași secvențe (lungime 2 32 −1), dar defazate una față de cealaltă
• o buclă a unui număr fix de apeluri LFSR în configurația Galois este de aproximativ două ori mai rapidă decât în ​​configurația Fibonacci (compilatorul MS VS 2010 pe Intel Core i5)
• rețineți că în configurația Galois, ordinea biților din cuvântul de feedback este inversată în comparație cu configurația Fibonacci

Exemple de generatoare

Generatoare stop-and-go

Generator alternativ stop-and-go

Acest oscilator folosește ieșirea unui RSLOS pentru a controla frecvența de ceas a celuilalt RSLOS. Ieșirea ceasului RSLOS-2 este controlată de ieșirea RSLOS-1, astfel încât RSLOS-2 își poate schimba starea la momentul t numai dacă ieșirea RSDOS-1 la momentul t-1 a fost egală cu unu. Dar această schemă nu a rezistat confruntării corelației.

Prin urmare, a fost propus un generator îmbunătățit pe baza aceleiași idei. Se numește generator alternativ stop-and-go. Utilizează trei RFLO de lungimi diferite. RSLOS-2 este tactat când ieșirea RSLOS-1 este egală cu unu, iar RSLOS-3 este tactat când ieșirea RSLOS-1 este zero. Ieșirea generatorului este suma modulo 2 a RSLOS-2 și RSLOS-3. Acest generator are o perioadă lungă și o complexitate liniară mare. Autorii săi au arătat, de asemenea, o metodă de deschidere a corelației RSLOS-1, dar aceasta nu slăbește foarte mult generatorul.

cascada lui Gollmann

cascada lui Gollmann

Etapa Gollmann este o versiune consolidată a unui generator stop-and-go. Este alcătuită dintr-o secvență de RSLOS, a cărei tastatură este controlată de RSLOS anterior. Dacă ieșirea RSLOS-1 la momentul t este 1, atunci RSLOS-2 este tactat. Dacă ieșirea RSLOS-2 la momentul t este 1, atunci RSLOS-3 este tactat și așa mai departe. Ieșirea ultimului RSLOS este ieșirea generatorului. Dacă lungimea tuturor RFLOS este aceeași și este egală cu n, atunci complexitatea liniară a unui sistem de k LLS este egală cu.

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. Din păcate, sunt sensibili la un atac numit blocare. Pentru o durabilitate mai mare, se recomandă utilizarea k cel puțin 15. În plus, este mai bine să folosiți mai multe RFLO scurte decât mai puține RFLO lungi.

Generator de prag

Generator de prag

Acest generator încearcă să ocolească problemele de securitate ale generatoarelor anterioare utilizând un număr variabil de registre de deplasare. În teorie, atunci când se utilizează un număr mai mare de registre de deplasare, complexitatea cifrului crește, ceea ce s-a făcut în acest generator.

Acest generator este format dintr-un număr mare de registre de deplasare, ale căror ieșiri sunt alimentate la funcția de majorare. Dacă numărul de unități la ieșirile registrelor este mai mare de jumătate, atunci generatorul scoate unul. Dacă numărul de zerouri la ieșiri este mai mare de jumătate, atunci generatorul emite zero. Pentru ca compararea numărului de zerouri și unu să fie posibilă, numărul de registre de deplasare trebuie să fie impar. Lungimile tuturor registrelor trebuie să fie relativ simple, iar polinoamele de feedback trebuie să fie primitive pentru ca perioada secvenței generate să fie maximă.

Pentru cazul a trei registre de deplasare, generatorul poate fi reprezentat ca:

Acest generator este similar cu generatorul lui Geff, cu excepția faptului că generatorul de prag are o complexitate mai liniară. Complexitatea sa liniară este:

unde,, sunt lungimile primului, al doilea și al treilea registre de deplasare.

Dezavantajul său este că fiecare bit de ieșire oferă unele informații despre starea registrului de deplasare. Mai precis 0,189 biți. Prin urmare, este posibil ca acest generator să nu reziste unui atac de corelație.

Alte specii

Auto-subțierea

Generatoarele autodecimante sunt cele care își controlează propria frecvență. Au fost propuse două tipuri de astfel de generatoare. Primul constă dintr-un registru de deplasare cu feedback liniar și un circuit care ceasează acest registru, în funcție de valorile de ieșire ale registrului de deplasare. Dacă ieșirea RSLOS este egală cu unu, atunci registrul este tactat de de ori. Dacă ieșirea este zero, atunci registrul este tactat de k ori. Al doilea are aproape același design, dar ușor modificat: în circuitul de ceas, intrarea, ca verificare pentru 0 sau 1, nu primește semnalul de ieșire în sine, ci XOR al anumitor biți ai registrului de deplasare cu feedback liniar. Din păcate, acest tip de generator nu este sigur.

Generator cu mai multe viteze cu produs intern

Acest generator folosește două registre de deplasare cu feedback liniar cu frecvențe de ceas diferite: RSLOS-1 și RSLOS-2. Frecvența de ceas a RSLOS-2 este de de ori mai mare decât cea a RSLOS-1. Biții individuali ai acestor registre sunt combinați AND împreună. Apoi XOR este efectuat pe ieșirile operației AND. Secvența de ieșire este eliminată din acest bloc XOR. Din nou, acest generator nu este impecabil (nu a rezistat la deschiderea consistenței liniare. Dacă este lungimea RSLOS-1, este lungimea RSLOS-2 și d este raportul de frecvență a ceasului, atunci starea internă a generatorul poate fi obținut din secvența de ieșire a lungimii), dar are o complexitate liniară mare și o performanță statistică excelentă.

Secvențele de registru de deplasare sunt utilizate atât în ​​criptografie, cât și în teoria codificării. Teoria lor este bine dezvoltată, cifrurile cu flux de registru de schimbare au fost calul de bătaie al criptografiei militare cu mult înaintea electronicii.

Un registru de deplasare cu feedback este format din două părți: un registru de deplasare și o funcție de feedback (Figura 1.2.1). Un registru de deplasare este o secvență de biți. (Numărul de biți este determinat de lungimea registrului de deplasare. Dacă lungimea este de n biți, atunci registrul se numește registru de deplasare de n biți.) Ori de câte ori un bit trebuie preluat, toți biții registrului de deplasare sunt mutat 1 poziție la dreapta. Noul bit din stânga este o funcție a tuturor celorlalți biți din registru. Ieșirea registrului de deplasare este de un bit, de obicei cel mai puțin semnificativ. Perioada registrului de deplasare este lungimea secvenței primite înainte de începerea repetării acesteia.

Orez. 1.2.1.

Criptografilor le-au plăcut cifrurile fluxului de registru de schimbare: au fost implementate cu ușurință folosind hardware digital. Voi atinge doar puțin teoria matematică. În 1965, Ernst Selmer, criptograful șef al guvernului norvegian, a dezvoltat teoria secvențelor registrului de deplasare. Solomon Golomb, un matematician al NSA, a scris o carte subliniind unele dintre rezultatele sale și cele ale lui Selmer.

Cea mai simplă formă a unui registru cu deplasare cu feedback este un registru cu deplasare cu feedback liniar sau LFSR (Figura 1.2.2). Feedback-ul este pur și simplu un XOR al unora dintre biții de registru, o listă a acestor biți numită secvență tap. Acest registru este uneori numit configurația Fibbonacci. Datorită simplității secvenței de feedback, o teorie matematică destul de avansată poate fi utilizată pentru a analiza LFSR. Criptografilor le place să analizeze secvențele, convingându-se că secvențele sunt suficient de aleatorii pentru a fi sigure. LFSR-urile sunt cele mai utilizate registre de deplasare în criptografie.

Orez. 1.2.2.

În fig. 1.2.3 arată un LFSR pe 4 biți cu o atingere de la primul și al patrulea biți. Dacă este inițializat cu valoarea 1111, atunci înainte de repetare registrul va prelua următoarele stări interne:

Orez. 1.2.3. 4

Secvența de ieșire va fi un șir de biți mai puțin semnificativi:

1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....

Un LFSR de n biți poate fi într-una dintre 2n-1 stări interne. Aceasta înseamnă că, în teorie, un astfel de registru poate genera o secvență pseudo-aleatorie cu o perioadă de 2n-1 biți. (Numărul de stări interne și perioada sunt 2n-1, deoarece umplerea LFSR cu zerouri va face ca registrul de deplasare să scoată o secvență infinită de zerouri, ceea ce este absolut inutil.) Numai cu anumite secvențe de atingere, LFSR va trece prin cicluri. toate 2n-1 stări interne, astfel de LFSR-uri sunt LFSR-uri de perioadă maximă. Rezultatul rezultat se numește secvență M.

Pentru ca un anumit LFSR să aibă o perioadă maximă, polinomul format din secvența degetelor și constanta 1 trebuie să fie primitivă modulo 2. Gradul polinomului este lungimea registrului de deplasare. Un polinom primitiv de grad n este un polinom ireductibil care este un divizor, dar nu un divizor al lui xd + 1 pentru toți d care sunt divizori ai lui 2n-1.

În general, nu există o modalitate ușoară de a genera polinoame primitive de un anumit grad modulo 2. Cel mai simplu mod este să alegeți un polinom la întâmplare și să verificați dacă este primitiv. Nu este ușor - și un pic ca să verifici dacă un număr selectat aleatoriu este simplu - dar multe pachete de software de matematică pot face acest lucru.

Unele, dar cu siguranță nu toate, polinoame de diferite grade, primitive modulo 2. De exemplu, notația (32, 7, 5, 3, 2, 1, 0) înseamnă că următorul polinom este primitiv modulo 2:

x32 + x7 + x5 + x3 + x2 + x + 1

Acest lucru poate fi generalizat cu ușurință la LFSR de perioadă maximă. Primul număr este lungimea LFSR. Ultimul număr este întotdeauna 0 și poate fi omis. Toate numerele, cu excepția 0, specifică secvența degetelor, numărate de la marginea stângă a registrului de deplasare. Adică, membrii unui polinom cu un grad inferior corespund unor poziții mai apropiate de marginea dreaptă a registrului.

Continuând cu exemplul, scrierea (32, 7, 5, 3, 2, 1, 0) înseamnă că pentru registrul de deplasare de 32 de biți luat, un nou bit, un nou bit este generat prin XOR a treizeci și secundă, a șaptea, al cincilea, al treilea, al doilea și primul biți LFSR rezultat va avea lungimea maximă, parcurgând 232-1 valori pentru a se repeta.

Pentru a construi coduri de flux, secvențele pe registrele de deplasare sunt foarte des folosite. Registrul de deplasare cu feedback este format din două părți: un registru de deplasare și o funcție de feedback, așa cum se arată în Fig. 87. Registrul de deplasare în sine este o secvență de biți, al căror număr determină lungimea registrului. Deci, dacă n biți sunt implicați într-un registru, se spune că este un registru cu deplasare de n biți. De fiecare dată când un bit este preluat, toți biții din registrul de deplasare sunt deplasați cu o poziție la dreapta, de obicei către biții cei mai puțin semnificativi. Perioada registrului de deplasare este lungimea secvenței primite înainte de începerea repetării acesteia.

Orez. 87.

Orice funcție matematică care efectuează o acțiune asupra biților poate acționa ca un feedback. Cel mai simplu tip de registru cu deplasare cu feedback este un registru cu deplasare cu feedback liniar (LFLR). În RSLOS, feedback-ul este pur și simplu o operație de adăugare modulo 2 (XOR) pe unii biți de registru; lista acestor biți se numește o secvență de robinete, sau puncte de îndepărtare, așa cum se arată în fig. 88. Uneori, acest tipar se numește configurația Fibonacci. Datorită simplității secvenței de feedback, o teorie matematică destul de dezvoltată poate fi utilizată pentru a analiza RFLR. În orice caz, calitatea lățimii de bandă generate este evaluată printr-un set special de teste.

Orez. 88.

RSLOS sunt scrise sub formă de polinoame. În acest caz, pasul primului element al polinomului indică numărul de biți din registrul de deplasare, iar exponenții de putere ai membrilor rămași ai polinomului arată care puncte de preluare vor fi utilizate. Deci, de exemplu, înregistrarea x 4 + x + 1 înseamnă că va fi folosit un registru de patru elemente, pentru care biții bi și b 0 vor participa la formarea feedback-ului (Fig. 89).

Orez. 89,4

Luați în considerare funcționarea registrului prezentat în Fig. 89. O inițializam, de exemplu, cu valoarea 0101 (inițializarea inițială poate fi efectuată cu orice succesiune de biți, cu excepția unei secvențe de toate zerourile, deoarece în acest caz feedback-ul va forma întotdeauna o valoare de zero și registrul va nu generează lățimea de bandă de memorie așteptată). Deci, registrul este deplasat la dreapta cu o poziție. Bitul cel mai puțin semnificativ, egal cu 1, este evacuat din registru și formează primul bit al PRS. Acei biți care se aflau în pozițiile b și b 0, înainte de schimbare, sunt adăugați modulo 2 și formează un nou

cel mai semnificativ bit al registrului. Un exemplu ilustrativ de funcționare a RLOS considerat este prezentat în Fig. 90.

Orez. 90.

După cum se vede din fig. 90, completarea registrului va trece prin ponderea a 15 din 16 stări posibile (mai devreme am stabilit că a șaisprezecea stare, când RSLOS este 0000, nu poate fi luată în considerare). După aceea, umplerea registrului va fi din nou egală cu valoarea inițială a 0101, iar generarea secvenței de biți va începe să se repete. Secvența de ieșire a registrului va fi un șir de biți mai puțin semnificativi (până la linia orizontală din Fig. 90): 101011110001001. Mărimea secvenței de biți înainte de a fi repetă se numește perioadă. Pentru a asigura perioada maximă a unui anumit RSLOS (adică, pentru ca registrul să treacă prin ponderea unor posibile stări interne), polinomul care determină funcționarea registrului trebuie să fie primitiv modulo 2. Ca și în cazul numerelor prime mari. , nu există nicio modalitate de a genera astfel de polinoame. Puteți lua doar un polinom și verificați dacă este ireductibil modulo 2 sau nu. În cazul general, un polinom primitiv de grad n este un polinom ireductibil care este un divizor al lui x 2 "+1, dar nu este un divizor al lui xd +1 pentru toți d care sunt divizori ai lui 2" -1. În lucrare din B. Schneier, este dat un tabel al unor polinoame, care sunt ireductibile modulo 2.

Rezumând cunoștințele obținute ca urmare a luării în considerare a unui exemplu de funcționare a RSLOS (Fig. 90), putem spune că RSLOS pe n biți poate fi într-una din stările interne de 2 "-1. În teorie, un astfel de registru poate genera o secvență pseudo-aleatorie cu o perioadă de 2 n -1 biți. Astfel de registre se numesc registre RSLOS cu perioadă maximă. Rezultatul rezultat se numește secvență t.

Cel mai simplu tip de funcție de feedback este o funcție liniară, de exemplu, suma modulo 2 a conținutului anumitor biți. Un astfel de registru este numit Linear Feedback Shift Register (LFSR). În general, funcția de feedback liniar este dată de formula. Aici c k= 1 dacă k a-a cifră este utilizată în funcția de feedback și c k= 0 altfel. Simbolul Å denotă adiție modulo 2 (SAU exclusiv).

Ca exemplu, luați în considerare un LFSR cu o funcție de loopback (vezi figura).

Dacă starea inițială a registrului este 1111, atunci în ciclurile ulterioare de ceas va presupune următoarele serii de stări: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 001, 001, 001, 001 1100, 1110, 1111, ...

Secvența de ieșire este formată din bitul cel mai puțin semnificativ (cel mai din dreapta) al registrului. Va arăta astfel: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Se poate observa că secvența de biți generată este în întregime determinată de starea inițială a registrului și de funcția de feedback. Deoarece numărul tuturor stărilor posibile ale registrului este finit (este egal cu 2 L), apoi, mai devreme sau mai târziu, secvența de taste va începe să se repete. Lungimea maximă a unei părți care nu se repetă a unei secvențe de taste se numește perioadă. T... Perioada depinde de funcția de feedback. Perioada maximă posibilă este T max = 2 L-1 (registrul acceptă toate stările posibile, cu excepția 0000 ... 0). Se apelează secvența de ieșire a LFSR cu perioada maximă secvența M.

Pentru a afla condițiile în care LFSR va avea perioada maximă, funcțiile de feedback se potrivesc cu polinomul caracteristic. Deci, registrul dat mai sus ca exemplu corespunde unui polinom. Analiza teoretică arată că LFSR va avea o perioadă maximă dacă și numai dacă polinomul P(X) este o primitiv... Mai jos sunt câteva polinoame primitive recomandate pentru utilizare practică. Tabelul arată gradele variabilei Xîn notaţia polinomului. De exemplu, înregistrarea (31, 3) corespunde unui polinom.

LFSR-urile au fost proiectate inițial pentru a fi implementate în hardware ca un set de circuite digitale. Implementările software LFSR depășesc de obicei implementările hardware în ceea ce privește viteza. Pentru a crește viteza, este avantajos să stocați starea registrului ca număr întreg L-număr de biți, ai cărui biți individuali corespund cifrelor binare ale registrului. Apoi, operațiuni pe biți (deplasare, mascare etc.) sunt folosite pentru a accesa biți individuali.

Registrul de schimbare a feedback-ului este format din două părți: registrul de deplasare și funcții de feedback.

Figura 19. Registrul de deplasare a feedback-ului.

În general, un registru de deplasare este o succesiune a unor elemente ale unui inel sau câmp. Cel mai des folosit pic registre de deplasare. Lungimea unui astfel de registru este exprimată în numărul de biți. De fiecare dată când un bit este preluat, toți biții din registru sunt deplasați la dreapta cu o poziție. Noul bit cel mai semnificativ este calculat în funcție de toți ceilalți biți de registru. Ieșirea este de obicei bitul cel mai puțin semnificativ. Perioada registrului de deplasare este lungimea secvenței de ieșire înainte de începerea repetării acesteia.

Cel mai simplu tip de registre de deplasare este un registru de deplasare cu feedback liniar (RSLOS sau LRS). Feedback-ul este o operație XOR simplă pe unii biți de registru. Lista acestor biți este definită polinom caracteristicși a sunat succesiune de coturi... Aceasta se numește uneori Configurația Fibonacci.

Fig. 20. Configurația RLOS Fibonacci.

În implementarea software a RSLOS, se folosește o schemă modificată: pentru a genera un nou bit semnificativ, în loc să se utilizeze biții secvenței tap, se efectuează o operație XOR pe fiecare bit al acestuia cu ieșirea generatorului, înlocuind vechiul bit al secvența de atingere. Această modificare este uneori numită Configurația Galois.

Fig. 21. Configurația RSLOS Galois.

n-bit RSLOS poate fi în unul din 2 n- 1 stări interne. Aceasta înseamnă că, în teorie, un astfel de registru poate genera o secvență pseudo-aleatorie cu o perioadă de 2 n- 1 biți (completarea cu zerouri este complet inutilă). Treci pe toate 2 n- 1 stări interne sunt posibile numai cu anumite secvențe de atingeri. Astfel de registre se numesc RSLOS cu o perioadă maximă. Pentru a asigura perioada maximă a RSLOC-ului, este necesar ca polinomul său caracteristic să fie primitiv modulo 2. Gradul polinomului este lungimea registrului de deplasare. Polinom primitiv de grad n- Este așa ireductibil polinom care este un divizor, dar nu un divizor x d+ 1 pentru toți d care sunt divizori ai lui 2 n- 1. (Când discutăm despre polinoame, termenul număr prim se înlocuiește cu termenul polinom ireductibil). Polinomul caracteristic dat în figurile RSLOS:

X 32 + X 7 + X 5 + X 3 + X 2 + X + 1

este primitiv modulo 2. Perioada unui astfel de registru va fi maximă, parcurgând toate cele 2 32 - 1 valori până când se repetă. Cele mai frecvent utilizate sunt polinoamele subțiate, adică. care au doar niște coeficienți. cele mai populare sunt trinoamele.

Un parametru important al generatorului bazat pe RSLOS este complexitate liniară... Este definită ca lungime n cel mai scurt RLOS care poate simula ieșirea generatorului. Complexitatea liniară este importantă deoarece cu un simplu Algoritmul Berlenkamp-Massey puteți recrea un astfel de RSLOS bifând doar 2 n biți gamma. Odată cu definiția RSLOS dorit, cifrul fluxului este de fapt rupt.

Pe lângă RSLOS, sunt folosite și registrele de deplasare cu feedback neliniar, feedback de transport etc.

Un număr de generatoare sunt dezvoltate pe baza unei abordări teoretice a numărului (generatoare Bloom-Micali, RSA, BBS, compresive, generatoare de aditivi etc.).

Software-ul pentru sinteza algoritmilor criptografici de flux a fost dezvoltat mai detaliat și în comparație cu criptoalgoritmii bloc. Cu toate acestea, pentru a crea coduri de flux, criptoalgoritmii bloc sunt adesea folosiți în modurile OFB sau CFB.