DI Management Home > Mathematics > Using the CRT with RSA

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 Zn 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.

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 = cd 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 k3, so we have a lot more computing to do.

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

  1. 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 Zn, the set of numbers {0, 1, 2, ..., n-1}.
  2. To compute the message m given c do

    m1 = cdP mod p
    m2 = cdQ mod q
    h = qInv.(m1 - m2) mod p
    m = m2 + 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 (x1, x2) where 0 ≤ x1 < p and 0 ≤ x2 < q, there is a unique number x where 0 ≤ x < n such that
   x1 = x mod p, and
   x2 = x mod q.

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

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 = cd mod n. If we know the pair (cd mod p, cd mod q) then the CRT tells us there is a unique value of cd mod n in the range [0, n-1].

To recover x from its CRT representation (x1, x2) we use Garner's formula

x = x2 + h.q, where
h = ((x1 - x2))((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 (= k3 / 2(k/2)3). The extra cost of recovering m using Garner's formula is negligible compared to the exponentiations.

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

cd mod p = cd mod φ(p) mod p = cd mod (p-1) mod p

and similarly for the mod q value.

How do we get that? Write d as a multiple of φ(p) plus a remainder, d = kφ(p) + d mod φ(p), where k is some integer. Hence
cd = ckφ(p) + d mod φ(p) = (cφ(p))k.cd mod φ(p).
Now Euler's Theorem gives cφ(p) ≡ 1 (mod p). Thus
cd ≡ 1k.cd mod φ(p) ≡ cd mod φ(p) (mod p).
Finally, since p is prime then φ(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 (m1, m2) 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)
m1 = cdP mod p
m2 = cdQ mod q

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

qInv = (1/q) mod p
h = qInv.(m1 - m2) mod p
m = m2 + 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 = 5133 mod n = 8363.

To decrypt c we could compute cd mod n directly

m = 836311787 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
m1 = cdP mod p = 836391 mod 137 = 102
m2 = cdQ mod q = 836387 mod 131 = 120
h = qInv.(m1 - m2) mod p = 114.(102-120+137) mod 137 = 3 [we add in an extra p here to keep the sum positive]
m = m2 + 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 m1 on line 4 without needing more than 7 digits on our calculator.

8363 ≡ 6 (mod 137), so
836391 ≡ 691 (mod 137). Now
63 = 216 ≡ 79 (mod 137),
69 = (63)3 ≡ 793 = 493039 ≡ 113 (mod 137),
627 = (69)3 ≡ 1133 = 1442897 ≡ 13 (mod 137),
681 = (627)3 ≡ 133 = 2197 ≡ 5 (mod 137). Hence
691 = 681+9+1 = 681.69.61 ≡ 5.113.6 = 3390 ≡ 102 (mod 137).

References

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 x1 and x2 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 19 December 2013