Cryptography Reference
In-Depth Information
symbols can be easily included, see exercises below and also the implementations of
encryption schemes in the following chapters) we will use the string “thedieiscast”
instead. We obtain:
> c := CaesarEnc(19, "thedieiscast");
c := "maxwbxblvtlm"
Now, this ciphertext can be decrypted as follows:
> CaesarDec(19, c);
"thedieiscast"
Exercise 1.1
Write Maple functions that check that the above defined functions
code
and
char
are mutually inverse.
Exercise 1.2
Modify the alphabet and the above functions implementing the Caesar
cipher to allow for upper case letters and punctuation signs in messages.
Cryptanalysis of the Caesar Cipher
An analysis of the different types of cryptanalytic attack gives the following possi-
bilities:
1.
Ciphertext-only.
If Eve only has a ciphertext
c
, she can mount a
brute-force
attack
, consisting of an exhaustive search to determine which of the possible
26 keys is the correct one. This can be accomplished by decrypting
c
with each
key in turn, to find out which one gives a meaningful text. A brute-force attack
can always be attempted but, as we shall see in the case of other encryption
schemes, it does not always work. For example, the key space may be so large
as to make the search infeasible within a reasonable time. In the case of the
Caesar cipher this does not happen and, in fact, it is child's play (literally!) to
try all possible keys. Shannon defined, in statistical terms, using the concept of
entropy
,the
unicity distance
of an encryption scheme, which can be informally
described as the minimum length of ciphertext (here the length is just the number
of characters) for which one expects that there will be only one meaningful
plaintext when decrypting it with all possible keys. The theoretical estimates for
the unicity distance of the Caesar cipher over the English language suggest that
only two letters are needed to recover the key (and hence the plaintext). This
number should only be viewed as a lower bound (see Exercise 1.4 below for
the case of length 1) but, even if there are some longer English words that have
meaningful shifts (such as, for example, 'river' and 'arena', which are shifts of
each other and hence can produce the same Caesar ciphertext with appropriate
keys), these words are very few in number. Thus the brute-force attack will most
likely recover the key given a ciphertext of, say, length 4, with key recovery
being almost certain for ciphertexts of length
6. Anyway, in contrast with the
idea that the ciphertext should not leak any information about the plaintext, not
having a uniquely recoverable key is a very weak security property which will
not be of much interest to us.
≥
