Cryptography Reference
In-Depth Information
We choose an integer
a
such that gcd(
a, N
) = 1. We have that
a
λ
(
N
)
≡
1mod
N
.Let
b
=
a
N
+
2
−
√
N
. We construct two lists as follows,
L
1
=
a
v·M
mod
N
0
v<M
≤
and
a
−u
mod
N
0
u<M
.
According to Algorithm 7.5.1 in [3], we can sort these lists and find a common
value
a
v
0
·M
L
2
=
b
·
≤
a
−u
0
mod
N
in time
O
(
M
log
M
). A low-storage alternative
is to use Pollard's
λ
method [11]. Then
u
0
and
v
0
are known and
p
+
q
can be
=
b
·
recovered by
p
+
q
=2
√
N
+
u
0
+
v
0
·
M
. Finally we can get
p
and
q
from
the solutions of the equation
y
2
−
(
p
+
q
)
y
+
N
= 0. Thus the factorization of
N
follows.
Instead of considering
p
p
=
N
θ
to
get an additional result. We present an algorithm to factor
N
=
pq
with small
2
q − p
by using a more sophisticated square root attack which applied to RSA
with small CRT secret exponent. One can see [10] for details.
−
q
=
N
θ
, now we consider the case 2
q
−
p
=
N
θ
with
Theorem 3.
Let
N
=
pq
where primes
p
and
q
satisfy
2
q
−
4
<θ<
2
,then
N
canbefactoredintime
O
(
N
θ−
4
+
ε
)
.
Proof.
We have
1
2
√
2
N
)(
p
+2
q
+2
√
2
N
)
.
p
)
2
=(
p
+2
q
)
2
(2
q
−
−
8
N
=(
p
+2
q
−
p
=
N
θ
,then
If 2
q
−
2
√
2
N
=
p
)
2
p
+2
q
+2
√
2
N
p
)
2
4
√
2
N
≤
(2
q
−
(2
q
−
1
4
N
2
θ−
2
.
p
+2
q
−
<
Hence
φ
(
N
)=
N
+1
−
p
−
q
=
N
+2
−
(
p
+2
q
)+(
q
−
1)
2
√
2
N
=
N
+2
−
−
w
+(
q
−
1)
(3)
w<
4
N
2
θ−
2
.
with the unknown
w
satisfying 0
≤
By (3), we have that
2
√
2
N
N
+2
−
−
w
≡
0mod(
q
−
1)
,
(4)
and
2
√
2
N
)
w
−
(
N
+2
−
≡
0mod(
q
−
1)
.
(5)
Since
w<q
1and
q
is a prime, we can recover
w
from equation (5). Choose
an integer
a
such that gcd(
a, N
)=1.Wehave
a
q−
1
−
≡
1mod
q
.Thusby(5),we
have
a
w−
(
N
+2
−
2
√
2
N
)
=1mod
q.
Search WWH ::
Custom Search