Cryptography Reference
In-Depth Information
3
φ
(
N
)
N
4
|ρq−p|
1
Every key tuple (
N, e
)thatsatisfies(9)with0
<x
≤
and
e
|≤
|ρq−p|
φ
(
N
)
N
4
|
ex
yields the factorization of
N
in polynomial time. These tuples
(
N, e
) are weak keys that should not be used in the design of a crypto-system.
Our attack in Theorem 5 defines a weak class
C
. We are going to discuss how
large this weak class is. We are interested in a lower bound of
C
.
y
=
N
4
+
γ
and
0
<γ<
4
. Further, let
C
be the weak key class that is given by the public key
tuples
(
N, e
)
defined in Theorem 5 with the additional restriction that
e
Theorem 6.
Let
p
and
q
be safety prime numbers with
|
ρq
−
p
|
∈
Z
φ
(
N
)
and
e>
φ
(
N
)
4
,then
Size
C
(
N
)=
Ω
.
N
1
−γ
log log
2
(
N
2
)
[
ρq
]. Let
C
be the weak keys that is given by
the public key tuples (
N, e
) defined in Theorem 5 with the additional restriction
that
e
Proof.
Denote
Θ
(
N
)=
φ
(
N
)
−
and
e>
Θ
(
N
)
4
∈
Z
Θ
(
N
)
. Similarly as the proof of Theorem 7 in [1], we
have
Size
C
(
N
)=
Ω
.
N
1
−γ
log log
2
(
N
2
)
If
p
and
q
are safety prime numbers, then
p
=2
p
+1 and
q
=2
q
+1, and
φ
(
N
)=4
p
q
with
p
and
q
being primes. Thus we have
φ
(
N
)
1
≤
3
√
N.
i
=
φ
(
N
)
/
4
gcd(
i,φ
(
N
)
/
4)
=1
We have
Size
C
(
N
)=
{
∈
Z
φ
(
N
)
|
e
(
N, e
)
∈
C
}
{
∈
Z
Θ
(
N
)
|
≥
e
(
N, e
)
∈
C,
gcd(
e, φ
(
N
)) = 1
}
3
√
N
≥
Size
C
(
N
)
−
=
Ω
.
N
1
−γ
log log
2
(
N
2
)
This completes the proof of Theorem 6.
Thus when
p
and
q
are safety prime numbers, the result of Theorem 5 presents
new weak keys other than those
N
2
−ε
weak keys presented in [8].
4Con lu on
In this paper, we investigate the cryptoanalysis of RSA modulus
N
=
pq
with
small prime combination
|
ρq
−
p
|
where
ρ
is a known constant (1
≤
ρ
≤
2). We
Search WWH ::
Custom Search