4
$\begingroup$

I have an ECDSA implementation in Mathematica over secp256k1 and $r$ and $s$ are always positive numbers. But if you encode them as bytes, the most significant byte can be over 0x80, which would make it a negative number if the big-number is interpreted as being signed.

I'm asking because the bitcoin implementation has these checks which I don't understand:

if (S[0] & 0x80)
    return error("Non-canonical signature: S value negative");
if (R[0] & 0x80)
    return error("Non-canonical signature: R value negative");

The $r$ and $s$ values that I produce seem that they would fail these checks when they are larger than $2^{255}$

Improve this question
$\endgroup$
6
  • $\begingroup$ Actually, whether the most significant bit is 0x80 depends on the number of bytes Mathematica uses when it represents an integer. If it uses 32 bytes to represent a 256 bit integer, you are correct. If it uses 33 or more, then no, the leading byte will be 0. Since I don't know how Mathematica works internally, I'm not making this an answer; I'm just suggesting this as a possibility. $\endgroup$
    – poncho
    Commented Dec 20, 2013 at 15:26
  • $\begingroup$ I don't think it matters. I can convert it to any format I want, including to 32 bytes. And that 32 bytes representation looks like it would fail the bitcoin check. $\endgroup$
    – Meh
    Commented Dec 20, 2013 at 15:39
  • $\begingroup$ Yes, you can convert it into any format you want; however, what is the format that the bitcoin implementation uses when it does the above checks? $\endgroup$
    – poncho
    Commented Dec 20, 2013 at 15:41
  • 3
    $\begingroup$ If it's DER, then that's your answer; DER integers always have the high bit of the integer being the sign; if the msoctet has its high bit, then you prepend a 0x00 byte to preserve this property. $\endgroup$
    – poncho
    Commented Dec 20, 2013 at 15:58
  • 2
    $\begingroup$ @Meh Yes, Bitcoin is rejecting DER-valid r and s values. In fact it rejects a lot of DER-valid inputs with the explicit goal that each algebraic signature $(s, r)$ has exactly one encoding. The reason is that re-encoding signatures changes the byte representation of a transaction, which in turn changes its txid, which in many multi-transaction protocols is expected not to change. The keyword to search about this is "transaction malleability". $\endgroup$
    – Andrew Poelstra
    Commented Jun 4, 2017 at 16:04

1 Answer 1

Reset to default
4
$\begingroup$

You appear to be testing a DER-encoded integer.

DER-encoded integers are defined so that they can encode both positive and negative values (in cryptography, we don't need to encode negative integers all that often; however ASN.1 isn't specific to cryptography).

DER-encoded integers are defined this way:

  • Positive values are represented by the minimal number of bytes that can represent the integer (in bigendian byte order), with the msbit of the initial byte being clear.

    • For example, the value 32768 would be represented by the three bytes 0x00 0x80 0x00. We are not allowed to use the two octets 0x80 0x00, because 0x80 has the msbit set

  • Negative values are represented by the minimal number of bytes that can represent the integer (in two's complement notation), with the msbit of the initial byte being set.

  • Zero is represented as a single 0x00 byte

Hence, testing the msbit of the initial byte will correctly tell you whether the represented integer is nonnegative.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.