Message signing

From Bitcoin Wiki
(Redirected from Signed Message)
Jump to navigation Jump to search

Message signing is the action of signing a cryptographic message using a private key and its associated address, to prove that you have access to the address. These messages can be verified by wallets by checking the signature against the address to see if they correspond to each other. The result of message signing is often called a signed message.

Bitcoin signed messages have three parts, which are the Message, Address, and Signature. The message is the actual message text - all kinds of text is supported, but it is recommended to avoid using non-ASCII characters in the signature because they might be encoded in different character sets, preventing signature verification from succeeding.

The address is a legacy, nested segwit, or native segwit address. Message signing from legacy addresses was added by Satoshi himself and therefore does not have a BIP. Message signing from segwit addresses has been added by BIP137[1].

The Signature is a base64-encoded ECDSA signature that, when decoded, with fields described in the next section.

As of this writing, there is no message signing support for Taproot addresses. Not only do they use a different signing algorithm in the form of Schnorr, but public key recovery is not possible with Schnorr signatures, so they cannot be compared to addresses.


Displaying signed messages

Two formats are available to display and process the signed message:

  1. Bitcoin-QT format, where the Message, Address, and Signature are displayed and processed separately. (It is named Bitcoin-QT for legacy reasons.)
  2. RFC2440-like format, which will be described below.

The RFC2440-like format has the following structure, where Message, Address, and Signature are as defined at the beginning of this section:

BEGIN BITCOIN SIGNED MESSAGE-----

Message

BEGIN BITCOIN SIGNATURE-----

Address Signature

END BITCOIN SIGNATURE-----

The text must begin with "-----BEGIN BITCOIN SIGNED MESSAGE-----", including the 5 ASCII dashes on both the beginning and end of the line, followed by the Message, followed by "-----BEGIN BITCOIN SIGNATURE-----" along with the dashes similarly, followed by the Address, followed by the Signature, followed by "-----END BITCOIN SIGNATURE-----" with the dashes. All components must be separated by a newline (CRLF, LF, or CR).

Detailed specification of the message signature

ECDSA signatures generate a 32-byte r-value and a 32-byte s-value (see Elliptic Curve Digital Signature Algorithm), which collectively represent the signature. Bitcoin signatures have the r and s values mentioned above, and a 1-byte header. Therefore, the size of a signature is 65 bytes.

The header is used to specify information about the signature. It can be thought of as a bitmask with each bit in this byte having a meaning. The serialization format of a Bitcoin signature is as follows:

(1 byte for header data)(32 bytes for r-value)(32 bytes for s-value)

The header byte has a few components to it. First, it stores something known as the recID. This value is stored in the least significant 2 bits of the header, and uniquely identifies the correct signature for the signing public key. The lower bit represents the parity of the Y coordinate of the signature - even or odd - and the higher bit represents the correct r-value: 'r' or 'n+r'. For a rare subset of signatures which have r>=p-n, the only possible r-value will be 'r', thus the highest bit of the recID should be zero.

The following list demonstrates the correct signature corresponding to the value of recID:

  • 0: even Y, r = r
  • 1: odd Y, r = r
  • 2: even Y, r = n+r
  • 3: odd Y, r = n+r

The remaining bytes of the header format must be read together to fetch the correct address format. The original message signing format by Satoshi defined the following ranges for address types:

  • Header byte is 27-30: P2PKH uncompressed
  • Header byte is 31-34: P2PKH compressed

BIP137 additionally defines the following ranges for compressed segwit address types:

  • Header byte is 35-38: P2WPKH-P2SH compressed
  • Header byte is 39-42: P2WPKH compressed


Algorithm for signing and verifying messages

Below is a list of instructions for creating a BIP137-compliant message signing and verification algorithm.

It is not required, but you should strip trailing newlines from the message before signing it, because some clients cannot process messages that contain trailing newlines.

Below is a list of steps for signing and verifying a message, for each supported address type.


Definitions used in the algorithms

Modulo is written as mod, for example x modulo n is written as x mod n.

