Elliptic Curve Digital Signature Algorithm8 min read - Text Only
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.
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.
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.
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.
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.