Introduzione alle basi dei cifrari moderni con chiave simmetrica. Registri di spostamento del feedback lineare come generatori di numeri pseudocasuali Registro di spostamento del feedback lineare c

Nello shift register con retroazione lineare si distinguono due parti (moduli): lo shift register stesso e il circuito (o subroutine) che calcola il valore del bit inserito. Il registro è costituito da celle funzione (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 generalmente numerati da numeri, ognuno dei quali è in grado di memorizzare un bit, e il bit calcolato viene inserito nella cella e il bit successivo generato viene estratto dalla cella. Il calcolo del bit inserito viene solitamente eseguito prima dello spostamento del registro e solo dopo lo spostamento viene posto nella cella il valore del bit calcolato.

Il periodo del registro a scorrimento è la lunghezza minima della sequenza risultante prima che inizi a ripetersi. Poiché il registro delle celle di bit ha solo diversi stati diversi da zero, in linea di principio il periodo del registro non può superare questo numero. Se il periodo del registro è uguale a questo numero, tale registro è chiamato registro del periodo massimo.

Per LFSR, la funzione di feedback è una funzione booleana lineare degli stati di tutti o alcuni bit del registro. Ad esempio, la somma modulo due o il suo inverso logico è una funzione booleana lineare (operazione XOR, indicata come nelle formule) e viene utilizzata più spesso in tali registri.

In questo caso, di solito vengono chiamati quei bit che sono variabili della funzione di feedback curve.

Il controllo del registro nelle implementazioni hardware viene eseguito applicando un impulso di spostamento (altrimenti chiamato orologio o impulso di sincronizzazione) a tutte le celle, nel software - eseguendo un ciclo di programma, compreso il calcolo della funzione di feedback e lo spostamento di bit nella parola.

Durante ogni tick dell'orologio, vengono eseguite le seguenti operazioni:

Registro di spostamento 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 prodotta da LFSR sono strettamente correlate alle proprietà del polinomio associato. Vengono chiamati i suoi coefficienti diversi da zero curve, nonché le corrispondenti celle del registro, fornendo i valori degli argomenti della funzione di feedback.

Complessità lineare

La complessità lineare di una sequenza binaria è una delle caratteristiche più importanti dell'operazione LFSR. Introduciamo la seguente notazione:

La complessità lineare di una sequenza binaria infinitaè chiamato un numero, che è definito come segue:

La complessità lineare di una sequenza binaria finitaè chiamato numero , che è uguale alla lunghezza del LFSR più corto, che genera una sequenza che ha come primi termini .

Proprietà della complessità lineare

Siano e siano sequenze binarie. Quindi:

Indipendenza di correlazione

Per ottenere un'elevata complessità lineare, i crittografi cercano di combinare in modo non lineare i risultati di più sequenze di output. In questo caso, il pericolo è che una o più sequenze di output (spesso anche le uscite di singoli LFSR) 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 Siegenthaler ha dimostrato che l'indipendenza di correlazione può essere definita con precisione e che esiste un compromesso tra indipendenza di correlazione e complessità lineare.

L'idea principale alla base di questo hack è trovare una correlazione tra l'output di un generatore e l'output di una delle sue parti componenti. Quindi, osservando la sequenza di emissione, è possibile ottenere informazioni su questa uscita intermedia. Utilizzando queste informazioni e altre correlazioni, è possibile raccogliere dati su altri output intermedi fino a quando il generatore non viene violato.

Attacchi di correlazione o variazioni come attacchi di correlazione rapida sono stati utilizzati con successo contro molti generatori di flussi di chiavi basati su registro di spostamento del feedback lineare, che implicano un compromesso tra complessità ed efficienza computazionale.

Esempio

Per LFSR con un polinomio associato, la sequenza generata ha la forma . Supponiamo, prima dell'inizio del processo, che la sequenza sia scritta nel registro, quindi il periodo del flusso di bit generato sarà uguale a 7 con la seguente sequenza:

Poiché lo stato interno al settimo passaggio è tornato al suo stato originale, allora, a partire dal passaggio successivo, ci sarà una ripetizione. In altre parole, il periodo della successione risulta essere uguale a 7, cosa che avveniva per la primitività del polinomio.

Algoritmi per la generazione di polinomi primitivi

Tavoli pronti

Calcolare la primitività di un polinomio è un problema matematico abbastanza complesso. Pertanto, ci sono tabelle già pronte che elencano i numeri di sequenze di tocchi che forniscono il periodo massimo del generatore. Ad esempio, per un registro a scorrimento a 32 bit, esiste una sequenza . Ciò significa che per generare un nuovo bit è necessario sommare il 31°, 30°, 29°, 27°, 25° e 0° bit utilizzando la funzione XOR. Il codice per tale LFSR nel linguaggio C è il seguente:

Int LFSR (void ) ( statico senza segno lungo S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) e 1 )<< 31 ) | (S>> 1); ritorno S & 1 ; )

