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

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. In teoria, 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.

Ministero dell'Istruzione e della Scienza

UNIVERSITÀ SOCIALE DELLO STATO RUSSO

FACOLTA' DI TECNOLOGIE DELL'INFORMAZIONE

DIPARTIMENTO PER LA PROTEZIONE DELL'INFORMAZIONE

Metodi crittografici e mezzi per garantire la sicurezza delle informazioni

Corso di lavoro

"R registri a scorrimento con feedback lineare come generatori di numeri pseudo-casuali"

Completato:

Studente 3° anno

Gruppo KZOI-D-3

Larionov I.P.

Controllato:

Assoc. Baranova E.K.

Mosca 2011
CONTENUTO

introduzione ……………………………..…………………………………….3

Fondamenti teorici del lavoro…………………………………………4
1. Informazioni generali sui registri a turni di feedback…………..4
  1. Informazioni sui cifrari a flusso basati su RgCsLOS………………….………10
  2. Sulla complessità lineare della sequenza pseudo-casuale generata PgCsLOS……………………………………….……12
  3. Sull'indipendenza di correlazione della sequenza generata di numeri pseudocasuali PrCsLOS………..….13
  4. Su altri metodi di apertura della sequenza generata di numeri pseudocasuali RgCsLOS………………………………………..14
Implementazione software di RgCsLOS come generatore di sequenze pseudo-casuali….…………………………….15
1. Schema generalizzato dell'algoritmo…………………………………………...15
2. Descrizione dei moduli software e dell'interfaccia.………………….16
3. Manuale d'uso…………………………………………...20

Conclusione ………………………………………………………………22

Bibliografia………………………………………………….....23

Annesso A ….………………………………………………………..24

INTRODUZIONE

Lo scopo di questo lavoro è sviluppare un'applicazione software che implementi il funzionamento di un generatore di numeri pseudo-casuali basato su registri a scorrimento con feedback. Lo sviluppo di questa applicazione con interfaccia grafica avviene nella lingua C++ per sistema operativo Windows.

Con lo sviluppo della crittografia nel 20° secolo, i crittografi hanno dovuto affrontare il compito di creare dispositivi e macchine di crittografia in grado di crittografare e decrittografare i messaggi in modo rapido e affidabile. I sistemi di crittografia simmetrica già aperti in quel momento soddisfacevano questo requisito, ma il loro punto debole era una forte dipendenza dalla chiave e dalla sua segretezza. La classe di cifratura più conveniente che potrebbe essere utilizzata per questo scopo sono le cifrature di gioco. Sorgeva il problema di generare una gamma che non poteva essere rilevata quando il messaggio veniva decifrato. In teoria, ciò sarebbe stato possibile se ogni volta la gamma fosse casuale e cambiasse nel tempo. Tuttavia, quando si utilizza una gamma che cambia completamente in modo casuale, sarebbe difficile fornire una crittografia-decrittografia affidabile del messaggio. I crittografi si sono assunti il compito di risolvere questo problema, il cui scopo era trovare un algoritmo che implementasse la generazione di un intervallo casuale secondo una certa regola, tale sequenza dovrebbe contenere zeri e uno in posizioni "presumibilmente" casuali, e il il numero di uno e zero dovrebbe essere approssimativamente lo stesso. Questa sequenza casuale viene chiamatapseudo-casualepoiché è stato generato secondo una certa regola, e non casualmente.

La soluzione è stata presto trovata. Lo studio delle proprietà dei registri a scorrimento ha permesso di stabilire che i registri a scorrimento a feedback sono in grado di generare sequenze pseudocasuali sufficientemente resistenti alla decodifica per la loro struttura interna.

1. Fondamenti teorici del lavoro

1.1 Informazioni generali sui registri a scorrimento con feedback lineare

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.

Il registro a scorrimento del feedback (di seguito denominato PgCsOS) è costituito da due parti: un registro a scorrimento e una funzione di feedback.Il registro a scorrimento è una sequenza di bit. Il numero di bit è determinatolunghezza del registro a scorrimento, se la lunghezza è n bit, viene chiamato il registroregistro a scorrimento di n bit. Ogni volta che è necessario estrarre 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 il meno significativo.Periodo del registro a scorrimentoè la lunghezza della sequenza risultante prima che inizi a ripetersi.

