However elliptic curve technology is considered a patent minefield and quite some attempts have been made to clarify the status, e.g. IETF made an attempt with RFC6090 to describe only the fundamental algorithms on which all patents are known to have expired. The GnuTLS implementation of ECC is based on this document.

One of the interesting "improvements" that is not included in the fundamental algorithms, and is still patented is

*point compression*. To describe it we need a small (but not detailed) introduction to elliptic curves. An elliptic curve (at least for the needs of TLS protocol) is a set of points (x,y) that satisfy the following relation modulo a large prime p.

y

^{2}= x^{3}+ ax + bThis set of points has some properties, i.e., a group law allowing point addition, scalar multiplication etc. Without getting into details those points need to be exchanged during a protocol run and given that the points usually belong to a "large" prime field (e.g. 256-bits), reducing the exchanged bytes is an improvement. Point compression achieves that goal, so let's see how.

Say we have a point (x

_{0},y

_{0}) satisfying y

_{0}

^{2}= x

_{0}

^{3}+ ax

_{0}+ b. If x

_{0}is known, then the previous relation becomes a second degree polynomial, that has two solutions.

y

_{1,2}= ±√ x

^{3}+ ax + b

And surprisingly that's all about point compression. Instead of sending the tuple (x

_{0},y

_{0}), only x

_{0}and a bit identifying the sign of y is sent. The receiver only needs to calculate y

_{1,2}and then select the appropriate using the sign bit. Of course calculating square roots modulo a prime isn't as simple as in our example, but the idea is similar.

So is this worthwhile? Are implementations like GnuTLS that don't infringe this patent in a disadvantage? While it is a clever idea, it doesn't really add much value in real-world protocols. A 256-bit curve has points of around 32 bytes. Thus the bytes saved per TLS handshake are 64 bytes overall. Such handshake typically contains data of several kilobytes, and saving few bytes isn't going to make a dramatic difference. It wouldn't be a top priority addition even if it wasn't a patented method.

By the way, there exists a more efficient method to represent an ECC point in a compact form, as documented in Compact representation of an elliptic curve point.

ReplyDeleteThis method doesn't depend on the requirement to send 1 bit representing the

y. The entire point is represented by theycoordinate only.This specification is based on the year 1985 publication and is thus in the public domain.

That looks like a nice point you make. However, RFC4492 which describes TLS with ECC doesn't assign an identifier for it. That could be a nice amendment though.

ReplyDelete