Cryptography Reference
In-Depth Information
Exercise 8.2
Prove that the RSA problem is random self-reducible.
We will return to the RSA problem when discussing the RSA encryption scheme
but for now we just remark that, as already mentioned, a necessary condition for
the RSA assumption to hold is that factoring the modulus
n
be hard. Indeed, if the
factorization of
n
is known, then one may proceed as in the
Gen
RSA
algorithm to
solve the RSA problem: first
φ(
n
)
=
(
p
−
1
)(
q
−
1
)
is computed, then the inverse
d
=
e
−
1
mod
)
∈ Z
φ(
n
)
is computed by means of the extended Euclidean algorithm
and, finally,
y
d
mod
n
is computed by using the binary exponentiation method.
All these computations are efficient and hence the RSA assumption implies that
factoring the modulus
n
is hard. Thus, recalling the factoring assumption introduced
in Definition 3.15, we have proved the following:
φ(
n
Proposition 8.2
The RSA assumption implies the factoring assumption.
Since the RSA problem is no harder than factoring, it is natural to ask whether
the converse is also true, i.e., whether both assumptions are equivalent. In order to
disprove it one may try to find some condition that implies that the RSA problem is
easy but does not imply that factoring is easy. For example, it is clear that if one is
able to efficiently compute
on input
n
, then the RSA problem becomes easy
for we may take advantage of the knowledge of
φ(
n
)
e
−
1
∈ Z
φ(
n
)
φ(
n
)
to compute
d
=
.
However, this leads nowhere because we can show that
computing
φ(
n
)
is no easier
than factoring the modulus n
(and hence factoring
n
=
pq
and computing
φ(
n
)
=
(
p
−
1
)(
q
−
1
)
are equally hard). Indeed, suppose that both
n
and
φ(
n
)
are known.
Then
φ(
n
)
=
(
p
−
1
)(
q
−
1
)
=
pq
−
(
p
+
q
)
+
1 and hence we have equations:
p
+
q
=
n
−
φ(
n
)
+
1
pq
=
n
where
p
and
q
are the unknowns and the remaining terms are known. The zeros of
the polynomial
x
2
x
2
(
x
−
p
)(
x
−
q
)
=
−
(
p
+
q
)
x
+
pq
=
−
(
n
−
φ(
n
)
+
1
)
x
+
n
are precisely
p
and
q
and hence we only have to solve the quadratic equation:
x
2
−
(
n
−
φ(
n
)
+
1
)
x
+
n
=
0
whose coefficients are known, to find the factorization of
n
.
=
·
Example 8.1
Consider themodulus
n
p
q
, where
p
and
q
are (unknown) 1024-bit
φ(
)
primes, and the values of
n
and
n
are given by:
>n:=
23538372498408898020904820516194882190870515954482550253711433294824967383591284\
46844042074690277603497784339917211555362254378971172185266564969960989190738145\
81559762081612973350421474680153315264623295830664463318924022191113778607540232\
32012364526054251283789295120489864731342782075372824073611435656184645877272042\
24922319990089478607013995416230247080039877670515529684753026668533969494606154\
97754388878053194737328927330425629335766593509172159059739618216167237695957287\
65481579907273086935430737472301974772107008657018808368405599605158523746168029\
497346695193588274969164336700575376126547003051554101801:
