Partial key exposure attacks on RSA and its variant by guessing a few bits of one of the prime factors
Bull. Korean Math. Soc. 2009 Vol. 46, No. 4, 721-741
https://doi.org/10.4134/BKMS.2009.46.4.721
Printed July 1, 2009
Santanu Sarkar and Subhamoy Maitra
Indian Statistical Institute
Abstract : 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
Downloads: Full-text PDF  


Copyright © Korean Mathematical Society. All Rights Reserved.
The Korea Science Technology Center (Rm. 411), 22, Teheran-ro 7-gil, Gangnam-gu, Seoul 06130, Korea
Tel: 82-2-565-0361  | Fax: 82-2-565-0364  | E-mail: paper@kms.or.kr   | Powered by INFOrang Co., Ltd