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

The signed document is ( m, R, t ).
To verify the signature, Bob downloads Alice's public information and
checks whether

tA = H ( R, m ) R + B

is true. If it is, the signature is declared valid; otherwise, it is invalid.

6.6 The Digital Signature Algorithm

The Digital Signature Standard [1],[86] is based on the Digital Signature Al-
gorithm (DSA). The original version used multiplicative groups of finite fields.
A more recent elliptic curve version (ECDSA) uses elliptic curves. The algo-
rithm is a variant on the ElGamal signature scheme, with some modifications.
We sketch the algorithm here.
Alice wants to sign a document m , which is an integer (actually, she usually
signs the hash of the document, as in Section 6.5). Alice chooses an elliptic
curve over a finite field F q such that # E ( F q )= fr ,where r is a large prime
and f is a small integer, usually 1,2, or 4 ( f should be small in order to keep
the algorithm e cient). She chooses a base point G in E ( F q )oforder r .
Finally, Alice chooses a secret integer a and computes Q = aG . Alice makes
public the following information:

F q , E, , G, Q.

(There is no need to keep f secret; it can be deduced from q and r using
Hasse's theorem by the technique in Examples 4.6 and 4.7.) To sign the

message m Alice does the following:

1. Chooses a random integer k with 1 ≤ k<r and computes R = kG =
( x, y ).

2. Computes s = k − 1 ( m + ax )(mod r ).

The signed document is

( m, R, s ) .

To verify the signature, Bob does the following.

1. Computes u 1 = s − 1 m (mod r )and u 2 = s − 1 x (mod r ).

2. Computes V = u 1 G + u 2 Q .

3. Declares the signature valid if V = R .