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.
y2 = x3 + ax + b
This 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 (x0,y0) satisfying y02 = x03 + ax0 + b. If x0 is known, then the previous relation becomes a second degree polynomial, that has two solutions.
y1,2 = ±√ x3 + ax + b
And surprisingly that's all about point compression. Instead of sending the tuple (x0,y0), only x0 and a bit identifying the sign of y is sent. The receiver only needs to calculate y1,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 the y coordinate 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.
ReplyDeleteYES - if the US government uses elliptic curve compression, they know and presume their enemies know it's NOT secure. See 'Suite B' from the NSA. There isn't anything like 'Shor's Algorithm' for elliptic curves. Plus if you presume the riemann hypothesis is true and and use a mersanne prime finder - you have a pretty good chance of finding the right key in a reasonable time. Don't forget, the primes have to be roughly the same size (16363 & 3 work, but aren't secure!). If you wans security, just meet up with the guy you want to stay in contact with and have a 16Gb memory stick each - now fill with 1-time pad. 2Gbyte gives a few WEEKS of uninteruoted call time. While your at it, have a switch that turns off power to bluetooth & the utility that flashes the BIOS. Mobile phone security is truly a joke. Only with the advent of the Galaxy 5 mobile which, along with those hardware mods, mean nobody is going to rootkit your phone. Oh, and I would also enable some MESH software so your phone becomes like a walkie-talkie - not using towers at all......
ReplyDeleteI think there is one more aspect to point compression: if you don't sent both coordinates you don't have to verify that the point is actually on the curve. This seems to be one of the safe curve aspects http://safecurves.cr.yp.to/twist.html. While I think when you properly verify the points this is not a big deal, it should be mentioned here anyway.
ReplyDelete