Compute the first 50 terms of the recurrence

The initial values are $0\text{,}1\text{,}0\text{,}0\text{,}0$.

SOLUTION

The vector of coefficients is $[1\text{,}0\text{,}1\text{,}0\text{,}0]$ and the initial values are given by the vector $[0\text{,}1\text{,}0\text{,}0\text{,}0]$. Type

>> lfsr([1 0 1 0 0],[0 1 0 0 0],50)

ans =
   Columns 1 through 12
    0   1   0   0   0   0   1   0   0   1   0   1
   Columns 13 through 24
    1   0   0   1   1   1   1   1   0   0   0   1
   Columns 25 through 36
    1   0   1   1   1   0   1   0   1   0   0   0
   Columns 37 through 48
    0   1   0   0   1   0   1   1   0   0   1   1
   Columns 49 through 50
    1   1

Suppose the first 20 terms of an LFSR sequence are 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1. Find a recursion that generates this sequence.

SOLUTION

First, we find a candidate for the length of the recurrence. The command lfsrlength(v, n) calculates the determinants mod 2 of the first $n$ matrices that appear in the procedure described in Section 5.2 for the sequence $v$. Recall that the last nonzero determinant gives the length of the recurrence.

>> lfsrlength([1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1],10)
    Order Determinant
       1        1
       2        1
       3        0
       4        1
       5        0
       6        1
       7        0
       8        0
       9        0
      10        0

The last nonzero determinant is the sixth one, so we guess that the recurrence has length 6. To find the coefficients:

>> lfsrsolve([1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1],6)

ans =
    1  0  1  1  1  0

This gives the recurrence as

The ciphertext 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0 was produced by adding the output of a LFSR onto the plaintext mod 2 (i.e., XOR the plaintext with the LFSR output). Suppose you know that the plaintext starts 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0. Find the rest of the plaintext.

SOLUTION

XOR the ciphertext with the known part of the plaintext to obtain the beginning of the LFSR output:

>> x=mod([1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0]+[0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1],2)

x =
   Columns 1 through 12
    1   0   0   1   0   1   1   0   1   0   0   1
   Columns 13 through 17
    0   1   1   0   1

This is the beginning of the LFSR output. Let’s find the length of the recurrence:

>> lfsrlength(x,8)
    Order  Determinant
      1         1
      2         0
      3         1
      4         0
      5         1
      6         0
      7         0
      8         0

We guess the length is 5. To find the coefficients of the recurrence:

>> lfsrsolve(x,5)

ans =
    1   1   0   0   1  

Now we can generate the full output of the LFSR using the coefficients we just found plus the first five terms of the LFSR output:

>> lfsr([1 1 0 0 1],[1 0 0 1 0],40)

ans =
   Columns 1 through 12
    1   0   0   1   0   1   1   0   1   0   0   1
   Columns 13 through 24
    0   1   1   0   1   0   0   1   0   1   1   0
   Columns 25 through 36
    1   0   0   1   0   1   1   0   1   0   0   1
   Columns 37 through 40
    0   1   1   0

When we XOR the LFSR output with the ciphertext, we get back the plaintext:

>> mod(ans+[0 1 1 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0],2)

ans =
   Columns 1 through 12  
    1   1   1   1   1   1   0   0   0   0   0   0
   Columns 13 through 24
    1   1   1   0   0   0   1   1   1   1   0   0
   Columns 25 through 36
    0   0   1   1   1   1   1   1   1   0   0   0
   Columns 37 through 40
    0   0   0   0

This is the plaintext.