Cryptography Reference
In-Depth Information
> HillCryptanalysis(kpt, kct, 10, ciphertext);
"this cipher is easy to break"
Note that the recovered plaintext has some additional spaces at the end. This is
due to the fact that we used the last character in the alphabet (the space) to pad the
messages whose length is not a multiple of the block size. Observe also that the
function
HillCryptanalysis
actually recovers the key that is being used, and
can be modified in an obvious way to produce this key as output.
Exercise 1.16
Modify the function
HillCryptanalysis
to make it output the
key used. In this case only three arguments are necessary: the known plaintext, the
known ciphertext and the size of the key.
Exercise 1.17
Consider the following plaintext written in the 27-character English
alphabet that includes the space: “the hill cipher is highly vulnerable to a known
plaintext attack”. Suppose that this message is encrypted using the encryption algo-
rithm above and an invertible
n
Z
27
as key, and the adversary knows
both this plaintext and the corresponding ciphertext. Determine the maximum size
of
n
that allows the adversary a full recovery of the key using only the linear algebra
attack we have described, and for this maximum key size find the shortest plaintext
length that allows full key recovery by this method. Is there another text of the same
length that allows the full key recovery for a larger value of
n
?
×
n
matrix over
1.5 Some Conclusions
The history of cryptography is a fascinating subject and in this chapter we have looked
at several encryption schemes whose interest is mainly of a historical nature, as they
are far from secure and hence no longer used in serious cryptographic applications.
But we have not studied the history of the subject per se and, for a detailed account,
the interested reader may consult David Kahn's encyclopedic work [108] and also
[183], which is a less extensive but more up-to-date reference.
These systems are also often used in puzzles but the main reason why we have
studied them is not their recreational value but, rather, the fact that they teach us
valuable lessons fromwhichwe should learn. One of the first things we have observed
is that a large key space is a necessary, but not sufficient, condition for the security
of an encryption scheme. It is not sufficient because, among other possibilities, an
adversary can use statistical methods to find connections between the ciphertext and
the plaintext, such as in the case of monoalphabetic substitution ciphers and also of
the Vigenère cipher. Even when statistical methods do not work so well, there may
be structural connections that make a cipher insecure as we have seen in the case of
the Hill cipher, when these connections allow the recovery of the key with relatively
little effort.
One of the things that stands out from the analysis of these schemes bearing in
mind the previous remarks is that, speaking from the cryptographer's point of view,
