Turing and Reverse - Disappearing Cryptography - page 129

Whoopee Tie Yi Yay
Why spend your grief on a future that's wrecked
Whoopee Tie Yi Yay
Why look backward when hindsight is always so perfect.
8.2 Running Backward
The song that introduces this chapter is all about what happens to a
man when he finds a way to play the country music on his jukebox
backward. His dog walks, his girlfriend returns, and the money rolls
in. The goal of this chapter is to build a machine that hides data as it
runs forward. Running it in reverse allows you to recover it. Themain
advantage of using such a machine is that some theoretical proofs
show that this machine can't be attacked by a computer. These the-
oretical estimates of the strength of the system are not necessarily
reliable for practical purposes, but they illustrate a very interesting
potential.
Chapter 7 describedhow to use grammars tohide data in realistic-
sounding text. The system derived its strength from the structure of
the grammars and their ability to produce many different sentences
from a simple collection of inputs. The weaknesses of the system
were also fairly apparent. Grammars that were context-free could not
really keep track of scores of ballgames or other more complicated
topics. They just produced sentences with no care for the context.
A bit of cleverness could go a long way, but anyone who has tried to
create complicated grammars begins to understand the limitations
of the model.
This chapter will concentrate on a more robust and complete
model known as the Turing machine , a concept was named after Alan
Turing, who created it in the 1930s as a vehicle for exploring the lim-
its of computation. Although the model doesn't offer a good way to
whip up some good mimicry, it does offer a deeper theoretical look
at just how hard it may be to break the system.
A good way to understand the limits of context-free grammars is
to examine the type of machine that is necessary to recognize them.
When testing this, I built a parser for recovering the data from the
mimicry using a model of a push-down automata . The automata
refers to a mechanism that is a nest of if-then and goto statements.
The push-down refers to the type of memory available to it—in this
case a push-down stack that can store information by pushing it onto
a stack of data and retrieve it by pulling it off. Many people compare
this to the dishracks that are found in cafeterias. Dishes are stored in
a spring-loaded stack. The major limitation of this type of memory is