Cryptography Reference
In-Depth Information
1so
p
and
q
are the two roots of
X
2
notice that
ϕ
(
N
)
=
N
−
(
p
+
q
)
+
−
(
N
−
0. Solving this equation leads to the factorization of
N
.
RSAEMP reduces to RSAKRP
. If we can compute
d
, then we can get a multiple
of
ϕ
(
N
)
−
1)
X
+
N
=
λ
(
N
), namely
ed
−
1.
So it is sufficient to show that RSAFP reduces to RSAEMP in order to prove that
RSAKRP, RSAEMP, RSAOP, and RSAFP are all equivalent. Let us assume that we
know an integer
k
which is a multiple of
λ
(
N
). The following algorithm factorizes
N
in a surprisingly similar way to the Miller-Rabin primality test.
2
t
r
with
r
odd. (We isolate the powers of two.)
1. Let us thus write
k
=
∈
Z
N
x
r
2. We pick a random
x
and we compute
y
=
mod
N
. We iterate until
1. (Note that for at least three fourths of the
x
's which are not quadratic
residues modulo
p
or
q
, the corresponding
y
cannot be equal to 1, so we usually
do not have to iterate.)
3. If any of
y
,
y
2
y
=
mod
N
,...,
y
2
t
−
1
mod
N
is equal to
N
−
1, go back to the
previous step and try again. Otherwise, since
y
2
t
mod
N
must be 1, we have
found a nontrivial square root
z
of one.
4. Compute gcd(
z
+
1
,
N
) which must be a nontrivial factor of
N
: either
p
or
q
.
(See Fig. 9.8.) Note that if we have, for instance, (
p
)
1 and (
q
)
=
=−
1, then we
have
x
p
−
1
1 and
x
q
−
1
1. Thus, if 2
i
r
mod
p
=
mod
q
=
q
−
=
lcm(
p
−
1
,
q
−
1),
2
2
then
x
2
i
−
1
r
1 modulo
q
, hence it is a nontriv-
ial square root of one and the previous algorithm yields
p
and
q
. The same holds for
(
p
)
mod
N
is equal to 1 modulo
p
and to
q
−
1 and (
q
)
1. Thus the previous algorithm works for at least half of the
x
's ,
and eventually halts with the factorization of
N
.
=−
=
Here is the list of reductions that we have proven.
RSADP
⇐
RSAKRP
⇐
RSAOP
⇓
⇒
RSAEMP
RSAFP
The problem of whether breaking RSA is equivalent to the factorization of
N
or not
is a famous open problem. Paradoxically, it is a good thing to have no reduction, because
one would have been able to use it as a chosen ciphertext attack: using the decryptor as
an oracle in a chosen ciphertext attack would have led to the factorization of
N
, thus
at most
t
=
1
=
1
=
1
=
1
=
1
1
x
r
SQ
SQ
···
SQ
SQ
mod
n
is it
≡−
1?
Figure 9.8.
Reduction of RSAFP to RSAEMP.
Search WWH ::
Custom Search