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

Cryptanalysis of RSA with Small Prime
Combination

Xianmeng Meng

School of Statistics and Mathematics
Shandong University of Finance
Jinan 250014, P.R. China
[e-mail]

Abstract. Let N = pq be RSA modulus where primes p and q are of

1
4 + γ where ρ is a known constant
satisfying 1 ≤ ρ ≤ 2 and the constant γ satisfies 0 <γ< 4 , we show the
factorization attack on N and weak key attack against RSA modulus N .
We present algorithms to find the factorization of N in time O ( N γ + ε )
by some square root attacks, such as the baby-step giant-step method
and a more sophisticated square root attack. Using similar techniques
of Blomer and May (PKC 2004), we present a weak key attack and find
new weak keys over the work of Maitra and Sarkar (ISC 2008).

thesamebit-length.If |ρq − p| = N

Keywords: RSA, Factorization, Weak Keys.

1 Introduction

RSA is a public key cryptosystem, which was proposed by Rivest, Shamir and
Adleman [12] in 1978. The public exponent e and the private exponent d are
chosen to be inverse of each other modulo φ ( N )=( p 1).

It is well-known that small prime difference makes RSA insecure. In [14],
Weger showed that if p

− 1)( q −

q is small, RSA system with small exponent is much
more vulnerable. In [8] [9], Maitra and Sarker revisited Wiener's continued frac-
tion method and showed that given ρ (1

−

≤ ρ ≤ 2) is known to the attacker

and δ< 2 −

2 , where the RSA modulus

the RSA keys are weak when d = N δ

N γ

N = pq with

16 . And using similar techniques they also present new
result over the work of Blomer and May [1]. In fact, a similar result was also
obtained independently by Han and Xu [5].
In this paper, we investigate the square root attack on factoring N = pq with
small

| ρq − p |≤

| ρq − p | where ρ is a known constant satisfying 1 ≤ ρ ≤ 2. We show that

= N 4 + γ and 0 <γ< 4 , one can find the factorization of N in time
O ( N γ + ε ). Furthermore, we present a weak key attack against RSA with small
|

for | ρq − p |

ρq − p | . We find new weak keys over the work of Maitra and Sarkar [8]. And we are

This research is partially supported by Project 973 (no: 2007CB807902) and the
science and technology foundation of the ministry of education (no. 210123) and the
natural science foundation in Shandong province (no: Y2008A22) in China.