An advantage of low-exponent RSA with modulus primes sharing least significant bits

Ron Steinfeld, Yuliang Zheng

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

19 Citations (Scopus)


Let N = pq denote an RSA modulus of length n bits. Call N an (m − LSbS) RSA modulus if p and q have exactly m equal Least Significant (LS) bits. In Asiacrypt `98, Boneh, Durfee and Frankel (BDF) described several interesting `partial key exposure' attacks on the RSA system. In particular, for low public exponent RSA, they show how to recover in time polynomial in n the whole secret-exponent d given only the n=4 LS bits of d. In this note, we relax a hidden assumption in the running time estimate presented by BDF for this attack. We show that the running time estimated by BDF for their attack is too low for (m− LSbS) RSA moduli by a factor in the order of 2m. Thus the BDF attack is intractable for such moduli with large m. Furthermore, we prove a general related result, namely that if low-exponent RSA using an (m − LSbS) modulus is secure against poly-time conventional attacks, then it is also secure against poly-time partial key exposure attacks accessing up to 2m LS bits of d. Therefore, if low-exponent RSA using (n=4(1 − ɛ) − LSbS) moduli for small ɛ is secure, then this result (together with BDF's result on securely leaking the n=2 MS bits of d) opens the possibility of fast and secure public-server-aided RSA decryption/signature generation.

Original languageEnglish
Title of host publicationTopics in Cryptology - CT-RSA 2001
Subtitle of host publicationThe Cryptographers’ Track at RSA Conference 2001 San Francisco, CA, USA, April 8–12, 2001 Proceedings
EditorsDavid Naccache
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Number of pages11
ISBN (Electronic)9783540453536
ISBN (Print)3540418989, 9783540418986
Publication statusPublished - Apr 2001
EventCryptographers' Track at RSA Conference, CT-RSA - 2001 - San Francisco, United States
Duration: 8 Apr 200112 Apr 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


OtherCryptographers' Track at RSA Conference, CT-RSA - 2001
Country/TerritoryUnited States
CitySan Francisco


Dive into the research topics of 'An advantage of low-exponent RSA with modulus primes sharing least significant bits'. Together they form a unique fingerprint.

Cite this