TY - GEN

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

AU - Steinfeld, Ron

AU - Zheng, Yuliang

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84937575840&partnerID=8YFLogxK

U2 - 10.1007/3-540-45353-9_5

DO - 10.1007/3-540-45353-9_5

M3 - Conference Paper

AN - SCOPUS:84937575840

T3 - Lecture Notes in Computer Science

SP - 52

EP - 62

BT - Topics in Cryptology - CT-RSA 2001 - The Cryptographers’ Track at RSA Conference 2001, Proceedings

A2 - Naccache, David

PB - Springer

CY - Berlin Germany

T2 - Cryptographers' Track at RSA Conference, CT-RSA 2001

Y2 - 8 April 2001 through 12 April 2001

ER -