Le implementazioni software dei generatori RSLOS sono piuttosto lente e funzionano più velocemente se sono scritte in assembler piuttosto che in C. Una soluzione consiste nell'utilizzare 16 RLLS in parallelo (o 32, a seconda della lunghezza della parola nell'architettura di un determinato computer). In tale schema viene utilizzata una matrice di parole, la cui dimensione è uguale alla lunghezza dell'LFSR, e ogni bit della parola matrice si riferisce al suo LFSR. A condizione che vengano utilizzati gli stessi numeri di sequenza di tocco, ciò può fornire un notevole aumento delle prestazioni. [bisogno di codice di esempio] (Vedi: fetta di bit).

configurazione di Galois

Configurazione di Galois di un registro a scorrimento a feedback lineare

Lo schema di feedback può anche essere modificato. In questo caso il generatore non avrà una maggiore potenza crittografica, ma sarà più semplice implementarlo a livello di programmazione. Invece di utilizzare i bit della sequenza di tocchi per generare un nuovo bit più a sinistra, XOR ogni bit della sequenza di tocchi 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 . In linguaggio C si presenta così:

Int LFSR (void ) ( statico senza segno lungo Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Il vantaggio è che tutti gli XOR vengono eseguiti in un'unica operazione.

• si può dimostrare che la configurazione di Fibonacci data per prima e la configurazione di Galois qui data danno le stesse sequenze (di lunghezza 2 32 −1), ma sfasate l'una dall'altra
• un ciclo di un numero fisso di chiamate alla funzione LFSR nella configurazione di Galois è circa due volte più veloce della configurazione di Fibonacci (compilatore MS VS 2010 su Intel Core i5)
• si noti che nella configurazione di Galois, l'ordine dei bit nella parola di feedback è invertito rispetto alla configurazione di Fibonacci

Esempi di generatori

generatori stop-go

Generatore alternato Stop-and-Go

Questo oscillatore utilizza l'uscita di un LFSR per controllare la frequenza di clock di un altro LFSR. L'uscita di clock di RSLOS-2 è controllata dall'uscita di RSLOS-1, in modo che RSLOS-2 possa cambiare il suo stato all'istante t solo se l'uscita di RSLOS-1 all'istante t-1 era uguale a uno. Ma questo schema non ha resistito all'apertura di correlazione.

Pertanto, è stato proposto un generatore migliorato basato sulla stessa idea. Si chiama generatore interleaved stop-and-go. Utilizza tre LFSR di diverse lunghezze. LFSR-2 è sincronizzato quando l'uscita di LFSR-1 è uguale a uno e LFSR-3, quando l'uscita di LFSR-1 è uguale a zero. L'uscita del generatore è la somma modulo 2 di RSLOS-2 e RSLOS-3. Questo generatore ha un grande periodo e una grande complessità lineare. I suoi autori hanno anche mostrato un metodo per l'apertura di correlazione di RLOS-1, ma questo non indebolisce molto il generatore.

Cascata Gollmann

Cascata Gollmann

Il Gollmann Cascade è una versione migliorata del generatore stop-go. Consiste in una sequenza di LFSR, il tempo di ciascuno dei quali è controllato dal precedente LFSR. Se l'uscita di LFSR-1 all'istante t è 1, allora LFSR-2 è sincronizzato. Se l'uscita di LFSR-2 all'istante t è 1, allora LFSR-3 è sincronizzato e così via. L'uscita dell'ultimo LFSR è l'uscita del generatore. Se la lunghezza di tutti gli LFSR è la stessa ed è uguale a n, la complessità lineare del sistema di k LFSR è .

Questa idea è semplice e può essere utilizzata per generare sequenze con periodi enormi, grandi complessità lineari e buone proprietà statistiche. Ma, purtroppo, sono suscettibili di un'apertura, chiamata "locking" (lock-in). Per una maggiore stabilità, si consiglia di utilizzare k almeno 15. Inoltre, è meglio utilizzare LFSR più corto che LFSR meno lungo.

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 si utilizza un numero maggiore di registri a scorrimento, la complessità della cifra aumenta, cosa che è stata eseguita in questo generatore.

Questo generatore è costituito da un gran numero di registri a scorrimento, le cui uscite sono alimentate alla funzione di maggioranza. Se il numero di unità alle uscite dei registri è superiore alla metà, il generatore produce un'unità. Se il numero di zeri sulle uscite è superiore alla metà, il generatore produce uno zero. Affinché il confronto del numero di zeri e uno sia possibile, il numero di registri a scorrimento deve essere dispari. Le lunghezze di tutti i registri devono essere relativamente primi e i polinomi di feedback devono essere primitivi, in modo che 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, secondo e terzo registro a scorrimento.

Il suo svantaggio è che ogni bit di uscita fornisce alcune informazioni sullo stato del registro a scorrimento. Per essere esatti 0,189 bit. Pertanto, questo generatore potrebbe non resistere all'apertura di correlazione.

Altri tipi

Autodiradamento

I generatori autodecrescenti sono chiamati generatori che controllano la propria frequenza. Sono stati proposti due tipi di tali generatori. Il primo è costituito da un registro a scorrimento a feedback lineare e da un circuito che esegue il clock di questo registro, a seconda di quali sono i valori di uscita del registro a scorrimento. Se l'uscita LFSR è uguale a uno, il registro viene sincronizzato d volte. Se l'uscita è zero, il registro viene cronometrato k volte. Il secondo ha quasi lo stesso design, ma è leggermente modificato: nel circuito di clock, come controllo di 0 o 1, non viene ricevuto il segnale di uscita stesso, ma XOR di alcuni bit dello shift register con feedback lineare. Sfortunatamente, questo tipo di generatore non è sicuro.

Oscillatore multirate con prodotto interno

Questo generatore utilizza due registri a scorrimento con feedback lineare con diverse frequenze di clock: LFSR-1 e LFSR-2. La frequenza di clock di RLOS-2 è d volte superiore a quella di RLLS-1. I singoli bit di questi registri sono combinati con un'operazione AND. Le uscite dell'operazione AND vengono quindi XORed. La sequenza di emissione viene presa da questo blocco XOR. Anche in questo caso, questo generatore non è perfetto (non è sopravvissuto all'apertura della consistenza lineare. Se - la lunghezza di LFSR-1, - la lunghezza di LFSR-2, e d è il rapporto delle frequenze di clock, allora lo stato interno del generatore può essere ottenuto dalla sequenza di output di lunghezza), ma ha un'elevata complessità lineare e prestazioni statistiche eccellenti.

Le sequenze di registro a scorrimento sono utilizzate sia nella crittografia che nella teoria della codifica. La loro teoria è ben sviluppata, i cifrari a flusso basati su registro a scorrimento erano il cavallo di battaglia della crittografia militare molto prima dell'avvento dell'elettronica.

Un registro a scorrimento di feedback è costituito da due parti: un registro a scorrimento e una funzione di feedback (Figura 1.2.1). Il registro a scorrimento è una sequenza di bit. (Il numero di bit è determinato dalla lunghezza del registro a scorrimento. Se la lunghezza è n bit, il registro è chiamato registro a scorrimento a n bit.) Ogni volta che è necessario estrarre un bit, tutti i bit del registro a scorrimento vengono spostato a destra di 1 posizione. Il nuovo bit più a sinistra è una funzione di tutti gli altri bit nel registro. L'uscita del registro a scorrimento è un bit, solitamente il meno significativo. Il periodo del registro a scorrimento è la lunghezza della sequenza risultante prima che inizi a ripetersi.

Riso. 1.2.1.

Ai crittografi piacevano i cifrari a flusso basati su registro a scorrimento: erano facili da implementare con l'hardware digitale. Toccherò solo brevemente la teoria matematica. Nel 1965, Ernst Selmer, il capo crittografo del governo norvegese, sviluppò la teoria delle sequenze dei registri a scorrimento. Solomon Golomb, un matematico della NSA, ha scritto un libro che delinea alcuni dei risultati suoi e di Selmer.

Il tipo più semplice di registro di spostamento del feedback è il registro di spostamento del feedback lineare, o LFSR (Figura 1.2.2). Il feedback è semplicemente un XOR di alcuni bit in un registro, un elenco di questi bit è chiamato sequenza di tocco. A volte un tale registro è chiamato configurazione di Fibonacci. A causa della semplicità della sequenza di feedback, è possibile utilizzare una teoria matematica piuttosto avanzata per analizzare l'LFSR. I crittografi amano analizzare le sequenze, convincendosi che queste sequenze sono abbastanza casuali da essere sicure. Gli LFSR sono più comunemente usati in crittografia rispetto ad altri registri a scorrimento.

Riso. 1.2.2.

Sulla Fig. 1.2.3 mostra un LFSR a 4 bit con un tocco sul primo e sul quarto bit. Se viene inizializzato con il valore 1111, prima di ripetere il registro assumerà i seguenti stati interni:

Riso. 1.2.3. 4

La sequenza di output sarà una stringa di bit meno significativi:

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

Un LFSR a n bit può trovarsi in uno degli stati interni 2n-1. Ciò significa che, in teoria, un tale registro può generare una sequenza pseudo-casuale con un periodo di 2n-1 bit. (Il numero di stati interni e il periodo sono 2n-1, perché riempiendo l'LFSR con zeri farà sì che il registro a scorrimento produca una sequenza infinita di zeri, il che è assolutamente inutile.) Solo con alcune sequenze di tap, l'LFSR scorrerà tutti gli stati interni 2n-1, tali LFSR sono LFSR con un periodo massimo. Il risultato risultante è chiamato sequenza M.

Affinché un particolare LFSR abbia un periodo massimo, il polinomio formato dalla sequenza di tap e la costante 1 deve essere primitivo modulo 2. Il grado del polinomio è la lunghezza del registro a scorrimento. Un polinomio primitivo di grado n è un polinomio irriducibile che è un divisore ma non è un divisore di xd+1 per tutti i d che sono divisori di 2n-1.

In generale, non esiste un modo semplice per generare polinomi primitivi di un dato grado modulo 2. Il modo più semplice è scegliere un polinomio a caso e verificare se è primitivo. Non è facile, ed è un po' come controllare se un numero scelto a caso è primo, ma molti pacchetti di software per la matematica possono farlo.

Alcuni, ma certamente non tutti, i polinomi di vari gradi sono primitivi modulo 2. Ad esempio, la notazione (32, 7, 5, 3, 2, 1, 0) significa che il seguente polinomio è primitivo modulo 2:

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

Questo può essere facilmente generalizzato a LFSR con un periodo massimo. Il primo numero è la lunghezza dell'LFSR. L'ultimo numero è sempre 0 e può essere omesso. Tutti i numeri tranne 0 specificano una sequenza di tocchi, conteggiata dal bordo sinistro del registro a scorrimento. Cioè, i termini del polinomio con un grado inferiore corrispondono a posizioni più vicine al bordo destro del registro.

Continuando l'esempio, scrivere (32, 7, 5, 3, 2, 1, 0) significa che per un dato registro a scorrimento a 32 bit, viene generato un nuovo bit XORing il trentaduesimo, settimo, quinto, terzo, secondo , e i primi bit l'LFSR risultante avrà una lunghezza massima, scorrendo 232-1 valori prima dell'iterazione.

Per costruire cifrari a flusso, molto spesso vengono utilizzate sequenze sui registri a scorrimento. Un registro a scorrimento di feedback è costituito da due parti: un registro a scorrimento e una funzione di feedback, come mostrato in Fig. 87. Lo stesso registro a scorrimento è una sequenza di bit, il cui numero determina la lunghezza del registro. Quindi, se n bit sono coinvolti nel registro, allora dicono che il registro a scorrimento di n bit. Ogni volta che viene recuperato un bit, tutti i bit del registro a scorrimento vengono spostati a destra di una posizione, solitamente verso i bit meno significativi. Il periodo del registro a scorrimento è la lunghezza della sequenza risultante prima che inizi a ripetersi.

Riso. 87.

Qualsiasi funzione matematica che esegue un'operazione sui bit può fungere da feedback. Il tipo più semplice di registro di spostamento del feedback è il registro di spostamento del feedback lineare (LFSR). In LFSR, il feedback è semplicemente un'operazione di addizione modulo 2 (XOR) su alcuni bit di un registro; l'elenco di questi bit è chiamato sequenza di prese, o punti di prelievo, come mostrato in fig. 88. A volte un tale schema è chiamato configurazione di Fibonacci. A causa della semplicità della sequenza di feedback, una teoria matematica abbastanza sviluppata può essere utilizzata per analizzare l'LFSR. In ogni caso, la qualità dell'SRP prodotto viene valutata mediante un'apposita serie di test.

Riso. 88.

Gli LFSR sono scritti sotto forma di polinomi. In questo caso, il grado del primo elemento del polinomio indica il numero di bit nel registro a scorrimento e gli esponenti esponenziali dei restanti membri del polinomio indicano quali punti di prelievo verranno utilizzati. Quindi, ad esempio, scrivere x 4 + x + 1 significa che verrà utilizzato un registro di quattro elementi, per i quali i bit bi e b 0 parteciperanno alla formazione del feedback (Fig. 89).

Riso. 89.4

Si consideri il funzionamento del registro mostrato in Fig. 89. Inizializzarlo, ad esempio, con il valore 0101 (l'inizializzazione può essere eseguita da qualsiasi sequenza di bit, tranne una sequenza di soli zeri, poiché in questo caso la retroazione formerà sempre un valore zero e il registro non producono la PSP prevista). Quindi, nel registro c'è uno spostamento a destra di una posizione. Il bit meno significativo, pari a 1, esce dal registro e costituisce il primo bit del PRS. Quei bit che erano nelle posizioni b e b 0 prima dello spostamento vengono aggiunti modulo 2 e ne formano uno nuovo

bit alto del registro. Un esempio illustrativo del funzionamento dell'LFSR considerato è mostrato in fig. 90.

Riso. 90.

Come si può vedere dalla figura. 90, la compilazione del registro passerà attraverso un peso di 15 dei 16 possibili stati (abbiamo precedentemente stabilito che il sedicesimo stato, quando LFSR è 0000, non può essere considerato). Dopodiché, il riempimento del registro sarà nuovamente uguale al valore iniziale di 0101, e la generazione della sequenza di bit inizierà a ripetersi. La sequenza di uscita del registro sarà la stringa di bit meno significativi (fino alla linea orizzontale in Fig. 90): 1010111110001001. La dimensione della sequenza di bit prima che venga ripetuta è chiamata periodo. Per garantire il periodo massimo di un particolare LFSR (cioè, affinché il registro attraversi tutti i possibili stati interni), il polinomio che determina il funzionamento del registro deve essere primitivo modulo 2. Come per i numeri primi grandi, non c'è modo di generare tali polinomi. Si può solo prendere un polinomio e verificare se è irriducibile modulo 2 o meno. Nel caso generale, un polinomio primitivo di grado n è un tale polinomio irriducibile che è un divisore di x 2 "+1, ma non è un divisore di xd +1 per tutti i d che sono divisori di 2 "-1. B. Schneier fornisce una tabella di alcuni polinomi, che sono irriducibili modulo 2.

Riassumendo le conoscenze ottenute a seguito dell'esempio del funzionamento di LFSR (Fig. 90), possiamo dire che l'LFSR a n bit può trovarsi in uno degli stati interni 2”-1. Teoricamente, un tale registro può generare una sequenza pseudo-casuale con un periodo di 2 n -1 bit. Tali registri sono chiamati registri LFSR con un periodo massimo. L'output risultante è chiamato sequenza t.

Il tipo più semplice di funzione di feedback è una funzione lineare, come la somma modulo 2 del contenuto di determinati bit. Tale registro è chiamato Linear Feedback Shift Register (abbreviato LFSR). Nel caso generale, la funzione di feedback lineare è data dalla formula . Qui c k= 1 se K il bit viene utilizzato nella funzione di feedback, e c k= 0 altrimenti. Il simbolo Å sta per addizione modulo 2 (OR esclusivo).

Ad esempio, si consideri un LFSR con una funzione di feedback (vedi figura).

Se lo stato iniziale del registro è 1111, nei cicli successivi prenderà la seguente serie di stati: …

La sequenza di uscita è formata dalla cifra meno significativa (più a destra) del registro. Si presenterà così: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Si può notare che la sequenza di bit generata è interamente determinata dallo stato iniziale del registro e dalla funzione di feedback. Poiché il numero di possibili stati del registro è finito (è uguale a 2 l), quindi, prima o poi, la sequenza di tasti comincerà a ripetersi. La lunghezza massima di una parte non ripetuta di una sequenza di tasti è chiamata periodo. T. Il periodo dipende dalla funzione di feedback. Il periodo massimo possibile è T massimo=2 l-1 (il registro prende tutti gli stati possibili tranne 0000...0). Viene richiamata la sequenza di emissione dell'LFSR con il periodo massimo Sequenza M.

Per scoprire le condizioni in cui l'LFSR avrà il periodo massimo, le funzioni di feedback corrispondono al polinomio caratteristico . Quindi, il registro sopra riportato come esempio corrisponde al polinomio . L'analisi teorica mostra che la LFSR avrà un periodo massimo se e solo se il polinomio P(X) è un primitivo. Di seguito sono riportati alcuni polinomi primitivi consigliati per un uso pratico. La tabella mostra i gradi della variabile X nel polinomio. Ad esempio, la voce (31, 3) corrisponde al polinomio .

Gli LFSR sono stati originariamente progettati per essere implementati nell'hardware come un insieme di circuiti digitali. Le implementazioni software di LFSR sono generalmente più lente delle implementazioni hardware. Per aumentare le prestazioni, è vantaggioso memorizzare lo stato del registro come intero l- numero di bit, i cui singoli bit corrispondono alle cifre binarie del registro. Quindi le operazioni bit per bit (shift, masking, ecc.) vengono utilizzate per accedere ai singoli bit.

Registro a turni di feedbackè composto da due parti: il registro a scorrimento e funzioni di feedback.

Figura 19. Registro a scorrimento del feedback.

In generale, un registro a scorrimento è una sequenza di alcuni elementi di un anello o di un campo. Più comunemente usato po registri a scorrimento. La lunghezza di tale registro è espressa come numero di bit. Ogni volta che viene recuperato un bit, tutti i bit nel registro vengono spostati a destra di una posizione. Il nuovo bit più significativo viene calcolato in funzione di tutti gli altri bit nel registro. L'uscita è solitamente il bit meno significativo. Il periodo del registro a scorrimento è la durata della sequenza di uscita prima che inizi a ripetersi.

Il tipo più semplice di registri a scorrimento è un registro a scorrimento a feedback lineare (LFSR o LRS). Il feedback è una semplice operazione XOR su alcuni bit di un registro. L'elenco di questi bit è definito polinomio caratteristico e chiamato sequenza di tocchi. A volte questo schema è chiamato Configurazione di Fibonacci.

Fig.20. LFOS della configurazione di Fibonacci.

Nell'implementazione software di LFSR 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 ciascuno dei suoi bit con l'uscita del generatore, sostituendo il vecchio parte della sequenza di tocchi. Questa modifica è talvolta chiamata configurazione di Galois.

Fig.21. RLOS della configurazione di Galois.

n-bit LFSR può essere in uno di 2 n– 1 stati interni. Ciò significa che, in teoria, un tale registro può generare una sequenza pseudo-casuale con un periodo di 2 n– 1 bit (il riempimento con zeri è completamente inutile). Passaggio di tutti e 2 n– 1 stato interno possibile solo con determinate sequenze di tocchi. Tali registri sono chiamati LFSR con un periodo massimo. Per garantire il periodo massimo di LFSR, è necessario che il suo polinomio caratteristico sia primitivo modulo 2. Il grado del polinomio è la lunghezza del registro a scorrimento. Polinomio di grado primitivo n- è così irriducibile un polinomio che è un divisore ma non è un divisore x d+ 1 per tutti D, che sono divisori di 2 n– 1. (Quando si discutono i polinomi, il termine numero primo sostituito dal termine polinomio irriducibile). Il polinomio caratteristico della LFSR mostrato nelle figure:

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 si ripetono. I più comunemente usati sono i polinomi assottigliati, cioè che hanno solo alcuni coefficienti. i trinomi più popolari.

Un parametro importante del generatore basato su LFSR è complessità lineare. Si definisce come la lunghezza n il più breve LFSR in grado di simulare l'uscita del generatore. La complessità lineare è importante perché con un semplice Algoritmo Berlenkamp-Masseyè possibile ricreare un tale LFSR selezionando solo 2 n bit gamma. Con la definizione dell'LFSR desiderato, il cifrario di flusso è effettivamente rotto.

Oltre a LFSR, vengono utilizzati anche registri a scorrimento con feedback non lineare, feedback di trasferimento, ecc.

Alcuni generatori sono stati sviluppati sulla base dell'approccio della teoria dei numeri (generatori Blum-Micali, RSA, BBS, compressione, generatori additivi, ecc.).

Il supporto matematico per la sintesi di algoritmi di crittografia a flusso è stato sviluppato in modo più completo e dettagliato rispetto agli algoritmi di crittografia a blocchi. Tuttavia, per creare cifrari a flusso, vengono spesso utilizzati algoritmi di cifratura a blocchi in modalità OFB o CFB.