Cryptography Reference
In-Depth Information
measure of entropy of a bit stream. If one word is quite likely to
follow another, then there is not much information bound in it. If
many words are likely, then there is plenty of information bound in
this choice.
The equations measure the entropy of the entire language gen-
erated by a grammar. If the amount is large, then the information
capacity of the grammar is also large and a great deal of information
should be able to be transmitted before significant repetition occurs.
This practical approach can give a good estimate of the strength of a
grammar.
Both of these approaches show that it can be quite difficult to
discover the grammar that generated a text. They do not guarantee
security, but they show that the security may be difficult to achieve
in all cases. It can be even more difficult if the grammar is modified
in the process through expansions and contractions. These can be
chosen by both sides of a channel in a synchronized way by agreeing
on a cryptographically secure pseudo-random number generator.
7.3.5 Efficient Mimicry-Based Codes
The one problem with the mimicry system described in this chapter
is that it is inefficient. Even very complicated grammars will easily
double, triple, or quadruple the size of a file by converting it into text.
Less complicated grammars could easily produce output that is ten
times larger than the input. This may be the price that must be paid
to achieve something that looks nice, but there may be other uses for
the algorithm if it is really secure.
Efficient encryption algorithms using the techniques of this chap-
ter are certainly possible. The results look like ordinary binary data,
not spoken text, but they do not increase the size of a file. The key is
just to build a large grammar. Here's an example:
Terminal s
Let there be 256 terminal characters, that is, the values of
a byte between 0 and 255. Call these
{t
0
...t
255
}
.
Var iables
Let there be
n
variables,
{v
0
...v
n
}.
Each variable has 256
productions.
Productions
Each variable has 256 productions of the form
v
i
→
t
j
v
a
1
...v
a
k
. That is, each variable will be converted into a sin-
gle terminal and
variables. Some productions will have no
variables and some will have many. Each terminal will appear
on the right side of only one production for a particular vari-
able. This ensures that parsing is easy.
k
