Cryptography Reference
In-Depth Information
RSA Key Generation
Output
: public key:
k
pub
=(
n
,
e
) and private key:
k
pr
=(
d
)
1. Choose two large primes
p
and
q
.
2. Compute
n
=
p
·
q
.
3. Compute
Φ
(
n
)=(
p
−
1)(
q
−
1).
4. Select the public exponent
e
∈{
1
,
2
,...,
Φ
(
n
)
−
1
}
such that
gcd(
e
,
Φ
(
n
)) = 1
.
5. Compute the private key
d
such that
d
·
e
≡
mod
Φ
(
n
)
The condition that gcd(
e
,
Φ
(
n
)) = 1 ensures that the inverse of
e
exists modulo
Φ
(
n
), so that there is always a private key
d
.
Two parts of the key generation are nontrivial: Step 1, in which the two large
primes are chosen, as well as Steps 4 and 5 in which the public and private key
are computed. The prime generation of Step 1 is quite involved and is addressed
in Sect. 7.6. The computation of the keys
d
and
e
can be done at once using the
extended Euclidean algorithm (EEA). In practice, one often starts by first selecting a
public parameter
e
in the range 0
<
e
<
Φ
(
n
).Thevalue
e
must satisfy the condition
gcd(
e
,
(
n
)) = 1
.
We apply the EEA with the input parameters
n
and
e
and obtain
the relationship:
Φ
gcd(
Φ
(
n
)
,
e
)=
s
·
Φ
(
n
)+
t
·
e
If gcd(
e
,
(
n
)) = 1, we know that
e
is a valid public key. Moreover, we also know
that the parameter
t
computed by the extended Euclidean algorithm is the inverse of
e
, and thus:
Φ
d
=
t
mod
Φ
(
n
)
In case that
e
and
(
n
) are not relatively prime, we simply select a new value for
e
and repeat the process. Note that the coefficient
s
of the EEA is not required for
RSA and does not need to be computed.
We now see how RSA works by presenting a simple example.
Φ
Example 7.1.
Alice wants to send an encrypted message to Bob. Bob first computes
his RSA parameters in Steps 1-5. He then sends Alice his public key. Alice encrypts
the message (
x
= 4) and sends the ciphertext
y
to Bob. Bob decrypts
y
using his
private key.
