ECDSA: Elliptic Curve Signatures

原文链接：https://www.yuque.com/yangguangfanxing/zuyi8o/dl80bgzfgfdocs4d

The ECDSA (Elliptic Curve Digital Signature Algorithm) is a cryptographically secure digital signature scheme, based on the elliptic-curve cryptography (ECC). ECDSA relies on the math of the cyclic groups of elliptic curves over finite fields and on the difficulty of the ECDLP problem (elliptic-curve discrete logarithm problem). The ECDSA sign / verify algorithm relies on EC point multiplication and works as described below. ECDSA keys and signatures are shorter than in RSA for the same security level. A 256-bit ECDSA signature has the same security strength like 3072-bit RSA signature.

ECDSA uses cryptographicelliptic curves(EC) over finite fields in the classical Weierstrass form. These curves are described by their EC domain parameters, specified by various cryptographic standards such as SECG: SEC 2 and Brainpool (RFC 5639). Elliptic curves, used in cryptography, define:

• Generator point G, used for scalar multiplication on the curve (multiply integer by EC point)
• Order n of the subgroup of EC points, generated by G, which defines the length of the private keys (e.g. 256 bits)

For example, the 256-bit elliptic curve secp256k1 has:

• Order n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 (prime number)
• Generator point G {x = 55066263022277343669578718895168534326250603453777594175500187360389116729240, y = 32670510020758816978083085130507043184471273380659243275938904335757337482424}

Key Generation

The ECDSA key-pair consists of:

• private key (integer): privKey
• public key (EC point): pubKey = privKey * G

The private key is generated as a random integer in the range [0...n-1]. The public key pubKey is a point on the elliptic curve, calculated by the EC point multiplication: pubKey = privKey * G (the private key, multiplied by the generator point G).

The public key EC point {x, y} can be compressed to just one of the coordinates + 1 bit (parity). For the secp256k1 curve, the private key is 256-bit integer (32 bytes) and the compressed public key is 257-bit integer (~ 33 bytes).

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

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

1. Calculate the random point R = k * G and take its x-coordinate: r = R.x
2. Calculate the signature proof:

• The modular inverse is an integer, such that

1. Return the signature {r, s}.

The calculated signature {r, s} is a pair of integers, each in the range . 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.

ECDSA Verify Signature

The algorithm to verify a ECDSA signature takes as input the signed message msg + the signature {r, s} produced from the signing algorithm + the public key pubKey, corresponding to the signer's private key. The output is boolean value: valid or invalid signature. The ECDSA signature verify algorithm works as follows (with minor simplifications):

1. Calculate the message hash, with the same cryptographic hash function used during the signing: h = hash(msg)
2. Calculate the modular inverse of the signature proof:
3. Recover the random point used during the signing: R' = (h * s1) * G + (r * s1) * pubKey
4. Take from R' its x-coordinate: r' = R'.x
5. Calculate the signature validation result by comparing whether r' == r

The general idea of the signature verification is to recover the point R' using the public key and check whether it is same point R, generated randomly during the signing process.

How Does it Work?

The ECDSA signature {r, s} has the following simple explanation:

• The signing signing encodes a random point R (represented by its x-coordinate only) through elliptic-curve transformations using the private key privKey and the message hash h into a number s, which is the proof that the message signer knows the private key privKey. The signature {r, s} cannot reveal the private key due to the difficulty of the ECDLP problem.
• The signature verification decodes the proof number s from the signature back to its original point R, using the public key pubKey and the message hash h and compares the x-coordinate of the recovered R with the r value from the signature.

The Math behind the ECDSA Sign / Verify

Read this section only if you like math. Most developer may skip it.

How does the above sign / verify scheme work? It is not obvious, but let's play a bit with the equations.

The equation behind the recovering of the point R', calculated during the signature verification, can be transformed by replacing the pubKey with privKey * G as follows:

R' =

=

=

