Esempio di registro a scorrimento lineare. Registro a scorrimento con feedback lineare

Registro a scorrimento di feedback ( FSR ) è composto da due parti: registro a scorrimento E funzioni di feedback .

Un registro a scorrimento (Errore: origine riferimento non trovata) è una sequenza di bit. Quando è necessario recuperare un bit, 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 dai restanti bit del registro. Periodo Il registro a scorrimento è la lunghezza della sequenza risultante prima che inizi a ripetersi.

Il tipo più semplice di registro a scorrimento con feedback è registro a scorrimento lineare con feedback (LFSR – Sinistra Feedback Spostare Registrati) (Errore: fonte di riferimento non trovata). Il feedback è semplicemente XOR di alcuni p bit registro, viene chiamato l'elenco di questi bit sequenza di tocchi.

N-bit LFSR può trovarsi in uno di 2 N -1 stati interni. Ciò significa che, teoricamente, un registro di questo tipo 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 causerà la produzione di una sequenza infinita di zeri, il che è assolutamente inutile. Solo con determinate sequenze di tocco, l'LFSR le scorrerà tutte 2 N -1 stati interni. Questi LFSR sono chiamati LFSRcon periodo massimo.

Affinché un particolare LFSR abbia un periodo massimo, è necessario un polinomio formato dalla sequenza di prese e dalla costante 1 deve essere modulo primitivo 2 .

Calcolare la primitività di un polinomio è un problema matematico piuttosto complesso. Esistono quindi tabelle già pronte che mostrano il numero di sequenze di rubinetti 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 il trentaduesimo, il settimo, il quinto, il terzo, il secondo e il primo bit utilizzando la funzione XOR.

Il codice per un tale LFSR in C++ sarebbe così:

// Qualsiasi valore diverso da zero

RegistroShift = ((((RegistroShift >> 31)

^ (Registro di spostamento >> 6)

^ (Registro di spostamento >> 4)

^ (Registro di spostamento >> 2)

^ (Registro di spostamento >> 1)

^ Registro di spostamento)

&0x00000001)<<31)

| (Registro di spostamento >> 1);

return ShiftRegister & 0x00000001;

