Cryptography Reference
In-Depth Information
chi-squared statistic (see any introductory statistics text such as, for example, [168]
for an explanation of the chi-squared goodness-of-fit test). If
f
m
−
1
)
is the vector corresponding to the expected frequency distribution of the alpha-
betic characters in the language (English in this case) and
(
f
0
,
f
1
,...,
is
the observed frequency distribution of one of the
l
sub-ciphertexts into which the
given ciphertext is partitioned (where
l
is the key length), then for each of the
m
shifts
(
g
0
j
,
(
g
0
,
g
1
,...,
g
m
−
1
)
g
1
j
,...,
g
)
of
(
g
0
,
g
1
,...,
g
m
−
1
)
, with
j
=
0
,...,
m
−
1 and
g
0
j
=
g
j
,
(
m
−
1
)
j
=
m
−
1
i
2
f
i
. Then we choose the
shift
j
for which this value is lowest, which will give, with high probability, the key
letter corresponding to this sub-ciphertext. In our situation, this process is repeated
for each of the 12 sub-ciphertexts to reveal the 12 characters of the key. We will make
use of the following function to determine the position of the minimum element in
a list:
0
(
g
ij
−
f
i
)
2
we will compute the chi-squared statistic
χ
=
> findmin := lis -> ListTools:-Search(min(op(lis)), lis):
Next we give the function
frequencyanalysis
which actually computes the
key letter corresponding to one of the sub-ciphertexts following the method outlined
above:
> frequencyanalysis := proc(lis, {language := en})
uses ListTools;
local f, s, alphabet, modulus;
f := freqlist(language);
alphabet := alph(language);
modulus := StringTools:-Length(alphabet);
s := seq(DotProduct(map(i -> 1/i, f), map(i -> iˆ2, x-f)),
x = seq(Rotate(lis, i), i=0..modulus-1));
alphabet[findmin([s])]
end proc:
The function
VigenereKeyFind
below uses the preceding ones to find the
key that has been used. The input is the ciphertext and, optionally, the maximum
value that will be tested as possible length of the key and the language used. As in
the case of the function
keylength
above, and for the same reasons, the default
value for
max
is taken to be equal to
1
15
th of the length of the ciphertext. A little
experimentation shows that 25 ciphertext characters—or even 20 or fewer in many
cases—for each key character provides for successful key recovery most of the time.
> relativefrequencies := proc(text, language)
evalf(frequencies(text, language)/StringTools:-Length(text))
end proc:
VigenereKeyFind := proc(ciphertext, max:=floor(StringTools:-Length(ciphertext)/15),
{language:=en})
uses StringTools;
local freqs;
freqs := map(x -> relativefrequencies(x, language),
map(Implode, partit(Explode(ciphertext),
keylength(ciphertext, max, ':-language'=language))));
Implode(map(li -> frequencyanalysis(li, ':-language'=language), freqs))
end proc:
For the ciphertext given above as example, we obtain the following key:
