The RSA Cryptosystem - Understanding Cryptography - page 183

c p = 13 − 1 2 − 1 c q = 11 − 1

≡ ≡ 6 mod 11 ≡ 6 mod 13

The plaintext x follows now as:

x ≡ [ qc p ] x p +[ pc q ] x q mod n

x ≡ [13 · 6]9 +[11 · 6]11 mod 143

x ≡ 702 + 726 = 1428 ≡ 141 mod 143

If you want to verify the result, you can compute y d

mod 143 using the square-and-

multiply algorithm.
We will now establish the computational complexity of the CRT method. If we
look at the three steps involved in the CRT-based exponentiation, we conclude that
for a practical complexity analysis the transformation and inverse transformation
can be ignored since the operations involved are negligible compared to the actual
exponentiations in the transform domain. For convenience, we restate these CRT
exponentiations here:

y p = x d p

mod p

y q = x d q

mod q

q

If we assume that n has t + 1 bit, both p and q are about t / 2 bit long. All numbers
involved in the CRT exponentiations, i.e., x p , x q , d p and d q , are bound in size by
p and q , respectively, and thus also have a length of about t / 2 bit. If we use the
square-and-multiply algorithm for the two exponentiations, each requires on average
approximately 1 . 5 t / 2 modular multiplications and squarings. Together, the number
of multiplications and squarings is thus:

# SQ + # MU L = 2 · 1 . 5 t / 2 = 1 . 5 t

This appears to be exactly the same computational complexity as regular exponen-
tiation without the CRT. However, each multiplication and squaring involves num-
bers which have a length of only t / 2 bit. This is in contrast to the operations without
CRT, where each multiplication was performed with t -bit variables. Since the com-
plexity of multiplication decreases quadratically with the bit length, each t / 2-bit
multiplication is four times faster than a t -bit multiplication. 1 Thus, the total speed-
up obtained through the CRT is a factor of 4. This speed-up by four can be very
valuable in practice. Since there are hardly any drawbacks involved, CRT-based
exponentiations are used in many cryptographic products, e.g., for Web browser
encryption. The method is also particularly valuable for implementations on smart

1 The reason for the quadratic complexity is easy to see with the following example. If we multiply
a 4-digit decimal number abcd by another number wxyz , we multiply each digit from the first
operand with each digit of the second operand, for a total of 4 2 = 16 digit multiplications. On the
other hand, if we multiply two numbers with two digits, i.e., ab times wx , only 2 2 = 4 elementary
multiplications are needed.