Public-Private Keys Generation & Signature Verification using ECDSA Algorithm.

Note: This will be series of articles to break down the concept of cryptographic keys and how they are used to sign messages, typed structured data and to verify signatures.

Elliptic Curve Digital Signature Algorithm (ECDSA) is a asymmetric cryptography that is widely used to secure electronic transactions. ECDSA is based on the concept of elliptic curve cryptography, which involves using points on a curve over a finite field to generate cryptographic keys.

The concept of public and private keys is at the heart of asymmetric cryptography and to understand how ECDSA works, it is important to first understand the concepts of private and public keys in public-key cryptography.

To generate the public and private keys for ECDSA, we first select an elliptic curve and a point on that curve called the generator(also known as the base point). The private key is then a random number between 1 and the order of the generator, while the public key is the result of multiplying the base point by the private key using elliptic curve multiplication.

The process of elliptic curve multiplication involves repeatedly adding the base point to itself (in a process called "doubling") and adding it to other points on the curve (in a process called "adding"). This process is similar to traditional modular arithmetic, but with a few key differences that make it more difficult to compute, so main parameters involved in generating keys are:

An elliptic curve is a curve that is defined by an equation of the form y² = x³ + ax + b, where a and b are constants

Q: what are Public-Private keys role in sending and signing messages?

first we need to know different types of cryptographic signatures:

1- eth_sign: it used to be a signing method that allows signing an arbitrary hash, which means it can be used to sign transactions, or any other data, making it a dangerous phishing risk.

But because the geth client changed the behavior of their eth_sign method based on EIP-191 version 0x00similar to personal_sign, It now accepts an arbitrary message, prepends a known message, hashes the result using keccak256 it calculates the signature of the hash (breaks backwards compatibility!).

By adding a prefix 0x19to the message makes the calculated signature recognisable as an Ethereum specific signature. This prevents misuse where a malicious DApp can sign arbitrary data (e.g. transaction) and use the signature to impersonate the victim.

2- eth_signTypedData_v4: is based on EIP-712 version 0x01 and will be discussed in details in another article.

EIP-712

3- personal_sign: is based on EIP-191 version 0x45 explained in details below this article.

personal_signdifferent types of available signatures

EIP-191: Signed Data Standard

It proposes a specification about how to handle signed data in Ethereum contracts, and it has three versions:

1- Version 0x00 : the format for signed_data as follows:

0x19 <1 byte version> 

    ECDSA library from OZ.
    /**
     * @dev Returns an Ethereum Signed Data with intended validator, created from a
     * `validator` and `data` according to the version 0 of EIP-191.
     *
     * See {recover}.
     */
    function toDataWithIntendedValidatorHash(address validator, bytes memory data) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked("\x19\x00", validator, data));
    }

2- Version 0x001 : the format for structured data, which will be discussed in another article.

3- Version 0x45 : same semantics as eth_sign but also accepts the password of the account as last argument. - The private key used to sign the hash is temporary unlocked in the scope of the request. - The format for personal_sign as follows:

0x19 <0x45 (E)>

NB: The E in Ethereum Signed Message refers to the version byte 0x45. The character E is 0x45 in hexadecimal which makes the remainder, thereum Signed Message:\n + len(message), the version-specific data.

