Jump to content

Elliptic Curve Digital Signature Algorithm

From BitcoinWiki

Elliptic Curve Digital Signature Algorithm

The Elliptic Curve Digital Signature Algorithm (ECDSA) is a public-key signature scheme. A signer uses a private key to produce a signature over a message digest; anyone with the corresponding public key can verify the signature. ECDSA provides authentication and integrity, not encryption: it does not hide the signed message.[1]

Bitcoin uses ECDSA with the secp256k1 curve for many pre-Taproot and SegWit transaction outputs. Taproot outputs instead use BIP 340 Schnorr signatures over the same curve.[2]

Operation

An elliptic-curve domain defines a base point G of order n. The private key is an integer d, and the public key is the curve point Q = dG. To sign a message digest represented by z, the signer chooses a per-signature secret nonce k, computes R = kG, sets r from the x-coordinate of R, and calculates s = k⁻¹(z + rd) mod n. The signature is the pair (r, s).

Verification checks the allowed ranges of r and s, computes values derived from z, s and Q, and confirms that the resulting curve point has the expected x-coordinate. Verification proves that the signature matches the message and public key; it does not reveal the private key or establish the real-world identity of its holder.[1]

For a 256-bit curve, a private key is normally 32 bytes. A secp256k1 public key is commonly serialized as 33 bytes in compressed form or 65 bytes uncompressed. The mathematical signature contains two integers; its serialized length depends on the encoding.

Nonce safety

The nonce k must never repeat for two different messages under the same private key and must not be predictable. Reuse or bias can expose the private key through algebra or statistical attacks. This failure class caused well-known compromises, including recovery of a PlayStation 3 signing key and thefts from some Android Bitcoin wallets after a 2013 random-number-generator defect.

RFC 6979 defines deterministic ECDSA: k is derived from the private key and message digest with a keyed construction, avoiding dependence on fresh random input for each signature while remaining compatible with ordinary ECDSA verification.[3] Determinism does not protect an exposed private key, faulty curve arithmetic, side channels or a compromised signing device.

Implementations must also resist timing, power-analysis and fault-injection attacks. Constant-time arithmetic, public-key validation, protected secret storage and tested libraries matter as much as the high-level formula.

Use in Bitcoin

Bitcoin uses the secp256k1 domain parameters. Traditional Bitcoin transaction signatures encode the two ECDSA integers using Distinguished Encoding Rules (DER), followed by a Bitcoin signature-hash type byte. BIP 66 made strict DER encoding a consensus rule. Bitcoin implementations also use a low-S form to reduce ECDSA signature malleability: because both (r,s) and (r,n-s) can verify, accepting only the lower value removes that simple alternative encoding.[4]

The message being signed is a transaction-dependent digest, not the human-readable transaction alone. Different signature-hash modes determine which inputs and outputs the signature commits to. Wallet and hardware-signing interfaces therefore need to show the actual payment details that the signer is authorizing.

Taproot did not remove ECDSA from Bitcoin. Older output types continue to use it, while Taproot key-path and script-path signature checks use 64-byte BIP 340 Schnorr signatures. The distinction should be preserved when describing “Bitcoin signatures.”[5]

Quantum-computing research

A sufficiently capable fault-tolerant quantum computer running Shor's algorithm could recover an elliptic-curve private key from its public key. This is a prospective threat to ECDSA and Schnorr signatures, not a demonstrated ability of current hardware.

A September 2026 preprint reported optimized reversible secp256k1 point-addition circuits. At its stated cutoff, the best benchmark used 1,151 logical qubits and about 1.30 million average executed Toffoli gates per evaluated point-addition circuit, reducing the authors' width-times-gate score by more than half relative to one previously published comparison. The paper explicitly notes different accounting conventions and that its per-call sensitivity model is not a complete Shor-attack success estimate. Physical error correction, the many circuit calls in a full attack, runtime and hardware engineering remain additional costs.[6][7]

The research improves a resource estimate; it does not mean that Bitcoin or Ethereum keys can presently be recovered. Public keys already revealed on-chain would be the most direct cryptographic targets if suitable hardware were eventually built. Migration planning must distinguish that long-term protocol risk from today's much more common key theft, phishing and implementation failures.

See also

References

  1. ↑ 1.0 1.1 Standards for Efficient Cryptography Group, “SEC 1: Elliptic Curve Cryptography,” version 2.0, 2009.
  2. ↑ BIP 340: Schnorr Signatures for secp256k1, deployed.
  3. ↑ RFC 6979: Deterministic Usage of DSA and ECDSA, 2013.
  4. ↑ Bitcoin Core secp256k1 library, checked 16 September 2026.
  5. ↑ BIP 341: Taproot, deployed.
  6. ↑ Long et al., “ECDSA.Fail: Open Autoresearch for Optimizing Elliptic-Curve Point Addition in Shor's Algorithm”, submitted 9 September 2026.
  7. ↑ CoinDesk, “Crypto researchers cut Bitcoin and Ethereum quantum attack estimate by 50%”, 10 September 2026.
Retrieved from "https://bitcoinwiki.org/index.php?title=Elliptic_Curve_Digital_Signature_Algorithm&oldid=10399"