Cryptography Reference
In-Depth Information
that follows, we assume some knowledge of elementary number theory and some
familiarity with simple number-theoretic algorithms. Further discussion of the relevant
number theoretic material is presented in Appendix A.
2.4.3.1. The RSA Function
The RSA collection of functions has an index set consisting of pairs (
N
e
), where
N
is
a product of two (
2
·
log
2
N
)-bit primes, denoted
P
and
Q
, and
e
is an integer smaller
than
N
and relatively prime to (
P
−
1)
·
(
Q
−
1). The function of index (
N
,
e
) has
domain
{
1
,...,
N
}
and maps the domain element
x
to
x
e
mod
N
. Using the fact that
e
is relatively prime to (
P
−
1)
·
(
Q
−
1), it can be shown that the function is in fact a
permutation over its domain. Hence, the RSA collection is a collection of
permutations
.
We first substantiate the fact that the RSA collection satisfies the first condition for
the definition of a one-way collection (i.e., that it is easy to sample and compute). To
this end, we present the triplet of algorithms (
I
RSA
,
D
RSA
,
F
RSA
).
On input 1
n
, algorithm
I
RSA
selects uniformly two primes,
P
and
Q
, such that 2
n
−
1
,
≤
P
<
Q
<
2
n
, and an integer
e
such that
e
is relatively prime to (
P
−
·
(
Q
−
1).
(Specifically,
e
is uniformly selected among the admissible possibilities.
7
) Algorithm
I
RSA
terminates with output (
N
1)
Q
. For an efficient implementation
of
I
RSA
, we need a probabilistic polynomial-time algorithm for generating uniformly
(or almost uniformly) distributed primes. For more details concerning the uniform
generation of primes, see Appendix A.
As for algorithm
D
RSA
, on input (
N
,
e
), where
N
=
P
·
,
e
) it selects (almost) uniformly an element in
the set
D
N
,
e
def
={
1
,...,
N
}
. (The exponentially vanishing deviation is due to the fact
that we implement an
N
-way selection via a sequence of unbiased coin tosses.) The
output of
F
RSA
, on input ((
N
,
e
)
,
x
), is
RSA
N
,
e
(
x
)
def
=
x
e
mod
N
(2.10)
It is not known whether or not factoring
N
can be reduced to inverting RSA
N
,
e
, and
in fact this is a well-known open problem. We remark that the best algorithms known
for inverting RSA
N
,
e
proceed by (explicitly or implicitly) factoring
N
. In any case, it
is widely believed that the RSA collection is hard to invert.
In the foregoing description,
D
N
,
e
corresponds to the additive group mod
N
(and
hence will contain
N
elements). Alternatively, the domain
D
N
,
e
can be restricted to
the elements of the
mu
ltiplicative group modulo
N
(and hence will contain (
P
−
1)
·
(
Q
−
1)
≈
N
−
2
√
N
≈
N
elements). A modified domain sampler may work by se-
lecting an element in
{
1
,...,
N
}
and discarding the unlikely cases in which the selected
element is not relatively prime to
N
. The function RSA
N
,
e
defined earlier induces a
permutation on the multiplicative group modulo
N
. The resulting collection is as hard
to invert as the original one. (A proof of this statement is left as an exercise to the
reader.) The question of which formulation to prefer seems to be a matter of personal
taste.
7
In some sources,
e
is set to equal 3. In such a case, the primes (
P
and
Q
) are selected so that they are congruent
to 2 mod 3. It is not known whether or not the assumption that one variant is one-way implies that the other
also is.
