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

## 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`

.
The private exponent ^{d} mod n`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^{3},
so we have a lot more computing to do.

We can use the CRT to compute `m = c`

more efficiently.
The full algorithm from [PKCS1] is
^{d} mod n

- 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`dom_{1}= c^{dP}mod p

m_{2}= c^{dQ}mod q

h = qInv.(m_{1}- m_{2}) mod p

m = m_{2}+ 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

_{1}, x

_{2}) where 0 ≤ x

_{1}< p and 0 ≤ x

_{2}< q, there is a unique number x where 0 ≤ x < n such that

_{1}= x mod p, and

x

_{2}= x mod q.

So any integer x (0 ≤ x < n) can be expressed uniquely in its CRT representation (x_{1}, x_{2}).

## 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`

where φ(n) is Euler's totient function,
the number of positive
integers not exceeding ^{φ(n)} ≡ 1 (mod n)`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`

.
If we know the pair ^{d} mod n`(c`

) then the CRT tells us there
is a unique value of ^{d} mod p, c^{d} mod q`c`

in the range [0, n-1].
^{d} mod n

To recover `x` from its CRT representation `(x`

we use Garner's formula_{1}, x_{2})^{†}

_{2}+ h.q, where

h = ((x

_{1}- x

_{2}))((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`

).
The extra cost of recovering m using Garner's formula is negligible compared to the exponentiations.
^{3} / 2(k/2)^{3}

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

^{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 φ(p) plus a remainder, d = kφ(p) + d mod φ(p), where k is some integer.
Hence

c^{d} = c^{kφ(p) + d mod φ(p)} = (c^{φ(p)})^{k}.c^{d mod φ(p)}.

Now Euler's Theorem gives c^{φ(p)} ≡ 1 (mod p).
Thus

c^{d} ≡ 1^{k}.c^{d mod φ(p)} ≡ c^{d 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

^{-1}mod (p-1), and

d mod (q-1) = e

^{-1}mod (q-1).

We compute the CRT representation of the message (m_{1}, m_{2}) using
arithmetic modulo `p` and `q` and shorter, pre-computed CRT exponents, `dP` and `dQ`.

dQ = (1/e) mod (q-1) = d mod (q-1)

m

_{1}= c

^{dP}mod p

m

_{2}= c

^{dQ}mod q

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

h = qInv.(m

_{1}- m

_{2}) mod p

m = m

_{2}+ h.q

## A simple example

We will use this example from our RSA Algorithm page:

m = 513

c = 513

^{3}mod n = 8363.

To decrypt `c` we could compute `c`

directly
^{d} mod n

^{11787}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.

^{-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

_{1}= c

^{dP}mod p = 8363

^{91}mod 137 = 102

m

_{2}= c

^{dQ}mod q = 8363

^{87}mod 131 = 120

h = qInv.(m

_{1}- m

_{2}) mod p = 114.(102-120+137) mod 137 = 3 [

*we add in an extra p here to keep the sum positive*]

m = m

_{2}+ 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_{1} on line 4 without needing more than 7 digits on our calculator.

8363

^{91}≡ 6

^{91}(mod 137). Now

6

^{3}= 216 ≡ 79 (mod 137),

6

^{9}= (6

^{3})

^{3}≡ 79

^{3}= 493039 ≡ 113 (mod 137),

6

^{27}= (6

^{9})

^{3}≡ 113

^{3}= 1442897 ≡ 13 (mod 137),

6

^{81}= (6

^{27})

^{3}≡ 13

^{3}= 2197 ≡ 5 (mod 137). Hence

6

^{91}= 6

^{81+9+1}= 6

^{81}.6

^{9}.6

^{1}≡ 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_{1} and x_{2} 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*