If we take the number s = , calculated during the signing process, we can calculate s1 =

like this:

s1 =

=

=

Now, replace s1 in the point R'.

R' =

=

=

The final step is to compare the point R' (decoded by the pubKey) with the point R (encoded by the privKey). The algorithm in fact compares only the x-coordinates of R' and R: the integers r' and r.

It is expected that r' == r if the signature is valid and r' ≠ r if the signature or the message or the public key is incorrect.

ECDSA: Public Key Recovery from Signature

It is important to know that the ECDSA signature scheme allows the public key to be recovered from the signed message together with the signature. The recovery process is based on some mathematical computations (described in the SECG: SEC 1 standard) and returns 0, 1 or 2 possible EC points that are valid public keys, corresponding to the signature. To avoid this ambiguity, some ECDSA implementations add one additional bit v to the signature during the signing process and it takes the form {r, s, v}. From this extended ECDSA signature {r, s, v} + the signed message, the signer's public key can be restored with confidence.

The public key recovery from the ECDSA signature is very useful in bandwidth constrained or storage constrained environments (such as blockchain systems), when transmission or storage of the public keys cannot be afforded. For example, the Ethereum blockchain uses extended signatures {r, s, v} for the signed transactions on the chain to save storage and bandwidth.

Public key recovery is possible for signatures, based on the ElGamal signature scheme (such as DSA and ECDSA).

ECDSA: Sign / Verify - Examples

After we explained in details how the ECDSA signature algorithm works, now let's demonstrate it in practice with code examples.

In this example, we shall use the pycoin Python package, which implements the ECDSA signature algorithm with the curve secp256k1 (used in the Bitcoin cryptography), as well as many other functionalities related to the Bitcoin blockchain:

pip install pycoin

ECDSA Sign / Verify using the secp256k1 Curve and SHA3-256

First, define the functions for hashing, ECDSA signing and ECDSA signature verification:

from pycoin.ecdsa import generator_secp256k1, sign, verify
import hashlib, secrets

def sha3_256Hash(msg):
    hashBytes = hashlib.sha3_256(msg.encode("utf8")).digest()
    return int.from_bytes(hashBytes, byteorder="big")

def signECDSAsecp256k1(msg, privKey):
    msgHash = sha3_256Hash(msg)
    signature = sign(generator_secp256k1, privKey, msgHash)
    return signature

def verifyECDSAsecp256k1(msg, signature, pubKey):
    msgHash = sha3_256Hash(msg)
    valid = verify(generator_secp256k1, pubKey, msgHash, signature)
    return valid

The hashing function sha3_256Hash(msg) computes and returns a SHA3-256 hash, represented as 256-bit integer number. It will be used in the sign / verify processes later.

The signECDSAsecp256k1(msg, privKey) function takes a text message and 256-bit secp256k1 private key and calculates the ECDSA signature {r, s} and returns it as pair of 256-bit integers. The ECDSA signature, generated by the pycoin library by default is deterministic, as described in RFC 6979.

The verifyECDSAsecp256k1(msg, signature, pubKey) function takes a text message, a ECDSA signature {r, s} and a 2*256-bit ECDSA public key (uncompressed) and returns whether the signature is valid or not.

Now let's demonstrate the above defined functions to sign a message and verify its signature:

# ECDSA sign message (using the curve secp256k1 + SHA3-256)
msg = "Message for ECDSA signing"
privKey = secrets.randbelow(generator_secp256k1.order())
signature = signECDSAsecp256k1(msg, privKey)
print("Message:", msg)
print("Private key:", hex(privKey))
print("Signature: r=" + hex(signature[0]) + ", s=" + hex(signature[1]))

# ECDSA verify signature (using the curve secp256k1 + SHA3-256)
pubKey = (generator_secp256k1 * privKey).pair()
valid = verifyECDSAsecp256k1(msg, signature, pubKey)
print("\nMessage:", msg)
print("Public key: (" + hex(pubKey[0]) + ", " + hex(pubKey[1]) + ")")
print("Signature valid?", valid)

