Join Log in
Score:3
Pazu avatar Crypto

RSA decryption using CRT: How does it affect the complexity?

vn flag
Pazu

There is an efficient variant of the RSA using the CRT:

\begin{align*} d_p &= d \pmod{p-1}\\ d_q &= d \pmod{p-1} \\ q_{\operatorname{inv}} &= q^{-1} \pmod{p} \end{align*}

where the decryption is done as follows:

\begin{align*} c_p &= c \pmod{p} \\ c_q &= c \pmod{q} \\ m_p &= c_p^{d_p} \pmod{p} \\ m_q &= c_q^{d_q} \pmod{q} \\ h &= q_{\operatorname{inv}}(m_p - m_q) \pmod{p} \end{align*}

My first question is rather general: Where do I use the CRT-algorithm (as it is written there)? I mean the setup of the RSA already defines me $p,q,d,c$ and so I don't have a system of congruences.

My second question concerns the complexity. Assume $\log d = \log n = B$ and $\log p = \log q = \frac{B}{2}$ and $d, d_p, d_q$ have equally many $0$s and $1$s. What can I say about the number of operations of size $B$ of this variant?

439
0 + 0
rsa
Score:7
poncho avatar Crypto
my flag
poncho

There is an efficient variant of the RSA using the CRT

Actually, by the way we generally use terms, it is not a 'variant', instead it is an alternative implementation. That is, the only changes made to the RSA algorithm are done with how the private operation is done (and the format of the private keys); anyone doing only public operations need have no knowledge on what the private (signature generation or public key decryption) implementation is doing.

Where do I use the CRT-algorithm (as it is written there)?

Whenever you want somewhat more efficiency (4x), and don't mind a wee bit of extra complexity. Most of the time, this is a worthwhile tradeoff.

I mean the setup of the RSA already defines me p,q,d,c and so I don't have a system of congruences.

Actually, all the additional parameters $d_p, d_q, qinv$ are easily computed during key generation time, and so that's what we usually do.

Assume $\log d = \log n=B$ and $\log p = \log q = B/2$ and $d,d_p,d_q$ have equally many 0s and 1s. What can I say about the number of operations of size $B$ of this variant?

Actually, the number of 0s and 1s are mostly irrelevant, we can perform a modular exponentiation of an $B$ bit value with $(1 + o(1)) \log_2 B$ modular multiplies (independent on the hamming weight of the exponent); in the range of B's under consideration, this may be $(1 + 1/6) \log_2 B$.

With the textbook RSA private operation, this involves a single modular exponentiation of a $B$ bit value by a $B$ bit exponent; this is about $(1 + 1/6) \log_2 B$ multiplies. If we use an $O(n^2)$ modular multiply algorithm (which is about optimal for the range of B's we discussing - there are multiplication routines with lower asymptotic complexity, but with much larger constants of proportionality), we're talking about $(1 + 1/6) (\log_2 B)^3$

Now, with CRT, there are two modular exponentation of two $B/2$ bit by a $B/2$ bit exponent (plus some operations both before and after - those are both relatively quick). Using the same logic, this takes about $2 (1 + 1/6) (\log_2 B/2)^3 = 1/4 (1 + 1/6) (\log_2 B)$, that is, about 4 times as fast (yes, this is ignoring some small factors); however even if we account for those small factors, CRT is still considerably faster

0 + 0
ธงชาติไทย
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.