search

kokke / tiny-ECDH-c

Small portable Elliptic-Curve Diffie-Hellman in C
The Unlicense
254 stars 64 forks source link

Is point compression supported? #15

Open p0fi opened 5 years ago

p0fi commented 5 years ago

Is point compression supported? I need a compressed version of my public key which is 22 bytes long for a sect163k1 curve key pair. I can't find a way to get this right now.

kokke commented 5 years ago

Hi @p0fi and thanks for your interest.

I have chosen not to support point compression, because it seems to be patent encumbered: https://patents.google.com/patent/US6252960B1/en

I am not 100% sure when the patents will expire, but it should be soon.

p0fi commented 5 years ago

Oh really? Thats a pity, I really need a point compressed representation of the keys. Do you have any idea how I can maybe implement it myself easily? The patent link seems overwhelmingly complex since im not really into cryptography.

I found that https://github.com/kmackay/micro-ecc does support point compression but not the curve I need in particular.

kokke commented 5 years ago

Not many people know for sure how the patent situation is currently. Some patents cover only ECC-tech working on prime-field curves, others are for Galois-field (binary) curves. That could explain the difference, since Ken MacKay's library works on prime-field curves and mine works on Galois-fields (so-called binary curves)

ECC is quite the patent mine-field, so I haven't uploaded anything related to point compression, even though it's conceptually somewhat simple.

Basically, you exploit the fact that if you know the x-coordinate, there are only so many y-coordinates the point can have, if it lies on the curve. For prime-field curves, it requires you calculate a modular square root. For binary curves, you need to solve a quadratic equation to get the y-coordinate, so it's a bit more involved.

This page has great ECC resources, and pseudo-code for some field-operations: http://point-at-infinity.org/ecc/

I think this answer on crypto.stackexchange has a pretty good explanation of the math involved: https://crypto.stackexchange.com/questions/8914/ecdsa-compressed-public-key-point-back-to-uncompressed-public-key-point

There is a thorough description of formats under section 2.3 in this document: http://www.secg.org/sec1-v2.pdf

And this blog is a really approachable introduction to ECC in general: https://www.johannes-bauer.com/compsci/ecc/

trstovall commented 5 years ago

That patent link states the patent application expires today.

kokke commented 5 years ago

Hi @trstovall and thanks for chiming in.

I read that too :) The problem is, that this is not the only patent on ECC - far from - it's just one of the better known ones. There are no public lists of all patents covering which ECC techniques, and there are not many sources of information on what is unencumbered.

Most ECC patents should expire around 2020-2021, from what I've read, but there are no guarantees. There is even an RFC dedicated to what is covered by patents in ECC and what isn't: https://tools.ietf.org/html/rfc6090

Some patents are only valid in the US etc. etc. -- I don't know what to make of this. Software patents are an abomination...