Re: In RSA, does knowledge of d%(p1) and d%(q1) 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(p1, q1).
Efficient algorithms are known that recover p, q from n, e, d.
Rather, assume n, e, d%(p1) and d%(q1) 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%(p1), this means you have an integer
D such that e*D  1 = 0 (mod p1). 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, p1.
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%(p1) and d%(q1) allow factoring n?
 From: Francois Grieu
 Re: In RSA, does knowledge of d%(p1) and d%(q1) allow factoring n?
 From: Bodo Moeller
 In RSA, does knowledge of d%(p1) and d%(q1) allow factoring n?
 Prev by Date: Re: some guide
 Next by Date: Re: Rolling dices
 Previous by thread: Re: In RSA, does knowledge of d%(p1) and d%(q1) allow factoring n?
 Index(es):
Relevant Pages
