52 Things: Number 21: How does the CRT method improve performance of RSA?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year.

The Chinese Remainder Theorem (CRT) states that if we have two equations:

$x = a (mod N)$ and $x = b (mod M)$, then there is a unique solution modulo MN iff $gcd(N, M) = 1$.   

In RSA we must perform a modular exponentiation with respect to a modulus of a thousand or more bits [1]. As a generic remark we could say that public key algorithms are slower compared to symmetric schemes. This characteristic might result to slow web servers-networks and improving efficiency during implementation (software algorithms) plays a crucial role in order to avoid performance problems.

We denote that the main operation in RSA scheme is the modular exponentiation $M = C^d (mod N)$. A modular exponentiation, at an improved state, can be performed using (h - 1) multiplications and (t - 1) squarings (t is the bit length of the exponent and h is the Hamming weight). The number of multiplications and squarings on average is $t + t/2 -1$. 

Further performance improvements can be achieved using binary exponentiation algorithms (e.g. right-to-left exponentiation) or window methods. For the latter we process w bits of the exponent at a time. For this method we still need t squarings but the number of multiplications reduces to t/w on average. Further improvements can be obtained by adopting sliding window methods [t/(w + 1) multiplications on average].  

To make the RSA exponentiation even faster we can perform some additional tricks depending on whether we are performing an encryption operation with the public key or a decryption operation with the private key. The CRT is used in the case of RSA decryption. Thus, we are considering a private key operation which means that we have access to the private key and hence the factorization of the modulus, $N = pq$. If we suppose we want to decrypt a message, then our goal is to calculate $M = C^d (mod N)$.

First we will compute M modulo p and M modulo q as follows:

$M_p = C^d (mod p) = C^{d (mod p - 1)} (mod p)$

$M_q = C^d (mod q) = C^{d (mod q - 1)} (mod q)$

This calculation requires two exponentiations modulo 512-bit moduli and 512-bit exponents because $p$ and $q$ are 512-bit numbers. This is faster than a single exponentiation modulo a 1024-bit number with a 1024-bit exponent.

Using the CRT we recover $M$ from $M_p$ and $M_q$ as follows: 

Compute $T = p^{-1} (mod q)$, store it with the private key.

M (the message) can be recovered from $M_p$ and $M_q$ as follows:

$U = (M_q – M_p) T (mod q)$,

$M = M_p + up$.  

[1] http://www.cs.bris.ac.uk/~nigel/Crypto_Book/book.ps (Chapter 15)