3
$\begingroup$

Given the public key (n, e) and private exponent (d), how to calculate CRT parameters (p, q, dP, dQ, and qInv) of this RSA key pair?

$\endgroup$
  • 1
    $\begingroup$ You may be interested in this question / answers on SO. $\endgroup$ – Maarten Bodewes May 25 '15 at 14:11
  • $\begingroup$ Actually, that answer (despite being given by Thomas Pornin, who is generally accurate) is wrong; $ed-1$ needn't be a multiple of $\phi(n)$. Actually, Thomas notes this himself; for some reason, he doesn't give the full answer (possibly because he didn't want to get into number theory) $\endgroup$ – poncho May 25 '15 at 14:25
5
$\begingroup$

The first (and hardest) step is to factor $n$; the easiest way to do this (given $e$ and $d$) is with this randomized procedure:

  • Select a random value $z$ from the range $(2, n-2)$

  • Compute the value $\lambda = (ed-1)/2^k$, where $k$ is that integer that makes $\lambda$ an odd integer.

  • Compute $t = z^\lambda \bmod n$. If $t = 1$ or $t = n-1$, we fail on this selection of $z$.

  • Do this repeatedly, at most $k$ times:

    • Compute $u = t^2 \bmod n$.

    • If $u = -1$, we fail on this selection of $z$.

    • If $u = 1$, we have success (and we have the factorization $p = gcd(n,t-1)$, $q = gcd(n, t+1)$)

    • Otherwise, set $t = u$, and continue with the next loop

  • If we run through the above loop $k$ times without hitting either success or failure, then either we happened to have selected a $z$ that's not relatively prime to $n$, or $d, e$ are not a valid RSA exponent pair.

A random value of $z$ will fail at most half the time; so we run this procedure (selecting different random $z$ values) until it succeeds, and gives us the factorization.

Once we have the factorization of $n$, computing the rest of the CRT parameters is straight-forward.

$\endgroup$
  • $\begingroup$ The $\lambda$ in that calculation, isn't necessarily the usual $\lambda(n)$, right? Only a multiple of it. $\endgroup$ – CodesInChaos May 26 '15 at 8:19
  • $\begingroup$ @CodesInChaos: nope, it's just a temporary variable name. $\endgroup$ – poncho May 26 '15 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.