We investigate the security of a variant of the RSA public-key cryptosystem called
LSBS-RSA, in which the modulus primes share a large number of least-significant bits. We show that low public-exponent LSBS-RSA is inherently resistant to
Partial Key Exposure (PKE) attacks in which least-significant bits of the secret exponent are revealed to the attacker, and in particular that the Boneh-Durfee-Frankel PKE attack [5] on low public-exponent RSA is less effective for LSBS-RSA systems than for standard RSA. On the other hand, we show that large public-exponent LSBS-RSA is more vulnerable to such attacks than standard RSA. An application to server-aided RSA signature generation is proposed.
Key words RSA Cryptosystem - Communication Security - Cryptanalysis - Partial Key Exposure - Boneh-Durfee-Frankel Attack - Coppersmith Algorithm - Least-Significant Bits - Server-Aided Signature Generation
This is an extended version of an earlier paper presented at the Cryptographer
s Track RSA Conference (CT-RSA 2001), April 8-12 2001, San Francisco, USA [20].This work was done while the author was at the School of Network Computing, Monash University, Frankston, Australia.
Acknowledgement The authors would like to thank the anonymous referees of CT-RSA 2001 for their helpful comments on a preliminary version [20] of some of the results in this paper.