• Curve parameters (q, FR, a, b, B, p, h) have to be agreed (e.g. asymmetric key exchange)
  • message m is to be signed
  1. H(m) hash is any hash function
  2. Select key k so that 1< k < n-1
  3. Calculate point P, P = k * B
  4. r = P_{x} mod{p} P_{x} is x coordinate of point P if r=0 then select new k
Signature generation algorithm

Suppose Alice wants to send a signed message to Bob. Initially, the curve parameters (q, FR, a, b, G, n, h) must be agreed upon. Also, Alice must have a key pair suitable for elliptic curve cryptography, consisting of a private key d_A (a randomly selected integer in the interval [1, n-1]) and a public key Q_A (where Q_A = d_A G). Let L_n be the bit length of the group order n.

For Alice to sign a message m, she follows these steps:

# Calculate e = \textrm{HASH}(m), where HASH is a cryptographic hash function, such as SHA-1, and let z be the L_n leftmost bits of e. # Select a random integer k from [1, n-1]. # Calculate r = x_1 \pmod{n}, where (x_1, y_1) = k G. If r = 0, go back to step 2. # Calculate s = k^{-1}(z + r d_A ) \pmod{n}. If s = 0, go back to step 2. # The signature is the pair (r, s).

When computing s, the string z resulting from \textrm{HASH}(m) shall be converted to an integer. Note that z can be greater than n but not longer<ref>[ FIPS 186-3, pp. 19 and 26]</ref>.

Signature verification algorithm

For Bob to authenticate Alice's signature, he must have a copy of her public key Q_A. If he does not trust the source of Q_A, he needs to validate the key (O here indicates the identity element):

# Check that Q_A is not equal to O and its coordinates are otherwise valid # Check that Q_A lies on the curve # Check that nQ_A = O

After that, Bob follows these steps:

# Verify that r and s are integers in [1, n-1]. If not, the signature is invalid. # Calculate e = \textrm{HASH}(m), where HASH is the same function used in the signature generation. Let z be the L_n leftmost bits of e. # Calculate w = s^{-1} \pmod{n}. # Calculate u_1 = zw \pmod{n} and u_2 = rw \pmod{n}. # Calculate (x_1, y_1) = u_1 G + u_2 Q_A. # The signature is valid if r = x_1 \pmod{n}, invalid otherwise.

Note that using Straus's algorithm (also known as Shamir's trick) a sum of two scalar multiplications u_1 G + u_2 Q_A can be calculated faster than with two scalar multiplications.

Last modified: 2013/07/01 14:42