Cryptography Reference
In-Depth Information
to break the cryptosystem takes to run. What we thus need is a way of measuring
the time that it takes to run a process.
COMPLEXITY OF SIMPLE PROCESSES
We now look at the most common measure of processing time. All processes,
not just cryptographic ones, are implemented by means of some algorithm, which
specifies the machine operations required to conduct that process. The
complexity
of an algorithm gives, for each possible length of input to the algorithm, the time
needed to run the algorithm for that length of input.
The length of input is measured in terms of the number of bits of input. The
time is measured in terms of the number of basic machine operations (such as
adding two bits, or comparing two values) that it takes to run the algorithm. This
time is usually an approximation, rather than an attempt to measure the number
of operations precisely.
This is best illustrated by examples. The complexity of some basic processes
are shown in Table 3.3.
POLYNOMIAL AND EXPONENTIAL TIME
The study of the complexity of algorithms is an entire field of mathematical
science in itself. It will suffice for us to observe that there are two very important
general classes of process, determined by their complexity. A process can be
conducted in:
Polynomial time
if the time taken to execute the process for an input of size
n
is not greater than
n
r
, for some number
r
. Informally, polynomial-time
Table 3.3:
Complexity of some basic processes
Operation
Complexity Explanation
Addition of two
n
-bit
numbers
n
Ignoring carrying, when a computer adds two numbers it
performs one addition for every bit in the lengths of the
input numbers.
n
2
Multiplication of two
n
-bit numbers
Computers multiply numbers in a similar way to the way
we perform 'long multiplication'. Thus we have
n
different additions to perform, one for every bit of the
length of the input numbers.
n
3
Raising a number to an
n
-bit power
This process consists of
n
operations, each of which is
either a squaring or a multiplication, both of which take
n
2
operations, hence
n
3
in total (using the method
known as
Repeated Squares
).
2
n
Exhaustive key search
for an
n
-bit key
This involves trying out every possible
n
-bit key, of which
there are 2
n
.
