Cryptography Reference
In-Depth Information
The first variable,
AndFriend
, is expanded by creating a new
production for
noun
for all possible combinations. The pro-
duction for
AndFriend
disappears from the grammar:
→
Fred and Barney went bowling
where
noun
Fred and Barney went fishing
where
Fred
Alone
Alone
→
went fishing
where
went bowling
where
.
.
.
Contractions
These are the opposite of expansions. If there is some
pattern in several of the productions, it can be replaced by a
new variable. For instance, the pattern “Fred and Barney” is
found in two productions of
noun
:
noun
→
Fred and Barney went fishing
where
Fred and Barney went bowling
where
Fred
Alone
Alone
→
went fishing
where
went bowling
where
.
.
.
This can be contracted by introducing a new variable,
what
:
noun
→
Fred and Barney
what where
Fred
Alone
what
→
went bowling
went fishing
Alone
→
went fishing
where
went bowling
where
.
.
.
This new grammar is different from the one that began the ex-
pansion process. It produces the same sentences, but from dif-
ferent patterns of bits.
Permutation
The order of productions can be scrambled. This can
change their position in any Huffman tree that is built. Or the
scrambling can take place on the tree itself.
Any combination of expansion, contraction, and permutation
will produce a new grammar that generates the same language. But
this new language will produce the sentences from bits in a com-
pletely different manner. This increases security and makes it much
less likely that any attacker will be able to infer coherent information
about the grammar.
These expansions, contractions, and permutations can be driven
by a pseudo-random number generator that is seeded by a key. One
person on each end of the conversation could begin with the same
large grammar and then synchronize the randomnumber generators
