Cryptography Reference
In-Depth Information
that's of no interest to anybody anymore. We will see further below how the
algorithm can be cracked in a flash.
Apart from these dubious circumstances and the fact that A5 is one of the
encryption algorithms most frequently used in the world, this algorithm repre-
sents an encryption class we haven't dealt with in this topic yet: stream ciphers
using
LFSRs
(
Linear Feedback Shift Registers
). This impressive name hides
a rather simple method.
A
shift register
is nothing more than a memory location with
n
bits, where
n
does not have to be a power of 2; it can be an 'odd' number, for example, 9,
23, or 47. A special piece of hardware allows you to shift all bits concurrently
by one position to the left and to fill the least significant bit with a given value.
It would look like this in C:
|
R = (R << 1)
b
where
R
is a data type with
n
bits, and
b
is a value with all of its bits equal
to 0, except perhaps the least significant bit. Registers of microprocessors can
be shifted. However, microprocessors handle other tasks, too; conversely, shift
registers are specialized and particularly fast pieces of hardware.
Linear functions
on a shift register are defined exactly as at the beginning of
Section 4.4.4: some bits are chosen from the register and XORed.
Feedback
means that, in a shift, the least significant bit of the shift register is the result
of a linear function on that register. The most significant bit of the register
pushed out on the left is reused. Figure 5.22 shows how this process works.
(The shift could just as well run from left to right, and use the least significant
bit; the names are arbitrary.) The positions of the bits that 'participate' in the
output
feedback
XORing single bits
Figure 5.22:
A 10-bit shift register with linear feedback (LFSR).
