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

the document in such a way that it cannot be used again. However, it must
be possible for someone to verify that the signature is valid, and it should
be possible to show that Alice must have been the person who signed the
document. One solution to the problem relies on the di culty of discrete
logs. Classically, the algorithm was developed for the multiplicative group of
a finite field. In fact, it applies to any finite group. We'll present it for elliptic
curves.
Alice first must establish a public key. She chooses an elliptic curve E over
a finite field F q such that the discrete log problem is hard for E ( F q ). She also
chooses a point A ∈ E ( F q ). Usually the choices are made so that the order
N of A is a large prime. Alice also chooses a secret integer a and computes
B = aA . Finally, she chooses a function

f : E ( F q ) → Z .

For example, if F q = F p , then she could use f ( x, y )= x ,where x is regarded
as an integer, 0 ≤ x<p . The function f needs no special properties, except
that its image should be large and only a small number of inputs should
produce any given output (for example, for f ( x, y )= x ,atmosttwopoints
( x, y ) yield a given output x ).
Alice's public information is E , F q , f , A ,and B . She keeps a private. The
integer N does not need to be made public. Its secrecy does not affect our
analysis of the security of the system. To sign a document, Alice does the
following:

1. Represents the document as an integer m (if m>N ,choosealarger
curve, or use a hash function (see below)).

2. Chooses a random integer k with gcd( k, N ) = 1 and computes R = kA .

3. Computes s ≡ k − 1 ( m − af ( R )) (mod N ).

The signed message is ( m, R, s ). Note that m, s are integers, while R is a point
on E . Also, note that Alice is not trying to keep the document m secret. If
she wants to do that, then she needs to use some form of encryption. Bob
verifies the signature as follows:

1. Downloads Alice's public information.

2. Computes V 1 = f ( R ) B + sR and V 2 = mA .

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

V 1 = f ( R ) B + sR = f ( R ) aA + skA = f ( R ) aA +( m − af ( R )) A = mA = V 2 .

We have used the fact that sk ≡ m − af ( R ), hence sk = m − af ( R )+ zN for
some integer z . Therefore,

skA =( m − af ( R )) A + zNA =( m − af ( R )) A + ∞ =( m − af ( R )) A.