Bulletin of the
Korean Mathematical Society BKMS

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