Rete di Feistel

Da Wikipedia, l'enciclopedia libera.

In crittologia, un cifrario di Feistel è un algoritmo di cifratura a blocchi con una particolare struttura sviluppata dal crittologo dell'IBM Horst Feistel e da lui questa struttura ha preso il nome di rete di Feistel. Moltissimi algoritmi di cifratura a blocchi utilizzano questa struttura incluso il Data Encryption Standard (DES). La struttura inventata da Feistel ha il vantaggio che la cifratura e decifratura sono operazioni molto simili, spesso identiche e che basta invertire il funzionamento del gestore della chiave. Quindi i circuiti di cifratura e decifratura spesso sono gli stessi. Il meccanismo di criptatura ricorda le operazioni in cascata di Enigma .

La rete di Feistel venne commercializzata per la prima volta da IBM con il nome di Lucifer, un algoritmo progettato da Feistel e Don Coppersmith. La rete di Feistel divenne molto popolare quando il governo americano decise di utilizzarla come base per il suo algoritmo di cifratura, il DES. (Un algoritmo basato sul Lucifer con alcune modifiche apportate dalla NSA). Come altre parti del DES la rete di Feistel essendo una struttura che presupponeva più iterazioni dello stesso blocco era semplice da realizzare con i circuiti producibili allora. La cose sono cambiati nelle decadi successive, adesso anche circuiti molto complessi possono essere integrati con semplicità.

La rete di Feistel è simile come concezione al cifrario del prodotto e utilizza le seguenti operazioni:

Bit-shuffling (chiamata anche permutazione o P-box)
Semplice funzione non lineare (chiamata anche S-box)
Unione lineare (nel senso dell'algebra modulare) utilizzando lo XOR

queste, reiterate più volte (round), conferiscono alla rete di Feistel le proprietà di "confusione e diffusione" descritte da Claude Shannon.

Molti algoritmi moderni sono basati sulle reti di Feistel e la struttura proposta da Feistel è stata analizzata a fondo dai crittologi, anche se i più sicuri escono dal paradigma dell'invertibilità e sfruttano o la crittografia asimmetrica o tecnologie innovative come Qnet.

Le operazioni basilari sono le seguenti:

Dividi i dati di ingresso in due parti uguali, ( $L 0$ , $R 0$ )

Per ogni round $i =1,2,\dots,n$ , calcola

L i = R i - 1

$R_i = L_{i-1} \oplus f(R_{i-1}, K_i)$

dove $f$ è la funzione del round e $K i$ è la chiave di sessione.

Si ottiene il testo cifrato ( $L n$ , $R n$ ).

Senza considerare la funzione $f$ , la decifraziono si ottiene

R i - 1 = L i

$L_{i-1} = R_i \oplus f(R_{i-1}, K_i)$

Un vantaggio di questo modello è che le funzioni usate non sono invertibili e possono essere molto complesse.

Questo diagramma mostra la cifratura e la decifratura del messaggio. Notare l'inversione della chiave di sessione per la decifratura, è l'unica differenza rispetto alla cifratura del messaggio.

Il Cifrario di Feistel non bilanciato utilizza una versione modificata della struttura con L0 e R0 di dimensioni diverse. L'algoritmo di Skipjack è un esempio di questa tipologia di algoritmi.