Cryptography Reference
In-Depth Information
Remark 1.1
We have been using English words (or names) as keys for the Vigenère
cipher in our examples but we stress the fact that, as a general rule, for actual crypto-
graphic use randomly generated keys should be used. Indeed, the number of English
words of a given length is tiny in comparison with the number of all possible words
of the same length over the English alphabet and a similar remark applies in general
to other kinds of structured (and hence non-random) keys vis-a-vis random keys.
Using English words as keys greatly reduces the size of the key space and makes it
possible to use
dictionary attacks
, which are exhaustive searches restricted to words
or phrases in a dictionary. In the case of the Vigenère cipher this does not mat-
ter much because the cipher is easily broken by the index of coincidence method,
which does not exploit special characteristics of keys and works equally well with
random keys.
Example 1.6
We do an example with a Spanish text:
> st:="esteesunmensajedepruebadecriptoanalisisenespan olusandoelindicedecoincidencia":
Vigenere("wxyz", st, enc, language = es);
Vigenere("wxyz", %, dec, language = es);
VigenereKeyFind(%%, language = es);
"aprdapsmiblrwgccanptayycazphmqnzjxjhofqdjbqowlnkqpymzmckekbhybbdymgmyfbdjzgz"
"esteesunmensajedepruebadecriptoanalisisenespan olusandoelindicedecoincidencia"
"wxyz"
Exercise 1.13
Modify theMaple functions used to cryptanalyze the Vigenère cipher
in order to make them able to deal with more languages. In order to do it, compute
the frequency distributions of characters in the desired languages—or learn them
from the literature or the Web—and make the procedures work with them.
Exercise 1.14
Consider Vigenère encryptions with different ratios of ciphertext
length to key length and use the Maple functions
VigenereKeyFind
and
VigenereCryptanalysis
to explore the minimum ratio needed to obtain reli-
able decryptions by the index of coincidence method.
We will now have a brief look at the Kasiski test, which can be used as a com-
plement to the method based on the index of coincidence. Maple has a function
Kasiski
in the
StringTools
package but it does not do what we need, so we
give a simple function that computes the greatest common divisor of the distances
between repeated substrings of length at least 4 (length 3 substrings are often con-
sidered for this purpose but this way the method is more reliable):
> KasiskiTest := proc(ciphertext)
local positions;
positions := select(x -> evalb(3 < x[3]), [StringTools:-Repeats(ciphertext)]);
igcd(op(map(x -> x[2]-x[1], positions)))
end proc:
Example 1.7
Let us apply the function
KasiskiTest
to some of the previously
computed ciphertexts. For instance, for ciphertext
c
above, we have:
> KasiskiTest(c);
24
