Mount Allison Programming Showdown 2019

Start

2019-03-16 16:00 UTC

Mount Allison Programming Showdown 2019

End

2019-03-16 21:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -219 days 14:22:01

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Feistel Fun

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:

  1. $f$ is applied to the right half of the input block

  2. the resulting output of $f$ is combined with the left half of the input block via bitwise XOR ($\oplus $)

  3. the right half of the output block is the the $n$-bit vector produced by this XOR operation

  4. 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).

\includegraphics[width=0.6\textwidth ]{6rounds}
Figure 1: When $m=2$, the cipher becomes the identity mapping after $6$ rounds

Input

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

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

  1. Anyone familiar with symmetric-key cryptography knows that using matrix multiplication for $f$ is a really bad idea, but our goal here is the creation of an interesting programming competition problem, not a cryptographically strong cipher. Such a person will also notice that we are completely ignoring keys.
  2. As an assurance that we are not dealing with non-existent mathematical objects, note that it is not hard to prove that whenever $n \geq m$, there exist $n \times n$ binary matrices of order $m$.