Registro di spostamento del feedback di figura

I registri a scorrimento hanno trovato rapidamente uso nei cifrari a flusso, poiché sono stati facilmente implementati utilizzando l'hardware digitale. Nel 1965, Ernst Selmer, il capo crittografo del governo norvegese, sviluppò la teoria della sequenza del registro a scorrimento. Solomon Golomb, un matematico della NSA, ha scritto un libro che illustra alcuni dei suoi risultati e quelli di Selmer. Il tipo più semplice di registro a scorrimento di feedback èregistro a scorrimento a retroazione lineare ( registro a scorrimento a retroazione lineare, di seguito LFSR o RgCsLOS) . Il feedback di tali registri è semplicemente un XOR (addizione del modulo due) di alcuni bit del registro, un elenco di questi bit è chiamato sequenza di tap. A volte un tale registro è chiamato configurazione di Fibonacci. A causa della semplicità della sequenza di feedback, una teoria matematica piuttosto sviluppata può essere utilizzata per analizzare PgCsLOC. Analizzando le sequenze di output risultanti, è possibile verificare che queste sequenze siano abbastanza casuali da essere sicure. I registri a scorrimento sono usati più spesso di altri registri a scorrimento in crittografia.

Figura PgCsLOS Fibbonacci

In generale, n -bit PrCsLOS può essere in uno di N=2n -1 stati interni. Ciò significa che, in teoria, un tale registro può generare una sequenza pseudo-casuale con periodo T=2 n -1 bit. (Il numero di stati interni e il periodo sono uguali N=Tmax=2n -1 perché il riempimento di PrCsLOC con zeri farà sì che il registro a scorrimento emetta una sequenza infinita di zeri, il che è assolutamente inutile). Solo con determinate sequenze di tap PrCsLOS passerà ciclicamente tutte e 2 n -1 stati interni, tali sono RgCsLOSRgSsLOS con un periodo massimo. Il risultato risultante viene chiamatoSequenza M.

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

Numero di spunta del turno (stato interno)	Stato del registro	bit di uscita
Numero di spunta del turno (stato interno)		bit di uscita
Valore iniziale














15 (ritorno allo stato iniziale)
16 (stati ripetuti)

La sequenza di uscita sarà una stringa di bit meno significativi: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 con periodo T=15, il numero totale di possibili stati interni (tranne zero), N=2 4 -1=16-1=15= Tmax , pertanto, la sequenza di output è m -sequenza.

Affinché un particolare PgCsLOS abbia un periodo massimo, il polinomio formato dalla sequenza di colpi e la costante 1 deve essere primitivo modulo 2. Il polinomio è rappresentato come una somma di potenze, ad esempio un polinomio di grado n appare così:

anxn +a n-1 x n-1 +…+a 1 x 1 +a 0 x 0 =anxn +a n-1 x n-1 +…+a 1 x+a 0 , dove a i =(0, 1 ) per i=1…n, axi – indica il bit .

Il grado del polinomio è la lunghezza del registro a scorrimento. Un polinomio primitivo di grado n è un polinomio irriducibile divisore di x 2n-1 +1 ma non è un divisore di x D +1 per tutti d essendo divisori di 2 n -uno. La corrispondente teoria matematica 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 è scegliere un polinomio a caso e verificare se è primitivo. Questo non è facile ed è un po' come controllare se un numero scelto a caso non è primo, ma molti pacchetti software matematici possono risolvere questo problema.

Di seguito sono riportati alcuni, ma certamente non tutti, polinomi di vari gradi, primitiva modulo 2. Ad esempio, la voce

