4
$\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$
2
  • 1
    $\begingroup$ You may be interested in this question / answers on SO. $\endgroup$
    – Maarten Bodewes
    May 25, 2015 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, 2015 at 14:25

1 Answer 1

7
$\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$
2
  • $\begingroup$ The $\lambda$ in that calculation, isn't necessarily the usual $\lambda(n)$, right? Only a multiple of it. $\endgroup$ May 26, 2015 at 8:19
  • $\begingroup$ @CodesInChaos: nope, it's just a temporary variable name. $\endgroup$
    – poncho
    May 26, 2015 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.