Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 2 Solutions - Ex2.7

Monday. 18 December 2017 - 2 mins

Exercise 2.7

Compute the first two output bytes of the LFSR of degree 8 and the feedback polynomial from Table 2.3 where the initialization vector has the value FF in hexadecimal notation.

Note: The polynomial referred to is $x^8 + x^4 + x^3 + x + 1$.

Solution

This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

This LFSR derived from this polynomial can be visualised as such:

LFSR

The sequence generated by $FF_{16}$, which is $11111111_2$, is as follows:

$\begin{array}{c c c c c c c c|c} s_7 & s_6 & s_5 & s_4 & s_3 & s_2 & s_1 & s_0 & \text{Output} \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}$

The resulting first two output bytes are $1001000011111111_2 = {90FF}_{16}$.

Previous Exercise Next Exercise

Thomas Busby

I write about computing stuff