Il Linear Feedback Shift Register (LFSR) è un meccanismo per creare una sequenza pseudo-casuale di bit binari. Il registro (Fig. 1) è costituito da una serie di celle impostate da un vettore di inizializzazione (molto spesso una chiave segreta). Il funzionamento del registro è determinato dalla presenza o meno di comunicazione da ogni bit al feedback. I tap del registro di feedback non sono fissi ma fanno parte della chiave. Nella fase successiva, il contenuto delle celle del registro viene spostato di una posizione a destra e un bit che rimane libero come risultato dell'operazione XOR viene posizionato nella cella più a sinistra.
Figura: 1. Registro a scorrimento con feedback lineare
Per ottenere il periodo gamma di cifratura massimo, il numero di cifre mdel registro a scorrimento è selezionato per essere uguale a uno dei numeri primi di Mersenne (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...) e le connessioni interne del registro devono essere selezionate in base con polinomi primitivi irriducibili di massimo grado m... In questo caso, il periodo della gamma di cifratura può raggiungere (2 m-1).
LFSR è veloce e facile da implementare sia nel software che nell'hardware. Con la giusta scelta di bit di feedback, le sequenze generate hanno buone proprietà statistiche. LFSR viene utilizzato come elemento costitutivo di base per sistemi altamente sicuri.
Cascade of registers - Un insieme di LFSR collegati in modo tale che il comportamento di un LFSR dipenda dal comportamento del precedente LFSR nella cascata Questo comportamento "dipendente" è solitamente impostato per controllare il contatore di offset del successivo LFSR dal primo LFSR.
Ad esempio, il registro viene spostato di un passo se il valore del registro precedente è 1 e se il valore è 0, il registro viene spostato di due passi o in altro modo. Un gran numero di tali combinazioni fornisce una sicurezza molto elevata.
Le sequenze crittograficamente più forti sono fornite da un generatore di rimpicciolimento basato su una semplice interazione tra i risultati di due registri LFSR. I bit di un risultato determinano se i bit corrispondenti del secondo risultato verranno utilizzati come parte della "chiave di streaming" completa. Il generatore di compressione è semplice, scalabile e ha buone proprietà di schermatura. Il suo svantaggio è che la velocità di generazione della "chiave streaming" non sarà costante, se non si prendono alcune precauzioni.
Metodo di Fibonacci con ritardiUno dei generatori di Fibonacci più diffusi si basa sulla seguente formula iterativa:
dove Y k - numeri reali dell'intervallo
Figura: 2. Crittografia ciclica
La modalità di loopback dell'output DES può essere utilizzata per generare numeri pseudo-casuali, in modo simile a come viene utilizzata per la crittografia del flusso. L'output di ciascuna fase di crittografia è un valore a 64 bit, di cui solo i bit j più significativi vengono restituiti per la crittografia. Gli output a 64 bit costituiscono una sequenza di numeri pseudo-casuali con buone proprietà statistiche.
Il generatore di numeri pseudocasuali ANSI X9.17 è uno dei generatori di numeri pseudocasuali più potenti dal punto di vista crittografico. Le applicazioni che utilizzano questa tecnologia includono la sicurezza finanziaria e le applicazioni PGP.
Il generatore ANSI X9.17 è costituito dalle seguenti parti (Figura 3):
1. Ingresso: il generatore è controllato da due ingressi pseudocasuali. Il primo input è una rappresentazione a 64 bit della data e dell'ora correnti ( DT i) che cambiano ogni volta che crei un numero. Il secondo input è un valore iniziale a 64 bit, che viene inizializzato a un valore arbitrario e modificato durante la generazione di una sequenza di numeri pseudo-casuali ( V i).
2. Tasti: il generatore utilizza tre moduli DES tripli con due tasti K 1, K 2. Tutti e tre utilizzano la stessa coppia di chiavi a 56 bit, che deve essere tenuta segreta e utilizzata solo per generare un numero pseudo-casuale.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K 1, K 2 |
| DT i |
| V i |
| R i |
| V io + 1 |
3. Output: l'output consiste in un numero pseudocasuale R i a 64 bit e un valore a 64 bit che verrà utilizzato come valore iniziale durante la creazione del numero successivo ( V i +1) .
Figura: 3. ANSI X9.17 generatore di numeri pseudo-casuali
In un registro a scorrimento con retroazione lineare si distinguono due parti (moduli): il registro a scorrimento stesso e circuiti (o subroutine) che calcolano il valore del bit inserito. Il registro è costituito da celle funzionali (o bit di una parola macchina o più parole), ciascuna delle quali memorizza lo stato corrente di un bit. Il numero di celle è chiamato lunghezza del registro. I bit (celle) sono solitamente numerati con numeri, ognuno dei quali è in grado di memorizzare un bit, e il bit calcolato viene inserito nella cella e il bit successivo generato che viene espulso viene estratto dalla cella. Il calcolo del bit da inserire viene solitamente eseguito prima dello shift del registro, e solo dopo lo shift il valore del bit calcolato viene posto nella cella.
Il periodo del registro a scorrimento è la lunghezza minima della sequenza ricevuta prima dell'inizio della sua ripetizione. Poiché il registro delle celle di bit ha solo stati diversi da zero diversi, quindi, in linea di principio, il periodo del registro non può superare questo numero. Se il periodo del registro è uguale a questo numero, tale registro viene chiamato registro del periodo massimo.
Per RSLOS, la funzione di feedback è una funzione booleana lineare degli stati di tutti o alcuni dei bit di registro. Ad esempio, la somma modulo due o il suo inverso logico è una funzione booleana lineare (operazione XOR, indicata come nelle formule) ed è più spesso utilizzata in tali registri.
In questo caso, vengono solitamente chiamati quei bit che sono variabili della funzione di feedback rubinetti.
Il registro è controllato nelle implementazioni hardware applicando un impulso di spostamento (altrimenti chiamato orologio o impulso di sincronizzazione) a tutte le celle, nelle celle di programma - eseguendo un ciclo di programma, incluso il calcolo della funzione di feedback e lo spostamento di bit nella parola.
Durante ogni fase temporale vengono eseguite le seguenti operazioni:
Registro di scorrimento del feedback lineare
Pertanto, l'operazione logica XOR (OR esclusivo) viene presa come funzione di feedback, ovvero:
Proprietà dei polinomi primitivi
Proprietà
Le proprietà della sequenza emessa da RSLOS sono strettamente correlate alle proprietà del polinomio associato. Vengono chiamati i suoi coefficienti diversi da zero rubinetticosì come le corrispondenti celle di registro che forniscono i valori degli argomenti alla funzione di feedback.
Complessità lineare
La complessità lineare di una sequenza binaria è una delle caratteristiche più importanti del funzionamento di RSLOS. Introduciamo la seguente notazione:
DefinizioneComplessità lineare di una sequenza binaria infinita chiamato un numero, che è definito come segue:
Complessità lineare di una sequenza binaria finita è chiamato un numero che è uguale alla lunghezza del RLOS più breve, che genera una sequenza che ha come primi membri.
Proprietà di complessità lineare
Siano e siano sequenze binarie. Poi:
Indipendenza dalla correlazione
Per ottenere un'elevata complessità lineare, i crittografi cercano di combinare i risultati di più sequenze di output in modo non lineare. In questo caso, il pericolo è che una o più sequenze di output (spesso anche le uscite di singoli RFLOS) possano essere collegate da un flusso di chiavi comune e aperte utilizzando l'algebra lineare. Viene chiamato l'hacking basato su una tale vulnerabilità autopsia di correlazione... Thomas Sigenthaler ha dimostrato che l'indipendenza dalla correlazione può essere determinata con precisione e che esiste un compromesso tra indipendenza dalla correlazione e complessità lineare.
L'idea principale alla base di questo hack è trovare una correlazione tra l'output del generatore e l'output di una delle sue parti costituenti. Quindi, osservando la sequenza di output, è possibile ottenere informazioni su questo pin intermedio. Utilizzando queste informazioni e altre correlazioni, è possibile raccogliere dati su altre inferenze intermedie fino a quando il generatore non viene violato.
Gli attacchi o le variazioni di correlazione, come gli attacchi di correlazione rapida, sono stati utilizzati con successo contro molti generatori di keystream basati su registri a scorrimento di feedback lineare, che comportano un compromesso tra complessità computazionale ed efficienza.
Esempio
Per RSLOS con un polinomio associato, la sequenza generata ha la forma. Supponiamo che una sequenza venga scritta nel registro prima di avviare il processo, quindi il periodo del flusso di bit generato sarà 7 con la seguente sequenza:
| Numero di passaggio | condizione | Bit generato |
| 0 | - | |
| 1 | 1 | |
| 2 | 1 | |
| 3 | 0 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 1 | |
| 7 | 0 |
Poiché lo stato interiore al settimo passaggio è tornato al suo originale, quindi, a partire dal passaggio successivo, ci sarà una ripetizione. In altre parole, il periodo della sequenza è risultato essere 7, cosa che è avvenuta a causa della primitività del polinomio.
Algoritmi per la generazione di polinomi primitivi
Tavoli pronti
Calcolare la primitività di un polinomio è un problema matematico piuttosto difficile. Pertanto, ci sono tabelle già pronte che danno i numeri delle sequenze di tocco che forniscono il periodo massimo del generatore. Ad esempio, esiste una sequenza per uno shift register a 32 bit. Ciò significa che per generare un nuovo bit, è necessario XOR il 31 °, 30 °, 29 °, 27 °, 25 ° e 0 ° bit. Il codice per tale RSLOS in C è il seguente:
Int LFSR (void) (statico lungo senza segno S \u003d 1; S \u003d ((((S \u003e\u003e 31) ^ (S \u003e\u003e 30) ^ (S \u003e\u003e 29) ^ (S \u003e\u003e 27) ^ (S \u003e\u003e 25) ^ S) e 1)<< 31 ) | (S>\u003e 1); return S & 1; )
Le implementazioni software dei generatori RSLOS sono piuttosto lente e funzionano più velocemente se sono scritte in assembler e non in C. Una delle soluzioni consiste nell'utilizzare 16 RSLOS in parallelo (o 32, a seconda della lunghezza della parola nell'architettura di un particolare computer). In tale schema, viene utilizzato un array di parole, la cui dimensione è uguale alla lunghezza di RSLOS e ogni bit della parola nell'array fa riferimento al proprio RSLOS. A condizione che vengano utilizzati gli stessi numeri di sequenza delle dita, ciò può fornire miglioramenti significativi delle prestazioni. [esempio di codice necessario] (Vedi: bitslice).
Configurazione di Galois
Configurazione di Galois del registro a scorrimento a retroazione lineare
Anche il ciclo di feedback può essere modificato. In questo caso, il generatore non avrà una maggiore forza crittografica, ma sarà più facile implementarlo nel software. Invece di usare i bit di Finger Sequence per generare un nuovo bit più a sinistra, ogni bit della F-Sequence viene XORed e sostituito con l'uscita del generatore, quindi il risultato del generatore diventa il nuovo bit più a sinistra. In linguaggio C, assomiglia a questo:
Int LFSR (void) (statico lungo senza segno Q \u003d 1; Q \u003d (Q \u003e\u003e 1) ^ (Q & 1? 0x80000057: 0); return Q & 1;)
Il vantaggio è che tutti gli XOR vengono eseguiti in un'unica operazione.
- è possibile dimostrare che la configurazione di Fibonacci data nella prima e la configurazione di Galois qui data danno le stesse sequenze (lunghezza 2 32 −1), ma sfasate l'una dall'altra
- un ciclo di un numero fisso di chiamate LFSR nella configurazione Galois è circa due volte più veloce rispetto alla configurazione Fibonacci (compilatore MS VS 2010 su Intel Core i5)
- si noti che nella configurazione Galois, l'ordine dei bit nella parola di feedback è invertito rispetto alla configurazione di Fibonacci
Esempi di generatori
Generatori stop-and-go
Generatore alternato stop-and-go
Questo oscillatore utilizza l'uscita di un RSLOS per controllare la frequenza di clock dell'altro RSLOS. L'uscita del clock RSLOS-2 è controllata dall'uscita RSLOS-1, in modo che RSLOS-2 possa cambiare il suo stato all'istante t solo se l'uscita RSDOS-1 all'istante t-1 era uguale a uno. Ma questo schema non ha resistito alla resa dei conti della correlazione.
Pertanto, è stato proposto un generatore migliorato basato sulla stessa idea. Si chiama generatore alternato stop-and-go. Utilizza tre RFLO di diverse lunghezze. RSLOS-2 ha un clock quando l'uscita di RSLOS-1 è uguale a uno e RSLOS-3, quando l'uscita di RSLOS-1 è zero. L'uscita del generatore è la somma modulo 2 di RSLOS-2 e RSLOS-3. Questo generatore ha un lungo periodo e una grande complessità lineare. I suoi autori hanno anche mostrato un metodo di apertura di correlazione di RSLOS-1, ma questo non indebolisce notevolmente il generatore.
La cascata di Gollmann
La cascata di Gollmann
Il palco Gollmann è una versione rinforzata di un generatore stop-and-go. Consiste in una sequenza di RSLOS, il clock di ciascuno dei quali è controllato dal precedente RSLOS. Se l'uscita di RSLOS-1 all'istante t è 1, RSLOS-2 è sincronizzato. Se l'uscita di RSLOS-2 all'istante t è 1, RSLOS-3 è sincronizzato e così via. L'ultima uscita RFLOS è l'uscita del generatore. Se la lunghezza di tutti gli RFLOS è la stessa ed è uguale an, allora la complessità lineare di un sistema di k LLS è uguale a.
Questa idea è semplice e può essere utilizzata per generare sequenze con periodi enormi, elevata complessità lineare e buone proprietà statistiche. Sfortunatamente, tuttavia, sono sensibili a un attacco chiamato "lock-in". Per una maggiore durata, si consiglia di utilizzare k almeno 15. Inoltre, è preferibile utilizzare RFLOS più brevi rispetto a un numero inferiore di RFLO lunghi.
Generatore di soglie
Generatore di soglie
Questo generatore tenta di aggirare i problemi di sicurezza dei generatori precedenti utilizzando un numero variabile di registri a scorrimento. In teoria, quando viene utilizzato un numero maggiore di registri a scorrimento, la complessità della cifratura aumenta, cosa che è stata eseguita in questo generatore.
Questo generatore è costituito da un gran numero di registri a scorrimento, le cui uscite vanno alla funzione di maggiorizzazione. Se il numero di unità alle uscite del registro è più della metà, il generatore ne emette uno. Se il numero di zeri alle uscite è più della metà, il generatore emette zero. Affinché sia \u200b\u200bpossibile il confronto tra il numero di zeri e uno, il numero di registri a scorrimento deve essere dispari. Le lunghezze di tutti i registri devono essere relativamente semplici ei polinomi di retroazione devono essere primitivi affinché il periodo della sequenza generata sia massimo.
Nel caso di tre registri a scorrimento, il generatore può essere rappresentato come:
Questo generatore è simile al generatore di Geff, tranne per il fatto che il generatore di soglia ha una complessità più lineare. La sua complessità lineare è:
dove ,, sono le lunghezze del primo, del secondo e del terzo registro a scorrimento.
Il suo svantaggio è che ogni bit di uscita fornisce alcune informazioni sullo stato del registro a scorrimento. Più precisamente 0,189 bit. Pertanto, questo generatore potrebbe non resistere a un attacco di correlazione.
Altri tipi
Assottigliamento
I generatori autodecimanti sono quelli che controllano la propria frequenza. Sono stati proposti due tipi di tali generatori. Il primo è costituito da un registro a scorrimento a retroazione lineare e da alcuni circuiti che sincronizzano questo registro, a seconda di quali sono i valori di uscita del registro a scorrimento. Se l'uscita RSLOS è uguale a uno, il registro viene sincronizzato d volte. Se l'uscita è zero, il registro viene sincronizzato k volte. Il secondo ha quasi lo stesso design, ma leggermente modificato: nel circuito di clock, l'ingresso, come controllo per 0 o 1, non riceve il segnale di uscita stesso, ma lo XOR di alcuni bit del registro a scorrimento con feedback lineare. Sfortunatamente, questo tipo di generatore non è sicuro.
Generatore a più velocità con prodotto interno
Questo generatore utilizza due registri a scorrimento con feedback lineare con diverse frequenze di clock: RSLOS-1 e RSLOS-2. La frequenza di clock di RSLOS-2 è d volte superiore a quella di RSLOS-1. I singoli bit di questi registri vengono associati in AND. Quindi XOR viene eseguito sugli output dell'operazione AND. La sequenza di output viene rimossa da questo blocco XOR. Ancora una volta, questo generatore non è impeccabile (non ha resistito all'apertura della consistenza lineare. Se è la lunghezza di RSLOS-1, è la lunghezza di RSLOS-2 ed è il rapporto di frequenza di clock, quindi lo stato interno del generatore può essere ottenuto dalla sequenza di output della lunghezza), ma ha un'elevata complessità lineare e ottime prestazioni statistiche.
Il tipo più semplice di funzione di feedback è una funzione lineare, ad esempio, la somma modulo 2 del contenuto di determinati bit. Tale registro è chiamato Linear Feedback Shift Register (LFSR). In generale, la funzione di feedback lineare è data dalla formula. Qui c k\u003d 1 se kla cifra è utilizzata nella funzione di feedback, e c k\u003d 0 altrimenti. Il simbolo Å indica l'addizione modulo 2 (OR esclusivo).
Ad esempio, si consideri un LFSR con una funzione di loopback (vedere la figura).
Se lo stato iniziale del registro è 1111, nei successivi cicli di clock assumerà la seguente serie di stati: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, ...
La sequenza di uscita è formata dal bit meno significativo (più a destra) del registro. Apparirà così: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Si può vedere che la sequenza di bit generata è interamente determinata dallo stato iniziale del registro e dalla funzione di feedback. Poiché il numero di tutti i possibili stati di registro è finito (è uguale a 2 L), quindi, prima o poi, la sequenza di tasti inizierà a ripetersi. La lunghezza massima di una parte non ripetitiva di una sequenza di tasti è chiamata periodo. T... Il periodo dipende dalla funzione di feedback. Il periodo massimo possibile è T max \u003d 2 L-1 (il registro accetta tutti gli stati possibili, tranne 0000 ... 0). Viene chiamata la sequenza di output dell'LFSR con il periodo massimo Sequenza M..
Per scoprire le condizioni in cui l'LFSR avrà il periodo massimo, le funzioni di feedback associano un polinomio caratteristico. Quindi, il registro dato sopra come esempio corrisponde a un polinomio. L'analisi teorica mostra che LFSR avrà un periodo massimo se e solo se il polinomio P(x) è un primitivo... Di seguito sono riportati alcuni polinomi primitivi consigliati per l'uso pratico. La tabella mostra i gradi della variabile xnella notazione del polinomio. Ad esempio, il record (31, 3) corrisponde a un polinomio.
| № | P(x) | № | P(x) | № | P(x) |
| (39, 16, 23, 35) | (38, 5, 6, 27) | (32, 2, 7, 16) | |||
| (30, 6, 4, 1) | (31, 6) | (31, 7) | |||
| (31, 13) | (31, 25, 23, 8) | (33, 13) | |||
| (35, 2) | (47, 5) | (48, 9, 7, 4) | |||
| (47, 11, 24, 32) | (46, 18, 31, 40) | (53, 6, 2, 1) | |||
| (55, 24) | (57, 7) | (58, 19) | |||
| (59, 7, 4, 2) | (41, 27, 31, 32) | (61, 5, 2, 1) | |||
| (42, 30, 31, 34) | (51, 15, 24, 46) | (50, 17, 31, 34) |
Gli LFSR sono stati originariamente progettati per essere implementati nell'hardware come un insieme di circuiti digitali. Le implementazioni software LFSR di solito superano le implementazioni hardware. Per aumentare la velocità, è vantaggioso memorizzare lo stato del registro come numero intero L-bit numero, i cui singoli bit corrispondono alle cifre binarie del registro. Quindi, le operazioni bit per bit (shift, mascheramento, ecc.) Vengono utilizzate per accedere ai singoli bit.
Registro di spostamento del feedback ( FSR ) consiste di due parti: registro a scorrimento e funzioni di feedback .
Un registro a scorrimento (Errore: sorgente di riferimento non trovata) è una sequenza di bit. Quando un bit deve essere recuperato, tutti i bit del registro a scorrimento vengono spostati a destra di 1 posizione. Il nuovo bit più a sinistra è il valore della funzione di feedback dal resto dei bit di registro. Periodo il registro a scorrimento è la lunghezza della sequenza risultante prima dell'inizio della sua ripetizione.
La forma più semplice di un registro a scorrimento di feedback è registro a scorrimento con feedback lineare (LFSR
–
Sinistra
Risposta
Cambio
Registrati)
(Errore: fonte di riferimento non trovata). Il feedback è semplicemente uno XOR di alcuni bit di p 
register, viene chiamato l'elenco di questi bit sequenza di deviazione.
n-bit LFSR può essere in uno dei file 2 n -1 stati interni. Ciò significa che teoricamente un tale registro può generare una sequenza pseudo-casuale con un punto 2 n -1 bit. Il numero di stati interni e il periodo sono uguali, perché riempire il registro di zeri farà sì che si produca una sequenza infinita di zeri, che è assolutamente inutile. Solo per alcune sequenze di tocco l'LFSR scorre tutte 2 n -1 stati interni. Tali LFSR sono chiamati LFSR con periodo massimo.
Affinché un particolare LFSR abbia un periodo massimo, il polinomio formato dalla sequenza di derivazione e la costante 1 deve essere primitivo modulo 2 .
Calcolare la primitività di un polinomio è un problema matematico piuttosto difficile. Pertanto, ci sono tabelle già pronte che danno i numeri delle sequenze di tocco che forniscono il periodo massimo del generatore. Ad esempio, per un registro a scorrimento a 32 bit, è possibile trovare la seguente voce: (32,7,5,3,2,1,0) ... Ciò significa che per generare un nuovo bit, è necessario sommare i trentaduesimi, settimo, quinto, terzo, secondo e primo bit utilizzando la funzione XOR.
Il codice per un tale LFSR in C ++ sarebbe:
// Qualsiasi valore diverso da zero
ShiftRegister \u003d ((((ShiftRegister \u003e\u003e 31)
^ (ShiftRegister \u003e\u003e 6)
^ (ShiftRegister \u003e\u003e 4)
^ (ShiftRegister \u003e\u003e 2)
^ (ShiftRegister \u003e\u003e 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (ShiftRegister \u003e\u003e 1);
return ShiftRegister & 0x00000001;
Le implementazioni software di LFSR sono piuttosto lente e funzionano più velocemente se sono scritte in assembler piuttosto che in C. Una soluzione è usare 16 LFSR in parallelo (o 32, a seconda della lunghezza della parola nella particolare architettura del computer). In tale schema, viene utilizzato un array di parole, la cui dimensione è uguale alla lunghezza dell'LFSR e ogni unità della parola dell'array fa riferimento al proprio LFSR. A condizione che vengano utilizzati gli stessi numeri di sequenza delle dita, ciò può fornire miglioramenti significativi delle prestazioni.
A PARTIRE DAL 
anche la chimica del feedback può essere modificata. In questo caso, il generatore non avrà una maggiore forza crittografica, ma sarà più semplice implementarlo a livello di codice. Invece di utilizzare i bit della sequenza dito per generare un nuovo bit più a sinistra, XOR ogni bit della sequenza F con l'uscita del generatore e sostituirlo con il risultato di questa azione, quindi il risultato del generatore diventa il nuovo bit più a sinistra (Errore: sorgente di riferimento non trovata).
Questa modifica è chiamata configurazione di Galois... In linguaggio C assomiglia a questo:
statico lungo senza segno ShiftRegister \u003d 1;
void seed_LFSR (seme lungo non firmato)
ShiftRegister \u003d seed;
int Galua_LFSR (void)
if (ShiftRegister & 0x00000001) (
ShiftRegister \u003d (ShiftRegister ^ mask \u003e\u003e 1) | 0x8000000;
ShiftRegister \u003e\u003e \u003d 1;
Il vantaggio è che tutti gli XOR vengono eseguiti in un'unica operazione. Questo circuito può anche essere parallelizzato.
Gli stessi LFSR sono buoni generatori di sequenze pseudo-casuali, ma hanno alcune proprietà non casuali indesiderabili. I bit consecutivi sono lineari, rendendoli inutili per la crittografia. Per lunghezza LFSR nlo stato interno rappresenta il precedente nbit di uscita del generatore. Anche se lo schema di feedback è tenuto segreto, può essere determinato da 2 ni bit di uscita del generatore utilizzando algoritmi speciali. Inoltre, grandi numeri casuali generati utilizzando bit contigui di questa sequenza sono altamente correlati e, per alcuni tipi di applicazioni, non sono casuali. Nonostante ciò, gli LFSR vengono spesso utilizzati per creare algoritmi di crittografia. Per questo vengono utilizzati diversi LFSR, di solito con lunghezze e numeri di ramo diversi. La chiave è lo stato iniziale dei registri. Ogni volta che è necessario un nuovo bit, tutti i registri vengono spostati. Questa operazione è chiamata tempismo... Il bit di uscita è una funzione, preferibilmente non lineare, di alcuni bit LFSR. Questa funzione è chiamata combinando, e il generatore nel suo complesso lo è generatore di combinazione... Molti di questi generatori sono ancora al sicuro.
Registro di spostamento del feedback consiste di due parti: un registro a scorrimento e funzioni di feedback.
Figura 19. Registro a scorrimento ad anello chiuso.
In generale, un registro a scorrimento è una sequenza di alcuni elementi di un anello o di un campo. Più comunemente usato po registri a turni. La lunghezza di tale registro è espressa nel numero di bit. Ogni volta che viene recuperato un bit, tutti i bit di registro vengono spostati a destra di una posizione. Il nuovo bit più significativo viene calcolato in funzione di tutti gli altri bit di registro. L'output è solitamente il bit meno significativo. Il periodo del registro a scorrimento è la lunghezza della sequenza di output prima che inizi a ripetersi.
Il tipo più semplice di shift register è un registro a scorrimento con feedback lineare (RSLOS o LRS). Il feedback è una semplice operazione XOR su alcuni bit di registro. L'elenco di questi bit è definito polinomio caratteristico e chiamato sequenza di curve... Questo a volte viene chiamato configurazione di Fibonacci.
Fig.20. Configurazione RLOS Fibonacci.
Nell'implementazione software di RSLOS, viene utilizzato uno schema modificato: per generare un nuovo bit significativo, invece di utilizzare i bit della sequenza di tap, viene eseguita un'operazione XOR su ogni bit di esso con l'uscita del generatore, sostituendo il vecchio bit della sequenza di tap. Questa modifica viene talvolta chiamata configurazione di Galois.
Fig.21. Configurazione RSLOS Galois.
n-bit RSLOS può essere in uno di 2 n - 1 stati interni. Ciò significa che teoricamente un tale registro può generare una sequenza pseudo-casuale con un periodo di 2 n - 1 bit (il riempimento con zeri è completamente inutile). Passa tutti 2 n - 1 stato interno possibile solo con determinate sequenze di colpi. Tali registri sono chiamati RSLOS con un periodo massimo. Per garantire il periodo massimo dell'RSLOC, è necessario che sia il suo polinomio caratteristico primitivo modulo 2. Il grado del polinomio è la lunghezza del registro a scorrimento. Polinomio primitivo di grado n - è così irriducibile polinomio che è un divisore ma non un divisore x d + 1 per tutti dche sono divisori di 2 n - 1. (Quando si parla di polinomi, il termine numero primo è sostituito dal termine polinomio irriducibile). Il polinomio caratteristico dato nelle figure RLOS:
x 32 + x 7 + x 5 + x 3 + x 2 + x + 1
è primitivo modulo 2. Il periodo di tale registro sarà massimo, scorrendo tutti i 2 32 - 1 valori finché non vengono ripetuti. I più comunemente usati sono i polinomi assottigliati, ad es. che hanno solo alcuni coefficienti. i più popolari sono i trinomi.
Un parametro importante del generatore basato su RSLOS è complessità lineare... È definita come la lunghezza n il più breve RLOS in grado di simulare l'uscita del generatore. La complessità lineare è importante perché con simple algoritmo di Berlenkamp-Massey puoi ricreare un simile RSLOS selezionando solo 2 n bit gamma. Con la definizione dell'RSLOS desiderato, il cifrario a flusso è effettivamente rotto.
