Using the CRT with RSA

On this page we look at how the Chinese Remainder Theorem (CRT) can be used to speed up the calculations for the RSA algorithm. We show how the CRT representation of numbers in Z_n can be used to perform modular exponentiation about four times more efficiently using three extra values pre-computed from the prime factors of n, and how Garner's formula is used.

We use JavaScript to display the mathematics on this page. Please enable JavaScript in your browser for it to work.

RSA calculations

When we come to decrypt ciphertext c (or generate a signature) using RSA with private key (n, d), we need to calculate the modular exponentiation m = c^d mod n. The private exponent d is not as convenient as the public exponent, for which we can choose a value with as few '1' bits as possible. For a modulus n of k bits, the private exponent d will also be of similar length, with approximately half being '1'. The effort to compute the exponent is proportional to k³, so we have a lot more computing to do.

We can use the CRT to compute m = c^d mod n more efficiently. The full algorithm from [PKCS1] is

Precompute the following values given p, q with p > q
```
dP = (1/e) mod (p-1)
dQ = (1/e) mod (q-1)
qInv = (1/q) mod p
```
where the (1/e) notation means the modular inverse. The expression x = (1/e) mod N is also written as x = e^-1 mod N, and x is any integer that satisfies x.e ≡ 1 (mod N). In our case, where N = n = pq, we use the unique value x in Z_n, the set of numbers {0, 1, 2, ..., n-1}.
To compute the message m given c do

m₁ = c^dP mod p
m₂ = c^dQ mod q
h = qInv.(m₁ - m₂) mod p
m = m₂ + h.q

We store our private key as the quintuple (p, q, dP, dQ, qInv).

We need two theorems from number theory here: a special case of the Chinese Remainder Theorem (CRT) and Euler's Theorem (also called the Euler-Fermat Theorem).

The Chinese Remainder Theorem - special case

A special case of the Chinese Remainder Theorem (CRT) can be written as follows.

Theorem. Let p and q be distinct primes and n = p.q. For any pair (x₁, x₂) where 0 ≤ x₁ < p and 0 ≤ x₂ < q, there is a unique number x where 0 ≤ x < n such that

x₁ = x mod p, and
x₂ = x mod q.

So any integer x (0 ≤ x < n) can be expressed uniquely in its CRT representation (x₁, x₂).

Euler's Theorem

Euler's Theorem is a generalisation of Fermat's Little Theorem. It is sometimes called the Euler-Fermat Theorem.

Theorem. If n is a positive integer and a is any integer with gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n) where φ(n) is Euler's totient function, the number of positive integers not exceeding n which are relatively prime to n.

Euler's totient function is also called Euler's phi function. For a prime p, the value of φ(p) = p-1, since all positive integers less than p are coprime to it.

Arithmetic in CRT representation

We want to compute m = c^d mod n. If we know the pair (c^d mod p, c^d mod q) then the CRT tells us there is a unique value of c^d mod n in the range [0, n-1].

To recover x from its CRT representation (x₁, x₂) we use Garner's formula^†

x = x₂ + h.q, where
h = ((x₁ - x₂))((1/q) mod p)) mod p.

The CRT coefficient qInv = (1/q) mod p can be pre-computed. The cost of doing modular exponentiation increases by the cube of the number of bits k in the modulus, so doing two exponentiation calculations mod p and mod q is much more efficient than doing one exponentiation mod n. Since p and q are approximately half the size of n, the overall saving in computing operations is about a factor of 4 (= k³ / 2(k/2)³). The extra cost of recovering m using Garner's formula is negligible compared to the exponentiations.

Even better, to compute c^d mod p, we can use Euler's Theorem to reduce the exponent d modulo (p-1):

c^d mod p = c^{d mod φ(p)} mod p = c^{d mod (p-1)} mod p

and similarly for the mod q value.

How do we get that?

Write $d$ as a multiple of $\phi(p)$ plus a remainder, $d = k\phi(p) + d \bmod \phi(p)$, where $k$ is some integer. Hence
$$c^d = c^{k\phi(p) + d \bmod \phi(p)} = \left(c^{\phi(p)}\right)^k \cdot c^{d \bmod \phi(p)}$$ Now Euler's Theorem gives c^φ(p) ≡ 1 (mod p). Thus
$$c^d = 1^k\cdot c^{d\bmod \phi(p)} \equiv c^{d\bmod\phi(p)} \pmod p$$ Finally, since p is prime then $\phi(p) = p - 1$, and the result follows.

