Chapter 3 Cryptography 73
Cryptography Overview

Creating the Key Pair

To compute a public/private key pair:
1. Generate a random value, d, between 1 and n–1.
2. Compute the elliptic curve point dP, that is, P added to itself d times. Call this
point Q; it is a pair of field elements (xQ,yQ).
The key pair is (Q,d): Q is the public key, d is the private key. As previously
mentioned, even if you know P and Q, you cannot easily calculate d.
ECDSA Signature Scheme
Once you have generated elliptic curve parameters and created a public/private key
pair, you can use this information to create an elliptic curve analogue of the Digital
Signature Algorithm (DSA).

Signing a Message

The holder of the private key can sign a message as follows:
1. Digest the outgoing message using SHA1. This yields a 20-byte (160-bit) digest, e.
2. Compute a random value, k, between 1 and n–1.
3. Compute the elliptic curve point kP = (x1,y1).
4. Currently, the first coordinate, x1, is an element of the finite field. To perform
further calculations, we must convert x1 to an integer, called . We do this as
follows:
For Fp, x1 is an integer α in the range 0 to p–1. Let = α. (Essentially, no
conversion is required.)
For F2m, x1 is a bit string of length m bits: s1s2...sm. Because F2m has a very strange
arithmetic, we need a way to think of its elements as integers. To do this, let the
integer be a weighted sum of the bits of x1:
In either case, once you have calculated , set r= . If r is zero, go back to step 2.
Note: Although this lets you take a member of the field F2m and represent it as an
integer, it has some limitations. If you perform any arithmetic operations on
x1
x1
x1
x12mi–()
si
⋅
i1=
m

∑

=
x1x1