Note: the ‘0x19' was originated from \x18Bitcoin signed message:\n, where \x18 is a Bitcoin VarInt (for small numbers, it's just the same as the value) for 24, which is the length of the string "Bitcoin signed message:\n". So, \x19 is the Bitcoin VarInt for the length of the string `Ethereum signed message:\n".

As it turned out, 0x19 is a value that isn't a valid RLP encoded array, which is what all transactions are encoded as, and so EIP-191 was able to retcon it as the version byte.

Resource: you can practice all kinds of signatures using MetaMask Interactive simulation. Just take into consideration allowing eth-sign from advanced settings & that MetaMask kept the old eth_sign method to support existing applications.

let's say Mike wants to send a message to Frank, to do so Mike will need:

And that would relate to the below function from ECDSA Library from Open Zeppelin:

function toEthSignedMessageHash(bytes32 hash) internal pure returns (bytes32 message) {
        // 32 is the length in bytes of hash,
        // enforced by the type signature above
        /// @solidity memory-safe-assembly
        assembly {
            mstore(0x00, "\x19Ethereum Signed Message:\n32")
            mstore(0x1c, hash)
            message := keccak256(0x00, 0x3c)
        }
    }

The breakdown of the function as follows:

Ethereum Signature using ECDSA

Signature consists of {r, s, v} which is 65 bytes long as follows:

If signature is unique(immalleable) then the value for v is 27/28.

ECDSA library from Open Zeppelin in tryRecover function accepts only unique signatures with sin the lower half curve & vis 27 or 28 as follows:

uint256(s) > 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0

ECDSA Sign:

The ECDSA signing algorithm takes as input a message hash + a private key and produces as output a signature, which consists of pair of integers {r, s} The ECDSA signing algorithm works as follows:

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. The proof s is by idea verifiable using the corresponding public Key.

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, corresponding to the signer's private key. The output is boolean value: valid or invalid signature. The ECDSA signature verify algorithm works as follows:

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.

Below is the code snippet of the above tutorial used for signature verification:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

/* Signature Verification

How to Sign and Verify
# Signing
1. Create message to sign
2. Hash the message
3. Sign the hash (off chain, keep your private key secret)

# Verify
1. Recreate hash from the original message
2. Recover signer from signature and hash
3. Compare recovered signer to claimed signer
*/

contract VerifySignature {
    /* 1. Unlock MetaMask account
    ethereum.enable()
    */

    /* 2. Get message hash to sign
    getMessageHash(
        0x14723A09ACff6D2A60DcdF7aA4AFf308FDDC160C,
        123,
        "coffee and donuts",
        1
    )

    hash = "0xcf36ac4f97dc10d91fc2cbb20d718e94a8cbfe0f82eaedc6a4aa38946fb797cd"
    */
    function getMessageHash(
        address _to,
        uint _amount,
        string memory _message,
        uint _nonce
    ) public pure returns (bytes32) {
        return keccak256(abi.encodePacked(_to, _amount, _message, _nonce));
    }

    /* 3. Sign message hash
    # using browser
    account = "copy paste account of signer here"
    ethereum.request({ method: "personal_sign", params: [account, hash]}).then(console.log)

    # using web3
    web3.personal.sign(hash, web3.eth.defaultAccount, console.log)

    Signature will be different for different accounts
    0x993dab3dd91f5c6dc28e17439be475478f5635c92a56e17e82349d3fb2f166196f466c0b4e0c146f285204f0dcb13e5ae67bc33f4b888ec32dfe0a063e8f3f781b
    */
    function getEthSignedMessageHash(
        bytes32 _messageHash
    ) public pure returns (bytes32) {
        /*
        Signature is produced by signing a keccak256 hash with the following format:
        "\x19Ethereum Signed Message\n" + len(msg) + msg
        */
        return
            keccak256(
                abi.encodePacked("\x19Ethereum Signed Message:\n32", _messageHash)
            );
    }

    /* 4. Verify signature
    signer = 0xB273216C05A8c0D4F0a4Dd0d7Bae1D2EfFE636dd
    to = 0x14723A09ACff6D2A60DcdF7aA4AFf308FDDC160C
    amount = 123
    message = "coffee and donuts"
    nonce = 1
    signature =
        0x993dab3dd91f5c6dc28e17439be475478f5635c92a56e17e82349d3fb2f166196f466c0b4e0c146f285204f0dcb13e5ae67bc33f4b888ec32dfe0a063e8f3f781b
    */
    function verify(
        address _signer,
        address _to,
        uint _amount,
        string memory _message,
        uint _nonce,
        bytes memory signature
    ) public pure returns (bool) {
        bytes32 messageHash = getMessageHash(_to, _amount, _message, _nonce);
        bytes32 ethSignedMessageHash = getEthSignedMessageHash(messageHash);

        return recoverSigner(ethSignedMessageHash, signature) == _signer;
    }

    function recoverSigner(
        bytes32 _ethSignedMessageHash,
        bytes memory _signature
    ) public pure returns (address) {
        (bytes32 r, bytes32 s, uint8 v) = splitSignature(_signature);

        return ecrecover(_ethSignedMessageHash, v, r, s);
    }

    function splitSignature(
        bytes memory sig
    ) public pure returns (bytes32 r, bytes32 s, uint8 v) {
        require(sig.length == 65, "invalid signature length");

        assembly {
            /*
            First 32 bytes stores the length of the signature

            add(sig, 32) = pointer of sig + 32
            effectively, skips first 32 bytes of signature

            mload(p) loads next 32 bytes starting at the memory address p into memory
            */

            // first 32 bytes, after the length prefix
            r := mload(add(sig, 32))
            // second 32 bytes
            s := mload(add(sig, 64))
            // final byte (first byte of the next 32 bytes)
            v := byte(0, mload(add(sig, 96)))
        }

        // implicitly return (r, s, v)
    }
}

Q: Is it possible for anyone to reveal the private key if nonce used in signature is known?

The answer is yes, even if your private key hasn't been breached & you kept it safe all the time. Since your public key is known on the blockchain & shareable and since the nonce generated when signing the message is known "which shouldn't" it's possible to crackdown the private key.

It's extremely important that you don't store your nonce every time you sign a message or a transaction.

References: