Bulletin of the
Korean Mathematical Society

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016



Bull. Korean Math. Soc. 2009; 46(4): 721-741

Printed July 1, 2009


Copyright © The Korean Mathematical Society.

Partial key exposure attacks on RSA and its variant by guessing a few bits of one of the prime factors

Santanu Sarkar and Subhamoy Maitra

Indian Statistical Institute


Consider RSA with $N = pq$, $q < p < 2q$, public encryption exponent $e$ and private decryption exponent $d$. We first study cryptanalysis of RSA when certain amount of the Most Significant Bits (MSBs) or Least Significant Bits (LSBs) of $d$ is known. The basic lattice based technique is similar to that of Ernst et al. in Eurocrypt 2005. However, our idea of guessing a few MSBs of the secret prime $p$ substantially reduces the requirement of MSBs or LSBs of $d$ for the key exposure attack. Further, we consider the RSA variant proposed by Sun and Yang in PKC 2005 and show that the partial key exposure attack works significantly on this variant.

Keywords: cryptanalysis, factorization, lattice, LLL algorithm, RSA, side channel attacks, weak keys

MSC numbers: Primary 11Y05; Secondary 94A60