# Comparing complexity of RSA decryption with/without CRT

(Cross-listed on math stackexchange, received no replies) For context, this is a homework question from an assignment already turned in. I am looking for better understanding of the concepts involved, mainly complexity theory since I have not seen it before outside this class (and prior knowledge was assumed).

I am asked to evaluate the complexity of RSA decryption with and without using CRT, without using asymptotic complexity. Instead use $$c_1$$ as the constant for modular multiplication, $$c_2$$ for modular exponentiation, and $$c_3$$ for finding a multiplicative inverse.

My attempt: Let $$s_1$$ be the length of $$p$$, $$s_2$$ be the length of $$q$$, $$s$$ the length of $$n$$, and $$x$$ the length of $$d$$. Consider the following complexities:

computation complexity
$$m_1=c^d\mod p$$ $$c_2s_1^2x$$
$$m_2=c^d\mod q$$ $$c_2s_2^2x$$
$$q^{-1}\mod p$$ $$c_3s_1$$
$$p^{-1}\mod q$$ $$c_3s_2$$

So the complexity of using the CRT to compute $$m=m_1(q^{-1}\mod p)q+m_2(p^{-1}\mod q)p\mod n$$ is $$c_1^2c_2c_3s_1^3x+c_1^2c_2c_3s_2^3x=c_1^2c_2c_3x(s_1^3+s_2^3)$$.

Meanwhile, the complexity to compute $$m=c^d\mod n$$ is $$c_2s^2x$$, so the difference is $$c_2x(s^2-c_1^2c_3(s_1^3+s_2^3))$$.

I believe this is wrong since I don't think it is true in general that $$s^2\geq s_1^3+s_2^3$$ (CRT should make decryption faster), and I don't know if we can make any assumptions about the constants.

• Hints: It's generally made $m_1:=c^{d_p}\bmod p$ where $d_p=d\bmod(p-1)$ is precomputed. Same for $m_2$. It's generally precomputed $q_{\text{inv}}=q^{-1}\bmod p$. There is no need for both $q^{-1}\bmod p$ and $p^{-1}\bmod q$ when using the formula $m:=((m_1-m_2)\,q_{\text{inv}}\bmod p)\,q+m_2$. The standard private key format includes $d_p$, $d_q$, $q_{\text{inv}}$. Answering one's own question is smart! $a=b\bmod n$ implies $0\le a<n$ but $a\equiv b\pmod n$ does not, and the difference matters in RSA, thus the ambiguous $a=b\pmod n$ is best avoided.
– fgrieu
Nov 8 '21 at 16:48
• You're multiplying the costs of the stages when you should be adding them. So for example computing $m_1(q^{-1}\mod p)$ costs $c_2s_1^2x+c_3s_1+c_1s_1^2$ (assuming high-school multiplication methods). Nov 8 '21 at 17:49
• @DanielS how did you find $c_1s_1^2$? I had $c_1^2$ for using mod multiplication twice. Thanks for correcting, I had read somewhere that O(m)*O(n)=O(mn) and thought that applied. Nov 8 '21 at 19:49
• Another issue is you have $m_1 = c^d \bmod p$ with complexity $c_2 s_1^2 x$; actually, real implementations compute $m_1 = c^{d \bmod p-1} \bmod p$; this gives a complexity of $c_2 s_1^3$, which is considerably smaller (with $d_p = d \bmod p-1$ being precomputed, as mentioned by fgrieu). This efffective halving of the private exponent is where a good portion of the speed up comes from Nov 8 '21 at 19:55
• @poncho so we are assuming $s_1<x$? Nov 8 '21 at 20:16