# RSA CRT modulo reduction

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 :)

• 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 ? Oct 27, 2014 at 20:42
• 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.
– fgrieu
Oct 27, 2014 at 23:26
• @fgrieu Is that a possible answer? Oct 28, 2014 at 12:15

## 1 Answer

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.