# Linear Feedback Shift Register (LFSR) Stream Ciphers

A linear feedback shift register (LFSR) is a type of digital circuit that has several storage areas, each of which can hold 1 bit, connected in a chain. The output of each storage area is connected to the input of the next storage area in the chain, resulting in a circuit that shifts the data stored in it one place to the right each time the circuit is run. The way the storage areas are connected varies from circuit to circuit, and each configuration will change the pattern in which the bits move from one storage area to the next.

LFSRs have many important uses in digital communication, not just in cryptography. They are used in TV broadcast signals, data transfer via USB cable, and GPS navigation. LFSR circuits are still used to encrypt GSM cell phone signals, despite having serious security issues.

To learn more about how LFSR's work, watch the 10-minute video below.

In this course, we will not use actual circuits to generate the pseudo-random keystream of bits, but first generate them by hand using the system described in the video, and later with Python code.

# LFSR Stream Cipher

Let's encrypt the message `C3P0`

using a 4-bit LFSR with seed `0110`

and definition: $b_4 \leftarrow b_1' + b_2' + b_4'$

The first step is to convert the Base64 string to binary:

```
Base64 plaintext: C3P0
binary plaintext: 000010 110111 001111 110100
```

Next, compute the output stream of the LFSR so there are as many bits as needed for the message. In this case, 24.

$b_4$ | $b_3$ | $b_2$ | $b_1$ |
---|---|---|---|

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

`0` |
`1` |
`1` |
`0` |

`1` |
`0` |
`1` |
`1` |

`1` |
`1` |
`0` |
`1` |

Looking at the right-most column, you obtain the bitstream:

`011011 011011 011011 011011`

Performing the XOR Cipher on these keystreams:

$$ \begin{array}{r} \texttt{000010 110111 001111 110100} \\ \oplus\text{ } \texttt{011011 011011 011011 011011} \\ \hline \texttt{011001 101100 010100 101111} \end{array} $$Which when converted back to Base64 plaintext yields `ZsUv`

To decipher a LFSR Stream cipher, you need to perform a bitwise subtraction of the keystream fromt he ciphertext binary stream. Fortunately, bitwise subtraction is identical to bitwise addition, so you simply use the XOR operation again.

```
Base64 ciphertext: ZsUv
binary ciphertext: 011001 101100 010100 101111
```

Using the same binary keystream: `011011 011011 011011 011011`

Which converts back to the Base64 plaintext: `C3P0`

## Maximizing Period of Repeating Streams

You may have noticed that in the previous example, the number of bits and the rules associated with those bits resulted in a less than ideal sequence of bits. In fact, the sequence generated was no better than a Caesar cipher, since bit $b_1$ left the pattern `011`

repeating over and over, resulting in the values `011011`

aligned over each character.

When using a LFSR Stream to encipher a message, you should try a few rule configurations to make sure that the bitstream isn't too predictable. As a general rule, if your LFSR system uses $n$ bits, there is a rule system that will result in the bitstream not repeating itself for $2^n - 1$ bits. You wouldn't want to always use the same rule, because that would be too predictable for an eavesdropper to guess, but you should attempt to ensure that the bitstream does not repeat itself during the string used for enciphering the message.

The table below shows a selection of rules for different size LFSR systems that result in a maximum period, which is the number of bits before the pattern repeats.

Bits ($n$) | Definition | Period $$ ( 2^n-1 ) $$ |
---|---|---|

2 | $$b_2 \leftarrow b_1' + b_2'$$ | 3 |

3 | $$b_3 \leftarrow b_1' + b_2'$$ | 7 |

4 | $$b_4 \leftarrow b_1' + b_2'$$ | 15 |

5 | $$b_5 \leftarrow b_1' + b_3'$$ | 31 |

6 | $$b_6 \leftarrow b_1' + b_2'$$ | 63 |

7 | $$b_7 \leftarrow b_1' + b_2'$$ | 127 |

8 | $$b_8 \leftarrow b_1' + b_3' + b_4' + b_5'$$ | 255 |