1
$\begingroup$

I am working on RSA CRT and there is a point that I don't understand :

So we have $n=pq$ and $c = m^e \bmod n$ an encrypted message.

To decrypt $c$ with RSA CRT, we have to compute :

$d_p = d \bmod (p-1)$ and $d_q = d \bmod (q-1)$

Why do we have to do a reduction $\bmod (p-1)$ and not $\bmod p$ ? (Same for $(q-1)$ and $q$) Plus, next computations are made $\bmod p$ and $\bmod q$, right ? ($m_p = c^{d_p} \bmod p$ and $m_q = c^{d_q} \bmod q$)

To reduce modulo $p$ instead of $(p-1)$ to compute $d_p$ could allow attacks for example ?

Thank you in advance :)

$\endgroup$
  • $\begingroup$ I think I got it : As $d = e^{-1} \bmod (p-1)(q-1)$, we reduce $\bmod (p-1)$ and $\bmod (q-1)$ because, doing this way, $d_p = e^{-1} \bmod (p-1)$ and $d_q = e^{-1} \bmod (q-1)$, that's it ? $\endgroup$ – Raoul722 Oct 27 '14 at 20:42
  • $\begingroup$ What you wrote in comment is true, but does not satisfactorily answer your question. Fermat's Little Theorem goes a long way towards that; use it to prove that $\forall x\not\equiv0\pmod p, x^d\equiv x^{d_p}\pmod p$. $\;$ Also, notice that you do not HAVE to compute $d_p$ and $d_q$ the way you do; $d_p=d_q=d$ will also work, albeit with much less savings compared to regular modular exponentiation. $\endgroup$ – fgrieu Oct 27 '14 at 23:26
  • $\begingroup$ @fgrieu Is that a possible answer? $\endgroup$ – Maarten Bodewes Oct 28 '14 at 12:15
4
$\begingroup$

RSA CRT (with $N$ the product of two distinct primes $p$ and $q$) implements the $x\to y=x^d\bmod N$ private-key function by computing $y_p=x^d\bmod p$ and $y_q=x^d\bmod q$; then combining $y_p$ and $y_q$ into the desired $y$ by constructing the solution to the equations $y\equiv y_p\pmod p$, $y\equiv y_q\pmod q$, $0\le y<N$, with that last step requiring comparatively little computing effort. It is beneficial from a computational perspective because (assuming $p$ and $q$ have the same bit size, or nearly so)

  • we can compute $y_p=x^d\bmod p$ as $y_p={(x\bmod p)}^d\bmod p$; this computation multiplies numbers half as wide as $x^d\bmod N$ would do, hence requires (asymptotically) 4 times less elementary operations when using standard multiplication algorithms; so total computational effort can be reduced by a factor of (near) 2;
  • it is easy to run the two sub-calculations in parallel, so elapsed time can be reduced by a further factor of (near) 2.

So, in RSA with CRT, we do not have to compute $d_p=d\bmod(p-1)$ and $d_q=d\bmod(p-1)$ as stated in the question; we can do it for additional savings, as explained below.

One form of Fermat's Little Theorem states that if integer $x$ is not a multiple of prime $p$, then $x^{p-1}\equiv1\pmod p$. If we set $d_p=d\bmod(p-1)$, or more generally chose any $d_p\equiv d\pmod{(p-1)}$, then by definition $d=k\cdot(p-1)+d_p$ for some integer $k$, thus $$x^d\equiv x^{k\cdot(p-1)+d_p}\equiv(x^{p-1})^k\cdot x^{d_p}\equiv1^k\cdot x^{d_p}\equiv x^{d_p}\pmod p$$ Noticing that the above equation also holds when $x$ is a multiple of $p$ provided that $d>0$ and $d_p>0$, we can thus compute $y_p=x^d\bmod p$ as $y_p=x^{d_p}\bmod p$, or rather $y_p={(x\bmod p)}^{d_p}\bmod p$. The reduced exponent $d_p$ is less wide than $d$ by a factor of (nearly) 2, with about that saving in computational effort and time (combinable with the aforementioned savings).

Note: It may turn out that $d_p=k\cdot(p-1)+(d\bmod(p-1))$ for some $k$ (possibly negative) with small $|k|$ would be a more efficient choice than $d_p=d\bmod(p-1)$. That's typically only a tiny extra saving; exactly when will depend on the particular exponentiation algorithm used, and for negative $k$ on the cost of computing a modular inverse $\pmod p$.

Note: RSA CRT also has drawbacks, e.g. different vulnerability to fault injection and side-channel attacks.

As to why $d_p=d\bmod p$ does not work: there is no reason that it would, and experiment with small values proves that it does not in the general case.

$\endgroup$

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.