Cryptography Reference
In-Depth Information
Definition 24.1.9
Let
N,e
be such that gcd(
e,λ
(
N
))
=
1. The
RSA problem
(also called
)
∗
to compute
x
such that
x
e
the
e
th roots problem
)is:given
y
∈
(
Z
/N
Z
≡
y
(mod
N
).
It is clear that the RSA problem is not harder than factoring.
Lemma 24.1.10
The OWE-CPA security of textbook RSA is equivalent to the RSA problem.
Proof
(Sketch) We show that an algorithm to break OWE-CPA security of textbook RSA
can be used to build an algorithm to solve the RSA problem. Let
A
be an adversary against
the OWE-CPA security of RSA. Let (
N,e,
c
) be a challenge RSA problem instance. If
1
<
gcd(
c
,N
)
<N
then split
N
and solve the RSA problem. Otherwise, call the adversary
A
on the public key (
N,e
) and offer the challenge ciphertext
c
.If
A
returns the message
m
then we are done. If
A
returns
⊥
(e.g., because the decryption of
c
does not lie in
M
κ
) then
replace
c
by
c
r
e
(mod
N
) for a random 1
<r<N
and repeat. When
M
κ
={
κ
−
2
then
with probability at least 1
/
4, the reduction will succeed, and so one expects to perform 4
trials. The converse is also immediate.
0
,
1
}
Exercise 24.1.11
Show that textbook RSA has selective signature forgery under passive
attacks if and only if the RSA problem is hard.
One of the major unsolved problems in cryptography is to determine the relationship
between the RSA problem and factoring. There is no known reduction of factoring to
breaking RSA. Indeed, there is some indirect evidence that breaking RSA with small
public exponent
e
is not as hard as factoring: Boneh and Venkatesan [
82
] show that an
efficient “algebraic reduction”
3
from FACTOR to low-exponent RSA can be converted into
an efficient algorithm for factoring. Similarly, Coppersmith [
131
] shows that some variants
of the RSA problem, where
e
is small and only a small part of an
e
th root
x
is unknown,
are easy (see Exercise
19.1.15
).
Definition
24.1.12
describes some computational problems underlying the security of
RSA. The reader is warned that some of these names are non-standard.
Definition 24.1.12
Let
S
be a set of integers, for example
S
= N
or
S
={
pq
:
p
and
q
are
primes such that
p<q<
2
p
}
. We call the latter set the
set of RSA moduli
.
∈
FACTOR:
Given
N
S
to compute the list of prime factors of
N
.
COMPUTE-PHI:
Given
N
S
to compute
ϕ
(
N
).
COMPUTE-LAMBDA:
Given
N
∈
∈
S
to compute
λ
(
N
).
RSA-PRIVATE-KEY:
Given (
N,e
)
∈
S
× N
to output
⊥
if
e
is not coprime to
λ
(
N
), or
d
such that
ed
≡
1(mod
λ
(
N
)).
Exercise 24.1.13
Show that RSA
≤
R
RSA-PRIVATE-KEY
≤
R
COMPUTE-LAMBDA
≤
R
FACTOR for integers
N
∈ N
.
3
We do not give a formal definition. Essentially this is an algorithm that takes as input
N
, queries an oracle for the RSA problem,
and outputs a finite set of short algebraic formulae, one of which splits the integer
N
.
