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

*From*: Francois Grieu <fgrieu@xxxxxxxxx>*Date*: Wed, 07 Feb 2007 21:08:17 +0100

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

.

**References**:**In RSA, does knowledge of d%(p-1) and d%(q-1) allow factoring n?***From:*Francois Grieu

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

- Prev by Date:
**Re: some guide** - Next by Date:
**Re: Rolling dices** - Previous by thread:
**Re: In RSA, does knowledge of d%(p-1) and d%(q-1) allow factoring n?** - Index(es):