# 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` ](https://github.com/richardkiss/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:

```python
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**:

```python
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**](https://tools.ietf.org/html/rfc6979).

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:

```python
# 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:

```python
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:

```python
pip install eth_keys
```

The [**eth\_keys**](https://github.com/ethereum/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:

```python
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!