# ECDSA verify tampered signature (using the curve secp256k1 + SHA3-256)
msg = "Tampered message"
valid = verifyECDSAsecp256k1(msg, signature, pubKey)
print("\nMessage:", msg)
print("Signature (tampered msg) valid?", valid)

Run the above code example: https://repl.it/@nakov/ECDSA-sign-verify-in-Python.

The output from the above code is like this:

Message: Message for ECDSA signing
Private key: 0x79afbf7147841fca72b45a1978dd7669470ba67abbe5c220062924380c9c364b
Signature: r=0xb83380f6e1d09411ebf49afd1a95c738686bfb2b0fe2391134f4ae3d6d77b78a, s=0x6c305afcac930a3ea1721c04d8a1a979016baae011319746323a756fbaee1811
Message: Message for ECDSA signing
Public key: (0x3804a19f2437f7bba4fcfbc194379e43e514aa98073db3528ccdbdb642e240, 0x6b22d833b9a502b0e10e58aac485aa357bccd1df6ec0fa4d398908c1ac1920bc)
Signature valid? True
Message: Tampered message
Signature (tampered msg) valid? False

As it is visible from the above output, the random generated secp256k1 private key is 64 hex digits (256 bits). After signing, the obtained signature {r, s} consists of 2 * 256-bit integers. The public key, obtained by multiplying the private key by the curve generator point, consists of 2 * 256 bits (uncompressed). The produced ECDSA digital signature verifies correctly after signing. If the message is tampered, the signature fails to verify.

Public Key Recovery from the ECDSA Signature

As we already know, in ECDSA it is possible to recover the public key from signature. Let's demonstrate this by adding the following code at the end of the previous example:

from pycoin.ecdsa import possible_public_pairs_for_signature

def recoverPubKeyFromSignature(msg, signature):
    msgHash = sha3_256Hash(msg)
    recoveredPubKeys = possible_public_pairs_for_signature(
        generator_secp256k1, msgHash, signature)
    return recoveredPubKeys

msg = "Message for ECDSA signing"
recoveredPubKeys = recoverPubKeyFromSignature(msg, signature)
print("\nMessage:", msg)
print("Signature: r=" + hex(signature[0]) + ", s=" + hex(signature[1]))
for pk in recoveredPubKeys:
    print("Recovered public key from signature: (" +
          hex(pk[0]) + ", " + hex(pk[1]) + ")")

Run the above code example: https://repl.it/@nakov/ECDSA-public-key-recovery-in-Python.

The above code recovers the all possible EC public keys from the ECDSA signature + the signed message, using the algorithm, described in http://www.secg.org/sec1-v2.pdf. Note that multiple EC public keys (0, 1 or 2) may match the message + signature. The expected output from the above code (together with the previous code) looks like this:

Message: Message for ECDSA signing
Private key: 0xc374556584db050001c2c9265b546e66d3dbbe8239d17427c176d834a19638dc
Signature: r=0xd034c98af3274ad93f3c8ce944bbc17b11b6aa170c5f097ed98687fa0d93347c, s=0xa2318ceea2002caba38efbba3bf8ef8d43236a6edc33c040734d8eb2ed77f608
Message: Message for ECDSA signing
Public key: (0x10b5d9028ec828a0f9111e36f046afa5a0c677357351093426bcec10c663db7d, 0x271763c56fcd87b72d59ceaa5b9c3fd2122788fe344751a9bde373f903e5bb20)
Signature valid? True
Message: Tampered message
Signature (tampered msg) valid? False
Message: Message for ECDSA signing
Signature: r=0xd034c98af3274ad93f3c8ce944bbc17b11b6aa170c5f097ed98687fa0d93347c, s=0xa2318ceea2002caba38efbba3bf8ef8d43236a6edc33c040734d8eb2ed77f608
Recovered public key from signature: (0x1353fd26a6cb6110980cfd2bb5eca3b3cc3e08c930ad5991395dd826a250c79, 0xba6825142e230ee1fa2b406f3f9158a47ee49daca8ac47898c5fd92d805a101e)
Recovered public key from signature: (0x10b5d9028ec828a0f9111e36f046afa5a0c677357351093426bcec10c663db7d, 0x271763c56fcd87b72d59ceaa5b9c3fd2122788fe344751a9bde373f903e5bb20)

