Suppose Alice wants to send a signed message to Bob. Initially, the curve parameters must be agreed upon. Also, Alice must have a key pair suitable for elliptic curve cryptography, consisting of a private key (a randomly selected integer in the interval ) and a public key (where ). Let be the bit length of the group order .
For Alice to sign a message , she follows these steps:
# Calculate , where HASH is a cryptographic hash function, such as SHA-1, and let be the leftmost bits of . # Select a random integer from . # Calculate , where . If , go back to step 2. # Calculate . If , go back to step 2. # The signature is the pair .
When computing , the string resulting from shall be converted to an integer. Note that can be
greater than but not
longer<ref>[http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf FIPS 186-3, pp. 19 and 26]</ref>.
For Bob to authenticate Alice's signature, he must have a copy of her public key . If he does not trust the source of , he needs to validate the key ( here indicates the identity element):
# Check that is not equal to and its coordinates are otherwise valid # Check that lies on the curve # Check that
After that, Bob follows these steps:
# Verify that and are integers in . If not, the signature is invalid. # Calculate , where HASH is the same function used in the signature generation. Let be the leftmost bits of . # Calculate . # Calculate and . # Calculate . # The signature is valid if , invalid otherwise.
Note that using Straus's algorithm (also known as Shamir's trick) a sum of two scalar multiplications can be calculated faster than with two scalar multiplications.