In short, modular arithmetics are arithmetics in a finite field.
Now, let’s take a look at another cipher that works with a finite field of values (also known as a Galois field).
This cipher, however, does not always produce the same values given the same input, like shifting does.
Its purpose is to produce a stream of keys used to encrypt another stream.
Like a snake eating its own tail (a symbol often used for eternity), linear feedback shift registers work by feeding on their own output.
They are constructed in a way that makes them endlessly cycle through a pattern of values while outputting that seemingly random pattern.
The seed and all the outputted values are binary, meaning they get values 0 or 1.
The way new values are created is by using a logical operator, usually exclusive or (XOR).
Logical Gate XOR.
To describe this in a practical way, lets start looking at what we need to create a LFSR.
We need a seed, which is a list of ones and zeros.
The seed will be what we start shifting.
In addition to our seed (or shift register) we have a collection of taps.
The taps tell us which parts of the register we use when feeding back into it.
Say that we have a seed 001 and two taps, 1 and 3.
This means that when we start shifting, the new value will be a combination of the first and third numbers of the seed, 0 and 1.
We use an operation called exclusive or to combine the two.
0 xor 1 gives 1.
Since we are working with binary values, the feedback from our taps can be expressed as a polynomial in modulo 2.
The feedback polynomial from taps 3 and 1.
So, if our shift register is 001 and we get a new value, 1, we insert it in the beginning and drop the last number out.
Our new shift register state is now 100.
We continue this shifting until we notice that our shift register has returned to it’s initial state, 001.
Depending on the seed and taps we select, we can get loops of different lengths.
A loop is called maximal length if it passes through all possible different combinations before reaching its original state.
Since we’re using the binary system, the maximal length of a loop will be 2^n-1.
The loop can also end up leaving its original state and getting stuck in a shorter loop within, never returning to its original state.
Finding the seeds and taps that lead to a maximal-length cycle is essential.
Some of the criterions for finding these taps is that the number of taps must be even and that the taps are setwise co-primes, meaning that they have no common divisor except 1.
Wait, that doesn’t seem so random!.Wouldn’t a cycle like that be pretty easy to crack?.The thing about shift registers is that they get pretty long, pretty quickly.
Say we choose a seed of 20 bits and a tap of two values, 2 and 19.
The length of the loop produced is 1 048 575, meaning we would get quite a large amount of seemingly random binary values.
Linear Feedback Shift Register in Python3.
The flavour of LFSR we have briefly gone through is called Fibonacci LFSR.
There are also other variations, in which the way the register is shifted differs.
They all work to produce a pseudorandom stream of bits used to encrypt streams.
The range of applications for this type of encryption ranges from bluetooth to GSM (cellphone communication) standards.
In ConclusionAs a programmer, learning about the concept of modular arithmetics and division opens new ways in thinking about everyday coding problems.
However, in security-critical projects using ready-made systems and standards for encryption is always recommended, since specialists in the field of cryptography probably find a safer and more effective solution than an enthusiastic hobbyist.
Sources:Algebraic Structures in Cryptography by V.
NiemiTutorial on Linear Feedback Shift Registers by EETimesEncyclopedia of Cryptography and Security by Anne Canteout.