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

    16 Citations (Scopus)

    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 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
    PublisherSpringer
    Pages52-62
    Number of pages11
    ISBN (Electronic)3540418989, 9783540418986
    DOIs
    Publication statusPublished - 2001
    EventCryptographers' Track at RSA Conference, CT-RSA 2001 - San Francisco, United States of America
    Duration: 8 Apr 200112 Apr 2001

    Publication series

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

    Conference

    ConferenceCryptographers' Track at RSA Conference, CT-RSA 2001
    Abbreviated titleCT-RSA 2001
    CountryUnited States of America
    CitySan Francisco
    Period8/04/0112/04/01

    Cite this

    Steinfeld, R., & Zheng, Y. (2001). An advantage of low-exponent RSA with modulus primes sharing least significant bits. In D. Naccache (Ed.), Topics in Cryptology - CT-RSA 2001 - The Cryptographers’ Track at RSA Conference 2001, Proceedings (pp. 52-62). (Lecture Notes in Computer Science; Vol. 2020). Springer. https://doi.org/10.1007/3-540-45353-9_5