Added signature tag (duh...)
Link
user10496
user10496
Source Link
user10496
user10496

Rabin-Williams, blinding and size of Integer r?

I was reading the paper Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library. The library uses blinding, but it was not enough to stop key recovery.

But my question is about the Integer r used for blinding. Crypto++ uses a random integer in the range [1, n-1]. Then, the operation proceeds by calculating m * r (mod N); (m * r)d (mod N); and finally (m * r) d * r-d (mod N) = md (mod N). If n is 3072 bits, then r is effectively 3072 bits.

Since r needs to provide a mask at an equivalent security level of 128-bits, wouldn't a 256-bit integer suffice to mask the operation? In this case, its 128-bits times 2 because there's a 50/50 chance of selecting a 0 or 1. So someone trying to build a system of equations to deduce bits in the private key would need a table at least 2128 in size.

Is there criteria in selecting the size of the blinding integer r for Rabin-Williams? Or is it convention (or required) to always use the size of the modulus?