Registrul de schimbare a feedback-ului ( FSR ) constă din două părți: Registrul de deplasareȘi funcții de feedback .
Un registru de deplasare (Eroare: sursa de referință nu a fost găsită) este o secvență de biți. Când un bit trebuie recuperat, toți biții din registrul de deplasare sunt deplasați la dreapta cu 1 poziție. Noul bit din stânga este valoarea funcției de feedback din biții rămași ai registrului. Perioadă Registrul de deplasare este lungimea secvenței rezultate înainte de a începe să se repete.
Cel mai simplu tip de registru de schimbare a feedback-ului este registru cu deplasare liniară cu feedback (LFSR
–
Stânga
Părere
Schimb
Inregistreaza-te)
(Eroare: sursa de referință nu a fost găsită). Feedback-ul este pur și simplu XOR al unor p biți 
registru, se apelează lista acestor biți secvența de atingere.
n-bit LFSR poate fi într-unul dintre 2 n -1 stări interne. Aceasta înseamnă că, teoretic, un astfel de registru poate genera o secvență pseudo-aleatorie cu punct 2 n -1 biți Numărul de stări interne și perioada sunt egale deoarece umplerea registrului cu zerouri va face ca acesta să producă o secvență nesfârșită de zerouri, ceea ce este absolut inutil. Numai cu anumite secvențe de atingere, LFSR va trece prin toate 2 n -1 stări interne. Aceste LFSR sunt numite LFSRcu perioada maxima.
Pentru ca un anumit LFSR să aibă o perioadă maximă, se formează un polinom din secvența tap și constanta 1 trebuie să fie modulo primitiv 2 .
Calcularea primitivității unui polinom este o problemă matematică destul de complexă. Prin urmare, există tabele gata făcute care arată numărul de secvențe de tape care oferă perioada maximă a generatorului. De exemplu, pentru un registru cu deplasare pe 32 de biți puteți găsi următoarea intrare: (32,7,5,3,2,1,0) . Aceasta înseamnă că pentru a genera un nou bit, trebuie să însumați cei treizeci și doi, al șaptelea, al cincilea, al treilea, al doilea și primii biți folosind funcția XOR.
Codul pentru un astfel de LFSR în C++ ar fi astfel:
// Orice valoare, alta decât zero
ShiftRegister = ((((ShiftRegister >> 31)
^ (ShiftRegister >> 6)
^ (ShiftRegister >> 4)
^ (ShiftRegister >> 2)
^ (ShiftRegister >> 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (ShiftRegister >> 1);
returnează ShiftRegister & 0x00000001;
Implementările software ale LFSR sunt destul de lente și funcționează mai rapid dacă sunt scrise în limbaj de asamblare, mai degrabă decât în C. O soluție este utilizarea a 16 LFSR-uri în paralel (sau 32 în funcție de lungimea cuvântului în arhitectura computerului specific). Această schemă folosește o matrice de cuvinte a căror dimensiune este egală cu lungimea LFSR și fiecare unitate a unui cuvânt din matrice se referă la propriul său LFSR. Cu condiția ca aceleași numere de secvență de atingere să fie utilizate, acest lucru poate oferi un câștig de performanță vizibil.
CU 
Circuitul 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ă folosească bitul cel mai din stânga al secvenței de atingere pentru a genera noul bit din partea din stânga, acesta face XOR fiecare bit al secvenței de atingere cu ieșirea generatorului și îl înlocuiește cu rezultatul acestei acțiuni, apoi rezultatul generatorului devine noul bitul din stânga (Eroare: sursa de referință nu a fost găsită).
Această modificare se numește Configurația Galois. În C arată așa:
ShiftRegister lung static nesemnat = 1;
void seed_LFSR (sămânță lungă nesemnată)
ShiftRegister = sămânță;
int Galua_LFSR (void)
dacă (ShiftRegister & 0x00000001) (
ShiftRegister = (ShiftRegister ^ masca >> 1) | 0x8000000;
ShiftRegister >>= 1;
Avantajul este că toate XOR sunt efectuate într-o singură operație. Acest circuit poate fi, de asemenea, paralelizat.
LFSR-urile în sine sunt generatoare de secvențe pseudo-aleatoare bune, dar au unele proprietăți nealeatoare nedorite. Biții consecutivi sunt liniari, ceea ce îi face inutili pentru criptare. Pentru lungimi LFSR n starea internă reprezintă anterioară n biți de ieșire ale generatorului. Chiar dacă modelul de feedback este păstrat secret, acesta poate fi determinat de 2 n biți de ieșire ai generatorului folosind algoritmi speciali. În plus, numerele mari aleatorii generate folosind biți consecutivi ai acestei secvențe sunt foarte corelate și pentru unele tipuri de aplicații nu sunt aleatorii. În ciuda acestui fapt, LFSR-urile sunt adesea folosite pentru a crea algoritmi de criptare. În acest scop, sunt utilizate mai multe LFSR-uri, de obicei cu lungimi și numere de secvență diferite. Cheia este starea inițială a registrelor. De fiecare dată când este nevoie de un nou bit, toate registrele sunt deplasate. Această operație se numește pontaj. Bitul de ieșire este o funcție, de preferință neliniară, a unor biți LFSR. Această funcție este numită combinând, și generatorul ca întreg - generator combinat. Multe dintre aceste generatoare sunt încă în siguranță.
decriptare - p i = D (k i, c i), așa cum se arată în Fig. 7.21.
Orez. 7.21.
Cifrurile flux sunt mai rapide decât cifrurile bloc. Implementarea hardware a unui cifr de flux este, de asemenea, mai simplă. Când trebuie să criptăm fluxuri binare și să le transmitem cu o viteză constantă, cea mai bună alegere este să folosim un cifr de flux. Cifrurile de flux au o protecție mai mare împotriva coruperii biților în timpul transmisiei.
Într-un cifr de flux modern, fiecare r -bit cuvântul în fluxul de text simplu este criptat folosind r -bit cuvânt în fluxul de chei pentru a crea cel corespunzător r -bit cuvânt în fluxul de text cifrat.
Orez. 7.22.
Un bloc unic este cifrul perfect. El este perfect. Nu există nicio metodă care să permită unui adversar să recunoască cheia sau statisticile textului cifrat și textului simplu. Nu există nicio relație între original și text cifrat. Cu alte cuvinte, textul cifrat este un adevărat flux aleatoriu de biți, chiar dacă sunt obținute unele mostre din textul original. Eve nu poate rupe cifrul decât dacă încearcă toate fluxurile de chei aleatorii posibile, care ar fi 2n dacă dimensiunea textului simplu ar fi de n-biți. Cu toate acestea, există o problemă cu aceasta. Pentru ca transmițătorul și receptorul să partajeze un bloc de taste unic, trebuie să stabilească o conexiune de fiecare dată când doresc să facă schimb de informații. Trebuie să fie de acord cumva asupra unei chei aleatorii. Deci, acest cifru perfect și ideal este foarte greu de implementat.
Exemplul 7.17
Care este forma textului cifrat atunci când se folosește cifrul cu pad unic în fiecare dintre următoarele cazuri?
A. Textul sursă este format din n zerouri.
b. Textul sursă este format din n unități.
V. Textul sursă este alternând zerouri și unu.
d. Textul sursă este un șir aleatoriu de biți.
Soluţie
A. Deoarece 
, atunci fluxul de text cifrat se va potrivi cu fluxul cheie. Dacă cheia este aleatorie, textul cifrat este, de asemenea, aleatoriu. Părți din textul original nu sunt stocate în textul cifrat.
b. Deoarece 
, unde este complementul fluxului de text cifrat este complementul fluxului cheie. Dacă fluxul de chei este aleatoriu, atunci și textul cifrat este aleatoriu; porțiuni din textul original nu sunt stocate în textul cifrat.
c. În acest caz, fiecare bit din fluxul de text cifrat este fie același cu cel din fluxul cheie, fie complementul său. Prin urmare, rezultatul este, de asemenea, aleatoriu dacă fluxul cheie este aleatoriu.
d. În acest caz, textul cifrat este în mod clar aleatoriu, deoarece efectuarea unei operații XOR pe doi biți aleatori duce la un flux aleatoriu de biți.
Registrul de schimbare a feedback-ului
O îmbunătățire a pad-ului unic este (FSR - Feedback Shift Register). FSR poate fi implementat fie în software, fie în hardware, dar pentru simplitate vom lua în considerare implementarea hardware. Registrul de schimbare a feedback-ului cuprinde registru de schimbare și funcții de feedback, așa cum se arată în fig. 7.23.
Orez. 7.23.
Un registru de deplasare este o secvență de m celule de la b 0 la b m-1, în care fiecare celulă este proiectată pentru a stoca un singur bit. Celulele sunt tratate ca un cuvânt de n biți, numit la început „valoarea semințelor” sau sursă. Ori de câte ori un bit trebuie să fie scos (de exemplu, dintr-un semnal la un anumit moment), fiecare bit este deplasat cu o celulă la dreapta. Aceasta înseamnă că valoarea fiecărei celule este atribuită celulei adiacente din dreapta și ia valoarea celulei din stânga. Celula din dreapta b 0 este considerată ieșire și dă valoarea de ieșire (k i ). Celula din stânga, b m-1, își primește valoarea în funcție de valoarea informațiilor funcției de feedback. Notăm ieșirea funcției cu informații de feedback b m . Funcția de informații de feedback determină ce valori trebuie să calculeze celulele b m . Registrul de deplasare a informațiilor de feedback poate fi liniar sau neliniar.
Registrul linear de schimbare a feedback-ului (LFSR). Să presupunem că b m este o funcție liniară b 0, b 1,…..., b m-1, pentru care
Un registru de deplasare cu feedback liniar operează pe cifre binare, astfel încât înmulțirea și adunarea sunt în câmpul GF(2), deci valoarea lui C i este fie 1, fie 0, dar C 0 trebuie să fie 1 pentru a obține informații de feedback la ieșire. Operația de adăugare este o operațiune EXCLUSIVĂ SAU. Cu alte cuvinte,
Exemplul 7.18
Să construim un registru de deplasare cu feedback liniar cu 5 celule, în care .
Soluţie
Dacă C i = 0, b i nu joacă un rol în calculul lui b m, atunci aceasta înseamnă că b i nu este asociat cu funcția de informații de feedback. Dacă c i = 1, b i este inclus în calculul lui b m. În acest exemplu, c 1 și c 3 sunt zerouri, ceea ce înseamnă că avem doar trei conexiuni. Figura 7.24 prezintă circuitul unui registru de deplasare cu feedback liniar.
Orez. 7.24.
Exemplul 7.19
Să construim un registru de deplasare cu feedback liniar cu 4 celule, în care 
. Afișați valoarea registrului după 20 operațiuni (ture), dacă valoarea inițială este (0001) 2 .
Soluţie
Figura 7.25 prezintă proiectarea și utilizarea unui registru de deplasare liniar în buclă închisă pentru criptare.
Orez. 7.25.
Tabelul 7.6. arată valoarea fluxului cheie. Pentru fiecare tranziție, se calculează prima valoare a lui b4 și apoi fiecare bit este deplasat cu o celulă la dreapta.
| valoarea actuala | b 4 | b 3 | b 2 | b 1 | b 0 | k i |
|---|---|---|---|---|---|---|
| Valoarea initiala | 1 | 0 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 1 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 0 | 1 | 1 | 0 |
| 8 | 1 | 0 | 1 | 0 | 1 | 1 |
| 9 | 1 | 1 | 0 | 1 | 0 | 1 |
| 10 | 1 | 1 | 1 | 0 | 1 | 0 |
| 11 | 1 | 1 | 1 | 1 | 0 | 1 |
| 12 | 0 | 1 | 1 | 1 | 1 | 0 |
| 13 | 0 | 0 | 1 | 1 | 1 | 1 |
| 14 | 0 | 0 | 0 | 1 | 1 | 1 |
| 15 | 1 | 0 | 0 | 0 | 1 | 1 |
| 16 | 0 | 1 | 0 | 0 | 0 | 1 |
| 17 | 0 | 0 | 1 | 0 | 0 | 0 |
| 18 | 1 | 0 | 0 | 1 | 0 | 0 |
| 19 | 1 | 1 | 0 | 0 | 1 | 0 |
| 20 | 1 | 1 | 1 | 0 | 0 | 1 |
Rețineți că fluxul cheie este 1000100110101111 1001……. Arată, la prima vedere, ca o secvență aleatorie, dar dacă ne uităm la un număr mare de tranzacții (schimbări), putem vedea că secvențele sunt periodice. Această repetiție de 15 biți este prezentată mai jos.
Cheia de flux este generată folosind un registru de deplasare cu feedback liniar secvență pseudoaleatoare, în care se repetă secvențe de lungime N. Debitul este periodic. Depinde de circuitul generatorului și de informațiile inițiale și nu poate fi mai mare de 2 m – 1. Fiecare circuit generează secvențe de m biți, de la cele care conțin toate zerourile până la cele care le conțin pe toate. Cu toate acestea, dacă secvența inițială este cu toate zerourile, rezultatul este inutil - textul original ar fi un flux de toate zerourile. Prin urmare, o astfel de secvență inițială este exclusă.
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 de flux bazate pe registru de schimbare au fost calul de bătaie al criptografiei militare cu mult înainte de apariția electronicii.
Un registru de deplasare în buclă închisă (denumit în continuare RGSSOC) constă din două părți: un registru de deplasare și o funcție de feedback. Un registru de deplasare este o secvență de biți. Numărul de biți este determinat lungimea registrului de deplasare, dacă lungimea este de n biți, atunci registrul este apelat registru cu deplasare de n biți. Ori de câte ori un bit trebuie recuperat, toți biții din registrul de deplasare sunt deplasați la dreapta cu 1 poziție. 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 schimb este lungimea secvenței rezultate înainte de a începe repetarea acesteia.
Figura 1. Registrul de deplasare a feedback-ului
Registrele de deplasare și-au găsit rapid folosirea în cifrurile de flux, deoarece au fost implementate cu ușurință folosind hardware digital. În 1965, Ernst Selmer, criptograf șef al guvernului norvegian, a dezvoltat teoria secvenței registrului de deplasare. Solomon Golomb, un matematician NSA, a scris o carte în care prezintă unele dintre rezultatele lui și ale lui Selmer. Cel mai simplu tip de registru cu deplasare cu feedback este un registru cu deplasare cu feedback liniar (LFSR). Feedback-ul unor astfel de registre este pur și simplu un XOR (adăugare modul doi) a unor biți de registru, o listă a acestor biți numită secvență tap. Uneori, un astfel de registru se numește configurație Fibbonacci. Datorită simplității secvenței de feedback, teoria matematică destul de avansată poate fi utilizată pentru a analiza PrCsVOC. Analizând secvențele rezultate, puteți verifica dacă secvențele sunt suficient de aleatorii pentru a fi sigure. RGCCLOS este folosit mai des decât alte registre de deplasare în criptografie.
Figura 2. PrCsLOS Fibbonacci
În general, un PrCsLOS de n biți poate fi într-una dintre N=2 n -1 stări interne. Aceasta înseamnă că teoretic un astfel de registru poate genera o secvență pseudo-aleatorie cu o perioadă de T=2 n -1 biți. (Numărul de stări interne și perioada sunt egale cu N=T max =2 n -1, deoarece completarea PrCsLOS cu zerouri va face ca registrul de deplasare să producă o succesiune infinită de zerouri, ceea ce este absolut inutil). Numai pentru anumite secvențe de ramificație PrCsLOS va trece ciclic prin toate cele 2 n -1 stări interne, astfel de PrCsLOS sunt RgSsLOS cu perioada maximă. Rezultatul rezultat se numește secvența M.
Exemplu . Figura de mai jos arată un PrCCLOS pe 4 biți cu primul și al patrulea biți selectați. Dacă este inițializat cu valoarea 1111, atunci înainte de a se repeta registrul va avea următoarele stări interne:
 Schimbă numărul de ceas (stare internă) |
Starea de înregistrare |
Bit de ieșire |
|||
|
Valoarea initiala |
|||||
|
15 (revenirea la starea inițială) |
|||||
|
16 (stări repetate) |
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 cu o perioadă T=15, numărul total de stări interne posibile (cu excepția zero), N=2 4 -1=16-1= 15=T max , prin urmare, secvența de ieșire este o secvență M.
Pentru ca un anumit PrCsLOS să aibă o perioadă maximă, polinomul format din secvența tape și constanta 1 trebuie să fie primitiv modulo 2. Polinomul este reprezentat ca o sumă de puteri, de exemplu, un polinom de gradul n este reprezentat după cum urmează :
A n x n +a n-1 x n-1 + … +a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 + … +a 1 x+a 0 , unde un i =(0,1) pentru i=1…n, a x i - indică cifra.
Gradul polinomului este lungimea registrului de deplasare. Un polinom primitiv de gradul n este un polinom ireductibil care este un divizor al lui x 2n?1 +1, dar nu este un divizor al lui x d +1 pentru toți d care sunt divizori ai lui 2 n -1. Teoria matematică corespunzătoare poate fi găsită în.
În general, nu există o modalitate ușoară de a genera polinoame primitive de un anumit grad modulo 2. Cel mai simplu mod este de a selecta un polinom la întâmplare și de a verifica dacă este primitiv. Acest lucru nu este ușor și este un pic ca verificarea pentru a vedea dacă un număr selectat aleatoriu este prim - dar multe pachete de software de matematică pot rezolva această problemă.
Unele, dar cu siguranță nu toate, polinoamele de diferite grade care sunt primitive modulo 2 sunt prezentate mai jos. De exemplu, înregistrați
(32, 7, 5, 3, 2, 1, 0) înseamnă că următorul polinom este primitiv modulo 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.
Acest lucru poate fi generalizat cu ușurință la PrCsVOC cu o perioadă maximă. Primul număr este lungimea PrCsLOS. Ultimul număr este întotdeauna 0 și poate fi omis. Toate numerele, cu excepția lui 0, specifică o secvență de atingere, numărată de la marginea din stânga a registrului de deplasare. Adică, termenii unui polinom cu grade inferioare corespund pozițiilor mai apropiate de marginea dreaptă a registrului.
Continuând cu exemplul, scrierea (32, 7, 5, 3, 2, 1, 0) înseamnă că pentru un registru de deplasare de 32 de biți dat, un nou bit este generat prin XOR al treizeci și al doilea, al șaptelea, al cincilea, al treilea, al doilea și primii biți, PrCsLOS rezultat va avea o lungime maximă, parcurgând 2 32 -1 valori înainte de a se repeta.
Figura 4. PrCCLOS pe 32 de biți cu lungime maximă
Să luăm în considerare codul de program PrCsLOS, în care secvența tape este caracterizată de un polinom (32, 7, 5, 3, 2, 1, 0). În C arată așa:
ShiftRegister lung static nesemnat = 1;
/* Totul în afară de 0. */
ShiftRegister = ((((ShiftRegister >> 31)
^(ShiftRegister >> 6)
^(ShiftRegister >> 4)
^(ShiftRegister >> 2)
^(ShiftRegister >> 1)
^ShiftRegister))
| (ShiftRegister >> 1);
returnează ShiftRegister & 0x00000001;)
Dacă registrul de deplasare este mai lung decât un cuvânt de calculator, codul devine mai complicat, dar nu mult. Anexa B conține un tabel al unor polinoame primitive modulo 2; îl vom folosi în viitor pentru a identifica unele proprietăți ale acestor polinoame, precum și în implementarea software-ului pentru a specifica secvența de tap.
Vă rugăm să rețineți că toate elementele tabelului au un număr impar de coeficienți. Acest tabel lung este furnizat pentru lucrări ulterioare cu RgCsLOC, deoarece RgCsLOC este adesea folosit pentru criptare cu cifruri de flux și în generatoare de numere pseudo-aleatoare. În cazul nostru, putem folosi polinoame cu cel mai mare grad de cel mult șapte.
Dacă p(x) este primitiv, atunci x n p(1/x) este primitiv, deci fiecare element al tabelului definește de fapt două polinoame primitive. De exemplu, dacă (a, b, 0) este primitiv, atunci (a, a-b, 0) este și el primitiv. Dacă (a, b, c, d, 0) este primitiv, atunci (a, a-d, a-c, a-b, 0) este de asemenea primitiv. Din punct de vedere matematic:
dacă x a +x b +1 este primitiv, atunci x a +x a-b +1 este primitiv,
dacă x a +x b +x c +x d +1 este primitiv, atunci x a +x a-d +x a-c +x a-b +1 este primitiv. Trinoamele primitive sunt cele mai rapide de implementat în software, deoarece pentru a genera un nou bit trebuie să XOR doar doi biți din registrul de deplasare (termenul zero nu este luat în considerare, adică x 0 = 1, vezi exemplul de mai sus). Într-adevăr, toate polinoamele de feedback date în tabel sunt rare, adică au puțini coeficienți. Sparsitatea este întotdeauna o sursă de slăbiciune, care uneori este suficientă pentru a rupe algoritmul. Pentru algoritmii criptografici, este mult mai bine să folosiți polinoame primitive dense, cele cu mulți coeficienți. Folosind polinoame dense, mai ales ca parte a unei chei, se poate folosi PrCsLOS mult mai scurt.
Generarea de polinoame primitive dense modulo 2 nu este ușoară. În general, pentru a genera polinoame primitive de gradul k, trebuie să cunoașteți factorizarea numărului 2 k -1.
Prin ei înșiși, PrCsLOS sunt generatori buni de secvențe pseudo-aleatoare, dar au unele proprietăți nealeatoare (deterministe) nedorite. Biții consecutivi sunt liniari, ceea ce îi face inutili pentru criptare. Pentru un PrCcLOS de lungime n, starea internă este cei n biți de ieșire anteriori ai generatorului. Chiar dacă circuitul de feedback este păstrat secret, acesta poate fi determinat din cei 2n biți de ieșire ai oscilatorului folosind algoritmul extrem de eficient Berlekamp-Massey.
În plus, numerele mari aleatorii generate folosind biți consecutivi ai acestei secvențe sunt foarte corelate și, pentru unele tipuri de aplicații, nu sunt deloc aleatorii. În ciuda acestui fapt, RgCCLOS sunt adesea folosite pentru a crea algoritmi de criptare ca componente ale sistemelor și algoritmi de criptare.
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 de flux bazate pe registru de schimbare au fost calul de bătaie al criptografiei militare cu mult înainte de apariția 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 recuperat, toți biții registrului de deplasare sunt deplasate la dreapta cu 1 poziție. 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 rezultate înainte de a începe să se repete.
Orez. 1.2.1.
Criptografilor le-au plăcut cifrurile în flux bazate pe registre de deplasare: erau ușor de implementat folosind hardware digital. Voi aborda doar pe scurt teoria matematică. În 1965, Ernst Selmer, criptograf șef al guvernului norvegian, a dezvoltat teoria secvenței registrului de deplasare. Solomon Golomb, un matematician NSA, a scris o carte în care prezintă unele dintre rezultatele lui și ale lui Selmer.
Cel mai simplu tip de registru cu deplasare cu feedback este registrul cu deplasare cu feedback liniar sau LFSR (Figura 1.2.2). Feedback-ul este pur și simplu un XOR al unor biți de registru, o listă a acestor biți numită secvență de atingere. Uneori, un astfel de registru se numește configurație Fibbonacci. Datorită simplității secvenței de feedback, teoria 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. Figura 1.2.3 prezintă un LFSR pe 4 biți cu atingeri de la primul și al patrulea biți. Dacă este inițializat cu valoarea 1111, atunci înainte de a se repeta registrul va avea 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 pe n biți poate fi într-una dintre 2n-1 stări interne. Aceasta înseamnă că, teoretic, 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ă producă un șir nesfârșit de zerouri, ceea ce este absolut inutil.) Numai pentru anumite secvențe de atingeri LFSR va trece prin toate cele 2n- 1 stări interne, astfel de LFSR-uri sunt LFSR-uri cu o perioadă maximă. Rezultatul rezultat se numește secvență M.
Pentru ca un anumit LFSR să aibă o perioadă maximă, polinomul format din secvența tape și constanta 1 trebuie să fie primitive modulo 2. Gradul polinomului este lungimea registrului de deplasare. Un polinom primitiv de gradul n este un polinom ireductibil care este divizor, dar nu este 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 de a selecta un polinom la întâmplare și de a verifica dacă este primitiv. Acest lucru nu este ușor - și este un pic ca verificarea pentru a vedea dacă un număr aleatoriu este prim - dar multe pachete de software de matematică pot rezolva această problemă.
Unele, dar cu siguranță nu toate, polinoamele de diferite grade sunt primitive modulo 2. De exemplu, scrierea (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 perioada maximă LFSR. Primul număr este lungimea LFSR. Ultimul număr este întotdeauna 0 și poate fi omis. Toate numerele, cu excepția lui 0, specifică o secvență de atingere, numărată de la marginea din stânga a registrului de deplasare. Adică, termenii unui polinom cu grade inferioare corespund pozițiilor mai apropiate de marginea dreaptă a registrului.
Continuând cu exemplul, scrierea (32, 7, 5, 3, 2, 1, 0) înseamnă că pentru un registru de deplasare de 32 de biți dat, un nou bit este generat prin XOR al treizeci și al doilea, al șaptelea, al cincilea, al treilea, al doilea și primii biți LFSR rezultat va avea o lungime maximă, parcurgând 232-1 valori înainte de a se repeta.
Linear Feedback Shift Register (LFSR) este un mecanism pentru crearea unei secvențe pseudo-aleatoare de biți binari. Registrul (Fig. 1) constă dintr-un număr de celule care sunt stabilite printr-un vector de inițializare (cel mai adesea o cheie secretă). Funcționarea registrului este determinată de prezența sau absența comunicării de la fiecare bit la feedback. Atingerile registrului de feedback nu sunt fixe, dar fac parte din cheie. La pasul următor, conținutul celulelor de registru este deplasat cu o poziție la dreapta și un bit rămas liber ca rezultat al operației XOR este plasat în celula din stânga.
Orez. 1. Registru de deplasare cu feedback liniar
Pentru a atinge perioada maximă gamma de cifrare, numărul de biți m Registrul de deplasare este ales să fie egal cu unul dintre numerele prime Mersenne (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203...) și conexiunile interne ale registrului trebuie alese conform cu polinoame primitive ireductibile cu gradul cel mai mare m. În acest caz, perioada gamma a cifrului poate atinge (2 m-1).
LFSR este rapid și ușor de implementat atât în software, cât și în hardware. Cu alegerea corectă a biților de feedback, secvențele generate au proprietăți statistice bune. LFSR este folosit ca element de bază pentru construirea de sisteme extrem de sigure.
O cascadă de registru este un set de LFSR-uri conectate în așa fel încât comportamentul unui LFSR depinde de comportamentul LFSR-ului anterior în cascadă. Acest comportament „dependent” este de obicei conceput pentru a controla contorul de schimbare al următorului LFSR de către primul LFSR.
De exemplu, un registru este deplasat cu un pas dacă valoarea registrului precedent este 1, iar dacă valoarea este 0, atunci registrul este deplasat cu doi pași sau într-un alt mod. Un număr mare de astfel de combinații permite o securitate foarte ridicată.
Cele mai sigure secvențe sunt produse de un generator de micșorare bazat pe o interacțiune simplă între rezultatele a două registre LFSR. Biții unui rezultat determină dacă biții corespunzători ai celui de-al doilea rezultat vor fi utilizați ca parte a „cheii fluxului” completă. Generatorul de compresie este simplu, scalabil și are proprietăți de protecție bune. Dezavantajul său este că rata de generare a „cheii de flux” nu va fi constantă decât dacă se iau unele măsuri de precauție.
Metoda Fibonacci cu decalaje Unul dintre generatoarele Fibonacci utilizate pe scară largă se bazează pe următoarea formulă iterativă:
Unde Y k- numere reale din interval
Orez. 2. Criptare rotund-robin
Modul de feedback de ieșire DES poate fi utilizat pentru a genera numere pseudoaleatoare, similar modului în care este utilizat pentru criptarea fluxului. Ieșirea fiecărei etape de criptare este o valoare de 64 de biți, din care doar cei mai semnificativi biți j sunt reintroduși pentru criptare. Ieșirile pe 64 de biți sunt o secvență de numere pseudoaleatoare cu proprietăți statistice bune.
Generatorul de numere pseudo-aleatoare, descris în standardul ANSI X9.17, este unul dintre cei mai siguri generatori de numere pseudo-aleatoare. Aplicațiile care utilizează această tehnologie includ securitate financiară și aplicații PGP.
Generatorul ANSI X9.17 este format din următoarele părți (Fig. 3):
1. Intrare: Generatorul este controlat de două intrări pseudo-aleatorie. Prima intrare este o reprezentare pe 64 de biți a datei și orei curente ( DT i), care se schimbă de fiecare dată când este creat un număr. Cea de-a doua intrare este o sămânță de 64 de biți, care este inițializată la o valoare arbitrară și modificată în timpul generării unei secvențe de numere pseudoaleatoare ( V i).
2. Chei: Generatorul folosește trei module DES triple cu două chei K1, K2. Toate trei folosesc aceeași pereche de chei pe 56 de biți, care trebuie păstrată secretă și folosită doar pentru a genera un număr pseudo-aleatoriu.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K1, K2 |
| DT i |
| V i |
| R i |
| V i+1 |
( V i +1) .
Orez. 3. Generator de numere pseudoaleatoare ANSI X9.17
