Cryptography Reference
In-Depth Information
abused my power. -
Casanova, 1757, as quoted by David
Kahn in
The Codebreakers
.
[Kah67]
The grammar relies heavily on the structure of the baseball game
to give form to the final output. The number of balls, strikes, and
outs are kept accurately because the grammar was constructed care-
fully. The number of runs, on the other hand, is left out because the
grammar has no way of keeping track of them. This is a good illus-
tration of what the modifier “context-free” means. The productions
applied to a particular variable do not depend on the context that
surrounds the variable. For instance, it doesn't matter in the basic
example whether Fred or Barney is fishing or bowling. The decision
on whether it is done in Minnesota or Iowa is made independently.
The baseball grammar that generated Figure 7.1 uses a separate
variable for each half-inning. One half-inning might end up produc-
ing a collection of sentences stating that everyone was hitting home
runs. That information and its context does not affect the choice of
productions in the next half-inning. This is just a limitation enforced
by the way that the variables and the productions were defined. If
the productions were less arbitrary and based onmore computation,
even better text could be produced.
1
Several other grammars live on at
spammimic.com
.Themainver-
sion will encode a message with phrases grabbed from the flood of
spam pouring into our mailboxes. Figure 7.2 shows some of the re-
sults.
7.2.2 Parsing and Going Back
Hiding information as sentences generated from a particular gram-
mar is a nice toy. Recovering the data from the sentences turns the
parlor game into a real tool for transmitting information covertly.
The reverse process is called
parsing
and computer scientists have
studied it extensively. Computer languages like C are built on a
context-free grammar. The computer parses the language to under-
stand its instructions. This chapter is only interested in the process
of converting a sentence back into the list of bits that led to its pro-
duction.
Parsing can be complex or easy. Most computer languages are de-
signed to make parsing easy so the process can be made fast. There
is no reason why this can't be done with mimicry as well. You can al-
ways parse the sentence from any context-free grammar and recover
1
It is quite possible to create a more complex grammar that does a better job of
encoding the score at a particular time, but it won't be perfect. It will do a better job,
but it won't be exactly right. This is left as an exercise.
