Cryptography Reference
In-Depth Information
7.5.2 Fast Decryption with the Chinese Remainder Theorem
We cannot choose a short private key without compromising the security for RSA.
If we were to select keys
d
as short as we did in the case of encryption in the section
above, an attacker could simply brute-force all possible numbers up to a given bit
length, i.e., 50 bit. But even if the numbers are larger, say 128 bit, there are key
recovery attacks. In fact, it can be shown that the private key must have a length of
at least 0
.
3
t
bit, where
t
is the bit length of the modulus
n
. In practice,
e
is often
chosen short and
d
has full bit length. What one does instead is to apply a method
which is based on the Chinese Remainder Theorem (CRT). We do not introduce
the CRT itself here but merely how it applies to accelerate RSA decryption and
signature generation.
Our goal is to perform the exponentiation
x
d
mod
n
efficiently. First we note that
the party who possesses the private key also knows the primes
p
and
q
. The basic
idea of the CRT is that rather than doing arithmetic with one “long” modulus
n
,
we do two individual exponentiations modulo the two “short” primes
p
and
q
.This
is a type of transformation arithmetic. Like any transform, there are three steps:
transforming into the CRT domain, computation in the CRT domain, and inverse
transformation of the result. Those three steps are explained below.
Transformation of the Input into the CRT Domain
We simply reduce the base element
x
modulo the two factors
p
and
q
of the modulus
n
, and obtain what is called the modular representation of
x
.
x
p
≡
x
mod
p
x
q
≡
x
mod
q
Exponentiation in the CRT Domain
With the reduced versions of
x
we perform the following two exponentiations:
y
p
=
x
d
p
mod
p
y
q
=
x
d
q
mod
q
q
where the two new exponents are given by:
d
p
≡
d
mod (
p
−
1)
d
q
≡
d
mod (
q
−
1)
Note that both exponents in the transform domain,
d
p
and
d
q
, are bounded by
p
and
q
, respectively. The same holds for the transformed results
y
p
and
y
q
. Since the two