Byte concatenation is written as || and implies that both operands shall be cast to byte arrays before concatenation.

Array subscripting for byte arrays is written as x[i:j] and should be interpreted to create a copy of the byte array x of length (j-i) with the i-th byte as the first byte and the (j-1)-th byte as the last byte (i ≥ 0, j ≥ 0).

Floor division is written as / and involves truncating the floating-point remainder from the division result.

Modular inverse is written as modinv(x,n), where n is a constant, variable, or expression, and is equivalent to x^-1 mod p.

Modular exponentiation is written as x^n where n is a constant, variable, or expression, and does not include modulus. The modulus must be explicitly specified using mod eg. x^2 mod n.

Bitwise AND is written as AND.

Bitwise XOR is written as XOR.

Hexadecimal byte arrays are represented as hex(byte sequence), where the byte sequence consists of sequences of two hexadecimal characters which may or may not be separated by space (for example hex(01 02) and hex(0102) both generate the byte array identical to the evaluation of '\x01\x02' in the C programming language). There is no leading '0x' or '0X' in the output.

Cast from byte array or byte sequence to 256-bit integer is represented as int(x).

Cast from string or 256-bit integer to byte array is represented as bytes(x).

Construction of a point with an x-coordinate x and y-coordinate y is represented as (x, y) and implies that both x and y will be cast to integers before point construction.

For a point P, its x-coordinate is represented as P.x, and its y-coordinate is represented as P.y. All coordinates have

Test for whether a y-coordinate of a point is even is written has is_even(y) for integers. is_even(P) is equivalent to is_even(P.y). This function is identical to computing y AND 1 == 0 or y mod 2 == 0, because odd numbers represent negative Y coordinates, which is the actual basis for even/odd classification.

For brevity, is_odd(P) and is_odd(P.y) is equivalent to !is_even(P) and !is_even(y) respectively.

UTF-8 strings are represented as "text", where text is the desired text. It should be noted that all string constants in this document contain only ASCII characters.

Constants

The constant Inf shall refer to the point at infinity, of the secp256k1 curve.

The constant p shall refer to the secp256k1 field size, aka. curve characteristic, defined as int(FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F)

The constant n shall refer to the secp256k1 curve order, defined as int(FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141)

The constant G shall refer to the secp256k1 generator point, defined as (79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798, 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8)

Message signing method

It takes the following parameters:

  • The private key (PrivateKey)
  • The public key (PublicKey) (optional, if performance is desired)
  • The address (Address)
  • The message (Message)

ECDSA signing, with P2PKH uncompressed addresses

  1. Compute z = SHA256(Message)
  2. Generate a cryptographically secure random nonce k between 1 and n-1. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's 0 or ≥ n), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce.
  3. Compute (x,y) = G*k
  4. If r mod n == 0 or (x,y) == Inf, go back to step 3.
  5. Compute s = modinv(k) * (z + r * PrivateKey) mod n. If s == 0, go back to step 3.
  6. Compute the header byte. If r < p-n and is_even(y), set HeaderByte to 30. If r < p-n and is_odd(y), set HeaderByte to 27. If r ≥ p-n and is_even(y), set HeaderByte to 28. If r ≥ p-n and is_odd(y), set HeaderByte to 29.
  7. Compute Signature=Base64Encode(HeaderByte || r || s)

ECDSA signing, with P2PKH compressed addresses

  1. Compute z = SHA256(Message)
  2. Generate a cryptographically secure random nonce k between 1 and n-1. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's 0 or ≥ n), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce.
  3. Compute (x,y) = G*k
  4. If r mod n == 0 or (x,y) == Inf, go back to step 3.
  5. Compute s = modinv(k, n) * (z + r * PrivateKey) mod n. If s == 0, go back to step 3.
  6. Compute the header byte. If r < p-n and is_even(y), set HeaderByte to 34. If r < p-n and is_odd(y), set HeaderByte to 31. If r ≥ p-n and is_even(y), set HeaderByte to 32. If r ≥ p-n and is_odd(y), set HeaderByte to 31.
  7. Compute Signature=Base64Encode(HeaderByte || r || s)

