Cryptography Reference
In-Depth Information
and hence
c
d
(mod
n
) properly decrypts to
m
.
In our toy example, the ciphertext
c
= 119 is decrypted as follows:
c
d
(mod
n
) = 119
147
(mod 253) = 26
m
≡
Consequently, we have properly decrypted our originally encrypted plaintext
message
m
=26.
If the RSA
Decrypt
algorithm has access to the prime factors
p
and
q
(in
addition to
d
), then the CRT (i.e., Theorem 3.6) can be used to speed up the
decryption process considerably. Instead of directly computing
m
c
d
(mod
n
),
≡
one can compute
c
d
(mod
p
)
m
p
≡
and
c
d
(mod
q
)
,
m
q
≡
and then use the CRT to compute
m
∈
Z
n
, which satisfies
m
≡
m
p
(mod
p
) and
m
≡
m
q
(mod
q
). In our toy example, we have
c
d
(mod
p
)
119
147
(mod 11) = 4
m
p
≡
≡
and
c
d
(mod
q
)
119
147
(mod 23) = 3
.
m
q
≡
≡
We can then use the CRT to compute
m
∈
Z
253
, which satisfies
m
≡
4 (mod 11) and
m
≡
3 (mod 11), and the resulting plaintext message is again
m
=26.
In addition to the CRT, there are several other possibilities and techniques
to speed up the RSA decryption (and signature generation) algorithm. Examples
include batch RSA, multifactor RSA, and rebalanced RSA as overviewed and
discussed in [6]. These possibilities and techniques are important when it comes
to an implementation of the RSA asymmetric encryption system, especially if one
uses low-power computational devices. They are, however, beyond the scope of this
topic.
