Re: In RSA, does knowledge of d%(p-1) and d%(q-1) allow factoring n?



In article <slrnesjth4.9i.bmoeller@xxxxxxxxxxx>,
Bodo Moeller <bmoeller@xxxxxxx> wrote:

Francois Grieu <fgrieu@xxxxxxxxx>:

Consider an RSA key (n,e,d) with n = p*q, p and q large primes,
e odd, e>2, e*d=1 mod LCM(p-1, q-1).

Efficient algorithms are known that recover p, q from n, e, d.

Rather, assume n, e, d%(p-1) and d%(q-1) are known. That is, the
exponents used in the CRT expression of the private key leaked.

Is it possible to recover p, q, or oherwise perform the private
RSA function x -> (x^d)%n ?

You bet! If you know D = d%(p-1), this means you have an integer
D such that e*D - 1 = 0 (mod p-1). So compute f = e*D - 1,
pick some random integer z such that 0 < z < n, and compute
z^f mod n.

Let's look what we have here -- even though we may not know p yet, we
can make some statements about what is happening in this computation,
taken mod p: Namely, we can show that z^f = 1 (mod p) (unless we
were lucky enough to pick a random number z such that z mod p = 0,
in which case we can factor n just by computing gcd(z, n)), because
exponent f is some multiple of the group order, p-1.

So take z^f - 1 (which accordingly will satisfy z^f - 1 = 0 (mod p))
and compute gcd(n, z^f - 1). Chances are the result will be p.

That's correct, well explained, correct, and previously unknown to me.
Thanks a lot!

Hence, if either of the two exponents used in the CRT expression of
the private key leaks, that fully compromize the private key.


Francois Grieu
.