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 (x
Q
,y
Q
).
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 = (x
1
,y
1
).
4. Currently, the first coordinate, x
1
, is an element of the finite field. To perform
further calculations, we must convert x
1
to an integer, called . We do this as
follows:
For F
p
, x
1
is an integer α in the range 0 to p–1. Let = α. (Essentially, no
conversion is required.)
For F
2
m, x
1
is a bit string of length m bits: s
1
s
2
...s
m
. Because F
2
m 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 x
1
:
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 F
2
m and represent it as an
integer, it has some limitations. If you perform any arithmetic operations on
x
1
x
1
x
1
x
1
2
mi–()
s
i
⋅
i1=
m
∑
=
x
1
x
1
