Elliptic Curve Digital Signature Algorithm
Here's what you should know about how ECDSAs work without diving into the exact
mathematical construction.
--------------------------------------------------------------------------------
Elliptic Curve Digital Signature Algorithm
==========================================
8 min read
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.
/[cendyne: puppy-confused]-----------------------------------------------------\
| Could you explain what probabilistic and deterministic mean? |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------[jacobi: thumbs-up]\
| 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. |
\------------------------------------------------------------------------------/
/--------------------------------------------------------------[jacobi: typing]\
| 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.
/---------------------------------------------------------------[jacobi: heart]\
| "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. |
\------------------------------------------------------------------------------/
/[cendyne: gendo]--------------------------------------------------------------\
| What about this mathematical operation makes it important? |
\------------------------------------------------------------------------------/
/------------------------------------------------------------[jacobi: teaching]\
| 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.
/[cendyne: peeking-from-door]--------------------------------------------------\
| What's this about a prime-order? |
\------------------------------------------------------------------------------/
/-----------------------------------------------------------[jacobi: crossmark]\
| 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.
/---------------------------------------------------------------[jacobi: notes]\
| To see more on how ECDSA is implemented, check out RFC6979 [L1] section |
| 2.3.5 and section 2.4. RFC6979 [L1] 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.
/----------------------------------------------------------[jacobi: point-left]\
| You can find out more how ECDSA was poorly implemented in Sony PlayStation 3 |
| ECDSA random number reuse [L2] (archived [L3]). |
\------------------------------------------------------------------------------/
--------------------------------------------------------------------------------
Elliptic Curve Digital Signature Algorithm (ECDSA):
A DSA which uses elliptic curve operations to sign a message. See /topics/
ecdsa.html [L4] for how it works.
Digital Signature Algorithm (DSA):
A digital signature algorithm produces and verifies signatures on a message
and authenticates to a verifier that the sender signed the message. The
minimum security property requirement for a DSA is EUF-CMA. See Why Digital
Signature Algorithms [L5].
[L1]: https://tools.ietf.org/html/rfc6979
[L2]: https://yingtongli.me/blog/2019/01/28/crypto-failures.html
[L3]: https://archive.ph/sS4HI
[L4]: /topics/ecdsa.html
[L5]: /posts/2022-03-05-why-dsa.html