Notes - Computer Security MT24, Feistel structures
Flashcards
@Prove that the function
\[\mathbf{Round}\langle x, y\rangle = \langle y, F(y) \oplus x\rangle\]
is invertible with inverse
\[\mathbf{Round}^{-1}\langle x', y'\rangle = \langle F(x') \oplus y', x'\rangle\]
where $F$ is an arbitrary (hopefully confusing) function, and explain why this is useful.
\[\begin{aligned}
\mathbf{Round} \circ \mathbf{Round}^{-1}\langle x', y'\rangle &= \mathbf{Round} \langle F(x') \oplus y', x'\rangle \\\\
&= \langle x', F(x') \oplus F(x') \oplus y'\rangle \\\\
&= \langle x', y' \rangle
\end{aligned}\]
\[\begin{aligned}
\mathbf{Round}^{-1} \circ \mathbf{Round}\langle x, y\rangle &= \mathbf{Round}^{-1}\langle y, F(y) \oplus x \rangle \\\\
&= \langle F(y) \oplus F(y) \oplus x, y \rangle \\\\
&= \langle x, y \rangle
\end{aligned}\]
This is useful because it forms the basis for Feistel structures. If $F$ is a mangler function which mixes up its inputs, then this gives a function which mixes up its inputs but is still invertible.
Suppose $m$ is some plaintext you wish to encrypt and $F(K _ i, X _ i)$ is a mangling function which takes a subkey/round key and a message to mangle. Describe how a Feistel structure works.
To encrypt:
- Split plaintext $m$ into two halves $L _ 0 \parallel R _ 0 = m$.
- Iterate through $r$ rounds:
- $L _ {n+1} = R _ n$
- $R _ {n+1} = F(K _ {n+1}, R _ n) \oplus L _ n$
- Output: $R _ r \parallel L _ r$.
To decrypt:
- Split ciphertext $c$ into two halves $L’ _ 0 \parallel R _ 0’ = c$.
- Iterate through $r$ rounds:
- $L’ _ {n+1} = R’ _ n$
- $R’ _ {n+1} = F(K _ {r - n}, R’ _ n) \oplus L’ _ n$ (note that $K$ has changed!)
- Output: $R _ r \parallel L _ r$.
So encryption is the same as encryption, except the subkeys are in reverse order.