Cryptography Reference
In-Depth Information
de
≡
1(mod
φ
(
n
))
using, for example, the extended Euclid algorithm (i.e., Algorithm 3.2).
6
The output of the
Generate
algorithm is a public key pair that consists of
a public key (
n, e
) and a corresponding private key (
n, d
).
7
The public key is
mainly used for encryption, whereas the private key is mainly used for decryption.
Consequently,
e
is sometimes also referred to as
public
or
encryption exponent
,
whereas
d
is referred to as
private
or
decryption exponent
.
Let us consider a toy example to illustrate what is going on in the RSA
Generate
algorithm (and the other algorithms of the RSA asymmetric encryption
system). In the first step, the RSA
Generate
algorithm selects
p
=11and
q
=23,
and then computes
n
=11
22 = 220.Inthe
second step, the RSA
Generate
algorithm selects
e
=3and uses the extended
Euclid algorithm to compute
d
= 147 modulo 220 (note that 3
·
23 = 253 and
φ
(253) = 10
·
≡
1 (mod 220), and hence
d
= 147 really represents the multiplicative inverse
element of
e
=3modulo 220). Then (253
,
3) represents the public key, and
(253
,
147) represents the private key.
·
147 = 441
14.2.1.2
Encryption Algorithm
In its basic form, the RSA
Encrypt
algorithm is deterministic. It takes as input a
public key (
n, e
) and a plaintext message
m
∈
Z
n
, and it generates as output the
ciphertext
m
e
(mod
n
)
.
c
=RSA
n,e
(
m
)
≡
To compute
c
,theRSA
Encrypt
algorithm must employ a modular exponen-
tiation algorithm, such as, for example, the square-and-multiply algorithm (i.e., Al-
gorithm 3.3). In either case, the computation can be done efficiently.
If we want to encrypt the plaintext message
m
=26in our toy example, then
we compute
m
e
(mod
n
)
26
3
(mod 253) = 119
.
c
≡
≡
6
Note that
gcd
(
e, φ
(
n
)) = 1 suggests that an integer
d
with
de ≡
1(mod
φ
(
n
)) exists.
Note that the modulus
n
need not be a part of the private key. It is, however, often useful and
convenient to include it in the private key.
7
