Cryptography Reference
In-Depth Information
Alice
Bob
k
pub
←−−−−−−−−−−−−
k
pub
,
k
pr
choose random
k
y
=
e
k
pub
(
k
)
y
−−−−−−−−−−−−→
k
=
d
k
pr
(
y
)
encrypt message
x
:
z
=
AES
k
(
x
)
z
−−−−−−−−−−−−→
x
=
AES
−
k
(
z
)
Fig. 6.5
Basic key transport protocol with AES as an example of a symmetric cipher
Definition 6.1.1
One-way function
A function f
()
is a one-way function if:
1. y
=
f
(
x
)
is computationally easy, and
2. x
=
f
−
1
(
y
)
is computationally infeasible.
Obviously, the adjectives “easy” and “infeasible” are not particularly exact. In
mathematical terms, a function is easy to compute if it can be evaluated in polyno-
mial time, i.e., its running time is a polynomial expression. In order to be useful in
practical crypto schemes, the computation
y
=
f
(
x
) should be sufficiently fast that
it does not lead to unacceptably slow execution times in an application. The inverse
computation
x
=
f
−
1
(
y
) should be so computationally intensive that it is not feasi-
ble to evaluate it in any reasonable time period, say, 10,000 years, when using the
best known algorithm.
There are two popular one-way functions which are used in practical public-key
schemes. The first is the integer factorization problem, on which RSA is based.
Given two large primes, it is easy to compute the product. However, it is very dif-
ficult to factor the resulting product. In fact, if each of the primes has 150 or more
decimal digits, the resulting product cannot be factored, even with thousands of PCs
running for many years. The other one-way function that is used widely is the dis-
crete logarithm problem. This is not quite as intuitive and is introduced in Chap. 8.
6.2 Practical Aspects of Public-Key Cryptography
Actual public-key algorithms will be introduced in the next chapters, since there is
some mathematics we must study first. However, it is very interesting to look at the
principal security functions of public-key cryptography which we address in this
section.
