ECDSA is a cryptographic algorithm used to create digital signatures, providing authenticity, integrity, and non-repudiation for digital messages and transactions.
Let’s see it in action with a simplified example. Imagine Alice wants to send a message to Bob, and she wants Bob to be sure it came from her and hasn’t been tampered with.
First, Alice needs a pair of keys: a private key (which she keeps secret) and a public key (which she can share with anyone, like Bob).
# Using a hypothetical cryptography library
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives.asymmetric.utils import encode_dss_signature
from cryptography.exceptions import InvalidSignature
# Alice generates her keys
private_key = ec.generate_private_key(ec.SECP256k1()) # Using the secp256k1 curve, popular in cryptocurrencies
public_key = private_key.public_key()
# Alice's message
message = b"Hello Bob, this is an important message."
# 1. Hashing the message
# A hash is a fixed-size fingerprint of the message.
digest = hashes.Hash(hashes.SHA256())
digest.update(message)
h = digest.finalize() # h is the message digest
# 2. Signing the hash with her private key
# This is where ECDSA comes in. It uses the private key and the message hash
# to produce a unique signature. The signature consists of two numbers, 'r' and 's'.
signature = private_key.sign(
h,
ec.ECDSA(hashes.SHA256()) # Specifies the signing algorithm and hash function
)
# Alice sends the message and the signature to Bob
# Bob receives the message and the signature. He also needs Alice's public key.
# 3. Verifying the signature with Alice's public key
# Bob hashes the received message himself to get the same digest 'h'.
received_digest = hashes.Hash(hashes.SHA256())
received_digest.update(message) # Using the *received* message
received_h = received_digest.finalize()
# Now, Bob uses Alice's public key to verify the signature against the received message's hash.
try:
public_key.verify(
signature,
received_h, # Bob verifies against the hash of the message he received
ec.ECDSA(hashes.SHA256())
)
print("Signature is valid! The message is authentic and has not been tampered with.")
except InvalidSignature:
print("Signature is invalid! The message may have been altered or is not from Alice.")
The core idea is that only Alice, with her private key, can create a signature that her public key can successfully verify. If anyone tries to alter the message, the hash will change, and the signature verification will fail. If someone tries to forge a signature without Alice’s private key, they won’t be able to generate the correct r and s values that match Alice’s public key and the message hash.
This process solves the problem of trust in digital communication. Without digital signatures, you’d have no way to know if the message you received is actually from the sender it claims to be, or if it’s been altered along the way.
Internally, ECDSA leverages the mathematical properties of elliptic curves. An elliptic curve is a specific type of smooth, non-intersecting curve defined by an equation like y^2 = x^3 + ax + b. For ECDSA, a specific curve and a base point G on that curve are chosen.
Alice’s private key is a large random integer, let’s call it d. Her public key Q is calculated by multiplying the base point G by her private key d on the elliptic curve: Q = d * G. This multiplication is a form of scalar multiplication on the curve. The critical mathematical property here is that it’s easy to compute Q given d and G, but computationally infeasible to find d given Q and G. This is the "elliptic curve discrete logarithm problem" (ECDLP), which forms the basis of ECDSA’s security.
When signing, the algorithm takes the message hash h and uses d and h to generate the signature pair (r, s). The verification process uses Q (Alice’s public key) and h to check if the signature (r, s) is valid. The calculations involve points on the elliptic curve and modular arithmetic.
The choice of elliptic curve matters significantly. Different curves offer varying levels of security for a given key size. For example, SECP256k1 (used in Bitcoin) and NIST P-256 are common choices. The parameters of these curves (like the coefficients a and b, the field size, and the base point G) are standardized.
The specific calculations for signing involve generating a random ephemeral key k for each signature, calculating r based on k and the curve’s parameters, and then calculating s using h, d, r, and k. Verification then reverses these steps using Q instead of d. The ephemeral key k is crucial; using the same k twice would leak the private key d.
What most people miss is that the signature is not a direct encryption of the hash. Instead, it’s a complex mathematical relationship derived from the hash and the private key, expressed as points on an elliptic curve. The verification process essentially checks if the provided signature (r, s) is consistent with the public key Q and the message hash h on that specific elliptic curve. It’s not about decrypting anything; it’s about proving that the signer possessed the private key corresponding to the public key used for verification.
The next step is understanding how these signatures are used in practice, particularly in distributed systems like blockchains, and the implications of different elliptic curve choices.