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 PaperResearchpeer-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 - The Cryptographers’ Track at RSA Conference 2001, Proceedings
    EditorsDavid Naccache
    Place of PublicationBerlin Germany
    Number of pages11
    ISBN (Electronic)3540418989, 9783540418986
    Publication statusPublished - 2001
    EventCryptographers Track held at the RSA Conference (CT-RSA) 2001 - San Francisco, United States of America
    Duration: 8 Apr 200112 Apr 2001 (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceCryptographers Track held at the RSA Conference (CT-RSA) 2001
    Abbreviated titleCT-RSA 2001
    Country/TerritoryUnited States of America
    CitySan Francisco
    Internet address

    Cite this