On the security of RSA with primes sharing least-significant bits

Ron Steinfeld*, Yuliang Zheng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


We investigate the security of a variant of the RS A public-key cryptosystem called LSBS-RSA, in which the modulus primes share a large number of least-significant bits. We show that low public-exponent LSBS-RSA is inherently resistant to Partial Key Exposure (PKE) attacks in which least-significant bits of the secret exponent are revealed to the attacker, and in particular that the Boneh-Durfee-Frankel PKE attack [5] on low public-exponent RSA is less effective for LSBS-RSA systems than for standard RSA. On the other hand, we show that large public-exponent LSBS-RSA is more vulnerable to such attacks than standard RSA. An application to server-aided RSA signature generation is proposed.

Original languageEnglish
Pages (from-to)179-200
Number of pages22
JournalApplicable Algebra in Engineering, Communications and Computing
Issue number3-4
Publication statusPublished - Nov 2004


  • Boneh-Durfee-Frankel Attack
  • Communication Security
  • Coppersmith Algorithm
  • Cryptanalysis
  • Least-Significant Bits
  • Partial Key Exposure
  • RSA Cryptosystem
  • Server-Aided Signature Generation


Dive into the research topics of 'On the security of RSA with primes sharing least-significant bits'. Together they form a unique fingerprint.

Cite this