Cryptography Reference
In-Depth Information
Naturally, a clever code writer would truncate the fixed part of this beginning,
but that doesn't matter much. One of the most effective compression meth-
ods, the Ziv - Lempel - Welch compression, creates tables listing the strings in
parallel to the text read. Instead of these strings, only the number of the table
entry appears in the text. When building the tables, these numbers cannot be
arbitrarily large at the beginning; their possible upper limit grows by 1 with
each step. This means that you can't decompress any arbitrary byte sequence
(in contrast to encryption methods that are supposed to always diligently 'deci-
pher' nonsense). So we can make an assumption for the first character and,
using this assumption, consider the probable substitutions for the second char-
acter. Not all of them will produce compressed text; we will discard those.
Next, we look at possible remaining substitutions for the third character, and
so on. We might get stuck proceeding like this, however. If we do, we must
have made a mistake in one of the previous steps. We go back a step and start
over again from there, using the next possibility. This is like systematically
running around in a labyrinth with a very special structure, the
tree structure
.
Sloppy programming would cost us huge amounts of computing power for such
a search (as we have seen in the
subscrack
example). In practice, however, we
would discard more and more possibilities as we penetrate this labyrinth. At
some point along the road, there will only be a few alleys left; one of them leads
to the light. Now the key is known. And mind you, we didn't need one single
character from the plaintext! Experience has shown that, using appropriate
Figure 2.1:
Successful search in a tree structure.
