Chapter 3 Cryptography 77
Cryptography Overview
6. Compute an authentication tag, tag = SHA1 (x
1
|| M’). That is, tag is the SHA1
hash of concatenation of the x-coordinate of the secret point k
1
Q and the message
M’. Since tag is an SHA1 hash, tag is 20 bytes long.
7. Transmit the ciphertext c =(Q
1
,M’,tag). The total length of c in bytes is: 21+2 · (the
length of a field element in bytes) + f.
Decrypting a Message Using the Private Key
A message that had been encrypted in the previous example can be decrypted using
the private key as follows:
1. Parse the received ciphertext c =(Q
1
,M’,tag) into its components, Q
1
, M’, and tag.
2. Use the private key k
2
to compute the elliptic curve point S
2
= k
2
Q
1
. S
2
is a pair
(x
2
,y
2
). If the message was transmitted correctly and encoded with the correct
public key, S
2
is equal to S
1
.
3. To verify that S
2
is equal to S
1
, compute tag' = SHA1 (x
2
|| M'). If tag' is different
from tag, output an error and stop.
4. Compute a one time pad, otp’, of length f, from x
2
using the key derivation
function outlined in Step 4 on page 76. Use x
2
instead of x
1
. Since x
1
= x
2
,
otp’ = otp.
5. Compute M = otp XOR M’.
Elliptic Curve Diffie-Hellman Key Agreement
It is possible to construct a version of the Diffie-Hellman key agreement that uses
elliptic curves. (For more information on Diffie-Hellman key agreement, see “Diffie-
Hellman Public Key Agreement” on page 62.) Like Diffie-Hellman, EC Diffie-
Hellman provides for key agreement, but not encryption or authentication.
The elliptic curve Diffie-Hellman key agreement algorithm provides a method for two
parties to each compute the same secret key without exchanging secret information.
The algorithm is made up of two parts: Phase 1 and Phase 2. Before they begin, the
two parties must agree on the elliptic curve parameters: a base field, an elliptic curve
over the base field, and point P of prime order, along with its order n. See the section
“Elliptic Curve Parameters” on page 66 for details. See Figure 3-13 on page 79 for an
illustration of Elliptic Curve Diffie-Hellman key agreement.
