Cifrario di Feistel

Il cifrario di Feistel prende il nome dal suo inventore, Horst Feistel. E' un cifrario a blocchi il cui funzionamento è simmetrico. In particolare, il blocco di input viene suddiviso in due parti, dette L e R. La parte destra viene lasciata immutata, mentre la parte sinistra viene combinata con una operazione di xor all'output di una funzione. Questa funzione, detta Funzione di Feistel, riceve in input la parte destra e un certo blocco di dati chiamato sottochiave. Dalla chiave di cifratura vengono generate tante sottochiavi quanti sono i round dell'algoritmo.
Successivamente le due parti vengono scambiate, e si ripete il processo. Ogni passo del cifrario viene detto round. Al termine di tutti i round, le due parti formano il blocco di output.

Cifratura

feistel.png

Nella cifratura, sia $L_0$ e $R_0$ le due parti del blocco in chiaro. Al termine del primo round si hanno due blocchi di dati $L_1$ e $R_1$ tali che:

(1)
\begin{eqnarray} L_1 &=& R_0 \\ R_1 &=& L_0 \oplus F(R_0, k_1) \end{eqnarray}

dove $k_1$ è la sottochiave generata per il primo round. In generale, all'i-esimo round si avranno i seguenti dati:

(2)
\begin{eqnarray} L_i &=& R_{i-1} \\ R_i &=& L_{i-1} \oplus F(R_{i-1}, k_i) \end{eqnarray}

Supponendo che si effettuino 16 round, allora il testo cifrato è costituito da $L_{16}$ e $R_{16}$.

Decifratura

Nella decifratura, sia $L'_{16}$ e $R'_{16}$ le due parti del blocco cifrato. Le sottochiavi sono impiegate in ordine opposto rispetto alla cifratura. Al generico round i-esimo, si impiega la sottochiave $k_{16-i}$si ha:

(3)
\begin{eqnarray} L'_i &=& R'_{i-1} \\ R'_i &=& L'_{i-1} \oplus F(R'_{i-1}, k_{16-i}) \end{eqnarray}

Dimostrazione

Si può dimostrare che l'input (in chiaro) nella funzione di cifratura all'i-esimo round è identico all'output della funzione di decifratura nello stesso round. L'algoritmo decifratura riceve in input i dati $L'_{0}$, $R'_{0}$ e, dopo 16 round, produce i dati in chiaro $L'_{16}$ e $R'_{16}$.

All'ultimo round di cifratura vengono generati i dati $L_{16}$, $R_{16}$, tali che:

(4)
\begin{eqnarray} L_{16} &=& R_{15} \\ R_{16} &=& L_{15} \oplus F(R_{15}, k_{15}) \end{eqnarray}

I dati sono inseriti nell'algoritmo di decifratura, scambiandoli:

(5)
\begin{eqnarray} L'_0 &=& R_{16} \\ R'_0 &=& L_{16} \end{eqnarray}

sostituendo si ha:

(6)
\begin{eqnarray} L'_0 &=& R_{16} = L_{15} \oplus F(R_{15}, k_{15}) \\ R'_0 &=& L_{16} = R_{15} \end{eqnarray}

al primo round di decifrazione vengono generati i dati $L'_{1}$, $R'_{1}$ in questo modo:

(7)
\begin{eqnarray} L'_1 &=& R'_0 \\ R'_1 &=& L'_0 \end{eqnarray}

sostituendo le eq. (6) nelle (7) si ottiene:

(8)
\begin{eqnarray} L'_1 &=& R'_0 = L_{16} = R_{15} \\ R'_1 &=& L'_0 \oplus F(R'_0, k_{15}) \end{eqnarray}

quindi, poiché le sottochiavi $k_i$ sono inserite in senso inverso, al primo round di decifrazione viene impiegata l'ultima sottochiave. Sostituendo il valore di $L'_0$ della eq. (6) dell'espressione di $R'_1$ della eq. (8) si ha:

(9)
\begin{eqnarray} L'_1 &=& R_{15} \\ R'_1 &=& \left[ L_{15} \oplus F(R_{15}, k_{15}) \right] \oplus F(R'_0, k_{15}) \end{eqnarray}

poiché, in base alla eq. (6) $R'_0 = R_{15}$, sostituendo si ottiene:

(10)
\begin{eqnarray} L'_1 &=& R_{15} \\ R'_1 &=& \left[ L_{15} \oplus F(R_{15}, k_{15}) \right] \oplus F(R_{15}, k_{15}) \end{eqnarray}

L'operazione di xor gode delle seguenti proprietà:

(11)
\begin{align} a \oplus (b \oplus c) = (a \oplus b) \oplus c \end{align}
(12)
\begin{align} a \oplus a = 0 \end{align}
(13)
\begin{align} a \oplus 0 = a \end{align}

Considerando la seconda equazione della (9), e applicando la proprietà (11) si ottiene:

(14)
\begin{align} R'_1 = \left[ L_{15} \oplus F(R_{15}, k_{15}) \right] \oplus F(R_{15}, k_{15}) = L_{15} \oplus \left[ F(R_{15}, k_{15}) \oplus F(R_{15}, k_{15}) \right] \end{align}

per la proprietà (12) l'equazione diventa

(15)
\begin{align} R'_1 = L_{15} \oplus \left[ F(R_{15}, k_{15}) \oplus F(R_{15}, k_{15}) \right] = L_{15} \oplus 0 \end{align}

infine, per la proprietà (13) si ha

(16)
\begin{align} R'_1 = L_{15} \oplus 0 = L_{15} \end{align}

quindi l'eq. (9) diventa

(17)
\begin{eqnarray} L'_1 &=& R_{15} \\ R'_1 &=& L_{15} \end{eqnarray}

quindi, l'output del primo round di decifrazione è identico all'input dell'ultimo round di decifrazione. Si può, analogamente, proseguire questo ragionamento fino a dimostrare che:

(18)
\begin{eqnarray} L'_{15} &=& R_0 \\ R'_{15} &=& L_0 \end{eqnarray}

dimostrando che l'output, dopo i 16 round, dell'algoritmo di decifrazione è identico all'input della funzione di cifrazione e quindi la correttezza del sistema crittografico.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License