Cryptography Reference
In-Depth Information
Next we define the RSA experiment about the hardness of inverting the RSA
function:
Definition 8.10
The
RSA experiment
RSA
A,
Gen
RSA
(
k
)
, where
A
is a PPT adversary
and
k
any value of the security parameter, is the following:
1.
1
k
(
n
,
e
,
d
)
←
Gen
RSA
(
)
.
2.
x
← Z
n
is randomly chosen and
y
:=
RSA
(
n
,
e
)
(
x
)
∈ Z
n
is computed.
is given
n
,
e
,
y
, and outputs
x
∈ Z
n
.
4. The output of the experiment is 1 if
x
3.
A
x
and 0 otherwise.
=
This experiment allows us to formally define the hardness of the 'RSA problem':
Definition 8.11
The RSA problem is
said to be hard relative to
Gen
RSA
if, for every
PPT adversary
A
, there exists a negligible function
negl
such that
Pr
(
RSA
A
,
Gen
RSA
(
k
)
=
1
)
≤
negl
(
k
).
The
RSA assumption
is the assumption that the RSA problem is hard.
Remarks 8.5
1. In the description of
Gen
RSA
given in Algorithm 8.1 we required that, on input
1
k
,
Gen
RSA
should return a modulus
n
which is the product of two random
primes of length
k
. The reason for taking primes of the same length is to make
the modulus as difficult to factor as possible relative to its size since, as we have
mentioned, there are factoring algorithms like ECM whose running time is a
function of the size of the smallest factor of the number being factored. It is
not strictly necessary that the two primes have exactly the same length, so this
condition is often relaxed by requiring that both primes have
approximately
the
same length.
2.
Gen
RSA
may be modified by computing
d
as the inverse of
e
in
Z
λ(
n
)
, where
λ
is the
Carmichael lambda function
, with
λ(
n
)
defined as the smallest positive
∈ Z
n
. It is straightforward to
see that Proposition 8.1 also holds if this value of
d
is used instead of the one in
Algorithm 8.1 and this implies that the modified version of
Gen
RSA
may be used
in all the RSA-based schemes we will introduce in the sequel. This variant has
the advantage that this way
d
may be a little smaller (see Exercise 8.4 below).
3. The definition of hardness of the RSA problem is relative to the instance gener-
ator algorithm
Gen
RSA
, as we may consider different variants of this algorithm
(for example, there is the variant mentioned in the preceding item and, on the
other hand, the way in which
e
should be chosen was not specified). However,
the most important known requirement that
Gen
RSA
must fulfill for the RSA
problem to be hard is that
n
should be the product of two randomly chosen
primes of (approximately) the same length. This condition is already included
in our definition and hence, in what follows, we shall not make explicit mention
of
Gen
RSA
when referring to the RSA problem.
integer such that
a
λ(
n
)
≡
1
(
mod
n
)
for each
a
