Computational Complexity

The complexities of conducting attacks

The next aspect of practical security worth knowing concerns the time taken to conduct an attack. This requires knowing the answer to two separate questions:

1. What computational processes are involved in known attacks on the cryptosystem?

2. How much time does it take to conduct these processes?

The first of these is the task of a cryptanalyst. However, for modern established cryptosystems which have already undergone a rigorous analysis, the computational processes involved should be fairly well understood. This is because, in order to demonstrate security, a well-designed cryptosystem is usually built around a computational problem that is widely perceived to be hard to solve. Such a cryptosystem will have, at its heart, at least one computational process that is understood and widely believed to be very slow to conduct.

Because of this, establishing the time required to conduct an attack against a cryptosystem requires a formal way of measuring how long the computational process required to break the cryptosystem takes to run. So what we need is a way of measuring the time 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 the 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 the input.

The length of the 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 it takes to run the algorithm, such as adding two bits or comparing two values. This time is usually an approximation rather than a precise measure of the number of operations involved.

This is best illustrated by examples. The complexity of some basic processes is shown in the following table: