ECDSA sign

The ECDSA signing algorithm (RFC 6979) takes as input a message msg ****+ a private key privKey ****and produces as output a signature, which consists of pair of integers {r, s}. The ECDSA signing algorithm is based on the ElGamal signature scheme and works as follows (with minor simplifications):

  1. Calculate the message hash, using a cryptographic hash function like SHA-256: h = hash(msg)

  2. Generate securely a random number k in the range [1..n-1]

    • In case of deterministic-ECDSA, the value k is HMAC-derived from h + privKey (see RFC 6979)

  3. Calculate the random point R = k * G and take its x-coordinate: r = R.x

  4. Calculate the signature proof: s = kāˆ’1āˆ—(h+rāˆ—privKey)(modn)k^{-1} * (h + r * privKey) \pmod n

    • The modular inverse kāˆ’1(modn)k^{-1} \pmod n is an integer, such that kāˆ—kāˆ’1ā‰”1(modn)k * k^{-1} \equiv 1 \pmod n

  5. Return the signature {r, s}.

The calculated signature {r, s} is a pair of integers, each in the range [1...n-1]. It encodes the random point R = k * G, along with a proof s, confirming that the signer knows the message h and the private key privKey. The proof s is by idea verifiable using the corresponding pubKey.

ECDSA signatures are 2 times longer than the signer's private key for the curve used during the signing process. For example, for 256-bit elliptic curves (like secp256k1) the ECDSA signature is 512 bits (64 bytes) and for 521-bit curves (like secp521r1) the signature is 1042 bits.


Last updated