RSA Security 5.2.2 manual Ecdsa Signature Scheme, Creating the Key Pair, Signing a Message

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, point Q; it is a pair of field elements (xQ,yQ

P added to itself d times. Call this ).

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 x1 . We do this as follows:

For Fp, x1 is an integer α in the range 0 to p–1. Let x1 = α. (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 x1 be a weighted sum of the bits of x1:

m

x1 = ∑ 2(m – i) ⋅ si i = 1

In either case, once you have calculated x1 , set r = x1 . 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

C h a p t e r 3 C r y p t o g r a p h y 7 3