Cryptography Reference
In-Depth Information
> SubstitutionDec(k, c);
"sellthesharesbeforetomorrow"
The Caesar cipher is a particular case of the substitution cipher. It can be recovered
as follows (where the function
sshift
below takes care of converting a Caesar key
to a permutation given as a list of integers in the 1
..
26 range):
> sshift := k -> map(i->(i+k mod 26)+1,[$0..25]):
SCaesar := (key, message) ->
CharacterMap(alphabet, Permute(alphabet, sshift(key)), message):
SCaesar(19, "thedieiscast");
"maxwbxblvtlm"
SCaesar(-19, %);
"thedieiscast"
(the symbol % is the 'ditto operator' in Maple and takes the value of the previous
output).
Cryptanalysis of the Substitution Cipher.
Let us now examine the security of the substitution cipher. What we have gained by
replacing the shift cipher by a general substitution cipher is that now
|
K
|=
n
!
is
much larger than
n
. When
Σ
is the English alphabet, the number of possible keys
10
26
so trying all possible keys is definitely out of the question for now
although it may become feasible in a not-too-distant future.
To get a more precise idea about the size of this task one can have a look at
one of the largest successful brute-force attacks so far, the one against the 'Data
Encryption Standard' (DES)
4
carried out in 1999 in response to the 'DES Challenge
Deep Crack
which contained about 1500 processors, working cooperatively with
many other computers coordinated through a web site called
distributed.net
.The
search rate was 245 billion keys per second and the plaintext was recovered in just
over 22 h. We can see that, if the same computing power were applied to a brute-
force search of a substitution cipher over the English alphabet and if one assumes
that the key is found after searching one half of the key space (as would be expected
on average), then the required time would be more than 2
is 26
!
>
4
·
10
7
years. Even taking
into account the increase of computing power since 1999, breaking the cipher this
way is not yet feasible as of this writing.
.
6
·
Exercise 1.6
Assuming that computational power doubles every two years as a
consequence of
Moore's law
([145]) and the use of parallel computing, and taking as
reference the 1999 DES cracking effort, compute the year in which one could expect
the brute-force attack on the substitution cipher to succeed within one month.
In addition to the previous remarks, one should also bear in mind that the compu-
tational cost of breaking a substitution cipher by exhaustive search grows steeply (or,
