Cryptography Reference
In-Depth Information
numbers
a
and
b
together. The key is not just
a
, and neither is it just
b
, the key
consists of both. Note, however, that we also use brackets in mathematics just to
keep symbols 'together' (much as we do in sentences such as this one). Thus the
following two pieces of notation have quite different meanings:
•(
p
−
1)(
q
−
1) means the number
p
−
1multiplied by the number
q
−
1 (without
the brackets the statement would be confusing);
•(
p
1 should be
treated as a pair of numbers that occur together as a package (for example,
they form a cryptographic key).
Note that brackets are sometimes used in other mathematical texts to mean
different things.
−
1
,
q
−
1) means that the number
p
−
1 and the number
q
−
5.1.4
One-way functions for public-key cryptography
Having stated the blueprint for a public-key cryptosystem, we now need to
consider how such a public-key cryptosystem can be designed. The first step
in this direction is to state more precisely the properties that we need public-key
encryption to satisfy.
TRAPDOOR ONE-WAY FUNCTIONS
Public-key encryption can be thought of as a function that anyone should be able
to compute, since the encryption key is public. This function has two obvious
properties:
The function should be 'easy' to compute
. In other words, it should be
computable in polynomial time. If this is not the case then it will be impractical
to encrypt anything.
The function should be 'hard' to reverse
. In other words, any algorithm for
finding an input from an output should run in exponential time. If this is not
the case then an attacker might be able to efficiently determine a plaintext from
knowledge of a ciphertext and the public encryption key.
A function that has the above properties is often referred to as a
one-way function
(see also Section 6.2.1).
However, public-key encryption should not always be a one-way function.
Rather, it should
almost
always be a one-way function. We have omitted one
important aspect. While the encryption operation should be one-way as far
as most entities are concerned, there is one entity who should be able to
determine the plaintext from a ciphertext, namely the intended recipient of the
ciphertext! If the encryption function is completely one-way then it is certainly
secure, but impractical for most applications (see Section 6.2.2 for a notable
exception).
