5 Prime field elliptic curve digital signatures explained
This chapter explains how elliptic curve digital signatures provide mathematical proof that a document came from the holder of a private key. The basic idea is to combine a hash of the message with secret key material to produce a signature, then let anyone with the matching public key repeat the relevant calculations and decide whether the signature is valid. It also emphasizes an important real-world point: cryptography alone is not enough, because the verifier must also be sure the public key itself is authentic and not substituted by an attacker.
Two signature schemes are then compared in detail: Schnorr and the NIST version of ECDSA. Schnorr is presented first as the simpler and more compact construction, while ECDSA is described as a more elaborate but widely used alternative. Both rely on generating a fresh random value for each signature, deriving an elliptic curve point from that value, hashing the point together with the message, and combining the hash with the private key. The chapter highlights the tradeoff between the two: Schnorr is conceptually cleaner and slightly faster, but its signature carries more data, whereas ECDSA uses a smaller signature but more arithmetic.
The implementation sections show how these schemes can be coded using GMP-style big integers and elliptic curve helper routines. For Schnorr, the signature stores a point and one integer, and verification recomputes the same hash and checks whether the reconstructed point matches the signed point exactly. For ECDSA, the signature stores two integers, and verification inverts one component, rebuilds a point from the message hash and public key, then confirms that the resulting x-coordinate matches the signature value. In both cases, the examples demonstrate that signing and verifying succeed when the message is unchanged, reinforcing that even a one-bit alteration causes verification to fail.
Schnorr signature steps
ECDSA signature steps
Summary
- Schnorr digital signature combines a random value times a base point (called \(Q\)) with a document and computes the hash of the combination.
- With the Schnorr digital signature, the signer’s private key is combined with the hash value and random value to create the other part of the signature.
- Verification of Schnorr uses the signer’s public key with the signature to check for a match. Since this requires a hash of the point \(Q\) and document, even one bit difference will fail.
- NIST (2023) created a standard for the elliptic curve digital signature algorithm (ECDSA). ECDSA uses the hash of a message, a random value, and the signer’s private key to create one value of the signature. The \(x\) component of the random value times the base point is the second value.
- To verify with ECDSA, several calculations are combined with the hash of the document and the signature. These values are multiplied by the base point and the signer’s public key whose sum is then compared with a signature value. A match verifies and one bit error will fail.
FAQ
What is a digital signature in elliptic curve cryptography?
A digital signature is a mathematical proof of authorship created with a private key and a hash of the document. The corresponding public key is then used to verify that the signature was produced by the matching private key.Why does a signature need both a private key and a public key?
The private key is used to create the signature, while the public key is used to verify it. If the public key matches the signer’s private key pair, the verifier can confirm the document was signed by that key holder.What is the difference between Schnorr signatures and ECDSA?
Schnorr signatures are shorter and more concise, while ECDSA is more involved mathematically and produces two signature values. Schnorr uses a full point and one scalar, whereas ECDSA uses a pair of scalar values.Why is the random value k important in Schnorr and ECDSA signing?
The valuek must be random and ideally different for every signature because it is critical to security. Reusing it or choosing a weak value can expose the private key or weaken the signature.How is a Schnorr signature created?
First, choose a randomk, compute Q = kB, hash the concatenation of Q and the message to get e, and then compute s = k - e·s_p mod n. The signature is the pair (Q, s).How does Schnorr signature verification work?
The verifier recomputese from the signature point and the message, then checks whether Q = sB + eP_p. If the points match, the signature is accepted; otherwise, it is rejected.How is an ECDSA signature created?
ECDSA hashes the message to gete, chooses a random k, computes R = kB, sets c = R.x mod n, and then computes d = k^-1(e + c·s_p) mod n. The signature is the pair (c, d).How does ECDSA verification work?
The verifier computes the message hash, findsh = d^-1 mod n, then calculates h1 = e'h mod n and h2 = ch mod n. It forms R' = h1B + h2P_p and checks whether R'.x = c.Why is the message hash used in both signing and verification?
The hash binds the signature to the exact message content. If even one bit of the message changes, the recomputed hash changes and verification fails.Which is more compact: Schnorr or ECDSA?
ECDSA is more compact in this chapter’s presentation because its signature contains twompz_t values, while Schnorr uses three components: a point Q and one scalar s.
Elliptic Curve Cryptography for Developers ebook for free