[ Pobierz całość w formacie PDF ]
registers with hundreds of registers. Lemma 10.4 shows that, from the point
41
of view of a determined, well equipped and technically competent opponent,
cryptographic systems based on such registers are the equivalent of leaving
your house key hidden under the door mat. Professionals say that such
systems seek `security by obscurity'.
However, if you do not wish to ba e the CIA, but merely prevent little
old ladies in tennis shoes watching subscription television without paying for
it, systems based on linear feedback registers are cheap and quite e ective.
Whatever they may say in public, large companies are happy to tolerate a
certain level of fraud. So long as 99.9% of the calls made are paid for, the
pro ts of a telephone company are essentially una ected by the .1% which
`break the system'.
What happens if we try some simple tricks to increase the complexity of
the cypher text stream.
Lemma 10.5. If xn is a stream produced by a linear feedback system of
length N with auxiliary polynomial P and yn is a stream produced by a linear
feedback system of length N with auxiliary polynomial Q then xn + yn is a
stream produced by a linear feedback system of length N + M with auxiliary
polynomial P(X)Q(X).
Note that this means that adding streams from two linear feedback system
is no more economical than producing the same e ect with one. Indeed the
situation may be worse since a stream produced by linear feedback system of
given length may, possibly, also be produced by another linear feedback system
of shorter length.
Lemma 10.6. Suppose that xn is a stream produced by a linear feedback
system of length N with auxiliary polynomial P and yn is a stream produced
by a linear feedback system of length N with auxiliary polynomial Q. Let P
have roots , , : : : and Q have roots , , : : : over some eld
1 2 N 1 2 M
K F2 . Then xnyn is a stream produced by a linear feedback system of length
NM with auxiliary polynomial
Y Y
(X ; ):
i j
1 i N 1 i M
We shall probably only prove Lemmas 10.5 and 10.6 in the case when all
roots are distinct, leaving the more general case as an easy exercise. We
Q Q
shall also not prove that the polynomial (X ; ) obtained
i j
1 i N 1 i M
in Lemma 10.6 actually lies in F2 but (for those who are familiar with the
phrase in quotes) this is an easy exercise in `symmetric functions of roots'.
Here is an even easier remark.
42
Lemma 10.7. Suppose that xn is a stream which is periodic with period N
and yn is a stream which is periodic with period M. Then the streams xn + yn
and xnyn are periodic with periods dividing the lowest common multiple of N
and M.
Exercise 10.8. One o f the most con dential German codes (called FISH by
the British) involved a complex mechanism which the British found could be
simulated by two loops of paper tape o f length 1501 and 1497. If kn = xn + yn
where xn is a stream of period 1501 and yn is stream of period 1497 what is
the longest possible period of kn. How many consecutive values of kn do you
need to to specify the sequence completely.
It might be thought that the lengthening of the underlying linear feed-
back system obtained in Lemma 10.6 is worth having but it is bought at a
substantial price. Let me illustrate this by an informal argument. Suppose
we have 10 streams xj n (without any peculiar properties) produced linear
Q
10
feedback registers of length about 100. If we form kn = xj n then the
j=1
Berlekamp-Massey method requires of the order of 1020 consecutive values of
kn and the periodicity of kn can be made still more astronomical. Our cypher
key stream kn appears safe from prying eyes. However it is doubtful if the
prying eyes will mind. Observe that (under reasonable conditions) about 2;1
Q
10
of the xj n will have the value 1 and about 2;10 of the kn = xj n will
j=1
have value 1. Thus if zn = pn + kn, in more than 999 cases out of a 1000 we
will have zn = pn. Even if we just combine two streams xn and yn in the way
suggested we may expect xnyn =0 for about 75% of the time.
Here is another example where the apparent complexity of the cypher key
stream is substantially greater than its true complexity.
Example 10.9. The following is a simpli ed version of a standard satel-
lite TV decoder. We have 3 streams xn, yn, zn produced by linear feedback
registers. If the cypher key stream is de ned by
kn =xn if zn =0
kn =yn if zn =1
then
kn =(yn + xn)zn + xn
and the cypher key stream is that produced by linear feedback register.
It might be thought that the best way round these di culties is to use a
non-linear feedback generator f. This is not the easy way out that it appears.
43
If chosen by an amateur the complicated looking f so produced will have the
apparent advantage that we do not know what is wrong with it and the very
real disadvantage that we do not know what is wrong with it.
Another approach is to observe that, so far as the potential code breaker
is concerned, the cypher stream method only combines the `unknown secret'
(here the feedback generator f together with the seed (k0 k1 : : : kd;1)) with
the unknown message p in a rather simple way. It might be better to consider
a system with two functions F : Fm Fn ! Fq and G : Fm Fq ! Fn . such
2 2 2 2 2 2
that
G(k F(k p)) = p:
Here k will be the shared secret, p the message z = F(k p) the encoded
message we can be decoded by using the fact that G(k z) = p.
In the next section we shall see that an even better arrangement is pos-
sible. However, arrangements like this have the disadvantage that the the
message p must be entirely known before it is transmitted and the encoded
message z must have been entirely received before in can be decoded. Stream
ciphers have the advantage that they can be decoded `on the y'. They are
also much more error tolerant. A mistake in the coding, transmission or
decoding of a single element only produces an error in a single place of the
[ Pobierz całość w formacie PDF ]