Cryptography Reference
In-Depth Information
In order to cryptanalyze it we first determine the key length—let's call it
l
—as
follows. We partition the ciphertext into a collection of
t
sub-ciphertexts (for
t
=1,2,
3, ...) in such a way that the first one consists of the characters whose position in the
ciphertext is congruent to 1 modulo
t
, the second one those with position congruent
to 2 modulo
t
and so on, until the
t
th one, which consists of the characters whose
position is congruent to 0modulo
t
.Wedothisuptoavalueof
t
which is as large as the
key length we are trying to find (we have to guess this value but if, after completing
the process, the key length is not within the considered interval, we can try with
larger values of
t
). For each of those sub-ciphertexts, we compute the IC and then we
compute, for each value of
t
, the mean of the ICs of the
t
sub-ciphertexts. We expect
that, if
l
is the (still unknown) key length, the mean of these ICs for
t
l
should be
very close to the IC of English, that is, to 0.066. The reason is that, when
t
equals the
key length, each of the sub-messages we are considering has been encrypted with the
same shift cipher and so its expected IC is that of the language used. On the contrary,
for values of
t
different from
l
, the characters of each sub-message were not encrypted
with the same substitution and so the corresponding ICs will be lower, closer to that of
a random text. The next function partitions the ciphertext (given as a list of elements in
Z
m
, where
m
=
modulus = 26
in our case) into sub-ciphertexts as indicated above,
with 1
=
≤
t
≤
long
.
> partit:= (lis, long) -> [seq([seq(lis[(i-1)*long+t], i =
1..floor(((nops(lis)-t)/long)+1))],t = 1..long)]:
Now, the following function computes the mean IC for the sub-ciphertexts corre-
sponding to each value of
t
:
> indiceslist := proc(text, min, max)
uses StringTools;
local i, ind, ic, t;
i := min;
while i <= max do
ind := map(IndexOfCoincidence, map(Implode, partit(Explode(text), i)));
ic := evalf((sum(ind[t], t=1..nops(ind)))/nops(ind));
i := i+1;
printf("%2d %9f\n", i-1, ic);
end do;
end proc:
We may look at the list of indices obtained when we apply this function to our
sample ciphertext
c
above, with
t
ranging from 1 to 15. The list is the following:
> indiceslist(c, 1, 15);
1 0.039338
2 0.041093
3 0.044679
4 0.049851
5 0.039578
6 0.049834
7 0.037323
8 0.047631
9 0.041010
10 0.044026
11 0.035723
12 0.070599
13 0.035762
14 0.036218
15 0.045370
