Cryptography Reference
In-Depth Information
•
e
3 is no good, since 3 is a factor of both 3 and 12. For a similar reason we
can also rule out all multiples of 3, namely
e
=
=
6 and
e
=
9.
11. Since in each case there
is no number that divides into these choices of
e
and 12, other than 1, all these
choices of
e
are valid.
Unlike in this 'toy' example, for the sizes of
p
and
q
that we tend to use
in real RSA implementations we will find that many numbers less than
(
p
−
1)(
q
−
1) have the right property to be used as
e
.
Forming the public key
. The pair of numbers (
n
,
e
) form the RSA public key and
can be made available to anyone who wishes to send encrypted messages to
the holder of the private key (which we have not yet generated). The primes
p
and
q
must not be revealed. Recall that although
n
is part of the public key, the
fact that multiplication of two primes is a one-way function (see Section 5.1.4)
should prevent them frombeing discovered by any entities not entitled to know
them. Note that occasionally we may refer to the public key as simply being
e
.
This is only done in situations where the value of the RSA modulus
n
is clear
and assumed.
Generating the private key
. We compute the private key
d
from
p
,
q
and
e
.
The private key
d
is uniquely determined by the public key (
n
• The remaining choices are
e
=
5,
e
=
7, and
e
=
e
), meaning
that given an
n
and an
e
there can only ever be one possible value
d
. This
is essentially the clever part of RSA, since it is the mathematical relationship
between
e
and
d
that makes RSA work. We thus have to be precise about how
to find this value
d
.
In mathematical terminology, the private key
d
is the
inverse of e modulo
,
(
p
1) (see the Mathematics Appendix for more details). What this
means is that
d
is the unique number less than (
p
−
1)(
q
−
−
1)(
q
−
1) that, when
−
−
multiplied by
e
, is equal to 1 modulo (
p
1). Written mathematically
(which is much simpler) this relationship is expressed by:
1)(
q
ed
=
1mod (
p
−
1)(
q
−
1)
.
It is sufficient just to accept that, if we choose
e
correctly, such a
d
exists
and is unique. Conveniently, there is a simple algorithm to compute
d
. This
algorithm is known as the
Extended Euclidean Algorithm
, which takes as input
p
,
q
and
e
, and outputs
d
. The Extended Euclidean Algorithm can be computed
in polynomial time by anyone who knows
p
and
q
. However, anyone who does
not know
p
and
q
cannot run it to find
d
. This is why it is important that
n
=
pq
is difficult to factor. If
n
was easy to factor then an attacker could compute
p
and
q
and then run the Extended Euclidean Algorithm to obtain
d
.
It is worth providing an example of RSA key generation, just to make sure that the
process is clear. This example will, of course, use numbers that are
far too small
to be used in practice. Just keep in mind that the primes we use are just six bits
long, rather than the thousands of bits long that is often recommended for RSA
implementations.
