On the Security of RSA with Primes Sharing Least-Significant Bits

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.This is an extended version of an earlier paper presented at the Cryptographers 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.