[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