Cryptography Reference
In-Depth Information
Definition 7.8 (RSA assumption)
Let
I
k
:=
{
(
n, e
)
∈
I
|
n
=
pq
;
|
p
|
=
|
q
|
=
k
}
for
k
]
be a positive polynomial, and
A
(
p, g, y
)
be a PPT algorithm.
Then the RSA assumption says that there exists a
k
0
∈
N
∈
N
,
p
(
k
)
∈
Z
[
N
, such that
1
p
(
k
)
u
←
u
←
Z
n
]
Pr[
A
(
n, e, y
)=RSA
n,d
(
y
):(
n, e
)
I
k
;
y
≤
for all
k
k
0
.
Again, the PPT algorithm
A
models the adversary who tries to compute
RSA
n,d
(
y
) without knowing the trapdoor information. The RSA assumption may
be interpreted in an analogous way to the DLA. The fraction of keys (
n, e
) in
I
k
,for
which
A
has a significant chance to succeed, must be negligibly small if the security
parameter
k
is sufficiently large.
There is also a stronger version of the RSA assumption known as the
strong
RSA assumption
. The strong RSA assumption differs from the RSA assumption
in that the adversary can select the public exponent
e
: given a modulus
n
and a
ciphertext
c
, the adversary must compute any plaintext
m
and public exponent
e
such that
c
=
m
e
(mod
n
). For the purpose of this topic, we don't use the strong
RSA assumption anymore.
If we accept the RSA assumption, then the
RSA problem
(RSAP) captured in
Definition 7.9 is intractable.
Definition 7.9 (RSA problem)
Let
(
n, e
)
be a public key and
c
=
m
e
(mod
n
)
.
The RSAP is to determine
m
(i.e., the
e
th
root of
c
modulo
n
) if the private key
(
n, d
)
and the factorization of
n
(i.e.,
p
and
q
) are not known.
≥
The RSA assumption and the RSAP are at the core of many public key cryp-
tosystems, including, for example, the RSA public key cryptosystem (see Sections
14.2.1 and 15.2.1). Because the prime factors of
n
(i.e.,
p
and
q
) represent a(nother)
trapdoor for RSA
n,d
(in addition to
d
), somebody who is able to factor
n
is also able
to compute RSA
n,d
and to invert RSA
n,e
accordingly. Consequently, one must make
the additional assumption that it is computationally infeasible (for the adversary one
has in mind) to factor
n
. This is where the
integer factoring assumption
(IFA) as
formally expressed in Definition 7.10 comes into play.
Definition 7.10 (Integer factoring assumption)
Let
I
k
:=
{
n
∈
I
|
n
=
pq
;
|
p
|
=
|
,
p
(
k
)
be a positive polynomial, and
A
(
n
)
be a PPT algorithm.
Then the IFA says that there exists a
k
0
∈
N
q
|
=
k
}
for
k
∈
N
, such that
1
p
(
k
)
u
←
Pr[
A
(
n
)=
p
:
n
I
k
]
≤
