1
$\begingroup$

(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.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Nov 8 '21 at 16:48
  • 1
    $\begingroup$ 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). $\endgroup$
    – Daniel S
    Nov 8 '21 at 17:49
  • $\begingroup$ @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. $\endgroup$
    – mrose
    Nov 8 '21 at 19:49
  • 1
    $\begingroup$ 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 $\endgroup$
    – poncho
    Nov 8 '21 at 19:55
  • $\begingroup$ @poncho so we are assuming $s_1<x$? $\endgroup$
    – mrose
    Nov 8 '21 at 20:16

Your Answer

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

Browse other questions tagged or ask your own question.