(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 PrCcLOC con un periodo massimo. Il primo numero è la lunghezza di PrCsLOS. 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 , il risultante RgCsLOS avrà una lunghezza massima, ciclicamente fino a ripetersi dopo 2 32 -1 valori.

Figura 4 PrCsLOS a 32 bit con lunghezza massima

Si consideri il codice di programma PgCsLOS, in cui la sequenza di tap è caratterizzata dal polinomio (32, 7, 5, 3, 2, 1, 0). In linguaggio C si presenta così:

int LFSR()(

statico senza segno lungo ShiftRegister = 1;

/* Tutti tranne 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(Registra Maiuscole >> 6)

^(Registra Maiuscole >> 4)

^(ShiftRegistra >> 2)

^(Registra Maiuscole >> 1)

^Registra turno))

& 0x00000001)

<<31)

| (Registro turno >> 1) ;

restituisce ShiftRegister & 0 x 00000001;)

Se il registro a scorrimento è più lungo di una parola del computer, il codice diventa più complicato, ma non di molto. Nell'applicazione B viene fornita una tabella di alcuni polinomi primitivi modulo 2, la useremo in seguito per identificare alcune proprietà di questi polinomi, nonché nell'implementazione software per impostare una sequenza di tap.

Va notato che tutti gli elementi della tabella hanno un numero dispari di coefficienti. Una tabella così lunga viene fornita per ulteriori lavori con PrCfLOC, poiché PrCfLOC viene spesso utilizzato per la crittografia con cifrari a flusso e in generatori di numeri pseudo-casuali. Nel nostro caso, possiamo usare polinomi con il grado più alto non superiore a sette.

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

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

se x è primitivo a + x b + x c + x d +1, allora è primitivo e x a + x a-d + x a-c + x a-b +1. I trinomi primitivi sono i più veloci da implementare a livello di programmazione, poiché per generare un nuovo bit è necessario XOR solo due bit dello shift register (il termine zero non viene preso in considerazione, cioè x 0 =1, vedi esempio sopra). In effetti, tutti i polinomi di feedback riportati nella tabella sono sparsi, cioè hanno pochi coefficienti. La scarsità è sempre una fonte di debolezza, che a volte è sufficiente per aprire l'algoritmo. Per gli algoritmi crittografici, è molto meglio usare densi polinomi primitivi, quelli che hanno molti coefficienti. Usando polinomi densi, specialmente come parte della chiave, si può usare PrCcLOC molto più breve.

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

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

Inoltre, i 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ò, i PrCsLOS vengono spesso utilizzati per creare algoritmi di crittografia come componenti di sistemi e algoritmi di crittografia.

1.2 Informazioni sui cifrari a flusso basati su RgCsLOS

L'approccio di base alla progettazione di un generatore di keystream basato su PrCsLOS è semplice. Per prima cosa vengono presi uno o più PrCsLOS, di solito con diverse lunghezze e diversi polinomi di feedback. (Se le lunghezze sono coprimi e tutti i polinomi di feedback sono primitivi, il generatore risultante avrà una lunghezza massima.) La chiave è lo stato iniziale dei registri PrCcLOC. Ogni volta che è necessario un nuovo bit, spostare un po' i registri PrCsLOS (a volte chiamato clocking). Il bit di uscita è una funzione, preferibilmente non lineare, di alcuni bit dei registri PrCsLOC. Questa funzione è chiamata funzione di combinazione e il generatore nel suo insieme è chiamato generatore combinatorio. (Se il bit di uscita è una funzione di un singolo PgCsLOS, l'oscillatore è chiamato oscillatore del filtro.) Gran parte della teoria alla base di questo tipo di dispositivi è stata sviluppata da Selmer e Neal Zierler. Puoi introdurre una serie di complicazioni. In alcuni generatori, vengono utilizzate frequenze di clock diverse per PgCsLOS diversi, a volte la frequenza di un generatore dipende dall'uscita di un altro. Queste sono tutte versioni elettroniche delle idee di macchine di cifratura precedenti alla seconda guerra mondiale chiamate oscillatori controllati dall'orologio ( generatori controllati da orologio ). Il controllo del clock può essere feed-forward, in cui l'uscita di un PgSsLOS controlla la velocità di clock di un altro PgSsLOS, o ad anello chiuso, in cui l'uscita di un PgSsLOS controlla il proprio clock. Sebbene tutti questi generatori siano sensibili, almeno in teoria, agli attacchi di annidamento e alle probabili correlazioni, molti di essi sono ancora al sicuro.

Ian Cassells, ex presidente di matematica pura a Cambridge e crittoanalista a Bletchly Park, ha affermato che "la crittografia è un misto di matematica e confusione e, senza confusione, la matematica può essere usata contro di te". Intendeva dire che nei cifrari a flusso, alcune strutture matematiche, come PrCcLOC, sono necessarie per fornire la lunghezza massima e altre proprietà, ma devono essere introdotti alcuni complessi pasticci non lineari per impedire a qualcuno di ottenere il contenuto del registro e di crackare l'algoritmo. Questo consiglio vale anche per algoritmi a blocchi.

La maggior parte dei cifrari a flusso reale si basa su PrCsLOS. Anche agli albori dell'elettronica, erano facili da costruire. Un registro a scorrimento non è altro che un array di bit e una sequenza di feedback è un insieme di porte XOR. Anche quando si utilizza VLSI, un cifrario a flusso basato su PrCsLOS fornisce una notevole sicurezza con l'aiuto di diverse porte logiche. Il problema con PgCsLOS è che la loro implementazione del software è molto inefficiente. Devi evitare polinomi a feedback sparsi - rendono più facili gli attacchi di correlazione - e polinomi a feedback densi sono inefficienti.

Questo ramo della crittografia sta crescendo rapidamente ed è sotto il controllo vigile del governo NSA . La maggior parte degli sviluppi sono classificati: molti sistemi di crittografia militari in uso oggi sono basati su PrCsLOS. In effetti, la maggior parte dei computer Cray (Cray 1, Cray X-MP, Cray Y-MP) ha un'istruzione molto interessante comunemente chiamata "conta della popolazione". Conta il numero di 1 in un registro e può essere utilizzato sia per calcolare in modo efficiente la distanza di Hamming tra due parole binarie sia per implementare una versione vettorializzata di PrCcLOS. Questa istruzione è considerata l'istruzione canonica della NSA e appare in quasi tutti i contratti informatici.

D'altra parte, un numero sorprendentemente elevato di generatori di registri a scorrimento apparentemente complessi è stato violato. E, naturalmente, il numero di tali generatori violati da istituzioni crittoanalitiche militari come la NSA è ancora maggiore.

1.3 Sulla complessità lineare della sequenza generata di numeri pseudocasuali PrCsLOS

I cifrari a flusso sono spesso più facili da analizzare rispetto ai cifrari a blocchi. Ad esempio, un parametro importante utilizzato per analizzare i generatori basati su PgCsLOC è la complessità lineare, o intervallo lineare. È definito come la lunghezza n del PrCsLOS più corto in grado di simulare l'uscita del generatore. Qualsiasi sequenza generata da un automa finito su un campo finito ha una complessità lineare finita. La complessità lineare è importante perché con un semplice algoritmo chiamato algoritmo Berlekamp-Massey, è possibile determinare questo PrCcLOC esaminando solo 2n bit del flusso di chiavi. Ricreando il PrCsLOS desiderato, si interrompe il cifrario del flusso.

Questa idea può essere estesa dai campi agli anelli e ai casi in cui la sequenza di output è trattata come numeri in un campo di caratteristica dispari. Un'ulteriore espansione porta all'introduzione del concetto di profilo di complessità lineare, che determina la complessità lineare di una sequenza man mano che si allunga. Esistono anche concetti di complessità sferica e quadratica. In ogni caso va ricordato che un'elevata complessità lineare non garantisce necessariamente la sicurezza del generatore, ma una bassa complessità lineare indica una sicurezza del generatore insufficiente.

1.4 Sull'indipendenza di correlazione della sequenza generata di numeri pseudocasuali PrCsLOS

I crittografi cercano di ottenere un'elevata complessità lineare combinando i risultati di alcune sequenze di output in modo non lineare. Il pericolo qui è che una o più sequenze di output interne - spesso solo le uscite di singoli PrCsLOC - possono essere collegate da un flusso di chiavi comune e scoperte usando l'algebra lineare. Spesso una tale resa dei conti è chiamata resa dei conti di correlazione o resa dei conti del divide et impera. Thomas Siegenthaler ha mostrato 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 dell'apertura di correlazione è trovare una correlazione tra l'uscita del generatore e l'uscita di uno dei suoi componenti. Quindi, osservando la sequenza di emissione, si possono 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.

Gli attacchi di correlazione e le relative variazioni, come gli attacchi di correlazione rapida, sono stati utilizzati con successo contro molti generatori di keystream basati su PgCsLOC, offrendo un compromesso tra complessità ed efficienza computazionale.

1.5 Su altri metodi per aprire la sequenza generata di numeri pseudocasuali PgCsLOS

Esistono altri modi per interrompere i generatori di keystream. Il test di coerenza lineare cerca di trovare alcuni sottoinsiemi della chiave di crittografia utilizzando la tecnica della matrice. C'è anche un attacco di coerenza meet-in-the-middle sulla correttezza. L'algoritmo della sindrome lineare si basa sulla capacità di scrivere un frammento della sequenza di output come un'equazione lineare. C'è un attacco di migliore approssimazione affine e un attacco di sequenza derivato. I metodi di crittoanalisi differenziale e lineare possono essere applicati anche ai cifrari a flusso.

2. Descrizione dell'implementazione software di PrCsLOS come generatore di sequenze pseudo-casuali

2.1 Schema generalizzato dell'algoritmo

2.2 Descrizione dei moduli software e dell'interfaccia

La figura 3 sotto mostra la finestra del programma.

Figura Interfaccia del programma

Il menu ha le seguenti funzioni:

File->Salva rapporto

Questa funzione genera un file di report, dove vengono scritti lo stato iniziale di PrCsLOS, la sequenza di tap, il periodo della sequenza di bit pseudocasuale ricevuta, la sequenza stessa e la tabella di stato. Se il file è stato salvato correttamente, viene visualizzato un messaggio di salvataggio riuscito (Figura 4). L'estensione di file consigliata per il rapporto è *. TXT.

Disegno

File->Esci

Questa funzione garantisce che l'applicazione sia chiusa.

Imposta la sequenza di escape

Questa funzione genera una sequenza di tocchi leggendo i valori dalle celle che l'utente ha spuntato nella maschera. Successivamente, notifica all'utente la creazione di una sequenza di tocchi (Figura 5). La sequenza di tocco determina quali flip-flop del registro a scorrimento riceveranno il feedback. XOR per formare un bit di offset. Di default il feedback del primo trigger è sempre attivo, in assenza di altri collegamenti verrà effettuato uno spostamento a sinistra con il cambio del bit meno significativo nella posizione di quello più significativo.

Disegno

Imposta il valore iniziale

Questa funzione legge dalla finestra il valore iniziale del registro inserito dall'utente Modificare 1 e verifica il valore inserito secondo le condizioni specificate: la stringa inserita non è vuota (Figura 6), la stringa inserita ha una lunghezza di otto (8bit=1byte, Figura 7), la stringa inserita contiene solo zeri e/o uno (Figura 8), la stringa immessa è diversa da zero (Figura 9). In caso contrario, vengono visualizzati messaggi di errore, l'utente deve correggerli e premere nuovamente il pulsante. In caso di esito positivo del controllo, il valore iniziale verrà scritto nella tabella di stato nella riga "Iniziale" e verrà emessa una notifica (Figura 10).

Disegno

Eseguire uno spostamento di registro

Questa funzione emula il funzionamento di un registro a scorrimento. Effettuando in sequenza 256 spostamenti, ogni spostamento genera un bit di uscita di una sequenza pseudo-casuale e un nuovo stato del registro. Non appena lo stato del registro è uguale a quello iniziale, il periodo viene calcolato e visualizzato nel campo promemoria 1 ha ricevuto una sequenza pseudo-casuale.

Aiuto-> Informazioni su

Questa funzione visualizza una breve descrizione del programma e delle istruzioni (Figura 11).

Disegno

Aiuto-> Informazioni sull'autore

Questa funzione visualizza le informazioni sull'autore del programma (Figura 12).

Disegno

2.3 Manuale d'uso

Per prima cosa impostare lo stato iniziale del registro. Deve contenere otto caratteri binari. In caso contrario, verrà visualizzato un messaggio di errore e sarà necessario correggere il valore inserito. Premere la voce di menu "Imposta valore iniziale".
Quindi seleziona le caselle di controllo per i feedback di registrazione (Sequenza di tocco). Premere la voce di menu "Imposta sequenza di tocco".
Quindi, fai clic sulla voce di menu "Registra turno". Assicurati di aver completato i passaggi 1 e 2 prima di farlo, altrimenti si verificherà un errore del software.
Una volta ricevuti i risultati, è possibile salvarli cliccando sulla voce di menu "File->Salva report". Assicurati di aver completato i passaggi 1-3 prima di eseguire questa operazione, altrimenti si verificherà un errore del software.
Per ottenere assistenza, fare clic sulle voci di menu "File->Informazioni", "File->Informazioni sull'autore".
Per vedere il funzionamento del registro con altri valori della sequenza di tocchi e lo stato iniziale del registro, ripetere i passaggi dei passaggi 1-3 in sequenza, inserendo altri parametri.

CONCLUSIONE

In questo documento, RgCsLOS sono stati considerati generatori di numeri pseudo-casuali. Il programma può servire come dimostrazione visiva dei principi di funzionamento dei registri a scorrimento con feedback lineare attivo XOR . Su di esso puoi studiare il principio della formazione di una sequenza di bit pseudocasuale, la relazione tra il valore iniziale del registro e il valore della sequenza pseudocasuale, la sequenza di colpi e il periodo. La gamma pseudo-casuale risultante può essere utilizzata in un'altra applicazione software (ad esempio, un'implementazione software di un cifrario gamma).

Ad oggi, questi registri non sono utilizzati come generatori di numeri pseudocasuali indipendenti, ma fanno parte di dispositivi più complessi. Tuttavia, furono loro ad aprire nuove direzioni in matematica (ricerca di polinomi primitivi in campi finiti, metodi matematici per rompere i generatori di numeri pseudocasuali). Senza la conoscenza dei principi di funzionamento dei generatori su RgCsLOS, è impossibile comprendere il funzionamento di dispositivi più complessi. Grazie alla loro semplice implementazione hardware, sono ampiamente utilizzati nella tecnologia. La ricerca di PrCsOS ha portato alla nascita di nuovi cifrari - block e stream - basati su questi tipi di registri (sliding permutation cipher, DES eccetera.; EDS, funzioni hash).

In generale, la ricerca in questo settore ha fortemente stimolato lo sviluppo della crittografia e dei crittoanalisti, dei computer e dei dispositivi, e ha anche consentito di implementare una serie di altre utili funzioni (ad esempio, la correzione di codici ciclici).

BIBLIOGRAFIA

Schneier Bruce. Crittografia applicata. Protocolli, algoritmi, testi di partenza in linguaggio C. - M.: Trionfo, 2002
Babash AV Aspetti crittografici e teorici degli automi della moderna sicurezza delle informazioni. Volume 1 - M.: Ed. Centro EAOI, 2009. - 414 p.
E.S. Selmer. Monografia: "Ricorsione lineare in un campo finito". Università di Bergen, Norvegia, 1966.
N. Zierler e J. Brillhart. "On Primitive Trinomials Modulo 2", Journal of Information and Control, Vol. 13 No. 6 dicembre 1968, pp. 541-544.
K.Kh. Meyer e W.L. Tuchman. "I codici pseudo-casuali possono essere decifrati", rivista Electronic Design, n. 23 novembre 1972.
JL Massey. "Generalizzazione dei registri a scorrimento e decodifica del codice Bose-Chowdhury-Hokvingham", IEEE Transactions on Information Theory, v. IT-15, n . 1, gennaio 1969, pp. 122-127.
SU Golomb. Shift Register Sequences, San Francisco, Golden Day, 1967 (ristampato da Aigean Park Press, 1982).

Annesso A

Tabella di alcuni polinomi primitivi modulo 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Input dello stato iniziale (IS)

convalida dell'input

Emissione di un messaggio di errore

Impostazione della sequenza di tocchi

Registrazione IP nella tabella di stato

Registra i -esimo registro di stato e bit di output nella tabella di stato

IS==Stato attuale

Salvataggio dei risultati

Uscita sequenza pseudo-casuale

Uscita

lanciare

sì

Non

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 spesso utilizzata 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. I suoi coefficienti diversi da zero sono chiamati 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:

Definizione

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. Poi:

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 mostrato che è possibile definire esattamente l'indipendenza di correlazione 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:

Numero di passaggio	Stato	Bit generato
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

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 fa riferimento 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 RSDOS-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

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

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 consiste in un registro a scorrimento a feedback lineare e 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 ottime prestazioni statistiche.

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 morso 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.

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, il registro a scorrimento produrrà una sequenza infinita di zeri, il che è assolutamente inutile.) Solo con alcune sequenze di tap, l'LFSR scorrerà in sequenza 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.