Cryptography Reference
In-Depth Information
Exercise
24.1.13
tells us that FACTOR is at least as hard as RSA. A more useful
interpretation is that the RSA problem is no harder than factoring. We are interested in the
relative difficulty of such problems, as a function of the input size. Lemma
24.1.14
is the
main tool for comparing these problems.
4
Lemma 24.1.14
Let A be a perfect oracle that takes as input an integer N and outputs a
multiple of λ
(
N
)
. Then one can split N in randomised polynomial-time using an expected
polynomially many queries to A.
Proof
Let
N
be the integer to be factored. We may assume that
N
is composite, not a prime
power, odd and has no very small factors. Let
M
be the output of the oracle
A
on
N
.(Note
that the case of non-perfect oracles is not harder: one can easily test whether the output
of
A
is correct by taking a few random integers 1
<a<N
such that gcd(
a,N
)
=
1 and
checking whether
a
M
1(mod
N
).)
Since
N
is odd we have that
M
is even. Write
M
≡
2
r
m
where
m
is odd. Now choose uni-
formly at random an integer 1
<a<N
. Check whether gcd(
a,N
)
=
=
1. If not then we have
a
M
(mod
N
)
(this is similar to the Miller-Rabin test; see Section
12.1.2
). We know that
a
r
=
a
m
(mod
N
),
a
1
=
a
0
split
N
, otherwise compute
a
0
=
(mod
N
)
,...,a
r
=
1, so
either
a
0
=
1 or else somewhere along the way there is a non-trivial square root
x
of 1.
If
x
1
,N
) yields a non-trivial factor of
N
. All computations require a
polynomially bounded number of bit operations.
Let
p
and
q
be two distinct prime factors of
N
. Since
a
is chosen uniformly at random
it follows that gcd(
a,N
)
>
1or(
p
)
=−
1 then gcd(
x
+
(
q
) with probability at least 1
/
2. In either case,
the above process splits
N
. The expected number of trials to split
N
is therefore at most 2.
Repeating the above process on each of the factors in turn, one can factor
N
completely.
The expected number of iterations is
O
(log(
N
)). For a complete anaysis of this reduction
see Section 7.7 of Talbot and Welsh [
539
] or Section 10.6 of Shoup [
497
].
=−
Two special cases of Lemma
24.1.14
are FACTOR
≤
R
COMPUTE-LAMBDA and
FACTOR
≤
R
COMPUTE-PHI. Note that these reductions are randomised and the running
time is only an expected value. Coron and May [
140
] showed a deterministic polynomial-
time reduction FACTOR
≤
R
RSA-PRIVATE-KEY (also see Section 4.6 of [
371
]).
Exercise 24.1.15
Restricting attention to integers of the form
N
=
pq
where
p
and
q
are
distinct primes, show that FACTOR
≤
R
RSA-PRIVATE KEY.
Exercise 24.1.16
The
STRONG-RSA
problem is: given an RSA modulus
N
and
y
∈ N
to find any pair (
x,e
) of integers such that
e>
1 and
x
e
≡
y
(mod
N
)
.
4
The original RSA paper credits this result to G. Miller.
