Subject: [COSE] Use of bignum in cbor encoding

From: "Jim Schaad" <[email-masked]>
Date: Sat, 10 Oct 2015 18:51:47 -0700

There is a CBOR type of bignum which appears to have been designed to have
big integers placed it in.  Are there any objections to changing from using
the binary string (bstr) to big number (bignum) in those locations?   My
understanding of the document is that the length of the resulting encoding
is going to be the same.

Jim

---

From: Carsten Bormann <[email-masked]>
Date: Sun, 11 Oct 2015 11:28:27 +0200

> understanding of the document is that the length of the resulting encoding

Good question.

CBOR has bignums so there is a common convention for representing
integers that don't fit in 64 bits.  At the data model level, a bignum
is a sign (which is encoded into the tag) and the byte string that
represents that number in binary.  The expectation is that environments
that can represent such numbers in a natural way will decode bignums
right in the generic CBOR decoder, so the application will simply see an
integer; more constrained applications will see the tag and the byte string.

That a specific place really holds an integer may be clear from the
context, so it may not be necessary to tag the byte string representing
that integer as a bignum*).
If a large integer is represented as a byte string without a tag, you
lose the automatic decoding in the less constrained environments.  You
also lose the sign bit.  So, if you have that context, the tag costs you
8 bits if the integer really is unsigned, 7 bits if you would have
encoded the sign efficiently in the byte string (e.g., using two's
complement), and possibly nothing at all if your sign representation is
less efficient (or causes expansion of the byte string by one byte).

Jim: I think you are looking at the places marked CREF14 and CREF15 in
-05.  For ECC, while it is certainly possible to specify that leading
zero bytes are not to be removed, forcing bignums to do that here would
lose the benefit from using a generic encoder (which would very likely
remove those leading zeroes).  For RSA, it would be natural to use
bignums, or if that byte is really too much, possibly just exactly the
byte string encoding from bignums without the tag.

Grüße, Carsten

*) (Conversely, the tag *is* the natural way to represent a choice in a
place where the information model has a choice between a possibly large
integer and a byte string.)

---

From: "Jim Schaad" <[email-masked]>
Date: Mon, 12 Oct 2015 19:04:05 -0700

After thinking about this, I think we are better off leaving things as binary strings than changing to big numbers.

The main problem I have is that there could be implementations that are going to strip leading zeros when doing the encoding.  This is a problem because it makes it harder to ensure that items are the right length.  Going with binary strings eliminates this problem.

I am not truly worried about the possible lack of implementation.  I think that any library which is used for COSE is going to get this added to the implementation in any event if keys are going to be passed around.

Jim

> -----Original Message-----
> From: Carsten Bormann [mailto:[email-masked]]
> Sent: Sunday, October 11, 2015 2:28 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [COSE] Use of bignum in cbor encoding
> 
> > There is a CBOR type of bignum which appears to have been designed to
> > have big integers placed it in.  Are there any objections to changing from using
> > understanding of the document is that the length of the resulting
> > encoding is going to be the same.
> 
> Good question.
> 
> CBOR has bignums so there is a common convention for representing integers
> that don't fit in 64 bits.  At the data model level, a bignum is a sign (which is
> encoded into the tag) and the byte string that represents that number in binary.
> The expectation is that environments that can represent such numbers in a
> natural way will decode bignums right in the generic CBOR decoder, so the
> application will simply see an integer; more constrained applications will see the
> tag and the byte string.
> 
> That a specific place really holds an integer may be clear from the context, so it
> may not be necessary to tag the byte string representing that integer as a
> bignum*).
> If a large integer is represented as a byte string without a tag, you lose the
> automatic decoding in the less constrained environments.  You also lose the sign
> bit.  So, if you have that context, the tag costs you
> 8 bits if the integer really is unsigned, 7 bits if you would have encoded the sign
> efficiently in the byte string (e.g., using two's complement), and possibly nothing
> at all if your sign representation is less efficient (or causes expansion of the byte
> string by one byte).
> 
> Jim: I think you are looking at the places marked CREF14 and CREF15 in -05.  For
> ECC, while it is certainly possible to specify that leading zero bytes are not to be
> removed, forcing bignums to do that here would lose the benefit from using a
> generic encoder (which would very likely remove those leading zeroes).  For RSA,
> it would be natural to use bignums, or if that byte is really too much, possibly
> just exactly the byte string encoding from bignums without the tag.
> 
> Grüße, Carsten
> 
> *) (Conversely, the tag *is* the natural way to represent a choice in a place
> where the information model has a choice between a possibly large integer and
> a byte string.)