Cryptography Reference
In-Depth Information
This grammar generates exactly the same group of sentences or
language as the other version. The only difference is in the order
in which choices are made. Here, there is no choice available when
the variable
where
is tackled. No bits would be stored away at this
point. The variables for
direction
and
state
would be handled in or-
der. The result is that the sentence “Barney went fishing in northern
Minnesota” is produced by the bits 1001. In the previous grammar
on page 107, the sentence emerged from hiding bits 1010.
Parsing the result from a context-free grammar that is in Greibach
The programwas a
mimetic weapon,
designed to absorb local
color and present itself
as a crash priority
override in whatever
context it encountered.
—William Gibson in
Burning Chrome
Normal Form is generally easy. The table on page 107 shows how the
sentence “Barney went fishing in northernMinnesota” was produced
from the bits 1010. The parsing process works along similar lines.
Here's the sentence being parsed using the grammar in GNF on 110.
Sentence Fragment
Step
in Question
Matching Production
Bit Recovered
→
1
Barney
went fishing
noun
Fred
Barney
1
in northern Minnesota.
2 ar ey
went fishing
→
verb
went fishing
where
0
in northern Minnesota.
went bowling
where
3 ar ey e t s i g
where
→
in
direction state
.
none
in
northern Minnesota.
4 ar ey e t s i g
direction
→
northern
southern
0
in
northern
Minnesota.
5 ar ey e t s i g
state
→
Iowa.
Minnesota.
1
in northern
Minnesota.
The bits 1001 are recovered in step 5. This shows how a parsing
process can recover bits stored inside of sentences produced using
grammar in GNF. Better parsing algorithms can handle any arbitrary
context-free grammar, but this is beyond the purview of this topic.
7.2.3 How Good Is It?
There are many ways to measure goodness, goodness knows, but the
most important ones here are efficiency and resistance to attack. The
efficiency of this method is something that depends heavily on the
grammar itself. In the examples in this section, one bit in the source
text was converted into words like “Minnesota” or “Barney”. That's
not particularly efficient.
The grammar could encode more bits at each stage in the pro-
duction if there were more choices. In each of the examples, there
were only two choices on the right side of the production, but there
is no reason why there can't be more. Four choices would encode
two bits. Eight choices would encode three bits, and so on. More
