Cryptography Reference
In-Depth Information
The RSA cryptosystemwas one of the first proposed, and remains one of themost-
used, public-key cryptosystems today. It is named after the three researchers Ron
Rivest, Adi Shamir and Len Adleman who first published the idea behind it. RSA
is surprisingly straightforward to understand if the simple mathematics behind it
can be grasped. It is important to have read Section 5.1.3 before continuing.
5.2.1
Setting up RSA
All the real work in RSA occurs during key generation. This should not be
surprising since the 'clever' part of any public-key cryptosystem is in designing a
relationship between two keys that allows one to reverse the effect of the other,
while allowing one of them to be publicly known. Note that we do not have to
be quite so mathematically clever when generating symmetric keys, which 'just'
requires an ability to randomly generate numbers (see Section 8.1). The wider
issues associated with key generation are discussed in more detail in Section 10.3.
GENERATING AN RSA KEY PAIR
We are now ready to generate an RSA key pair. The 'we' in this case is anyone
who is setting up an RSA key pair. This could be someone generating a key pair
for themselves, or a trusted key centre generating a key pair for a client. If we wish
to set up a network of users who may want to communicate with one another
using RSA then
every
user in the network will need to run this key pair generation
process, or have the trusted key centre run it for them. We proceed as follows:
Generating the modulus
. Let
n
be the product of two large primes
p
and
q
.In
other words, let
n
pq
.By
large
, we typically mean a minimum of 512 bits
long, preferably even longer. Thus
p
and
q
are very large primes, and
n
is an
even larger number. Finding primes of this size is not straightforward, but there
are known processes for generating them. The number
n
that is produced in
this step is usually referred to as an
RSA modulus
.
Generating
e
. We select a 'special' number
e
. The number
e
cannot be just any
number. For example, it must be greater than 1 and less than (
p
−
1)(
q
−
1).
The precise mathematical property that
e
must have is that there must be no
numbers that divide neatly into
e
and into (
p
−
1)(
q
−
1) except for 1. The
mathematical term for this property is that
e
and (
p
−
1)(
q
−
1) are
coprime
.
Consider the following simple example:
=
• Let
p
=
3 and
q
=
7. In this case (
p
−
1)(
q
−
1)
=
2
×
6
=
12. Any suitable
choice of
e
must have the property that there are no numbers that neatly divide
into
e
and 12, except for 1.
•
e
2 is no good, since 2 is a factor of both 2 and 12. For a similar reason we
can also rule out all multiples of 2, namely
e
=
=
4,
e
=
6,
e
=
8 and
e
=
10.
