Join Log in
Score:1
mrose avatar Crypto

Comparing complexity of RSA decryption with/without CRT

in flag
mrose

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

57
0 + 0
rsa
fgrieu avatar
ng flag
fgrieu
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](https://pkcs1.grieu.fr#page=41) 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.
1
Reply
Daniel S avatar
ru flag
Daniel S
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).
1
Reply
mrose avatar
in flag
mrose
@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.
0
Reply
poncho avatar
my flag
poncho
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
1
Reply
mrose avatar
in flag
mrose
@poncho so we are assuming $s_1<x$?
0
Reply
poncho avatar
my flag
poncho
Well, $s_1$ is the length of $p$, while $x$ is the length of $d$. If $d$ is so short that it's actually smaller than $p$, well, that's a known weakness; hence $s_1 < x$ is a pretty safe assumption...
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.