It is obvious that the recovered possible public keys are 2: one is equal to the public key, matching the signer's private key, and the other is not (it matches the math behind the public key recovery, but is not the correct one). To avoid this ambiguity, the signature can be extended to hold {r, s, v}, where v holds the parity of the y coordinate of the random point R from the ECDSA signing algorithm. This coordinate is lost, because the ECDSA signature takes just the x coordinate or R.

Public Key Recovery from Extended ECDSA Signature

To recover with confidence the public key from ECDSA signature + message, we need a library that generates extended ECDSA signatures {r, s, v} and supports internally the public key recovery. Let's play with the eth_keys Python library:

pip install eth_keys

The eth_keys is part of the Ethereum project and implements secp256k1-based ECC cryptography, private and public keys, ECDSA extended signatures {r, s, v} and Ethereum blockchain addresses. The following example demonstrates private key generation, message signing, public key recovery from signature + message and signature verification:

import eth_keys, os

# Generate the private + public key pair (using the secp256k1 curve)
signerPrivKey = eth_keys.keys.PrivateKey(os.urandom(32))
signerPubKey = signerPrivKey.public_key
print('Private key (64 hex digits):', signerPrivKey)
print('Public key (uncompressed, 128 hex digits):', signerPubKey)

# ECDSA sign message (using the curve secp256k1 + Keccak-256)
msg = b'Message for signing'
signature = signerPrivKey.sign_msg(msg)
print('Message:', msg)
print('Signature: [r = {0}, s = {1}, v = {2}]'.format(
    hex(signature.r), hex(signature.s), hex(signature.v)))

# ECDSA public key recovery from signature + verify signature
# (using the curve secp256k1 + Keccak-256 hash)
msg = b'Message for signing'
recoveredPubKey = signature.recover_public_key_from_msg(msg)
print('Recovered public key (128 hex digits):', recoveredPubKey)
print('Public key correct?', recoveredPubKey == signerPubKey)
valid = signerPubKey.verify_msg(msg, signature)
print("Signature valid?", valid)

Run the above code example: https://repl.it/@nakov/ECDSA-public-key-recovery-extended-in-Python.

The output from the above code looks like this:

Private key (64 hex digits): 0x68abc765746a33272e47b0a96a0b4184048f70354221e04219fbc223bfe79794
Public key (uncompressed, 128 hex digits): 0x30a6dc572da312587144e7ccda1e9abd901323adebe7091bb4985e1202c2a10bc25f681b3d2e1a671438f0b125287b473c09ca345c5583cd627232b536b9ca0a
Message: b'Message for signing'
Signature: [r = 0x4cddf146c578d20a31fa6128e5d9afe6ac666e5ef5899f2767cacb56a42703cc, s = 0x3847036857aa3f077a2e142eee707e5af2653baa99b9d10764a0be3d61595dbb, v = 0x0]
Recovered public key (128 hex digits): 0x30a6dc572da312587144e7ccda1e9abd901323adebe7091bb4985e1202c2a10bc25f681b3d2e1a671438f0b125287b473c09ca345c5583cd627232b536b9ca0a
Public key correct? True
Signature valid? True

The public key recovery will always be successful, because there is no ambiguity with the extended ECDSA signature. The signature verification will be successful, unless the message, the public key or the signature is tampered. You are free to play with the above code, to change it, to tamper the signed message and to see what happens. Enjoy!