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

[rcs at xmission.com]

In normal usage, both the encryption (E) and decryption (D) exponent for RSA
are odd numbers.  Suppose the RSA modulus is M = P*Q, with P and Q prime.
The product D*E must be congruent to 1 modulo GCD(P-1,Q-1).
This implies that P-1 divides D*E-1.  Assuming P>2, then P-1 is even,
so D*E-1 must be even.  Then D*E is odd, and so are D and E.
So the low bit of D is 1.
D can be masked by adding a random multiple of GCD(P-1,Q-1), but the
masked D is still an odd number (since the GCD is even).

Rich Schroeppel

-----
Quoting Ray Dillinger <bear at sonic.net>:
> 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