Cifrario Feistel

In crittografia, un cifrario Feistel è una struttura simmetrica utilizzata nella costruzione di cifrari a blocchi, che prende il nome dal crittografo tedesco della IBM Horst Feistel; è anche comunemente noto come rete Feistel. Un'ampia serie di cifratori a blocchi utilizza lo schema, compreso lo standard di cifratura dei dati

La struttura del Feistel ha il vantaggio che le operazioni di cifratura e decifratura sono molto simili, anche identiche in alcuni casi, e richiedono solo un'inversione del programma delle chiavi. Pertanto la dimensione del codice o della circuiteria necessaria per implementare un tale cifrario è quasi dimezzata.

La costruzione di Feistel è di natura iterativa, il che rende più facile l'implementazione del sistema di criptosistema nell'hardware.

Le reti Feistel e costruzioni simili sono cifrari di prodotti, e quindi combinano più cicli di operazioni ripetute, come ad esempio:

Bit-shuffling (spesso chiamate scatole di permutazione o P-box)
Semplici funzioni non lineari (spesso chiamate scatole di sostituzione o S-box)
Miscelazione lineare (nel senso di algebra modulare) utilizzando XOR per produrre una funzione con grandi quantità di ciò che Claude Shannon ha descritto come "confusione e diffusione".

Il bit shuffling crea l'effetto di diffusione, mentre la sostituzione viene utilizzata per creare confusione.

Lavoro teorico

Molti moderni cifrari a blocchi simmetrici utilizzano le reti Feistel, e la struttura e le proprietà dei cifrari Feistel sono state ampiamente esplorate dai crittografi. In particolare, Michael Luby e Charles Rackoff hanno analizzato la costruzione del cifrario a blocchi Feistel, e hanno dimostrato che se la funzione circolare è una funzione pseudorandom crittograficamente sicura, con _Ki usato come seme, allora 3 round sono sufficienti per rendere il cifrario a blocchi una permutazione pseudorandom, mentre 4 round sono sufficienti per renderlo una permutazione pseudorandom "forte" (il che significa che rimane pseudorandom anche ad un avversario che ottiene l'accesso oracolo alla sua permutazione inversa). A causa di questo risultato molto importante di Luby e Rackoff, i cifrari Feistel sono a volte chiamati cifrari a blocco Luby-Rackoff. Ulteriori studi teorici hanno generalizzato la costruzione e definito limiti più precisi per la sicurezza.

Costruzione

Lasciate che la F ${\rm F}$ sia la funzione circolare e lasciate che la K 1 , K 2 , ... , la K n n, K 1, K 2, K 2, K 2, K n, K 2, K n siano $K_1,K_2,\ldots,K_{n}$ i tasti secondari per i turni 1, 2, ..., n, n, n, n, $1,2,\ldots,n$ rispettivamente.

Quindi il funzionamento di base è il seguente:

Dividere il blocco di testo in due pezzi uguali, ( L 1 {\displaystyle L_{1}}} L_1 , R 1 {\displaystyle R_{1}}} R_1 )

Per ogni round i = 1 , 2 , ... , n {\i\i} per ogni round i=1,2,\i\i} $i =1,2,\dots,n$ , calcolare (calcolare)

L i + 1 = R i {\a6}=R_{i+1}=R_{i},} $L_{i+1} = R_i\,$

R i + 1 = L i ⊕ F ( R i , K i ) {\an8}(R_{i+1}=L_{i}\an8}oplus {\an8}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Quindi il testo cifrato è ( R n + 1 , L n + 1 ) {\i} (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Comunemente i due pezzi R n {\i}displaystyle R_{n}} R_n e L n {\i}displaystyle L_{n}} L_n non vengono scambiati dopo l'ultimo turno).

La decodifica di un testo cifrato ( R n , L n ) {\a6}(R_{n},L_{n})} (R_n, L_n) viene effettuata calcolando per i = n , n - 1 , ... , 1 {\a6}(R_{n},L_{n})}(i=n,n-1,\a6}(1) $i=n,n-1,\ldots,1$

