Confusione e diffusione - Confusion and diffusion

In crittografia , confusione e diffusione sono due proprietà del funzionamento di un cifrario sicuro identificato da Claude Shannon nel suo rapporto classificato del 1945 A Mathematical Theory of Cryptography . Queste proprietà, quando presenti, lavorano per contrastare l'applicazione delle statistiche e di altri metodi di crittoanalisi .

Questi concetti sono importanti anche nella progettazione di funzioni hash robuste e generatori di numeri pseudocasuali in cui la decorrelazione dei valori generati è di fondamentale importanza.

Definizione

Confusione

Confusione significa che ogni cifra binaria (bit) del testo cifrato dovrebbe dipendere da più parti della chiave, oscurando le connessioni tra le due.

La proprietà della confusione nasconde la relazione tra il testo cifrato e la chiave.

Questa proprietà rende difficile trovare la chiave dal testo cifrato e se un singolo bit in una chiave viene modificato, il calcolo della maggior parte o di tutti i bit nel testo cifrato sarà influenzato.

La confusione aumenta l'ambiguità del testo cifrato ed è utilizzata sia dai cifrari a blocchi che dai cifrari a flusso.

Nelle reti di sostituzione-permutazione , la confusione è fornita dalle caselle di sostituzione .

Diffusione

Diffusione significa che se cambiamo un singolo bit del testo in chiaro, allora dovrebbe cambiare circa la metà dei bit nel testo cifrato, e allo stesso modo, se cambiamo un bit del testo cifrato, allora dovrebbe cambiare circa la metà dei bit del testo in chiaro. Ciò equivale all'aspettativa che gli schemi di crittografia mostrino un effetto valanga .

Lo scopo della diffusione è nascondere la relazione statistica tra il testo cifrato e il testo in chiaro. Ad esempio, la diffusione garantisce che eventuali pattern nel testo in chiaro, come i bit ridondanti, non siano evidenti nel testo cifrato. I cifrari a blocchi ottengono ciò "diffondendo" le informazioni sulla struttura del testo in chiaro attraverso le righe e le colonne del cifrario.

Nelle reti di sostituzione-permutazione, la diffusione è fornita da scatole di permutazione .

Teoria

Nelle definizioni originali di Shannon, confusione si riferisce a rendere la relazione tra il testo cifrato e la chiave simmetrica il più complessa e coinvolta possibile; diffusione si riferisce alla dissipazione della struttura statistica del testo in chiaro sulla maggior parte del testo cifrato . Questa complessità viene generalmente implementata attraverso una serie ben definita e ripetibile di sostituzioni e permutazioni . La sostituzione si riferisce alla sostituzione di determinati componenti (di solito bit) con altri componenti, seguendo determinate regole. La permutazione si riferisce alla manipolazione dell'ordine dei bit secondo un algoritmo. Per essere efficace, qualsiasi disuniformità dei bit di testo in chiaro deve essere ridistribuita su strutture molto più grandi nel testo cifrato, rendendo tale non uniformità molto più difficile da rilevare.

In particolare, per un input scelto casualmente, se si inverte l' i -esimo bit, allora la probabilità che il j -esimo bit di output cambi dovrebbe essere la metà, per ogni i e j - questo è chiamato criterio della valanga rigorosa . Più in generale, si può richiedere che capovolgendo un insieme fisso di bit si cambi ogni bit di uscita con probabilità della metà.

Uno scopo della confusione è rendere molto difficile trovare la chiave anche se si dispone di un gran numero di coppie testo in chiaro-testo cifrato prodotte con la stessa chiave. Pertanto, ogni bit del testo cifrato dovrebbe dipendere dall'intera chiave e, in modi diversi, da diversi bit della chiave. In particolare, la modifica di un bit della chiave dovrebbe modificare completamente il testo cifrato. Il modo più semplice per ottenere sia la diffusione che la confusione è utilizzare una rete di sostituzione-permutazione . In questi sistemi, il testo in chiaro e la chiave hanno spesso un ruolo molto simile nella produzione dell'output, quindi lo stesso meccanismo garantisce sia la diffusione che la confusione.

Applicato alla crittografia

La progettazione di un metodo di crittografia utilizza entrambi i principi di confusione e diffusione. Confusione significa che il processo cambia drasticamente i dati dall'input all'output, ad esempio traducendo i dati attraverso una tabella non lineare creata dalla chiave. Esistono molti modi per invertire i calcoli lineari, quindi più non è lineare, più strumenti di analisi rompe.

Diffusione significa che la modifica di un singolo carattere dell'input cambierà molti caratteri dell'output. Fatto bene, ogni parte dell'input influisce su ogni parte dell'output, rendendo l'analisi molto più difficile. Nessun processo di diffusione è perfetto: lascia sempre passare alcuni schemi. Una buona diffusione disperde ampiamente questi modelli attraverso l'output e, se ci sono diversi modelli che lo attraversano, si mescolano a vicenda. Ciò rende i modelli molto più difficili da individuare e aumenta notevolmente la quantità di dati da analizzare per violare il codice.

Analisi di AES

L' Advanced Encryption Standard (AES) ha sia un'eccellente confusione che diffusione. Le sue tabelle di ricerca della confusione sono molto non lineari e sono brave a distruggere i modelli. Il suo stadio di diffusione distribuisce ogni parte dell'input a ogni parte dell'output: cambiando un bit di input cambia in media la metà dei bit di output. Sia la confusione che la diffusione vengono ripetute più volte per ogni input per aumentare la quantità di rimescolamento. La chiave segreta viene mischiata in ogni fase in modo che un utente malintenzionato non possa precalcolare cosa fa il cifrario.

Niente di tutto questo accade quando un semplice scramble a una fase si basa su una chiave. I modelli di input fluirebbero direttamente attraverso l'output. Potrebbe sembrare casuale all'occhio, ma l'analisi troverebbe schemi ovvi e il codice potrebbe essere rotto.

Guarda anche

Riferimenti

Opere citate