Cryptography Reference
In-Depth Information
running on everyone's computer would be able to read in a Turing
machine and run it forward or backward. If you wanted to send a
message, you would pack in the data and run the machine until it
stopped. The result would be the output, perhaps some computer-
generated poetry, and a pile of waste data that must be kept around
in order to run the machine in reverse.
At the other end, the recipient would load this information into
the same universal, reversible Turing machine and run it backward
to recover the data. The one problem with this scenario is that any
attacker could also have the same universal, reversible Turing ma-
chine. They could intercept the message and reverse it. For the tech-
nique to be successful, some data must be kept secret from the at-
tacker. This could travel separately. In the grammar machine from
Chapter 7, the grammar acts as the key. It must be distributed sepa-
rately.
One solution is to keep the structure of the Turing machine secret
and let it act as a key. Only the output and the extra, “waste” bits
of information must be transmitted to the recipient. Anyone can
intercept the message, but they cannot read it without a copy of the
program that created it.
How difficult can this be? Obviously, there will be some programs
that are pretty easy to crack. For instance, a program that merely
copiesthedatatobehiddenandspitsitoutwouldbeeasytode-
duce. The output would maintain all of the structure of the original
document. More and more complicated programs would get more
andmore complicated to deduce. Eventually, somethingmust be too
hard to crack. The tough question is whether there is some threshold
that can be established where it is positively known that programs
that are beyond it are completely safe.
Such a threshold can never be well-defined. That is, there can be
no neat machine that will examine any program and say, “This can't
be broken.” There might be machines that could point out flaws in
programs and show how they could be broken, but they would not
be guaranteed to find all flaws.
This uncertainty is a pain, but it affects the enemy in the same
way. The enemy can not come up with an arbitrary machine that
will be able to examine every message you send and discover the
program that was used to hide the data. It may be able to find some
solutions, but there will be no brute-force attack that will work in all
cases.
This is a nice beginning for security, but it is not absolute. The
one-time pad offers a similar security blanket. No brute-force attack
that will break the system, as long as the key bits are completely
