A Feistel network, named after IBM researcher Horst Feistel (1915–1990), is an important structure often used in the design of symmetric-key ciphers known as block ciphers. A block cipher encrypts binary data in (relatively large) fixed-length chunks called blocks. For a block cipher based on the Feistel network structure, the block size must be even, i.e., equal to $2n$, where $n$ is a positive integer.
As is the case for many block ciphers, a Feistel network block cipher encrypts its input block (the plaintext) to produce an output block (the ciphertext) by repeatedly applying a simpler encryption step called a round. (The number of round iterations is chosen by the cipher designer(s) to balance various criteria such as security and speed.) A single round takes in a block and outputs a block, i.e., it maps $\{ 0,1\} ^{2n}$ to $\{ 0,1\} ^{2n}$, where $\{ 0,1\} ^ b$ denotes the set of all $b$-bit vectors. Internally, a round makes use of a round function, $f$, that maps $\{ 0,1\} ^{n}$ to $\{ 0,1\} ^{n}$, i.e., $f$ operates on half blocks. Here is what happens in a single round:
$f$ is applied to the right half of the input block
the resulting output of $f$ is combined with the left half of the input block via bitwise XOR ($\oplus $)
the right half of the output block is the the $n$-bit vector produced by this XOR operation
the left half of the output block is a copy of the right half of the input block
Symbolically, if the $2n$-bit round input is denoted $(x,y)$, where $x$ is the left half and $y$ is the right half, then the round output is $(y, x \oplus f(y))$.
The properties of a Feistel network block cipher depend critically on the choice of the round function, $f$, for which there are many options, but we will make a simplifying assumption: the round function is just multiplication of its $n$-bit input with a fixed $n \times n$ binary matrix, $M$.^{1} Note that all values are restricted to $\{ 0,1\} $, so any intermediate integer produced during vector-matrix multiplication (or matrix-matrix multiplication) must be reduced $(\mathrm{mod}~ 2)$. For example,
\[ (1 \, \ 0 \, \ 1 \, \ 1) \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} \ = \ (1 \, \ 1\, \ 0\, \ 1) \]The order of an $n \times n$ matrix $M$ is the smallest positive integer $m$ such that $M^ m = I_ n$, where $I_ n$ is the $n \times n$ identity matrix, and $M^ m$ denotes $M$ multiplied by itself $m$ times.
All of this leads to a very interesting question. Given the order $m \geq 1$ of the matrix $M$ used in the round function, will the cipher become the identity mapping after a finite number of rounds, and, if so, what is the minimum number of rounds required to make this happen? A cipher is the identity mapping if every plaintext encrypts to itself. For example, if $m=2$, Figure $1$ shows that the Feistel network cipher we have described becomes the identity mapping after $6$ rounds (since the plaintext, $(x,y)$, is always equal to the ciphertext).
The input consists of a single positive integer, $m$ $(m \leq 40)$, the order of the matrix $M$ used in the round function of the Feistel network block cipher described above.^{2}
Output a single positive integer, the minimum number of rounds required for the cipher to become the identity mapping. For the values of $m$ under consideration, this is guaranteed to happen after a finite number of rounds.
Sample Input 1 | Sample Output 1 |
---|---|
1 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
2 |
6 |
Footnotes