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

Georgi Guninski guninski at guninski.com
Sun Sep 11 04:29:19 EDT 2016


On Sat, Sep 10, 2016 at 06:25:27PM -0600, rcs at xmission.com wrote:
> 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
>

Thanks. Several people pointed offlist that d is always odd, so the question
doesn't make sense.
I missed that and tried random d's and random padded hashes per d. 


More information about the cryptography mailing list