Elliptic Curve Digital Signature Algorithm

An Elliptic Curve Digital Signature Algorithm (ECDSA) is based on a commitment and verifier. With ECDSA, the commitment is typically a random point on the elliptic curve, and the verifier is an unguessable number which satisfies a verification equation that also takes a public key and message. Corruption to either the commitment or the verifier will result in an unverifiable signature.

Creating a signature involves both a probabilistic process and a few deterministic processes.

Could you explain what probabilistic and deterministic mean?

A probabilistic process is a computation that produces something that appears random, inputs may be given that tweak the properties of what comes out.

A deterministic process is a sequence of steps that always results in the same thing given the exact same inputs.

Also, I will refer to the private key, what you might see in a PEM file, as a "signing secret" or "signing secret key". Other created and forgotten secrets are involved as you will see next.

A commitment secret is chosen randomly and is a large number. This secret should be less than the prime number the curve is based on and it should be greater than zero. This commitment secret will be used in the signature equation later and, as named, should be kept secret. It is generated with a probabilistic process.

Then, the commitment secret is transformed into a public format called the commitment. This generally involves math where the "base point" or "generator" of the curve is multiplied by itself many times. If the commitment secret were 500 then the base point would be multiplied by itself 500 times. This is also referred to as exponentiation.

"Base point" and "generator" are terms used to refer to a point value defined by the curve. Points are defined as having an x and y coordinate. If you apply a whole number (called a "scalar") as an exponent to the coordinate, an elliptic curve operation is executed to compute a new point on the elliptic curve.

What about this mathematical operation makes it important?

Reversing this exponentiation operation is considered a computationally-hard problem. It is also sometimes called a "trap door function", where it is easy to fall in, but not to climb out. Often this problem is referred as "The Discrete Log Problem", or "DLog." Computationally-hard problems underpin all of modern practical cryptography.

We often call the commitment in specifications and papers "R", as it is a random point. The verifying application cannot confirm how the commitment was constructed. It may be maliciously constructed or unsafely constructed if the commitment secret were 0 or greater than the prime-order of the curve.

What's this about a prime-order?

ECDSA is based upon elliptic curves which involve a high-bit prime number in its definition. When the "base point" is multiplied to itself more times than the prime number, this reduces the security of the curve by introducing bias or malleability. So it is important that scalars used in exponentiation do not equal or exceed the prime number in honest implementations.

Before creating the verifier, the message is hashed (along with any other contextual information) and the hash is treated as a big number, in other words a "scalar." This hash is something the verifying application must recreate when using a verification equation. It is generated with a deterministic process.

The verifier is constructed with an equation which takes the secret signing key, the message hash, the public key, the commitment, and the curve parameters as inputs. Unlike the commitment which is a point, the verifier is just a large number.

A signature is the commitment and the verifier bundled together. Additional info like what curve, what hash algorithm, the public key identifier, etc. may also be included.

To verify a signature, an application must reconstruct the hash from the message and have the public key of the signer. A signature is verified with the signature components (the commitment and verifier, and contextual components like the message hash, the public key, and the curve parameters. It is verified by using an equation which if satisfied strongly indicates that the private key tied to the public key was used to sign the message hash.

To see more on how ECDSA is implemented, check out RFC6979 section 2.3.5 and section 2.4. RFC6979 describes a deterministic implementation, to read a non-deterministic implementation consider step 2 of section 2.4 to only contain:

A random value modulo q, dubbed k, is generated [with a cryptographic number generator].

And ignore section 3 entirely for a probabilistic ECDSA implementation.

ECDSA comes with a few weaknesses:

• If the same commitment is signed with two verifiers using the same public key, the private key can be trivially recovered;
• Insufficient randomness or broken randomness for commitment generation will allow private keys to be recovered;
• Libraries may allow the application to set the commitment, which may let the attacker influence or set the commitment and therefore allow private keys to be recovered;
• And if the public key is maliciously constructed, its signatures might be accepted for any or several messages.

You can find out more how ECDSA was poorly implemented in Sony PlayStation 3 ECDSA random number reuse (archived).