Elliptic Curve Cryptography - Elliptic Curves: Number Theory and Cryptography - page 169

need to have some way of establishing a key. For example, Bob could send
a messenger to Alice several days in advance. Then, when it is time to send
the message, they both will have the key. Clearly this is impractical in many
situations.
The other type of encryption is public key encryption , or asymmetric
encryption. In this case, Alice and Bob do not need to have prior contact.
Bob publishes a public encryption key, which Alice uses. He also has a private
decryption key that allows him to decrypt ciphertexts. Since everyone knows
the encryption key, it should be infeasible to deduce the decryption key from
the encryption key. The most famous public key system is known as RSA
and is based on the di culty of factoring integers into primes. Another well-
known system is due to ElGamal and is based on the di culty of the discrete
logarithm problem.
Generally, public key systems are slower than good symmetric systems.
Therefore, it is common to use a public key system to establish a key that
is then used in a symmetric system. The improvement in speed is important
when massive amounts of data are being transmitted.

6.2 Di e-Hellman Key Exchange

Alice and Bob want to agree on a common key that they can use for ex-
changing data via a symmetric encryption scheme such as DES or AES. For
example, Alice and Bob could be banks that want to transmit financial data.
It is impractical and time-consuming to use a courier to deliver the key. More-
over, we assume that Alice and Bob have had no prior contact and therefore
the only communication channels between them are public. One way to estab-
lish a secret key is the following method, due to Di e and Hellman (actually,
they used multiplicative groups of finite fields).

1. Alice and Bob agree on an elliptic curve E over a finite field F q such
that the discrete logarithm problem is hard in E ( F q ). They also agree
on a point P E ( F q ) such that the subgroup generated by P has large

order (usually, the curve and point are chosen so that the order is a
large prime).

∈

2. Alice chooses a secret integer a , computes P a = aP , and sends P a to
Bob.

3. Bob chooses a secret integer b , computes P b = bP , and sends P b to Alice.

4. Alice computes aP b = abP .

5. Bob computes bP a = baP .