Molti algoritmi di cifratura in uso ancora oggi sfruttando una struttura conosciuta come cifrari di Feistel. Per questo è importante definire prima i principi su cui si basa l'approccio di Feistel:
Motivazione per l'uso di una struttura a cifrario di Feistel
Un cifrario a blocchi opera su un blocco plaintext di n bits per produrre un testo cifrato di n bits. Ci sono
Tra il blocco in plaintext e il blocco in cipher text: deve esserci una corrispondenza biunivoca.
I seguenti esempi mostrano una non-singola trasformazione e una singola trasformazione per un numero di bit pari a 2.
Mappatura reversibile
| Plaintext | Ciphertext |
|---|---|
| 00 | 11 |
| 01 | 10 |
| 10 | 00 |
| 11 | 01 |
Mappatura non reversibile
| Plaintext | Ciphertext |
|---|---|
| 00 | 11 |
| 01 | 10 |
| 10 | 01 |
| 11 | 01 |
Nella mappatura non reversibile, il testo in chiaro 10 e 11 generano lo stesso testo cifrato.
La figura sotto mostra la logica generale di un cifrario a sostituzione con n = 4.
Un input di 4 bit produce uno dei 16 possibili output generabili.
16 perché per ogni posizione abbiamo due scelte (0, 1):
- per la prima posizione ho 2 possibilità,
- per la seconda altre 2,
- per la terza altre 2
- e per la quarta altre 2
il che mi restituisce:
Tuttavia, avendo sempre 4 bit, ci sono anche 16 possibili input.
Un input a 4 bit (1 su 16) produce un output a 4 bit (1 su 16).
L'immagine sopra mostra come sono collegati i singoli input/output. L'input 0 è collegato all'input 14, mentre l'input 1 è collegato con l'input 4. Da notare che, per rendere reversibile l'operazione, l'output 0 è connesso all'input 14 e l'output 4 è connesso all'input 1.
La mappatura di crittazione e decrittazione potrebbe essere definita con una tabella:
Questa è la forma generica di un cifrario a blocchi e può essere usato per definire qualsiasi mappatura reversibile tra un testo in chiaro e uno cifrato. Feistel si riferisce a questo come al cifrario a blocco ideale, poiché consente il numero massimo di mappature crittografiche possibili a partire da un blocco di testo in chiaro.
Ma c'è un problema pratico con il cifrario a blocchi ideale. Se viene usato un blocco di lunghezza corta, ad esempio di n = 4 bit, allora il sistema è equivalente al classico cifrario a sostituzione che è vulnerabile alla crittoanalisi statistica. Se n è abbastanza grande si riesce e soverchiare questa vulnerabilità.
Riconsiderando la tabella sopra, un blocco di testo in chiaro è mappato per un certo blocco di testo cifrato di n = 4 bit.
La mappatura è definita dalle righe nella seconda colonna (della tabella più a sinistra) che mostrano il testo cifrato per ogni blocco in chiaro. In questo caso, la chiave per determinare la giusta mappatura di un certo blocco in chiaro di 4 bit tra tutte le altre possibili 16 mappature è data dalla tabella sopra.
Per riuscire a decifrare un messaggio è necessaria la mappatura mostrata nella tabella sopra, o in alternativa una chiave.
La chiave è rappresentata come una sequenza di bit che indica il valore di output per ognuno dei 16 possibili input. Dal momento che ci sono 16 possibili input e che ognuno è mappato su 16 possibili output, la chiave avrebbe bisogno di 4 bit per ogni valore di input, per specificare l'intera mappatura. Quindi la chiave richiesta è lunga
Infatti in questo caso la chiave è la sequenza di bit nella colonna ciphertext della tabella più a sinistra: 1110 0100 1101 0001 0010 1111 1011 1000 0011 1010 0110 1100 0101 1001 0000 0111.
In tal modo so che quando ricevo 0000 come plaintext, che devo sostituirlo con il blocco in posizione 0 della chiave, ovvero: 1110. Se a conoscere la chiave sono solo i due nodi della comunicazione, nessuno sarà in grado di dire a cosa corrisponde 0000.
Se avessimo a che fare (cosa che succede nella internet odierna) con blocchi di 64 bit, la chiave sarebbe lunga
Feistel si rese conto che il cifrario a blocchi ideale non era pratico e che quello che era necessario era un approssimazione di questo, in modo che fosse facilmente realizzabile: cifrario di feistel.