Le implementazioni software di LFSR sono piuttosto lente e funzionano più velocemente se sono scritte in linguaggio assembly anziché in C. Una soluzione è utilizzare 16 LFSR in parallelo (o 32 a seconda della lunghezza delle parole nell'architettura specifica del computer). Questo schema utilizza un array di parole la cui dimensione è uguale alla lunghezza dell'LFSR e ciascuna unità di una parola nell'array si riferisce al proprio LFSR. A condizione che vengano utilizzati gli stessi numeri di sequenza di tocco, ciò può fornire un notevole miglioramento delle prestazioni.

CON Anche il circuito di feedback può essere modificato. In questo caso il generatore non avrà una maggiore forza crittografica, ma sarà più semplice da implementare nel software. Invece di utilizzare il bit più a sinistra della sequenza di tap per generare il nuovo bit più a sinistra, esegue uno XOR su ciascun bit della sequenza di tap con l'output del generatore e lo sostituisce con il risultato di questa azione, quindi il risultato del generatore diventa il nuovo bit più a sinistra (errore: origine del riferimento non trovata).

Questa modifica si chiama Configurazione di Galois. In C appare così:

statico senza segno lungo ShiftRegister = 1;

void seed_LFSR (seme lungo senza segno)

ShiftRegister = seme;

int Galua_LFSR (vuoto)

se (RegistroShift & 0x00000001) (

ShiftRegister = (ShiftRegister ^ maschera >> 1) | 0x8000000;

RegistroSpostamenti >>= 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, il che li rende inutili per la crittografia. Per la lunghezza LFSR N lo stato interno rappresenta il precedente N bit di uscita del generatore. Anche se il modello di feedback è tenuto segreto, può essere determinato da 2 N bit di uscita del generatore utilizzando algoritmi speciali. Inoltre, grandi numeri casuali generati utilizzando bit consecutivi 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. A questo scopo vengono utilizzati più LFSR, solitamente con lunghezze e numeri di sequenza di prese diversi. La chiave è lo stato iniziale dei registri. Ogni volta che è necessario un nuovo bit, tutti i registri vengono spostati. Questa operazione si chiama timbratura. Il bit di uscita è una funzione, preferibilmente non lineare, di alcuni bit LFSR. Questa funzione si chiama combinando, e il generatore nel suo complesso – generatore combinato. Molti di questi generatori sono ancora sicuri.

decrittazione - p i = D (k i, c i), come mostrato in Fig. 7.21.

Riso. 7.21.

I cifrari a flusso sono più veloci dei cifrari a blocchi. Anche l'implementazione hardware di un cifrario a flusso è più semplice. Quando dobbiamo crittografare flussi binari e trasmetterli a velocità costante, la scelta migliore è utilizzare un cifrario a flusso. I codici a flusso hanno una maggiore protezione contro la corruzione dei bit durante la trasmissione.

In un moderno cifrario a flusso, ciascuno R La parola a bit nel flusso di testo normale viene crittografata utilizzando R -bit nel flusso di chiavi per creare il corrispondente R parola a -bit nel flusso del testo cifrato.

Riso. 7.22.

Un one-time pad è la cifra perfetta. Lui è perfetto. Non esiste alcun metodo che consenta a un avversario di riconoscere la chiave o le statistiche del testo cifrato e del testo in chiaro. Non esiste alcuna relazione tra l'originale e il testo cifrato. In altre parole, il testo cifrato è un vero e proprio flusso casuale di bit, anche se si ottengono alcuni campioni del testo originale. Eva non può decifrare il codice a meno che non provi tutti i possibili flussi di chiavi casuali, che sarebbero 2n se la dimensione del testo in chiaro fosse n bit. Tuttavia, c’è un problema con questo. Affinché il trasmettitore e il ricevitore possano condividere un unico blocco di chiavi, devono stabilire una connessione ogni volta che desiderano scambiare informazioni. Devono in qualche modo concordare una chiave casuale. Quindi questo codice perfetto e ideale è molto difficile da implementare.

Esempio 7.17

Qual è l'aspetto del testo cifrato quando si utilizza la cifratura one-time pad in ciascuno dei seguenti casi?

UN. Il testo sorgente è composto da n zeri.

B. Il testo sorgente è composto da n unità.

V. Il testo di partenza è costituito da zero e uno alternati.

d. Il testo di origine è una stringa casuale di bit.

Soluzione

UN. Perché il , il flusso del testo cifrato corrisponderà al flusso della chiave. Se la chiave è casuale, anche il testo cifrato è casuale. Parti del testo originale non vengono memorizzate nel testo cifrato.

B. Perché il , dove è il complemento del flusso di testo cifrato è il complemento del flusso di chiave. Se il flusso di chiavi è casuale, anche il testo cifrato è casuale; parti del testo originale non vengono memorizzate nel testo cifrato.

C. In questo caso, ogni bit nel flusso del testo cifrato è lo stesso del flusso della chiave o il suo complemento. Pertanto anche il risultato è casuale se il flusso di chiavi è casuale.

D. In questo caso, il testo cifrato è chiaramente casuale perché l'esecuzione di un'operazione XOR su due bit casuali dà come risultato un flusso casuale di bit.

Registro a scorrimento di feedback

Un miglioramento del one-time pad è (FSR - Feedback Shift Register). FSR può essere implementato sia via software che hardware, ma per semplicità considereremo l'implementazione hardware. Registro a scorrimento di feedback comprende registro a scorrimento e funzioni di feedback, come mostrato in Fig. 7.23.

Riso. 7.23.

Un registro a scorrimento è una sequenza di m celle da b 0 a b m-1, dove ciascuna cella è progettata per memorizzare un singolo bit. Le celle vengono trattate come una parola di n bit, chiamata all'inizio "valore seme" o fonte. Ogni volta che è necessario emettere un bit (ad esempio, da un segnale in un determinato momento), ciascun bit viene spostato di una cella a destra. Ciò significa che il valore di ciascuna cella viene assegnato alla cella adiacente a destra e assume il valore della cella di sinistra. La cella più a destra b 0 è considerata l'output e fornisce il valore di output (k i ). La cella più a sinistra, b m-1, ottiene il suo valore in base al valore delle informazioni sulla funzione di feedback. Indichiamo l'output della funzione con le informazioni di feedback b m . La funzione di informazione di feedback determina quali valori devono avere le celle per calcolare b m . Il registro a scorrimento delle informazioni di feedback può essere lineare o non lineare.

Registro a scorrimento con feedback lineare (LFSR). Supponiamo che b m sia una funzione lineare b 0, b 1,…..., b m-1, per la quale

Un registro a scorrimento con feedback lineare opera su cifre binarie, quindi la moltiplicazione e l'addizione sono nel campo GF(2), quindi il valore di Ci è 1 o 0, ma C 0 deve essere 1 per ottenere informazioni di feedback in uscita. L'operazione di addizione è un'operazione OR ESCLUSIVO. In altre parole,

Esempio 7.18

Costruiamo un registro a scorrimento con feedback lineare con 5 celle, in cui .

Soluzione

Se C i = 0, b i non gioca un ruolo nel calcolo di b m, ciò significa che b i non è associato alla funzione di informazione di feedback. Se c i = 1, b i è incluso nel calcolo di b m. In questo esempio c 1 e c 3 sono zero, il che significa che abbiamo solo tre connessioni. La Figura 7.24 mostra il circuito di un registro a scorrimento con retroazione lineare.

Riso. 7.24.

Esempio 7.19

Costruiamo un registro a scorrimento con feedback lineare con 4 celle, in cui . Mostra il valore del registro dopo 20 operazioni (turni), se il valore originale è (0001) 2 .

Soluzione

La Figura 7.25 mostra la progettazione e l'uso di un registro a scorrimento lineare a circuito chiuso per la crittografia.

Riso. 7.25.

Tabella 7.6. mostra il valore del flusso di chiavi. Per ogni transizione, viene calcolato il primo valore di b 4, quindi ciascun bit viene spostato di una cella a destra.

Tabella 7.6.

valore attuale	b4	b3	b2	b1	b0	k io
Valore iniziale	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

Tieni presente che il flusso chiave è 1000100110101111 1001……. A prima vista sembra una sequenza casuale, ma se osserviamo un gran numero di transazioni (turni), possiamo vedere che le sequenze sono periodiche. Questa ripetizione di 15 bit è mostrata di seguito.

La chiave del flusso viene generata utilizzando un registro a scorrimento con feedback lineare sequenza pseudocasuale, in cui si ripetono sequenze di lunghezza N. Il flusso è periodico. Dipende dal circuito del generatore e dalle informazioni iniziali e non può essere superiore a 2 m – 1. Ogni circuito genera sequenze di m-bit che vanno da quelle contenenti tutti zeri a quelle contenenti tutti uno. Tuttavia, se la sequenza iniziale è composta da tutti zeri, il risultato è inutile: il testo originale sarebbe un flusso di tutti zeri. Pertanto tale sequenza iniziale è esclusa.

Le sequenze di registri a scorrimento vengono utilizzate sia nella crittografia che nella teoria dei codici. La loro teoria è ben sviluppata; i cifrari a flusso basati sui registri a scorrimento erano il cavallo di battaglia della crittografia militare molto prima dell’avvento dell’elettronica.

Un registro a scorrimento a circuito chiuso (di seguito denominato RGSSOC) è costituito da due parti: un registro a scorrimento e una funzione di feedback. Un registro a scorrimento è una sequenza di bit. Il numero di bit è determinato lunghezza del registro a scorrimento, se la lunghezza è n bit, viene chiamato il registro registro a scorrimento di n bit. Ogni volta che è necessario recuperare un bit, tutti i bit nel registro a scorrimento vengono spostati 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 meno significativo. Periodo del registro a scorrimentoè la lunghezza della sequenza risultante prima che inizi la sua ripetizione.

Figura 1. Registro a scorrimento di feedback

I registri a scorrimento trovarono rapidamente impiego nei cifrari a flusso perché erano facilmente implementabili utilizzando hardware digitale. Nel 1965 Ernst Selmer, capo crittografo del governo norvegese, sviluppò la teoria della sequenza del registro a scorrimento. Solomon Golomb, un matematico della NSA, ha scritto un libro in cui presenta alcuni dei suoi risultati e di Selmer. Il tipo più semplice di registro a scorrimento con feedback è un registro a scorrimento con feedback lineare (LFSR). Il feedback di tali registri è semplicemente uno XOR (addizione modulo due) di alcuni bit di registro, un elenco di questi bit chiamato sequenza di tap. A volte tale registro è chiamato configurazione di Fibbonacci. A causa della semplicità della sequenza di feedback, è possibile utilizzare una teoria matematica abbastanza avanzata per analizzare PrCsVOC. Analizzando le sequenze di output risultanti, è possibile verificare che le sequenze siano sufficientemente casuali da essere sicure. RGCCLOS viene utilizzato più spesso di altri registri a scorrimento in crittografia.

Figura 2. PrCsLOS Fibbonacci

In generale, un PrCsLOS a n bit può trovarsi in uno degli N=2 n -1 stati interni. Ciò significa che teoricamente un registro di questo tipo può generare una sequenza pseudo-casuale con un periodo di T=2 n -1 bit. (Il numero di stati interni e il periodo sono pari a N=T max =2 n -1, perché riempire PrCsLOS con zeri farà sì che il registro a scorrimento produca una sequenza infinita di zeri, il che è assolutamente inutile). Solo per alcune sequenze di rami PrCsLOS passerà ciclicamente attraverso tutti i 2 n -1 stati interni, tali PrCsLOS sono RgSsLOS con periodo massimo. Il risultato risultante viene chiamato Sequenza M.

Esempio . La figura seguente mostra un RgCCLOS a 4 bit con prese dal primo e dal quarto bit. Se viene inizializzato con il valore 1111, prima di ripetere il registro assumerà i seguenti stati interni:

Numero dell'orologio di spostamento (stato interno)	Stato del registro	Bit di uscita
Valore iniziale
15 (ritorno allo stato iniziale)
16 (ripeti stati)

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 con un periodo T=15, il numero totale di possibili stati interni (eccetto zero), N=2 4 -1=16-1= 15=T max , pertanto, la sequenza di output è una sequenza M.

Affinché un particolare PrCsLOS abbia un periodo massimo, il polinomio formato dalla sequenza di prese e dalla costante 1 deve essere primitivo modulo 2. Il polinomio è rappresentato come una somma di potenze, ad esempio, un polinomio di grado n è rappresentato come segue :

UN N xn+a n-1 xn-1+…+a 1 x1+a 0 x0 =a N xn+a n-1 xn-1+…+a 1 x+a 0 , dove un io =(0,1) per i=1…n, a x i - indica la cifra.

Il grado del polinomio è la lunghezza del registro a scorrimento. Un polinomio primitivo di grado n è un polinomio irriducibile che è divisore di x 2n?1 +1, ma non è divisore di x d +1 per tutti i d che sono divisori di 2 n -1. La teoria matematica corrispondente può essere trovata in.

In generale, non esiste un modo semplice per generare polinomi primitivi di un dato grado modulo 2. Il modo più semplice è selezionare un polinomio a caso e verificare se è primitivo. Questo non è facile ed è un po' come verificare se un numero casuale è primo, ma molti pacchetti software di matematica possono risolvere questo problema.

Di seguito sono riportati alcuni, ma certamente non tutti, polinomi di vario grado che sono primitivi modulo 2. Ad esempio, registra

(32, 7, 5, 3, 2, 1, 0) significa che il seguente polinomio è primitivo modulo 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.

Questo può essere facilmente generalizzato a PrCsVOC con un periodo massimo. Il primo numero è la lunghezza di PrCsLOS. L'ultimo numero è sempre 0 e può essere omesso. Tutti i numeri tranne lo 0 specificano una sequenza di tap, contata dal bordo sinistro del registro a scorrimento. Cioè, i termini di un polinomio con gradi inferiori corrispondono a posizioni più vicine al bordo destro del registro.

Continuando con 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 eseguendo XORing sul trentaduesimo, settimo, quinto, terzo, secondo e primo bit, il PrCsLOS risultante avrà una lunghezza massima, scorrendo 2 valori 32 -1 prima di ripetersi.

Figura 4. PrCCLOS a 32 bit con lunghezza massima

Consideriamo il codice di programma PrCsLOS, in cui la sequenza di tap è caratterizzata da un polinomio (32, 7, 5, 3, 2, 1, 0). In C appare così:

statico senza segno lungo ShiftRegister = 1;

/* Tutto tranne 0. */

RegistroShift = ((((RegistroShift >> 31)

^(RegistroShift >> 6)

^(RegistroShift >> 4)

^(Registro di spostamento >> 2)

^(Registro di spostamento >> 1)

^RegistroShift))

| (Registro di spostamento >> 1);

ritorna ShiftRegister & 0x00000001;)

Se il registro a scorrimento è più lungo di una parola del computer, il codice diventa più complicato, ma non di molto. L'Appendice B contiene una tabella di alcuni polinomi primitivi modulo 2 che utilizzeremo in futuro per identificare alcune proprietà di questi polinomi, nonché nell'implementazione software per specificare la sequenza dei tap;

Si prega di notare che tutti gli elementi della tabella hanno un numero dispari di coefficienti. Questa lunga tabella viene fornita per ulteriore lavoro con RgCsLOC, poiché RgCsLOC è spesso utilizzato per la crittografia con cifrari a flusso e nei generatori di numeri pseudocasuali. Nel nostro caso possiamo utilizzare polinomi con grado massimo non superiore a sette.

Se p(x) è primitivo, allora x n p(1/x) è primitivo, quindi ogni elemento della tabella definisce in realtà due polinomi primitivi. Ad esempio, se (a, b, 0) è primitivo, anche (a, a-b, 0) lo è. Se (a, b, c, d, 0) è primitivo, allora anche (a, a-d, a-c, a-b, 0) è primitivo. Matematicamente:

se x a +x b +1 è primitivo, allora x a +x a-b +1 è primitivo,

se x a +x b +x c +x d +1 è primitivo, allora x a +x a-d +x a-c +x a-b +1 è primitivo. I trinomi primitivi sono i più veloci da implementare nel software, poiché per generare un nuovo bit è necessario XOR solo due bit del registro a scorrimento (il termine zero non viene preso in considerazione, cioè x 0 = 1, vedere l'esempio sopra). In effetti, tutti i polinomi di feedback riportati nella tabella sono sparsi, cioè hanno pochi coefficienti. La scarsità è sempre fonte di debolezza, che a volte è sufficiente per rompere l’algoritmo. Per gli algoritmi crittografici è molto meglio utilizzare polinomi primitivi densi, quelli con molti coefficienti. Utilizzando polinomi densi, soprattutto come parte di una chiave, è possibile utilizzare PrCsLOS molto più breve.

Generare polinomi primitivi densi modulo 2 non è facile. In generale, per generare polinomi primitivi di grado k, è necessario conoscere la fattorizzazione del numero 2 k -1.

Di per sé, i PrCsLOS sono buoni generatori di sequenze pseudo-casuali, ma hanno alcune proprietà non casuali (deterministiche) indesiderabili. I bit consecutivi sono lineari, il che li rende inutili per la crittografia. Per un PrCcLOS di lunghezza n, lo stato interno sono i precedenti n bit di uscita del generatore. Anche se il circuito di retroazione è tenuto segreto, può essere determinato dai 2n bit di uscita dell'oscillatore utilizzando l'algoritmo altamente efficiente di Berlekamp-Massey.

Inoltre, grandi numeri casuali generati utilizzando bit consecutivi di questa sequenza sono altamente correlati e, per alcuni tipi di applicazioni, non sono affatto casuali. Nonostante ciò, gli RgCCLOS vengono spesso utilizzati per creare algoritmi di crittografia come componenti di sistemi e algoritmi di crittografia.

Le sequenze di registri a scorrimento vengono utilizzate sia nella crittografia che nella teoria dei codici. La loro teoria è ben sviluppata; i cifrari a flusso basati sui registri a scorrimento erano il cavallo di battaglia della crittografia militare molto prima dell’avvento dell’elettronica.

Un registro a scorrimento con feedback è composto da due parti: un registro a scorrimento e una funzione di feedback (Figura 1.2.1). Un 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 recuperare un bit, tutti i bit del registro a scorrimento vengono spostati 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 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 sui registri a scorrimento: erano facili da implementare utilizzando l'hardware digitale. Toccherò solo brevemente la teoria matematica. Nel 1965 Ernst Selmer, capo crittografo del governo norvegese, sviluppò la teoria della sequenza del registro a scorrimento. Solomon Golomb, un matematico della NSA, ha scritto un libro in cui presenta alcuni dei suoi risultati e di Selmer.

Il tipo più semplice di registro a scorrimento con feedback è il registro a scorrimento con feedback lineare, o LFSR (Figura 1.2.2). Il feedback è semplicemente uno XOR di alcuni bit di registro, un elenco di questi bit chiamato sequenza di tap. A volte tale registro è chiamato configurazione di Fibbonacci. A causa della semplicità della sequenza di feedback, è possibile utilizzare una teoria matematica abbastanza avanzata per analizzare LFSR. I crittografi amano analizzare le sequenze, convincendosi che le sequenze siano abbastanza casuali da essere sicure. Gli LFSR sono i registri a scorrimento più comunemente utilizzati in crittografia.

Riso. 1.2.2.

Nella fig. La Figura 1.2.3 mostra un LFSR a 4 bit con prese dal primo e dal 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, teoricamente, un registro di questo tipo può generare una sequenza pseudo-casuale con un periodo di 2n-1 bit. (Il numero di stati interni e periodo sono 2n-1 perché riempire l'LFSR con zeri farà sì che il registro a scorrimento produca una stringa infinita di zeri, il che è assolutamente inutile.) Solo per alcune sequenze di tap l'LFSR eseguirà il ciclo attraverso tutti i 2n- 1 stati interni, 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 prese e dalla 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 è selezionare un polinomio a caso e verificare se è primitivo. Questo non è facile - ed è un po' come verificare se un numero casuale è primo - ma molti pacchetti software di matematica possono risolvere questo problema.

Alcuni, ma certamente non tutti, polinomi di vario grado sono primitivi modulo 2. Ad esempio, scrivere (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 al periodo massimo LFSR. Il primo numero è la lunghezza dell'LFSR. L'ultimo numero è sempre 0 e può essere omesso. Tutti i numeri tranne lo 0 specificano una sequenza di tap, contata dal bordo sinistro del registro a scorrimento. Cioè, i termini di un polinomio con gradi inferiori corrispondono a posizioni più vicine al bordo destro del registro.

Continuando con 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 eseguendo XORing sul trentaduesimo, settimo, quinto, terzo, secondo e primo bit, l'LFSR risultante avrà una lunghezza massima, scorrendo i valori 232-1 prima di ripetersi.

Gommatura. Cifratura gamma. Metodi per generare una cifra gamma. Registro a scorrimento lineare.

Capitolo 3. Procedura per la registrazione dei singoli atti di stato civile

Registrazione statale dell'emissione (emissione aggiuntiva) di titoli.

Il registro a scorrimento con feedback lineare (LFSR) è un meccanismo per creare una sequenza pseudo-casuale di bit binari. Il registro (Fig. 1) è costituito da un numero di celle stabilite da un vettore di inizializzazione (molto spesso una chiave segreta). Il funzionamento del registro è determinato dalla presenza o assenza di comunicazione da ciascun bit al feedback. Le prese del registro di feedback non sono fisse, ma fanno parte della chiave. Nella fase successiva, il contenuto delle celle del registro viene spostato di una posizione a destra e un bit rimasto libero come risultato dell'operazione XOR viene posizionato nella cella più a sinistra.

Riso. 1. Registro a scorrimento con feedback lineare

Per ottenere il periodo gamma di cifratura massimo, il numero di bit M si sceglie che il registro a scorrimento sia uguale a uno dei numeri primi di Mersenne (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203...), e il le connessioni interne del registro devono essere scelte secondo i polinomi primitivi irriducibili di grado massimo M. In questo caso, il periodo gamma del cifrario può raggiungere (2 M-1).

LFSR è veloce e facile da implementare sia nel software che nell'hardware. Con la scelta adeguata dei bit di feedback, le sequenze generate hanno buone proprietà statistiche. LFSR viene utilizzato come elemento base per la creazione di sistemi altamente sicuri.

Una cascata di registri è 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" è tipicamente progettato per controllare il contatore di spostamento del successivo LFSR tramite il primo LFSR.

Ad esempio, un 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 qualche altro modo. Un gran numero di tali combinazioni consente una sicurezza molto elevata.

Le sequenze più sicure sono prodotte da un generatore di Shrinking 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 stream" completa. Il generatore di compressione è semplice, scalabile e ha buone proprietà protettive. Lo svantaggio è che la velocità di generazione della "chiave del flusso" non sarà costante a meno che non vengano prese alcune precauzioni.

Metodo Fibonacci con ritardi Uno dei generatori di Fibonacci ampiamente utilizzati si basa sulla seguente formula iterativa:

Dove Sì, ok- Numeri reali dall'intervallo

Riso. 2. Crittografia round-robin

La modalità di feedback dell'output DES può essere utilizzata per generare numeri pseudocasuali, in modo simile a come viene utilizzata per la crittografia del flusso. L'output di ogni fase di crittografia è un valore a 64 bit, di cui solo i j bit più significativi vengono restituiti per la crittografia. Gli output a 64 bit sono una sequenza di numeri pseudo-casuali con buone proprietà statistiche.

Il generatore di numeri pseudocasuali, descritto nello standard ANSI X9.17, è uno dei generatori di numeri pseudocasuali più cripto-sicuri. Le applicazioni che utilizzano questa tecnologia includono sicurezza finanziaria e applicazioni PGP.

Il generatore ANSI X9.17 è composto dalle seguenti parti (Fig. 3):

1. Ingresso: il generatore è controllato da due ingressi pseudo-casuali. Il primo input è una rappresentazione a 64 bit della data e dell'ora correnti ( DT i), che cambiano ogni volta che viene creato un numero. Il secondo input è un seme a 64 bit, che viene inizializzato su un valore arbitrario e modificato durante la generazione di una sequenza di numeri pseudocasuali ( V i).

2. Tasti: Il generatore utilizza tre moduli DES tripli con due tasti K1, K2. Tutti e tre utilizzano la stessa coppia di chiavi a 56 bit, che deve essere mantenuta segreta e utilizzata solo per generare un numero pseudo-casuale.

EDE

EDE

EDE

+

+

K1, K2

DT i

V i

R i

V i+1

3. Output: l'output è costituito da un numero pseudocasuale a 64 bit R i e da un valore a 64 bit che verrà utilizzato come seme durante la creazione del numero successivo ( V io +1) .

Riso. 3. Generatore di numeri pseudocasuali ANSI X9.17