Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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}$

share|improve this question
    
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. –  poncho Dec 20 '13 at 15:26
    
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. –  Adal Dec 20 '13 at 15:39
    
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? –  poncho Dec 20 '13 at 15:41
    
It looks like a DER encoded big-integer, which is why I'm confused, since it would seem that the check disallows valid $r$ and $s$ values –  Adal Dec 20 '13 at 15:54
2  
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. –  poncho Dec 20 '13 at 15:58
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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