Abstract
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 secretexponent 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 2^{m}. Thus the BDF attack is intractable for such moduli with large m. Furthermore, we prove a general related result, namely that if lowexponent RSA using an (m − LSbS) modulus is secure against polytime conventional attacks, then it is also secure against polytime partial key exposure attacks accessing up to 2m LS bits of d. Therefore, if lowexponent 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 publicserveraided RSA decryption/signature generation.
Original language  English 

Title of host publication  Topics in Cryptology  CTRSA 2001  The Cryptographers’ Track at RSA Conference 2001, Proceedings 
Editors  David Naccache 
Place of Publication  Berlin Germany 
Publisher  Springer 
Pages  5262 
Number of pages  11 
ISBN (Electronic)  3540418989, 9783540418986 
DOIs  
Publication status  Published  2001 
Event  Cryptographers Track held at the RSA Conference (CTRSA) 2001  San Francisco, United States of America Duration: 8 Apr 2001 → 12 Apr 2001 https://link.springer.com/book/10.1007/3540453539 (Proceedings) 
Publication series
Name  Lecture Notes in Computer Science 

Publisher  Springer 
Volume  2020 
ISSN (Print)  03029743 
ISSN (Electronic)  16113349 
Conference
Conference  Cryptographers Track held at the RSA Conference (CTRSA) 2001 

Abbreviated title  CTRSA 2001 
Country/Territory  United States of America 
City  San Francisco 
Period  8/04/01 → 12/04/01 
Internet address 
