3
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.