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.

Improve this question
$\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, 2021 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, 2021 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, 2021 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, 2021 at 19:55
  • $\begingroup$ @poncho so we are assuming $s_1<x$? $\endgroup$
    – mrose
    Nov 8, 2021 at 20:16

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.