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

1. Given a message m , the value H ( m ) can be calculated very quickly.

2. Given y , it is computationally infeasible to find m with H ( m )= y .(This
says that H is preimage resistant .)

3. It is computationally infeasible to find distinct messages m 1 and m 2
with H ( m 1 )= H ( m 2 ). (This says that H is strongly collision-free .)

The reason for (2) and (3) is to prevent Eve from producing messages with
a desired hash value, or two messages with the same hash value. This helps
prevent forgery. There are several popular hash functions available, for exam-
ple, MD5 (due to Rivest; it produces a 128-bit output) and the Secure Hash
Algorithm (from NIST; it produces a 160-bit output). We won't discuss these
here. For details, see [81]. Recent work of Wang, Yin, and Yu [127] has found
weaknesses in them, so the subject is somewhat in a state of flux.
If Alice uses a hash function, the signed message is then

( m, R H ,s H ) ,

where ( H ( m ) ,R H ,s H ) is a valid signature. To verify that the signature

( m, R H ,s H ) is valid, Bob does the following:

1. Downloads Alice's public information.

2. Computes V 1 = f ( R H ) B + s H R H and V 2 = H ( m ) A .

3. If V 1 = V 2 , he declares the signature valid.

The advantage is that a very long message m containing billions of bits has a
signature that requires only a few thousand extra bits. As long as the discrete
log problem is hard for E ( F q ), Eve will be unable to put Alice's signature on
another message. The use of a hash function also guards against certain other
forgeries (see Exercise 6.2).
A recent variant of the ElGamal signature scheme due to van Duin is very
ecient in certain aspects. For example, it avoids the computation of k − 1 ,
and its verification procedure requires only two computations of an integer
times a point. As before, Alice has a document m that she wants to sign. To
set up the system, she chooses an elliptic curve E over a finite field F q and
apoint A ∈ E ( F q ) of large prime order N . She also chooses a cryptographic
hash function H . She chooses a secret integer a and computes B = aA .The
public information is ( E,q,N,H,A,B ). The secret information is a .Tosign
m , Alice does the following:

1. Chooses a random integer k mod N and computes R = kA .

2. Computes t = H ( R, m ) k + a (mod N ).