Bull. Korean Math. Soc. 2009; 46(4): 721-741
Printed July 1, 2009
https://doi.org/10.4134/BKMS.2009.46.4.721
Copyright © The Korean Mathematical Society.
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
2014; 51(5): 1347-1356
2016; 53(1): 1-20
2001; 38(1): 191-195
2005; 42(1): 203-211
© 2022. The Korean Mathematical Society. Powered by INFOrang Co., Ltd