Elliptic curve point compression

[clehner]

The public keys in the test vectors for Secp256k1 are in compressed form (33 bytes), but for P-256 they are uncompressed (64 bytes, untagged). For Ed25519 they are compressed (32 bytes).

• Should P-256 use compressed form instead? The smaller size in a URI may be desirable, and this would be consistent with the use of Secp256k1 and Ed25519.
• Should did:key allow either form - compressed or uncompressed - for these key types? Or only a single form is allowed? Or either form allowed but one is preferred?

[OR13]

imo, did-key method spec should probably stick to compressed only... the main reason the NIST curves are uncompressed is that they are commonly represented uncompressed... I did the first version of them and now @troyronda and SecureKey have support for them as well...

I am not sure how hard it would be to convert did key for nist curves to compressed, but if we can, we should IMO.

[msporny]

• Should P-256 use compressed form instead? The smaller size in a URI may be desirable, and this would be consistent with the use of Secp256k1 and Ed25519.

Yes, because the smaller size URI is a desirable feature.

• Should did:key allow either form - compressed or uncompressed - for these key types? Or only a single form is allowed? Or either form allowed but one is preferred?

Let's just stick to compressed form, I don't see a need to support both.

[dlongley]

Some links on P-256 compressed form:

https://tools.ietf.org/html/rfc5480
https://tools.ietf.org/id/draft-jivsov-ecc-compact-05.html
https://stackoverflow.com/a/30431547/399274

Looks like you simply add the last bit of the Y coordinate to 0x02 (used as the prefix value) such that the prefix will be either 0x02 or 0x03 and then you follow that with the X coordinate and that's it (the rest of the Y coordinate is dropped).

[OR13]

One issue we have is that we only support did key variants that have some JWK representation, so we won't implement support for this until we can easily convert back and forth.... because we like interoperability with off the shelf JOSE libraries.

I will need to take a look at bi-directional transformations to be sure its possible to support.

[bshambaugh]

+1 Orie. I'm presently contemplating building a function that takes both the compressed and uncompressed versions and produces a JWK representation. It would be extra code to compress, send over the wire, then decompress but perhaps that could be better.

edit: I found a few links both today and yesterday: https://crypto.stackexchange.com/questions/8914/ecdsa-compressed-public-key-point-back-to-uncompressed-public-key-point , https://bitcoin.stackexchange.com/questions/69315/how-are-compressed-pubkeys-generated , https://stackoverflow.com/questions/53629537/how-to-generate-33-byte-compressed-nist-p-256-public-key ,https://stackoverflow.com/questions/6665353/is-there-a-standardized-fixed-length-encoding-for-ec-public-keys

I believe this contains the definition of the P-256 and other NIST curves: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

edit (5/02/2021): https://bitcoin.stackexchange.com/questions/92680/what-are-the-der-signature-and-sec-format , https://en.wikipedia.org/wiki/Endianness, https://tools.ietf.org/html/rfc5480 , https://www.secg.org/sec1-v2.pdf (see: 2.3.3) , https://www.secg.org/sec2-v2.pdf

[oed]

You can use a library such as elliptic to convert keys back and forth between compressed and uncompressed. Although, it's a big dependency that would be nice to avoid if possible!

let ec = new require('elliptic').ec('p256')
undefined
> ec.genKeyPair().getPublic(true, 'hex')
'03413029cb9a5a4a0b087a9b8a060116d0d32bb22d14aebf7778215744811bb6ce'
> pub = ec.keyFromPublic('03413029cb9a5a4a0b087a9b8a060116d0d32bb22d14aebf7778215744811bb6ce', 'hex').getPublic(false, 'hex')
'04413029cb9a5a4a0b087a9b8a060116d0d32bb22d14aebf7778215744811bb6ce40780d7bb9e2e068879f443e05b21b8fc0b62c9c811008064d988856077e35e7'

[bshambaugh]

I have some code over here that supports raw public keys, compressed public keys, and uncompressed public keys for P-256. ceramicnetwork/js-ceramic#1418

[OR13]

Anyone on this thread want to take a stab at updating the test vectors in this repo to use the compressed from for P-256, P-384, P-521?

just edits to the JSON files.

[bshambaugh]

I will look at it.

I can use (or slightly modify) this [1] to create test vectors (given the raw or uncompressed public key input):
[1] https://github.com/bshambaugh/key-did-provider-secp256r1/blob/main/src/index.ts + source extra curves from :
https://www.npmjs.com/package/elliptic or the existing test vectors.

By changing about 3 lines of code I believe that this could be written for P-384 and P-521.
https://github.com/bshambaugh/js-ceramic/blob/develop/packages/key-did-resolver/src/secp256r1.ts

[clehner]

I get the following for the P-256 one:

did:key:zDnaerx9CtbPJ1q36T5Ln5wYt3MQYeGRG5ehnPAmxcf5mDZpv

[bshambaugh]

did:key:zDnaeUKTWUXc1HDpGfKbEK31nKLN19yX5aunFd7VK1CUMeyJu
did:key:zDnaerx9CtbPJ1q36T5Ln5wYt3MQYeGRG5ehnPAmxcf5mDZpv

Yes. I had one that looked similar in my tests. The length after the key: is 49 for both yours and mine.

[bshambaugh]

Okay. I started a pull request: #36 . I'll look at this again tomorrow when more awake.

[bshambaugh]

I get the following for the P-256 one:

did:key:zDnaerx9CtbPJ1q36T5Ln5wYt3MQYeGRG5ehnPAmxcf5mDZpv

Awesome. Thanks. I am got the same thing.

[OR13]

I think this is done, recommend closing.

[oed]

👍
Note that multicodec table also have been updated to explicitly state that keys should be compressed: https://github.com/multiformats/multicodec/blob/master/table.csv#L136-L138

[bshambaugh]

I remember that P-521 had some problems. I recall writing some code for P-256 and P-384 NIST curves with a generic wrapper for it. P-521 was different, IIRC. I haven't touched this code in a while, but I thought I should get back to that a few days ago. I could open up a PR when I get to it, or whatever works.

…

-Brent

On Thu, Sep 23, 2021 at 12:42 PM Joel Thorstensson ***@***.***> wrote: 👍 Note that multicodec table also have been updated to explicitly state that keys should be compressed: https://github.com/multiformats/multicodec/blob/master/table.csv#L136-L138 — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#32 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABAC4YL7PJKXBRDHPFS743DUDNRJZANCNFSM4YTT4IGA> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[OR13]

@bshambaugh please consider raising a separate issue for that if you find anything wrong with P-521...