Cryptography Reference
In-Depth Information
processes are 'quick' on all inputs of 'reasonable' size. From Table 3.3 we
see that multiplication of two
n
-bit numbers has complexity
n
2
and thus can
be conducted in polynomial time. Thus multiplication is an easy process to
conduct. Likewise, we see that addition and raising a number to a power are
easy processes to conduct.
Exponential time
if the time taken to execute the process for an input of size
n
is
approximately
a
n
, for some number
a
. Informally, exponential-time processes
are 'slow' on all inputs of 'reasonable' size. As
n
increases, the length of time
necessary to run the necessary algorithm increases dramatically, until it is
impossible in practice to compute the result. If a bigger value of
a
is chosen
then this trend is exacerbated. From Table 3.3 we see that an exhaustive key
search has complexity 2
n
and thus can be conducted in exponential time.
Thus an exhaustive key search takes a long time to conduct, irrespective of the
computer(s) on which it is performed.
Note that:
1. Just because a process is
easy
to conduct does not necessarily mean that it is
efficient
to conduct. For example:
• multiplication can always be computed in a relatively short time with respect to
the size of the input numbers but, as the size of the input numbers increases, the
length of time it takes to process a multiplication might not always be acceptable;
• raising a number to a power (
exponentiation
, which confusingly runs in
polynomial
time
!) is also easy to conduct, but is generally regarded as being relatively
computationally expensive.
In fact, much work has been devoted to reducing the complexity of common
polynomial-time processes such as multiplication and exponentiation in an
attempt to make them faster to compute.
2. Just because a process is
generally
hard to conduct does not mean that it
is
always
hard to conduct. For example, an exhaustive key search is quite
feasible if
n
is small enough. The point is that if a process runs in exponential
time then, as
n
grows larger, the time needed to conduct the process grows
exponentially. Thus, after a certain point, the process takes too long to be
realistically conducted using current computing capabilities.
In terms of the design of cryptosystems, it should be clear that encryption
and decryption processes must run in polynomial time. Ideally an attacker who
does not have access to the decryption key should be required to conduct an
exponential-time process in order to obtain the plaintext or the decryption key
from the ciphertext.
Note that Table 3.3 contains a slight oversimplification. A complete exhaustive
key search for amodern symmetric algorithmwith an
n
-bit key actually involves 2
n
decryptions, each of which should consist of a polynomial-time operation. Hence
the complexity is really 2
n
×
n
r
, for some unspecified
r
. However, 2
n
increases so
much more rapidly than
n
r
that we can effectively 'forget' about the time taken to
