Feistel Cipher

Tags

cryptography

Is a [see page 18, theoretical-model] for a block cipher based on the idea of the repeated application of reversible rounds.

Rounds

Each [see page 16, round] has the same general format. For each round with input block \( {L}_{j-1}, {R}_{j-1} \) we produce the output:

\begin{align*} {L}_{j} &= {R}_{j-1} \
{R}_{j} &= {L}_{j-1} \xor f({R}_{j-1}, {K}_{j}) \
\end{align*}

With \( k_j \) being the subkey for the current round and \( f \) being some function.

Note: Each round [see page 16, swaps] the halves of the input. The left output depends on the right input and the right output depends on both inputs.

After all the rounds are finished we perform one final swap of the output blocks, just to make decryption more straightforward.

Single Round Completeness Proof

Observe that in a [see page 18, single-round] system with the input \( (L_0, R_0) \) we output \((R_0, L_1)\) where \[ L_1 = L_0 \xor f(R_0, K_0) \] which is subsequently swapped to lead to final-output of \( (L_1, R_0) \).

We can now send this output (\( (L_1, R_0) \)) back through the same round to get \( (R_0, L_{\lambda}) \) where:

\begin{align*} L_{\lambda} &= L_1 \xor f(R_0, K_0) \\

    &= L\_0 \xor f(R\_0, K\_0) \xor f(R\_0, K\_0) \\\\
    &= L\_0 \\\\

\end{align*}

As shown in figure 1. Observe that \( f(R_0, K_0) \) receives the arguments in both these cases (because we're using the same input with the same keys) and thus produces the same output. Thus XORing of the same values cancels out leaving the original input \( L_0 \) unchanged. Meaning we've essentially undone (decrypted) our encryption.

This property of sending the output of a series of rounds back through the same rounds, with the same keys in reverse, undoes the encryption and can extend to an [see page 24, arbitrary] number of rounds through induction.

Of course this same completeness proof extends to multiple rounds as well.