Cryptanalysis of RSA with Small Prime Combination - Information Security and Cryptology-ICISC 2010 - page 105

= N 4 + γ there are at least N 1 −γ−ε weak RSA-keys.
From this, we get a probabilistic factorization algorithm with expected running
time O ( N γ + ε ). This result perfectly matches our factoring algorithm result.
On the other hand, one can see that the weak key attack has a nice inter-
polation property towards our factoring algorithm: As

able to show that for | ρq − p |

| ρq − p |

decreases, the
number of weak public keys increases. For γ approaching zero almost all keys
are weak, corresponding to the fact that N canbefactoredwithoutanyhint
that is encoded in e .
The remainder of this paper is organized as follows. In section 2, we investigate
algorithms of factorization. In section 3, we present new result on weak RSA keys.
We conclude this paper in section 4.

2 Factorization Attack

Let N = pq be an RSA-modulus, where p and q are primes of equal bit-size (wlog
q<p< 2 q ). Let p − √ N<p N 4 .

Then it is known that the factorization of N can be recovered by the following
Coppersmith's theorem [2].
Theorem 1 (Coppersmith). Let N = pq where primes p and q are of the
same bit-size. Suppose we given an approximation of p with additive error at
most N 4 .Then N can be factored in time polynomial in log N .
If

q = N θ .If0 <θ

1

− ≤

4 ,wehavethat p

− q ≤

4 <θ< 2 , Weger [14] showed that the Fermat factoring method can factor
N in time O ( N 2 θ− 2 ). Here we show a square root attack by applying the baby-
step giant-step method of Shanks [13] which deals with the discrete logarithm
problem.
Theorem 2. Let N = pq where primes p and q satisfy p

1

q = N θ with

1
4

− <

θ< 2 ,then N can be factored in time O ( N θ− 4 + ε ) .
Proof. We have

2 √ N )( p + q +2 √ N ) .

q ) 2 =( p + q ) 2

( p − − 4 N =( p + q −

Hence

2 √ N =

q ) 2
p + q +2 √ N

q ) 2
4 √ N

( p −

< ( p

− 1

4 N 2 θ− 2 .

p + q − = (1)

The exponent of the multiplicative group modulo N is lcm( p − 1 ,q − 1). Let

λ ( N )=lcm( p − 1 ,q − 1). Here as usual, we assume gcd( p − 1 ,q − 1) = 2 and

λ ( N )= ( p

− 1)( q − 1) N +1

2 −

p + q
2

= . (2)

2

2 √ 2 N θ− 4 . By (1) and (2), we have that

1

Choose M to be an integer no less than

there exist integers u 0 and v 0 such that
λ ( N )= N +1

√ N

2 −

− u 0 − v 0 · M

with 0 ≤ u 0 ,v 0 <M .