[Cryptography] Finding the least significant bit of RSA secret exponent from few signatures?

[Ray Dillinger]

On 09/08/2016 12:29 AM, Georgi Guninski wrote:
> I suppose this is well known and useless (if true).
> 
> The least significant bit of RSA secret exponent $d$ can be found
> with high probability (and sometimes unconditionally) from signatures
> of random stuff very fast. Get experimental support assuming H_i^d mod n are
> the signatures, H_i is the padded hash (if this is not known from the
> signature, ignore this mail).
> 
> Is this well known and useless?

It is well known and one of the things that implementers of crypto
have to be careful about.  RSA as raw math is beautiful and simple;
RSA as a viable cryptographic primitive requires IVs, padding, and
very careful thought.

In principle the attack you describe works; in practice RSA crypto
pads values and transforms keys to prevent it.

				Bear


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160909/279af833/attachment.sig>