Cifrario Feistel - Feistel cipher

In crittografia , un cifrario Feistel (noto anche come cifrario a blocchi Luby – Rackoff ) è una struttura simmetrica utilizzata nella costruzione di cifrari a blocchi , dal nome del fisico e crittografo di origine tedesca Horst Feistel che ha svolto ricerche pionieristiche mentre lavorava per IBM (USA) ; è anche comunemente noto come rete Feistel . Una grande percentuale di cifrari a blocchi utilizza lo schema, compreso lo standard di crittografia dei dati degli Stati Uniti , il GOST sovietico / russo e le più recenti cifrature Blowfish e Twofish . In una crittografia Feistel, la crittografia e la decrittografia sono operazioni molto simili ed entrambe consistono nell'esecuzione iterativa di una funzione chiamata "funzione di arrotondamento" per un numero fisso di volte.

Storia

Molti cifrari a blocchi simmetrici moderni si basano su reti Feistel. Le reti Feistel sono state viste per la prima volta commercialmente nel cifrario Lucifer di IBM , progettato da Horst Feistel e Don Coppersmith nel 1973. Le reti Feistel hanno acquisito rispettabilità quando il governo federale degli Stati Uniti ha adottato il DES (un codice basato su Lucifer, con modifiche apportate dalla NSA ) nel 1976. Come altri componenti del DES, la natura iterativa della costruzione Feistel rende più semplice l'implementazione del sistema crittografico nell'hardware (in particolare sull'hardware disponibile al momento della progettazione del DES).

Design

Una rete Feistel utilizza una funzione round , una funzione che accetta due input, un blocco dati e una sottochiave e restituisce un output della stessa dimensione del blocco dati. In ogni round, la funzione round viene eseguita su metà dei dati da crittografare e il suo output viene XORed con l'altra metà dei dati. Questo viene ripetuto un numero fisso di volte e l'output finale sono i dati crittografati. Un importante vantaggio delle reti Feistel rispetto ad altri progetti di cifratura come le reti di sostituzione-permutazione è che l'intera operazione è garantita come invertibile (cioè, i dati crittografati possono essere decrittografati), anche se la funzione round non è invertibile di per sé. La funzione round può essere resa arbitrariamente complicata, poiché non ha bisogno di essere progettata per essere invertibile. Inoltre, le operazioni di crittografia e decrittografia sono molto simili, in alcuni casi persino identiche, e richiedono solo un'inversione della pianificazione della chiave . Pertanto, la dimensione del codice o della circuiteria richiesta per implementare tale cifratura è quasi dimezzata.

Lavoro teorico

La struttura e le proprietà dei cifrari Feistel sono state ampiamente analizzate dai crittografi .

Michael Luby e Charles Rackoff hanno analizzato la costruzione del cifrario Feistel e hanno dimostrato che se la funzione round è una funzione pseudocasuale crittograficamente sicura , con K _i usato come seme, allora 3 round sono sufficienti per rendere il cifrario a blocchi una permutazione pseudocasuale , mentre 4 round sono sufficienti per renderlo una permutazione pseudocasuale "forte" (il che significa che rimane pseudocasuale anche ad un avversario che ottiene l' accesso oracolare alla sua permutazione inversa). A causa di questo risultato molto importante di Luby e Rackoff, i cifrari Feistel sono talvolta chiamati cifrari a blocchi Luby – Rackoff.

Ulteriori lavori teorici hanno in qualche modo generalizzato la costruzione e dato limiti più precisi per la sicurezza.

Dettagli costruttivi

Sia la funzione round e siano rispettivamente le sotto-chiavi per i round . ${\ displaystyle {\ rm {F}}}$ ${\ displaystyle K_ {0}, K_ {1}, \ ldots, K_ {n}}$ ${\ displaystyle 0,1, \ ldots, n}$

Quindi l'operazione di base è la seguente:

Dividi il blocco di testo in chiaro in due parti uguali, ( , ) ${\ displaystyle L_ {0}}$ ${\ displaystyle R_ {0}}$

Per ogni round , calcola ${\ displaystyle i = 0,1, \ dots, n}$

{\ displaystyle L_ {i + 1} = R_ {i} \,}

{\ displaystyle R_ {i + 1} = L_ {i} \ oplus {\ rm {F}} (R_ {i}, K_ {i}).}

Dove significa XOR . Allora il testo cifrato è . ${\ displaystyle \ oplus}$ ${\ displaystyle (R_ {n + 1}, L_ {n + 1})}$

La decrittazione di un testo cifrato viene eseguita dall'elaborazione per ${\ displaystyle (R_ {n + 1}, L_ {n + 1})}$ ${\ displaystyle i = n, n-1, \ ldots, 0}$

{\ displaystyle R_ {i} = L_ {i + 1} \,}

{\ displaystyle L_ {i} = R_ {i + 1} \ oplus \ operatorname {F} (L_ {i + 1}, K_ {i}).}

Quindi è di nuovo il testo in chiaro. ${\ displaystyle (L_ {0}, R_ {0})}$

Il diagramma illustra sia la crittografia che la decrittografia. Notare l'inversione dell'ordine delle sottochiavi per la decrittografia; questa è l'unica differenza tra crittografia e decrittografia.

Cifrario Feistel sbilanciato

I cifrari Feistel sbilanciati utilizzano una struttura modificata dove e non hanno la stessa lunghezza. Il codice Skipjack è un esempio di tale codice. Il transponder della firma digitale di Texas Instruments utilizza un codice Feistel sbilanciato proprietario per eseguire l' autenticazione challenge-response . ${\ displaystyle L_ {0}}$ ${\ displaystyle R_ {0}}$

Il Thorp shuffle è un caso estremo di un cifrario Feistel sbilanciato in cui un lato è un singolo bit. Questo ha una sicurezza dimostrabile migliore di un cifrario Feistel bilanciato, ma richiede più round.

Altri usi

La costruzione Feistel viene utilizzata anche in algoritmi crittografici diversi dai cifrari a blocchi. Ad esempio, lo schema di riempimento della crittografia asimmetrica ottimale (OAEP) utilizza una semplice rete Feistel per randomizzare i testi cifrati in determinati schemi di crittografia a chiave asimmetrica .

Un algoritmo Feistel generalizzato può essere utilizzato per creare forti permutazioni su piccoli domini di dimensioni non pari a due (vedere crittografia a conservazione del formato ).

Reti Feistel come componente di design

Indipendentemente dal fatto che l'intero codice sia un codice Feistel o meno, le reti simili a Feistel possono essere utilizzate come componente del progetto di un codice. Ad esempio, misty1 è un cifrario di Feistel utilizzando una rete a tre-tutto Feistel nella sua funzione round, Skipjack è un Feistel modificato cifrario utilizzando una rete di Feistel nella sua permutazione G, e Threefish (parte di Matassa ) è un codice a blocchi non Feistel che utilizza una funzione MIX simile a Feistel.

Elenco dei cifrari Feistel

Feistel o Feistel modificato:

Feistel generalizzato:

Guarda anche

Crittografia
Cifrario di flusso
Rete di sostituzione-permutazione
Lo schema di sollevamento per la trasformata wavelet discreta ha praticamente la stessa struttura
Crittografia che preserva il formato
Schema Lai-Massey

Languages

In other projects