More on Correcting Errors in RSA Private Keys: Breaking CRT-RSA With Low Weight Decryption Exponents
Several schemes have been proposed towards the fast encryption and decryption in RSA and its variants. One popular idea is to use integers having low Hamming weight in the preparation of the decryption exponents. This is to reduce the multiplication effort in the square and multiply method in the exponentiation routine, both in encryption and decryption. In particular, the authors show that the CRT-RSA schemes presented in SAC 1996 and ACISP 2005 with low weight decryption exponents can be broken in a few minutes in certain cases.