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
.

Relevant Pages

  • Re: In RSA, does knowledge of d%(p-1) and d%(q-1) allow factoring n?
    ... Efficient algorithms are known that recover p, q from n, e, d. ... exponents used in the CRT expression of the private key leaked. ... pick some random integer z such that 0 < z < n, ...
    (sci.crypt)
  • recovering protected files
    ... >recover your previous installation of Windows in case it ... >all of my encrypted files was not in My documents folder, ... >Private key for encrypted files is stored in My ...
    (microsoft.public.windowsxp.security_admin)
  • Re: Need help with Windows XP EFS
    ... to have windows accept that master key, but when I drop it into a new ... I assume that letting Microsoft recover my ... private key will cost me a lot of money too. ... >> I just reinstalled my computer, and after that I found that the floppydisk>> with my certificate on it was broken. ...
    (microsoft.public.windowsxp.security_admin)
  • Re: Need help with Windows XP EFS
    ... Any idea what the costs of getting my private key recovered will be? ... Because I searched some and on the Microsoft ... >> to have windows accept that master key, but when I drop it into a new ... I assume that letting Microsoft recover ...
    (microsoft.public.windowsxp.security_admin)
  • Re: Need help with Windows XP EFS
    ... I do not know the cost, but do know it is not free. ... >>> to have windows accept that master key, but when I drop it into a new ... >>> it can decrypt the private key. ... I assume that letting Microsoft recover ...
    (microsoft.public.windowsxp.security_admin)