ECDSA signing, with P2WPKH-P2SH compressed addresses

  1. Compute z = SHA256(Message)
  2. Generate a cryptographically secure random nonce k between 1 and n-1. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's 0 or ≥ n), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce.
  3. Compute (x,y) = G*k
  4. If r mod n == 0 or (x,y) == Inf, go back to step 3.
  5. Compute s = modinv(k, n) * (z + r * PrivateKey) mod n. If s == 0, go back to step 3.
  6. Compute the header byte. If r < p-n and is_even(y), set HeaderByte to 38. If r < p-n and is_odd(y), set HeaderByte to 35. If r ≥ p-n and is_even(y), set HeaderByte to 36. If r ≥ p-n and is_odd(y), set HeaderByte to 37.
  7. Compute Signature=Base64Encode(HeaderByte || r || s)

ECDSA signing, with P2WPKH compressed addresses

  1. Compute z = SHA256(Message)
  2. Generate a cryptographically secure random nonce k between 1 and n-1. This can be implemented by generating four 64-bit random unsigned integers. If the resulting integer is out of range (e.g. it's 0 or ≥ n), then discard the entire nonce and generate its entirety all over again. This is to avoid attacks on specific parts of the nonce.
  3. Compute (x,y) = G*k
  4. If r mod n == 0 or (x,y) == Inf, go back to step 3.
  5. Compute s = modinv(k, n) * (z + r * PrivateKey) mod n. If s == 0, go back to step 3.
  6. Compute the header byte. If r < p-n and is_even(y), set HeaderByte to 42. If r < p-n and is_odd(y), set HeaderByte to 39. If r ≥ p-n and is_even(y), set HeaderByte to 40. If r ≥ p-n and is_odd(y), set HeaderByte to 41.
  7. Compute Signature=Base64Encode(HeaderByte || r || s)


Message verification method

It takes the following parameters:

  • The message (Message)
  • The address (Address)
  • An ECDSA signature (Signature)

The Header byte in the signature shall dictate the verification algorithm that is used.

Upon verification success, you should display a status message similar to: "Genuine signed message from address <Address>".

Preliminary steps for all verification Algorithms

  1. Set DecodedSignature = Base64Decode(Signature)
  2. Set HeaderByte = DecodedSignature[0]
    • If HeaderByte is between 27 and 30 inclusive, use "ECDSA verification, P2PKH uncompressed address".
    • Else, if HeaderByte is between 31 and 34 inclusive, use "ECDSA verification, P2PKH compressed address".
    • Else, if HeaderByte is between 35 and 38 inclusive, use "ECDSA verification, P2WPKH-P2SH compressed address".
    • Else, if HeaderByte is between 39 and 42 inclusive, use "ECDSA verification, P2WPKH compressed address".
    • Else, if HeaderByte is between 43 and 46 inclusive, use "Schnorr verification, P2TR (Taproot) compressed address".
    • Else, fail verification with an error similar to "Unknown signature type".

ECDSA verification, P2PKH uncompressed address

  1. Set r = DecodedSignature[1:33]. If r ≥ n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  2. Set s = DecodedSignature[33:65]. If s ≥ n or s == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  3. Set z = SHA256(Message)
  4. Set recID = Header AND 0x3
  5. If recID AND 0x2 == 0, set x = r, else set x = r+n
  6. Set x = (x^3 + 7) mod p
  7. Set y = x^((p+1)/4) mod p
  8. Calculate the correct parity of y using the 'recID':
    • If (is_even(beta) and is_odd(recID)) or (is_odd(beta) and is_even(recID)), set y = p-y.
  9. Set R = (x,y)
  10. Set e = (-int(z)) % n
  11. Set PublicKey = (R*s + G*e) * modinv(r, n)
  12. Compute EncodedPublicKey = "04" || hex(x) || hex(y)
  13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
  14. Compute DerivedAddress = Base58Check(hex(00) || AddressHash).
  15. If DerivedAddress == Address, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

ECDSA verification, P2PKH compressed address

  1. Set r = DecodedSignature[1:33]. If r ≥ n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  2. Set s = DecodedSignature[33:65]. If s ≥ n or s == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  3. Set z = SHA256(Message)
  4. Set recID = Header AND 0x3
  5. If recID AND 0x2 == 0, set x = r, else set x = r+n.
  6. Set x = (x^3 + 7) mod p
  7. Set y = x^((p+1)/4) mod p
  8. Calculate the correct parity of y using the 'recID':
    • If (is_even(beta) and is_odd(recID)) or (is_odd(beta) and is_even(recID)), set y = p-y.
  9. Set R = (x,y)
  10. Set e = (-int(z)) % n
  11. Set PublicKey = (R*s + G*e) * modinv(r, n)
  12. If is_even(y), compute EncodedPublicKey = "02" || hex(x). Else, compute EncodedPublicKey = "03" || hex(x)
  13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
  14. Compute DerivedAddress = Base58Check(hex(00) || AddressHash)
  15. If DerivedAddress == Address, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

ECDSA verification, P2WPKH-P2SH compressed address

  1. Set r = DecodedSignature[1:33]. If r ≥ n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  2. Set s = DecodedSignature[33:65]. If s ≥ n or s == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  3. Set z = SHA256(Message)
  4. Set recID = Header AND 0x3
  5. If recID AND 0x2 == 0, set x = r, else set x = r+n.
  6. Set x = (x^3 + 7) mod p
  7. Set y = x^((p+1)/4) mod p
  8. Calculate the correct parity of y using the 'recID':
    • If (is_even(beta) and is_odd(recID)) or (is_odd(beta) and is_even(recID)), set y = p-y.
  9. Set R = (x,y)
  10. Set e = (-int(z)) % n
  11. Set PublicKey = (R*s + G*e) * modinv(r, n)
  12. If is_even(y), compute EncodedPublicKey = "02" || hex(x). Else, compute EncodedPublicKey = "03" || hex(x)
  13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
  14. Compute RedeemScript = hex(00 14) || AddressHash
  15. Compute RedeemScriptHash = RIPEMD160(SHA256(RedeemScript))
  16. Compute DerivedAddress = Base58Check(hex(05) || RedeemScriptHash)
  17. If DerivedAddress == Address, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

ECDSA verification, P2WPKH compressed address

  1. Set r = DecodedSignature[1:33]. If r ≥ n or r == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  2. Set s = DecodedSignature[33:65]. If s ≥ n or s == 0, fail verification with an error similar to "Invalid ECDSA signature parameters".
  3. Set z = SHA256(Message)
  4. Set recID = Header AND 0x3
  5. If recID AND 0x2 == 0, set x = r, else set x = r+n.
  6. Set x = (x^3 + 7) mod p
  7. Set y = x^((p+1)/4) mod p
  8. Calculate the correct parity of y using the 'recID':
    • If (is_even(beta) and is_odd(recID)) or (is_odd(beta) and is_even(recID)), set y = p-y.
  9. Set R = (x,y)
  10. Set e = (-int(z)) % n
  11. Set PublicKey = (R*s + G*e) * modinv(r, n)
  12. If is_even(y), compute EncodedPublicKey = "02" || hex(x). Else, compute EncodedPublicKey = "03" || hex(x)
  13. Compute AddressHash = RIPEMD160(SHA256(EncodedPublicKey)
  14. Compute DerivedAddress = Bech32("bc", 0, AddressHash)
  15. If DerivedAddress == Address, succeed verification. Else fail verification with an error similar to "Wrong address for signature".

Alternative formats

Work is currently under way to create a new signing format called BIP322[2] that can verify signatures from all types of addresses, including scripts, multisig, and Taproot. It is currently a draft.

References

  1. ↑ https://github.com/bitcoin/bips/blob/master/bip-0137.mediawiki - BIP 137
  2. ↑ https://github.com/bitcoin/bips/blob/master/bip-0322.mediawiki - BIP 322
Retrieved from "https://en.bitcoin.it/w/index.php?title=Message_signing&oldid=70360"