ECDSA (Asymmetric) Cryptography

ECDSA is a widely adopted digital signature scheme based on elliptic curve discrete logarithm problems (ECDLP). Unlike RSA, which relies on integer factorization, ECDSA offers equivalent security with much smaller key sizes. For example, a 256-bit elliptic curve key (P-256) provides comparable strength to a 3072-bit RSA key. This efficiency makes ECDSA ideal for constrained environments such as mobile devices, IoT hardware, and blockchain applications like Bitcoin and Ethereum.

The algorithm supports two main operations: signing, where the private key is used to generate a signature over a hashed message; and verification, where the public key confirms the signature’s validity. ECDSA keys consist of a curve identifier and a point (x, y) on the curve for the public key, and a scalar d for the private key. Standard curves (P-256, P-384, P-521) are specified by NIST and widely supported in cryptographic libraries and protocols (e.g., TLS, JWT, SSH).

Elliptic curves used in ECDSA are defined over finite prime fields, with the general form y^2 = x^3 + ax + b mod p. The group law on the curve enables point addition and scalar multiplication. The security of ECDSA hinges on the hardness of computing the discrete logarithm k in Q = k · G, where G is the base point on the curve and Q is the public key point. Given G and Q, determining k is computationally infeasible with current algorithms for sufficiently large p.

Key generation involves selecting a random integer d in [1, n−1], where n is the order of the base point G. The public key point Q is computed as Q = d · G using efficient elliptic curve point multiplication. Security requires a cryptographically secure random number generator to produce d. Libraries may support deterministic key derivation from a seed, but each private key must remain secret to prevent private key recovery.

To sign a message, compute e = hash(message) using a secure hash function (e.g., SHA-256). Select a random nonce k ∈ [1, n−1] and compute the curve point R = k · G. Let r = R.x mod n. If r = 0, choose a new k. Compute s = k^−1(e + d·r) mod n. If s = 0, repeat with a new k. The signature is the pair (r, s). The randomness of k is critical: reusing k across signatures leaks d via simple algebraic relations, enabling private key recovery.

To verify a signature (r, s) on a message, check that r and s are in [1, n−1]. Compute e = hash(message). Compute w = s^−1 mod n, u1 = e·w mod n, u2 = r·w mod n. Compute the point X = u1·G + u2·Q. The signature is valid if X ≠ ∞ and X.x mod n = r. This operation uses elliptic curve point addition and multiplication, which are efficient on modern CPUs and hardware accelerators.

ECDSA’s security depends on the unpredictability of the nonce k. Deterministic ECDSA (RFC 6979) derives k from the private key and message hash, eliminating reliance on external RNG. Side-channel attacks on nonce generation or scalar multiplication can leak private key bits, so constant-time implementations and blinding techniques are recommended. Curve selection matters: some curves have known vulnerabilities or suboptimal parameters—use well-vetted curves like P-256, P-384, or those from the Brainpool or Curve25519 families when appropriate.

ECDSA signing is generally faster than RSA signing for equivalent security, due to smaller key sizes and fewer exponentiation operations. Verification may be slightly slower than signing, but still far faster than RSA public-key operations. Typical benchmarks on 64-bit hardware show thousands of ECDSA signature operations per second at P-256. Hardware support (e.g., ARM CryptoCell, Intel QAT) further accelerates these operations.

ECDSA keys and signatures are encoded in ASN.1 DER or PEM formats in X.509 certificates, JWT tokens, and SSH keys. JSON Web Keys (JWK) represent public keys as JSON objects with “kty”:“EC”, “crv”:“P-256”, and “x”/“y” coordinates base64url-encoded. Key export and import routines must handle coordinate normalization and curve parameters correctly to ensure compatibility across platforms.

ECDSA is used in TLS certificates (ECC-based CA certs), secure messaging protocols (Signal, TLS), blockchain and cryptocurrency transactions (Bitcoin, Ethereum), code signing (Microsoft Authenticode), and JWT authentication flows. Its small key and signature sizes reduce bandwidth and storage requirements, making it ideal for mobile and IoT devices.

– Use deterministic nonce generation (RFC 6979) to avoid RNG failures. – Implement scalar multiplication in constant time, with appropriate blinding. – Choose standardized curves with broad support (P-256, P-384, P-521). – Validate signature parameters (r, s) strictly before cryptographic operations. – Store private keys securely and avoid exposing them to untrusted code.

// Pseudocode for ECDSA signing in JavaScript-like syntax const { privateKey, publicKey } = generateKeyPair({ namedCurve: 'P-256' }); const signature = sign({ key: privateKey, data: message, hash: 'SHA-256', format: 'DER' }); const ok = verify({ key: publicKey, data: message, signature, hash: 'SHA-256', format: 'DER' });