Cifrario di Feistel

Feistel propose che possiamo approssimare il blocco cifrato ideale utilizzando il concetto di cifrario del prodotto (product cipher), che è l'esecuzione di due o più semplici cifrari in sequenza in modo che il risultato finale è crittograficamente più forte di qualsiasi altro cifrario singolo. In essenza si voleva sviluppare un cifrario a blocchi la cui chiave fosse lunga k per blocchi di lunghezza di n bit consentendo un totale di possibili trasformazioni invece di aventi con il blocco ideale. In particolare Feistel propose l'uso di un cifrario che alternava sostituzioni e permutazioni definito come segue:

  • Sostituzione: ogni elemento del plaintext o gruppo di elementi è unicamente sostituito da un elemento del ciphertext o un gruppo di elementi corrispondente.
  • Permutazione: una sequenza di elementi del plaintext è sostituito da una permutazione di tale sequenza. Tutto qui: nessun elemento viene aggiunto o eliminato o sostituito, solo l'ordine viene modificato.
    L'approccio di Feistel è una applicazione pratica che alterna confusione e diffusione.

Diffusione
...

Nella diffusione, la struttura statistica del plaintext viene distribuita in modo uniforme in tutto il ciphertext, questo effetto viene ottenuto avendo ogni bit in plaintext affetto da molti bit del testo cifrato. Per capire meglio, ecco un esempio:
immaginiamo di dover crittare un certo messaggio con la seguente operazione di cifratura, in cui ad ogni corrisponde una , la regola per cifrare il messaggio M è la seguente:
, dove è un numero qualsiasi di lettere da aggiungere, diciamo che . Ovvero, presa una m del messaggio cifrato, diciamo :

Per rendere l'esempio più concreto immaginiamo di avere M = (H, E, L, L, O), dovendo effettuare delle operazioni matematiche è necessario che le lettere corrispondano a dei numeri, per semplicità utilizziamo la tabella ASCII dove:

LetteraNumero ASCII
'H'72
'E'69
'L'76
'O'79



In ASCII la lettera 'a' è rappresentata con il numero 65, quindi , ovvero .


, ovvero


, ovvero

Facendo la stessa operazione:
e

Il messaggio cifrato è , in questo modo per esempio la lettera L che si ripete due volte, non ha sempre la stessa corrispondenza. L'analisi statistica è più complicata, ma comunque fattibile. Per questo entra in gioco la confusione.

Confusione
...

Che effettua delle permutazioni del messaggio cifrato, semplicemente scambiano l'ordine degli elementi del ciphertext.

Struttura del cifrario di Feistel
...

La figura in basso mostra la struttura proposta da Feistel.Pasted image 20230418154731.png

Cifratura
...

Gli input dell'algoritmo per crittare sono:

  • un blocco in plaintext di lunghezza bit
  • una chiave K
    Il blocco in plaintext è diviso in due metà:

  • Le due metà del dato da crittare attraversano n round del processo di cifratura e poi si combinano per produrre il blocco cifrato. Ogni round i ha come input e derivati dal round precedente, allo stesso modo vi sarà una sottochiave derivata da K. In generale, le sottochiavi sono diverse da K e anche tra ogni . Nelle figura, sono stati utilizzati 16 round, ma potrebbero esserne usati un numero arbitrario.

Ogni round ha la stessa struttura:
Pasted image 20230418160701.png
guardando l'immagine risulta chiaro che:

  • alla parte destra del dato () viene applicata una certa funzione F (round function)
  • la funzione F prende come parametro
  • al risultato di F viene messo in XOR con la parte sinistra ()
    L'indice i della chiave parte da 1, mentre quello di LE e RE parte da 0
    Possiamo definire F come segue:
  • prende come parametri: e
  • restituisce un valore di w bit

Tutti i round hanno la stessa struttura.

Dopo viene effettuata una permutazione che consiste nello scambio tra le due metà del blocco.

L'esatta realizzazione del cifrario di Feistel dipende dalla scelta dei seguenti parametri:

  • dimensione del blocco: un blocco più grande è un blocco più sicuro
  • dimensione della chiave: una chiave più grande implica sicurezza maggiore, ma potrebbe decrementare la velocità di cifratura/decifratura
  • numero di round: più round offrono più sicurezza, normalmente vengono settati 16 round
  • generazione della sottochiave: un algoritmo più complesso per la generazione di una sottochiave rende la vita difficile ai crittoanalisti
  • funzione F: ancora, una funzione F più complessa, implica una miglior resistenza ai crittoanalisti

Una considerazione importante riguardo l'implementazione è che il modo in cui un cifrario di Feistel è implementato deve essere semplice da analizzare, in maniera da rendere più facile la comprensione a qualcuno che vuole studiarlo ed eventualmente migliorarlo. DES, per esempio, non ha questa caratteristica.

Decifratura
...

Il processo di decifratura con un cifrario di Feistel è essenzialmente lo stesso del processo di cifratura. La regola è la seguente: usare il dato cifrato come input dell'algoritmo, ma usando le sotto-chiavi in ordine inverso.

Adesso è possibile passare alle argomentazioni che riguardano DES.