Cryptography Reference
In-Depth Information
run decryption for each of the keys in the search. We thus describe the complexity
in terms of the more significant computational requirement, which is the vast
number of keys that must be searched.
These ideas about complexity are very powerful because they tell us about
the general behaviour of algorithms. Note that as time goes by, computers get
faster, following a much-quoted trend known as
Moore's Law
, so an exhaustive
search for a particular input value of
n
that was once thought impractical might
become feasible in the future. We will discuss how this has happened for DES in
Section 4.4. However, knowing that an exhaustive key search runs in exponential
time tells us that if computers continue to work in the way that they do today then
there will always be a (relatively small) value of
n
beyond which it is impossible in
practice to conduct the search.
COMPUTING REAL ATTACK TIMES
Complexity provides an abstract notion of time that is based on computer
operations. To convert this into a real notion of time we need to know how
much real time it takes to run these basic computer operations. This of course
depends on the processor speed of the computer(s) used. To compute real attack
times, we thus proceed as follows:
1. estimate the computer speed (in terms of number of operations performed per
second);
2. calculate the real time to conduct the process for an input of
n
bits by the
formula:
complexity of process evaluated at
n
computer speed
seconds
.
For example, an exhaustive key search has complexity 2
n
. Thus, if we estimate that
our computer is capable of processing one million operations per second then an
exhaustive search for a 30-bit key will take:
2
30
10
6
seconds
.
Since 2
30
is approximately 10
9
, the real-time search will take approximately:
10
9
10
6
10
3
=
=
1000 seconds
,
which is just under 18 minutes.
The dramatic difference between polynomial time and exponential time is
best seen by looking at the rate of increase of real computational time of some
processes, expressed in Table 3.4 based on a computer speed of one million
operations per second. All the calculations in Table 3.4 were computed using
the technique just described.
