Cryptography Reference
In-Depth Information
4
N
2
θ−
2
.Thusby(7)wehave
with 0
<w
≤
2
√
stN
tN
+
s
−
−
w
=0mod(
q
−
1)
.
(8)
This is similar to equation (4). Then similarly as proving Theorem 3, we have
that Theorem 4 holds.
3 Weak Key Attack and New Weak Keys
In [1], Blomer and May proved that
p
and
q
can be found in polynomial time
for every
N
and
e
satisfying
ex
+
y
=0mod
φ
(
N
), with 0
<x≤
φ
(
N
)
e
N
4
p−q
1
3
q
=
N
4
+
γ
,itisprovedthatthenumberof
these
weak keys
is at least
N
1
−γ−ε
. In [8], Maitra and Sarkar showed that the
same result holds for 2
q
p−q
φ
(
N
)
N
4
and
|
y
|≤
ex
.Andif
p
−
p
=
N
4
+
γ
−
instead of
p
−
q
. Later in [9], Maitra and
=
N
4
+
γ
, and proved that the factorization
of
N
can be recovered in polynomial time for every
N
and
e
satisfying
ex
+
y
=
0mod
φ
(
N
), with 0
<x
|
ρq
−
p
|
Sarkar considered the case
φ
(
N
)
e
N
3
−
4
γ
|≤
|ρq−p|
φ
(
N
)
N
4
1
6
ex
. And it is
obtained that the number of these
weak keys
is at least
N
2
−ε
. In this section,
we revisit the weak key attack and find new weak keys. As usually, we formalize
the notion of weak keys as follows.
≤
and
|
y
8
Definition 1.
Let
C
be a class of RSA public keys
(
N, e
)
. The size of the class
C
is defined by
Size
C
(
N
)=
{
∈
Z
φ
(
N
)
|
e
(
N, e
)
∈
C
}
.
Aclass
C
is called weak if:
1.
Size
C
(
N
)=
Ω
(
N
τ
)
for some
τ>
0
;
2. There exists a probabilistic algorithm A that on every input
(
N, e
)
∈
C
outputs
the factorization of
N
in time polynomial in
log
N
.
Now we revisit the weak key attack and then present new weak keys over the
work of Maitra and Sarkar [9].
Theorem 5.
Let
N
=
pq
be an integer with primes satisfying
11
N
4
≤|
ρq
−
p
|
=
N
θ
<
√
N
where
ρ
is a known constant satisfying
1
<ρ
≤
2
.Denote
ρ
−
1
by
ρ
.
Define
[
ρq
]=
ρq
if
ρq
is even, otherwise
[
ρq
]=
ρq
. Suppose that
e
satisfies
the equation
ex
+
y
+
k
[
ρq
]=
kφ
(
N
)
(9)
for
k>
0
.Then
N
can be factored in polynomial time in
log
N
when
0
<x
≤
φ
(
N
)
e
N
4
|ρq−p|
|≤
|ρq−p|
φ
(
N
)
N
4
1
3
and
|
y
ex
.
We will apply the following classical theorem on diophantine approximations
(see Corollary 2, [1,
§
2] in [6]).
Search WWH ::
Custom Search