Cryptography Reference
In-Depth Information
What we need is a special piece of technical 'magic' that will allow the genuine
receiver to overcome the one-way property of the encryption function. One-way
functions for which there exists a
trapdoor
of this type, knowledge of which
allows the plaintext to be obtained from the ciphertext, are referred to as
trapdoor
one-way functions
.
Thus, to design a public-key cryptosystem, we will need to find a trapdoor
one-way function. The receiver will need to know the trapdoor, and be the only
entity who knows the trapdoor. This trapdoor will form the receiver's private key.
MULTIPLICATION OF TWO LARGE PRIMES
We will temporarily set aside the need for trapdoors and look at two one-way
functions on which we could potentially base a public-key cryptosystem. The first
one-way function is multiplication of two large primes.
It is easy to take two primes and multiply them together (the result is normally
called the
product
). If the numbers are fairly small then we can do this in our
heads, on a piece of paper, or perhaps on a calculator. Once they get bigger (and
bigger) it is still easy to write a computer program to compute the product. The
reason is that, as we observed in Section 3.2.3, multiplication can be conducted in
polynomial time. Multiplication of two primes is computationally easy.
However, given the product of two primes, the problem of working out what
these two primes are (known as
factoring
because it involves determining the
factors) is surprisingly hard. When we say 'hard', this of course applies to the
general case. Table 5.1 indicates the level of difficulty of factorisation for a range
of numbers that are the product of two primes. Note that factorisation is
unique
,
meaning that there is only one possible pair of prime factors for each product. This
observation explains the last two entries in Table 5.1. The last entry is implied from
Table 5.1:
Examples of the difficulty of factoring the product of two primes
Challenge number
Difficulty of solution
15
Everyone can do this instantly
143
Doable with a little thought
6887
Should not take more than a few minutes
31897
A calculator is now useful
20-digit number
A computer is now required
600-digit number
This is impossible in practice
600-digit even number
One factor immediate, other easily computed
600-digit number with small factor
One factor easily found, other easily computed
