Cryptography and computer security - Tutorial 27.10.2020

Linear feedback shift registers (LFSR)

Example:

• \(z_{i+4} = z_{i+3} + z_i\)
• \(z_{i+n} = \sum_{j=0}^{n-1} c_j z_{i+j}\)
• \(0 = -z_{i+n} + \sum_{j=0}^{n-1} c_j z_{i+j}\)
• \(C(x) = -1 + \sum_{j}^{n-1} c_j x^{n-j}\) connection polynomial

Exercise 1

Check that the polynomial \(C(x) = 1 + x + x^4\) is irreducible over \(\mathbb{Z}_2\). Is it also primitive over \(\mathbb{F}_{2^4}\)?

\(C(x) = A(x) B(x)\)

• irreducible polynomials of degree \(1\) over \(\mathbb{Z}_2\): \(x\), \(x+1\)
• irreducible polynomials of degree \(2\) over \(\mathbb{Z}_2\): \(x^2 + x + 1\)

  (x^4 + x + 1) / (x^2 + x + 1) = x^2 + x
- (x^4 + x^3 + x^2)
   x^3 + x^2 + x + 1
- (x^3 + x^2 + x)
                   1

Hence, \(C(x)\) is irreducible over \(\mathbb{Z}_2\).

• \(2^4 - 1 = 15 = 5 \cdot 3\) non-zero elements of \(\mathbb{F}_{2^4}\).
• \(C(x)\) is primitive over \(\mathbb{F}_q\) if the lowest \(t\) such that \(C(x)\) divides \(x^t - 1\) equals \(q^d - 1\), where \(d\) is the degree of \(C(x)\).

  (x^5 + 1) / (x^4 + x + 1) = x
- (x^5 + x^2 + x)
   x^2 + x + 1
   
  (x^15 + 1) / (x^4 + x + 1) = ...

\(C(x)\) is primitive over \(\mathbb{F}_{2^4}\).

Exercise 2

Generate output sequences for an LFSR of degree \(4\) with connection polynomial \(C(x)\) and all possible initial states. What are their periods?

0|0|0|0|0|0|0|0|0|...        period 1
000111101011001|0001         period 15

Exercise 3

Determine all possible periods of LFSRs defined by the equations

1. \(s_{i+3} = (s_i + s_{i+1} + s_{i+2}) \bmod{2}\),
2. \(s_{i+4} = (s_i + s_{i+1} + s_{i+2} + s_{i+3}) \bmod{2}\),
3. \(s_{i+4} = (s_i + s_{i+1} + s_{i+2} + s_{i+3}) \bmod{5}\),
4. \(s_{i+4} = (s_i + s_{i+1} + s_{i+2} + s_{i+3}) \bmod{10}\).

1. ​​​0|000           period 1
   ​​​0011|001        period 4
   ​​​01|010          period 2
   ​​​1|111           period 1
   

   \(C_1(x) \equiv 1 + x + x^2 + x^3 \equiv (1 + x) (1 + x^2) \equiv (1 + x)^3 \pmod{2}\)

2. ​​​0|0000            period 1
   ​​​00011|0001        period 5
   ​​​00101|0010        period 5
   ​​​01111|0111        period 5
   

   \(C_2(x) \equiv 1 + x + x^2 + x^3 + x^4 \pmod{2}\)

   ​​​​  (x^5 + 1) / (x^4 + x^3 + x^2 + x + 1) = x + 1
   ​​​​- (x^5 + x^4 + x^3 + x^2 + x)
   ​​​​         x^4 + x^3 + x^2 + x + 1
   ​​​​      - (x^4 + x^3 + x^2 + x + 1)
   ​​​​                               0
   

   \(C_2(x)\) is not primitive over \(\mathbb{F}_{2^4}\).

Exercise 4

Determine whether an LFSR of degree \(4\) can generate sequences

1. \(1011010000101\dots\) and
2. \((011101110)^*\).

Exercise 5

Find an LFSR of degree \(4\) that generates the sequence \(10101100\).

Shannon theory

Exercise 6

Prove that a cryptosystem has perfect secrecy if and only if

\[ P(Y = y \mid X = x_1) \ = \ P(Y = y \mid X = x_2) \]

for all \(x_1, x_2 \in \mathcal{P}\) and \(y \in \mathcal{C}\).

Exercise 7

Consider a cryptosystem in which \(\mathcal{P} = \lbrace a, b \rbrace\), \(\mathcal{K} = \lbrace k_1, k_2, k_3 \rbrace\) and \(\mathcal{C} = \lbrace 1, 2, 3 \rbrace\). Suppose that keys are chosen with probabilities \(P(K = k_1) = 1/2\), \(P(K = k_2) = P(K = k_3) = 1/4\), and plaintexts are chosen with probabilities \(P(X = a) = 1/4\), \(P(X = b) = 3/4\). The encryption matrix is as follows:

1. Compute the probability measures on the ciphertext, i.e., \(P(Y = y)\) for all \(y \in \mathcal{C}\).
2. Prove that this cryptosystem does not provide perfect secrecy.
3. Modify the plaintext and/or key distributions in such a way that perfect secrecy is obtained.

Exercise 8

Prove that the affine cipher over \(\mathbb{Z}_{26}\) achieves perfect secrecy if every key is used with equal probability \(1/312\).