RSA final calculation

We do one further simplification (actually more of a complication!) to obtain the same formula as in [PKCS1]. It can be shown (using the multiplicative properties of φ(n) - see RSA proof) that

d mod (p-1) = e^-1 mod (p-1), and
d mod (q-1) = e^-1 mod (q-1).

We compute the CRT representation of the message (m₁, m₂) using arithmetic modulo p and q and shorter, pre-computed CRT exponents, dP and dQ.

dP = (1/e) mod (p-1) = d mod (p-1)
dQ = (1/e) mod (q-1) = d mod (q-1)
m₁ = c^dP mod p
m₂ = c^dQ mod q

Then we use Garner's formula with our pre-computed qInv to recover m.

qInv = (1/q) mod p
h = qInv.(m₁ - m₂) mod p
m = m₂ + h.q

A simple example

We will use this example from our RSA Algorithm page:

p = 137, q = 131, n = 137.131 = 17947, e = 3, d = 11787.
m = 513
c = 513³ mod n = 8363.

To decrypt c we could compute c^d mod n directly

m = 8363¹¹⁷⁸⁷ mod 17947 = 513.

Pretty difficult to do on your pocket calculator. Now let's use the CRT method - notice how the exponent and modulus values are much smaller and manageable. This simple (but obviously insecure) example should demonstrate how much easier it is to break down the RSA calculation into two smaller ones.

dP = e^-1 mod (p-1) = d mod (p-1) = 11787 mod 136 = 91
dQ = e^-1 mod (q-1) = d mod (q-1) = 11787 mod 130 = 87
qInv = q^-1 mod p = 131^-1 mod 137 = 114
m₁ = c^dP mod p = 8363⁹¹ mod 137 = 102
m₂ = c^dQ mod q = 8363⁸⁷ mod 131 = 120
h = qInv.(m₁ - m₂) mod p = 114.(102-120+137) mod 137 = 3 [we add in an extra p here to keep the sum positive]
m = m₂ + h.q = 120 + 3.131 = 513.

This gives the same result and we can compute this on a pocket calculator. Note how we add in an extra 137 on line 6 to avoid having to deal with a negative number (remember with modular arithmetic that a + p ≡ a (mod p)). The modular inverse on line 3 can be computed by hand using the Euclidean algorithm. Here is one way to compute m₁ on line 4 without needing more than 7 digits on our calculator.

8363 ≡ 6 (mod 137), so
8363⁹¹ ≡ 6⁹¹ (mod 137). Now
6³ = 216 ≡ 79 (mod 137),
6⁹ = (6³)³ ≡ 79³ = 493039 ≡ 113 (mod 137),
6²⁷ = (6⁹)³ ≡ 113³ = 1442897 ≡ 13 (mod 137),
6⁸¹ = (6²⁷)³ ≡ 13³ = 2197 ≡ 5 (mod 137). Hence
6⁹¹ = 6⁸¹⁺⁹⁺¹ = 6⁸¹.6⁹.6¹ ≡ 5.113.6 = 3390 ≡ 102 (mod 137).

References

[PKCS1] PKCS #1, RSA Cryptography Standard, RSA Laboratories, Version 2.0, September 1998 (RFC 2437) [The older version 2.0 is easier to understand.]
[MENE97] Menezes, van Oorschot and Vanstone, Handbook of Applied Cryptography, CRC Press LLC, 1997. The complete book is available on-line.
Niels Ferguson and Bruce Schneier, Practical Cryptography, John Wiley, 2003.
M381 Mathematics and Computing: A Third Level Course, Number Theory Handbook, The Open University, 1996.
Chalmers University of Technology and University of Gothenburg, Cryptography 2010 Lecture 8 More Number Theory. [Careful: the formulae for CRT representation are different in this paper.]

Thanks to Adam Bantell for his encouragement to write up this article; to "Lars" and "Daniel" for pointing out typos; and to Tom Lake for pointing out we had x₁ and x₂ the wrong-way round in Garner's formula^†.

Contact us

Feedback: Send us a message.

This page last first published 19 February 2011 and last updated 5 December 2019