Rebalanced-RSA-CRT

cypherpunk cyphrpunk at gmail.com
Mon Apr 11 10:23:46 PDT 2005


On Apr 7, 2005 10:13 AM, Sarad AV <jtrjtrjtr2001 at yahoo.com> wrote:
> hi,
> 
> I am a little confused after reading this:
> 
> http://www.rsasecurity.com/rsalabs/cryptobytes/CryptoBytes_January_2002_final.pdf
> 
> RSA-CRT decryption is nearly four times faster than
> using only modular exponentiation for decryption. Is
> Rebalanced-RSA-CRT three times faster in decryption
> than RSA decryption only using modular exponentiation
> or is it three times faster than RSA-CRT in
> decryption?

It has to be the second one. If it were only 3 times faster than
vanilla RSA, while RSA-CRT was 4 times faster than vanilla, then
rebalanced would not be a speedup over the usual way of doing things. 
Rebalanced RSA is 3 times faster than RSA-CRT.

What "rebalanced RSA" means is that you choose the private exponent d
so that exponentiation with it is fast. This speeds up decryption at
the expense of encryption. You can't just choose a small d; this is
known to be insecure. Instead they propose to choose a d such that the
two exponents in the CRT, d mod p-1 and d mod q-1, are relatively
small, about 160 bits. This gives a factor of 3 speedup vs the usual
512 bit exponent in 1024 bit RSA-CRT.

Is this safe? Who knows? I wouldn't recommend using it until Don
Coppersmith chewed on it for a while. He's the guy who pushes the
state of the art on small-d attacks. I'd wait for his opinion on
whether this variant on small-d escapes his attacks.





More information about the cypherpunks-legacy mailing list