Cryptography Reference
In-Depth Information
The shaded area is a measure of the coincidence of the two curves. The question
as to which shift we should define as the 'statistically best' will always be
somewhat subjective, so we try to minimize the area content by selecting a
suitable shift.
In mathematical terms, we try to make an expression in the form
(g
0
-p
0
)
2
+(g
1
-p
1
)
2
+...+(g
255
-p
255
)
2
(2)
as small as possible in dependence on a shift, where
g
i
are the relative fre-
quencies of a shifted ciphertext, and
p
i
are the relative frequencies of a related
plaintext.
4
Let's go back to the XOR operation. It doesn't correspond to a shift, but
to a permutation of the 'byte alphabet'; anyway, this doesn't basically change
anything in our considerations. The only thing is that Figure 3.12 can no longer
be represented with this operation as it would be far too big. The so-called
objective function remains for minimizing the expression in (2).
So, we try all 256 key characters possible in each group and select the one
with the smallest objective function value. This is how we reveal the key.
Notice that there are more sophisticated cryptanalytic methods. But as long as
it's a matter of practical use on word processors, spreadsheets, etc., we will have
sufficient material for good statistics. That's purely pragmatic. The surprisingly
successful cryptanalysis using a program called
vigcrack
introduced in the next
section confirms that we can be pragmatic about it.
3.6.3 The
vigcrack
Program
This C program is not particularly long either (122 lines, excluding the comment
in the header; see listing in Figure 3.13), but it uses more theory, and it is a
lot more universal than
newwpcrack
from Section 3.5.2.
Since we've learned the theoretical background in Section 3.6.2, we can now
focus on important details of the implementation.
vigcrack
cracks Vigenere-
encrypted files with unequally distributed characters (i.e., readable texts, source
4
For mathematicians: what we basically do here is a kind of Chi-square adaptation test with
a distribution over 256 groups. Except that, rather than testing for a hypothesis with given
error probability, we select the most favorable, the one that would pass the hardest test, out of
several samples. However, the shaded area in Figure 3.12 corresponds to the sum of the absolute
amounts of the differences in (2) and not to their squares.
