Cryptography Reference
In-Depth Information
primes are in practice chosen to have roughly the same bit length, the two exponents
as well as
y
p
and
y
q
have about half the bit length of
n
.
Inverse Transformation into the Problem Domain
The remaining step is now to assemble the final result
y
from its modular represen-
tation (
y
p
,
y
q
). This follows from the CRT and can be done as:
y
≡
[
qc
p
]
y
p
+[
pc
q
]
y
q
mod
n
(7.7)
where the coefficients
c
p
and
c
q
are computed as:
q
−
1
p
−
1
c
p
≡
mod
p
,
c
q
≡
mod
q
Since the primes change very infrequently for a given RSA implementation, the two
expressions in brackets in Eq. (7.7) can be precomputed. After the precomputations,
the entire reverse transformation is achieved with merely two modular multiplica-
tions and one modular addition.
Before we consider the complexity of RSA with CRT, let's have a look at an
example.
Example 7.6.
Let the RSA parameters be given by:
p
= 11
e
= 7
e
−
1
q
= 13
d
≡
≡
103 mod 120
n
=
p
·
q
= 143
We now compute an RSA decryption for the ciphertext
y
= 15 using the CRT, i.e.,
the value
y
d
= 15
103
mod 143. In the first step, we compute the modular represen-
tation of
y
:
y
p
≡
15
≡
4 mod 11
2 mod 13
In the second step, we perform the exponentiation in the transform domain with the
short exponents. These are:
y
p
≡
15
≡
d
p
≡
103
≡
3 mod 10
d
q
≡
103
≡
7 mod 12
Here are the exponentiations:
y
d
p
= 4
3
= 64
x
p
≡
≡
9 mod 11
y
d
q
= 2
7
= 128
≡
≡
x
q
11 mod 13
In the last step, we have to compute
x
from its modular representation (
x
p
,
x
q
).For
this, we need the coefficients:
