Cryptography Reference
In-Depth Information
a subset of the register cells (i.e., if any only if it can be realized by XOR gates). An
exemplary LFSR is illustrated in Figure 10.14. In this example, three register cells
are added modulo 2 and fed from the left into the register.
LFSRs have the advantage that they are mathematically structured and can be
studied and formally analyzed accordingly. To study and formally analyze an
n
-cell
LFSR, one usually expresses its state as a polynomial
a
(
x
)=
a
n−
1
x
n−
1
+
...
+
a
1
x
1
+
a
0
of degree
n
−
1 in
F
2
[
x
], and its feedback coefficients as another polynomial
c
(
x
)=
c
n
x
n
+
c
n−
1
x
n−
1
+
...
+
c
1
x
1
+
c
0
of degree
n
in
F
2
[
x
]. One then looks at
F
2
[
x
]
c
—that is, the ring of polynomials with
degree less than or equal to
n
−
1 and the two operations addition and multiplication
modulo
c
(
x
).Thisringhas2
n
elements and is a (finite) field if and only if
c
(
x
)
F
2
[
x
]
c
is the multiplicative
is irreducible over
F
2
(see Section 3.3.6). In this case,
F
2
[
x
]
c
and has 2
n
group of
1 elements. This is the algebraic structure of choice
to study and formally analyze LFSRs (e.g., [20]). Note, however, that the output of
an LFSR should never be directly used as a key stream. Otherwise, one can use the
Berlekamp-Massey algorithm (see Section 9.1) to reconstruct the entire key stream
using only very few known key stream bits.
In 1987, Rivest proposed an additive stream cipher that is based on an entirely
different design paradigm (than LFSRs) and that has been widely deployed in many
commercial applications, including, for example, Microsoft Windows and Oracle
SQL. More importantly, the stream cipher is used in the
Wired Equivalent Privacy
(WEP) protocol used in many wireless networks, as well as the SSL and TLS
protocols used on the Web (see, for example, Chapter 6 of [21] for an overview
and discussion of the SSL/TLS protocol). The stream cipher was named
RC4
36
and
is currently one of the most widely deployed stream ciphers. The design of RC4
was kept (and is still being kept) as a trade secret of RSA Security, Inc.
37
In 1994,
however, the source code of an RC4 implementation was anonymously posted to
the Cypherpunks mailing list. The correctness of this unofficial posting was later
confirmed by comparing its outputs to those produced by licensed implementations.
Because the RC4 stream cipher is treated as a trade secret, the algorithm that was
−
36
The acronym RC stands for “Ron's Code.” Note that RC2, RC5, and RC6 are block ciphers that are
not closely related to RC4.
37
http://www.rsasecurity.com
