Cryptography Reference
In-Depth Information
2.7.2 Modular Exponentiation
One of the key ideas underlying the birth of public-key cryptography in the 1970s was
to use as encryption function a trapdoor one-way function, which can informally be
described as a function that is easy to compute but hard to invert (namely, a one-way
function, which will be formally defined later) and, moreover, has a trapdoor, i.e.,
information whose knowledge allows the efficient inversion of the function. The first
candidate for such a function was proposed in 1978 by Rivest, Shamir and Adleman
as the basis of what would become the RSA cryptosystem. The underlying hypothesis
on which RSA is based is the following:
•
Modular exponentiation with fixed exponent and modulus is a trapdoor one
-
way
function
Let us analyze the meaning of this assertion in some detail. The idea is that, if
n
is
a large integer (where the meaning of 'large' will be made precise when discussing
RSA) which is the product of two distinct primes
p
and
q
of approximately the same
size, and
e
is a positive exponent such that gcd
(
e
,(
p
−
1
)(
q
−
1
))
=
1 (where the
∈ Z
φ(
n
)
latter condition just means that
e
), then the function
Z
n
−→
Z
n
m
e
mod
n
m
→
,
is trapdoor one-way. This means that the following conditions should hold:
1. Computing
c
m
e
mod
n
is easy (in the complexity-theoretic sense of the term).
2. The inverse problem of
extracting e
th
roots modulo n
, that is, 'given a random
c
=
∈
∈ Z
φ(
n
)
Z
n
and a positive integer
e
(we may also assume that 1
<
e
<φ(
n
)
−
1
m
e
mod
n
' is hard.
3. If the prime factorization of
n
is known, then the computation of
e
th roots modulo
n
is easy (so that the factorization of
n
would be the trapdoor).
As we shall soon see, conditions 1 and 3 above do indeed hold and the only thing
that remains to be proved in order to ensure that modular exponentiation is a trapdoor
one-way function is condition 2. Because of this, the assertion that the function is
one-way is so far only a conjecture and, more generally, the existence of one-way
functions—which, if true, would imply the truth of the
to exclude trivial cases), compute
m
such that
c
=
conjecture—has
not been proved. But it is widely believed that some candidates such as modular
exponentiation are indeed trapdoor one-way and this is the reason why they are
currently used in cryptography.
We leave for later the discussion of conditions 2 and 3 above and we shall now
examine condition 1, which is easily shown to hold. To prove 1 we have to show that
modular powers can be efficiently computed and, as we will see when discussing
RSA, this also implies 3. More precisely, in terms of complexity theory we will show
that modular exponentiation can be done in polynomial time. It is not completely
obvious how to do this and, to analyze the difficulties that may arise, let us try to
compute an instance with Maple.
P
=
NP