R i = L i + 1 {\i}=L_{i}=L_{i+1},} $R_{i} = L_{i+1}\,$

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\a6}(L_{i}=R_{i+1}}\a6}(L_{i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Poi ( L 1 , R 1 ) {\an8}(L_{1},R_{1})} (L_1,R_1) è di nuovo il testo in chiaro.

Uno dei vantaggi di questo modello è che la funzione circolare F {\fscx130\fscy130\frx40}F{\fscx130\fscy130\frx40} ${\rm F}$ non deve essere necessariamente invertibile, e può essere molto complessa.

Il diagramma illustra il processo di cifratura. La decodifica richiede solo l'inversione dell'ordine della sottochiave K n , K n - 1 , ... , K 1 K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ utilizzando lo stesso processo; questa è l'unica differenza tra la codifica e la decodifica:

I cifrari Feistel sbilanciati usano una struttura modificata dove L 1 {\i}} L_1 e R 1 {\i} R_1 non sono di uguale lunghezza. Il cifrario di MacGuffin è un esempio sperimentale di tale cifrario.

La costruzione Feistel è utilizzata anche in algoritmi crittografici diversi dai cifrari a blocchi. Ad esempio, lo schema Optimal Asymmetric Encryption Padding (OAEP) utilizza una semplice rete Feistel per la randomizzazione di testi cifrati in alcuni schemi di cifratura a chiave asimmetrica.

Funzionamento della rete Feistel su cifrario a blocchi, dove P è il testo in chiaro e C è il testo cifrato

Elenco dei cifrari Feistel

Feistel o modificato Feistel: Pesce palla, Camelia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifero, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Sentimento generalizzato: CAST-256, MacGuffin, RC2, RC6, Skipjack

Domande e risposte

D: Che cos'è un cifrario Feistel?

R: Il cifrario Feistel è una struttura simmetrica utilizzata nella costruzione di cifrari a blocchi, che prende il nome dal crittografo tedesco dell'IBM Horst Feistel. È anche comunemente conosciuto come rete Feistel.

D: Quali sono i vantaggi dell'utilizzo di una struttura Feistel?

R: Il vantaggio principale dell'utilizzo di una struttura Feistel è che le operazioni di crittografia e decrittografia sono molto simili, persino identiche in alcuni casi, richiedendo solo un'inversione del programma della chiave. Questo riduce la dimensione del codice o del circuito necessario per implementare un tale cifrario di quasi la metà. Inoltre, la natura iterativa rende più facile l'implementazione del crittosistema nell'hardware.

D: Come descrive Claude Shannon la "confusione e la diffusione"?

R: Claude Shannon ha descritto la "confusione e la diffusione" come la presenza di una grande quantità di entrambi gli elementi, al fine di rendere difficile per un attaccante decifrare un messaggio criptato.

D: Quali tecniche vengono utilizzate per creare confusione e diffusione?

R: La confusione e la diffusione vengono create attraverso il mescolamento dei bit (spesso chiamati scatole di permutazione o P-box) e semplici funzioni non lineari (spesso chiamate scatole di sostituzione o S-box), così come la miscelazione lineare (nel senso dell'algebra modulare) utilizzando lo XOR. Il mescolamento dei bit crea l'effetto di diffusione, mentre la sostituzione viene utilizzata per la confusione.

D: Che tipo di cifratura è una rete Feistel?

R: Una rete Feistel è un tipo di cifrario prodotto che combina più cicli di operazioni ripetute per criptare i dati in modo sicuro.

D: Chi ha sviluppato questo tipo di crittografia?

R: La struttura Feistel è stata sviluppata dal crittografo tedesco dell'IBM Horst Feistel.

D: Il Data Encryption Standard si basa su questo tipo di crittografia?

R: Sì, Data Encryption Standard utilizza questo tipo di crittografia che sfrutta gli stessi principi sopra descritti per creare confusione e diffusione all'interno di un messaggio crittografato.