Cryptography Reference
In-Depth Information
Then 119 represents the ciphertext for the plaintext message 26. As such, it is
transmitted to the recipient(s).
In either case, it is important to note that the public key (
n, e
) is publicly
available, and hence anybody can use it to compute RSA
n,e
(
m
) and to encrypt
an arbitrary plaintext message
m
. Consequently, RSA encryption provides neither
data origin authentication nor data integrity. Complementary mechanisms must be
employed to provide these types of security services.
14.2.1.3
Decryption Algorithm
The RSA
Decrypt
algorithm is deterministic. It takes as input a private key (
n, d
)
and a ciphertext
c
, and it generates as output the corresponding plaintext message
c
d
(mod
n
)
.
m
=RSA
n,d
(
c
)
≡
Again, a modular exponentiation algorithm must be used to compute
m
,and
this computation can be done efficiently.
The correctness of the decryption algorithm results from Fermat's Little
Theorem (i.e., Theorem 3.7) and Euler's Theorem (i.e., Theorem 3.8). In fact,
Fermat's Little Theorem says that for every
m
∈
Z
n
with
gcd
(
m, p
)=1
m
kφ
(
p
)
m
φ
(
p
)
m
p−
1
≡
≡
≡
1(mod
p
)
.
If we multiply either side with
m
,thenweget
m
kφ
(
p
)+1
≡
m
(mod
p
)
.
This equivalence holds for all
m
∈
Z
n
(it trivially holds for all
m
≡
0(mod
p
)). The same arguments apply for
q
, and hence we have
m
kφ
(
p
)+1
≡
m
(mod
q
)
for all
m
∈
Z
n
. Putting the last two equivalences together, it follows that
m
kφ
(
n
)+1
m
ed
≡
≡
m
(mod
n
)
,
