Secondo Claude Shannon, il cifrario ideale dovrebbe oscurare le proprietà statistiche del messaggio originale. A tale scopo, Shannon suggerì di combinare sostituzioni e permutazioni/trasposizioni in modo da ottenere algoritmi di cifratura con due particolari proprietà:
Shannon introdusse dunque l’idea delle reti di sostituzioni e permutazioni (substitution-permutation network, S-P network), molto usate nella crittografia moderna.
Horst Feistel, un crittografo che lavorava come ricercatore presso IBM, fu uno dei primi a proporre una cifratura basata sulle reti S-P: la rete di Feistel (o struttura di cifratura di Feistel). Di per sè, questa non è un cifrario direttamente utilizzabile, ma piuttosto è una struttura generale sulla quale si possono basare dei cifrai concreti; un esempio di algoritmo basato su tale struttura è il DES.
La rete di Feistel è un cifrario del prodotto: la cifratura è eseguita in più fasi o round, ciascuna delle quali consiste nell’eseguire le stesse operazioni (sostituzioni e permutazioni) con una chiave diversa, che prende il nome di sottochiave di fase o di round. Ciò non significa però che sia necessario fornire in input più chiavi: le sottochiavi di fase vengono generate da un’unica chiave data in input, tramite un apposito algoritmo (che la struttura della rete di Feistel non fissa, e va invece specificato quando si definisce un cifrario concreto).
Una caratteristica particolare della rte di Feistel è che la cifratura e la decifratura sono praticamente identiche: come si vedrà in seguito, l’unica differenza tra queste due operazioni è l’inversione dell’ordine in cui vengono usate le sottochiavi. Ciò significa che la stessa implementazione può essere usata per cifrare e per decifrare, il che è un vantaggio soprattutto quando l’algoritmo viene realizzato a livello hardware tramite un circuito dedicato.
Gli input del processo di cifratura sono il plaintext, che deve essere un blocco di dati formato da un numero pari di bit, e una chiave, dalla quale vengono in qualche modo generate tante sottochiavi diverse quante sono le fasi da eseguire.
La dimensione del plaintext deve essere pari, $2w$ bit, perchè esso viene suddiviso in due metà, ciascuna di $w$ bit, le quali attraversano $n$ fasi di elaborazione, poi vengono scambiate (il perchè sarà spiegato in seguito) e ricombinate per ottenere il blocco di testo cifrato, ancora di $2w$ bit.
Si consideri, in generale, l’$i$-esima fase della cifratura (per $i=1, \dots, n$). I dati che essa riceve in input sono la sottochiave $K_i$ e le due metà del blocco generato dalla fase precedente — la metà sinistra $L_{i-1}$ (i primi $w$ bit del blocco) e la metà destra $R_{i-1}$ (i restanti $w$ bit del blocco). L’input destro $R_{i-1}$ diventa direttamente l’output sinistro $L_i$, senza subire alcuna modifica. Tuttavia, $R_{i-1}$ va anche in input, insieme alla sottochiave $K_i$, a una qualche funzione di round $F$, e il risultato di quest’ultima viene messo in OR esclusivo (XOR, $\oplus$) bit a bit con l’input sinistro $L_{i-1}$ per calcolare l’output destro $R_i$. La rete di Feistel non indica una specifica funzione $F$ da usare; gli unici vincoli sono che essa produca un risultato di $w$ bit (in modo da poter calcolare lo XOR bit a bit con metà dell’input) e che si usi la stessa funzione in tutte le fasi (perchè ogni fase deve essere identica alle altre: deve cambiare solo la sottochiave usata).
Complessivamente, l’output dell’$i$-esima fase è:
$$ L_i = R_{i-1} \\ R_i=L_{i-1} \oplus F(R_{i-1}, K_i) $$
In sostanza, ciascuna fase sostituisce solo la metà sinistra dell’input, lasciando la destra inalterata (non cifrata, se ci fosse una sola fase), ma poi scambia le due metà per far si che a fase successiva sostituisca l’altra metà.
Se si considera la singola fase, l’output dello XOR (ovvero l’output destro della fase, $R_i$) dipende dalle due metà dell’input e dalla sottochiave. Tuttavia, considerando insieme più fase, si osserva che la funzione $F$ riceve ogni volta in input e dalla sottochiave. Tuttavia, considerando insieme più fasi, si osserva che la funzione $F$ riceve ogni volta in input l’output dello XOR precedente, quindi il risultato dello XOR di una fase dipende anche dagli input e dalle sottochiavi di tutte le fasi precedenti.
Come già accennato, le due metà generate in output dall’ultimo round vengono scambiate prima di ricombinarle per ottenere l’intero blocco di testo cifrato. Si potrebbe osservare che ciò equivale a eilminare lo scambio effettuato all’interno dell’ultimo round, ma aggiungere uno scambio finale è preferibile perchè altrimenti l’ultimo round ovrebbe essere diverso dagli altri, il che complicherebbe soprattutto un’implementazione hardware (non sarebbe possibile utilizzare esattamente lo stesso circuito per eseguire tutti i round).