Cryptography Reference
In-Depth Information
have described . Rather, the latest best-practice guidelines outlined in the relevant
standards should be consulted and followed. In particular, it should be noted that
real implementations of RSA are advised to feature
probabilistic encryption
, which
we explain in Section 5.3.4.
Despite its relatively high profile, RSA is not the only public-key cryptosystem,
just the most well-established one. RSA is definitely the best-known public-key
cryptosystem whose security is assumed to be based on the difficulty of factoring.
Of the other public-key cryptosystems proposed, several are based on different
versions of the discrete logarithm problem. Some of the most important variants
of these are based on the use of
elliptic curves
(see Section 5.3.5) and offer some
significant practical benefits over RSA. Rather than describing approaches based
on elliptic curves directly, we will discuss the
ElGamal
cryptosystem, for several
important reasons:
1. ElGamal is the public-key cryptosystem on which elliptic curve variants are
based;
2. ElGamal does not require further significant mathematical concepts;
3. ElGamal forms the basis for several other important cryptographic primitives,
such as the Digital Signature Algorithm (see Section 7.3.6).
5.3.1
Setting up ElGamal
We now describe how to set up key pairs for use in ElGamal. Each user who wishes
an ElGamal key pair conducts the following process:
Choose a large prime
p
. We will present a simplified version of ElGamal that
works with numbers modulo
p
. In practice, ElGamal is often based on a slightly
more general number system (and in the case of elliptic curve variants, is based
on quite different number systems). By 'large' we mean a prime of similar size
length to an RSA modulus. Thus a reasonable length would be in the order of
1024 to 2048 bits.
Choose a special number
g
. The special number
g
must be what is known as a
primitive element
modulo
p
. This number must be between 1 and
p
−
1, but
cannot be
any
such number because not all numbers in this range are primitive.
It suffices to accept
g
as being 'special', but if you wish to learn more about
what
primitive
means then see the Mathematics Appendix.
Choose the private key
. The private key
x
can be any number bigger than 1 and
smaller than
p
1. We assume that the private key is generated using a suitably
random process, which results in it being extremely unlikely that two users of
the same system have the same private key.
−
