Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

[Jakob Breier <[e-mail]>]

Hey Rene,

thanks for your reply. I was well aware of the distinction between a) 
and b). The implicit argument, which I did not spell out unfortunately, 
was that

1. It's desirable to have as few point formats for a curve as possible 
(KISS rule). Elliptic curve cryptography might be a mess already, but if 
we never start simplifying things, it will still be a mess in 20 years. 
I'd like to be able to point people to the new IETF curves when the CFRG 
is through and tell them "use these curves / point formats (and if 
possible only those) and life will be as easy as ECC can get". A 
separate x-coordinate-only format for Montgomery multiplication is worth 
it in my opinion because of the implementation simplicity it affords, 
but having an additional compressed format is probably not.

2. Implementers will likely not go through the hassle of adding an 
additional compressed point format, but instead use the wire format they 
have to support. I'd like to be proven wrong on this, though.
As evidence I point to the OpenSSH key formats. They could already have 
used compressed points with nistp256 and, as far as I can tell, OpenSSL 
as well as the chosen storage format even supports them (the latter of 
which you have pointed out - thanks btw, I didn't recognize that 
before). But they only switched when they were forced to move away from 
OpenSSL to support Ed25519 and imported the SUPERCOP implementation [1] 
which *only* supports compressed points [2]. So only having one "right" 
format apparently did make the difference between having nice user 
facing point formats or not.

Please note however, that all the points I've made so far are second 
order arguments. While I would love to finally have short asymmetric 
keys, the far more important aspect for me is to assert that 
implementers cannot screw up point validation. And point compression 
seems to be necessary towards that end. I'll not rehash the reasons why 
implementers cannot be entrusted with such an easy step as plugging 
variables into an equation - this has already been amply discussed on 
this list and those reasons either convince you already, or don't.

I've only brought up the "human bandwidth" line of reasoning (which I 
nonetheless find significant) and caused the associated extra noise, 
because I'm afraid that point validation alone does not swing the tide 
towards compressed points.

Best regards,
Jakob Breier

[1] 
https://lists.mindrot.org/pipermail/openssh-unix-dev/2013-December/031871.html
[2] See e.g. the python implementation 
http://ed25519.cr.yp.to/python/ed25519.py , especially encodepoint and 
decodepoint.


On 13.03.2015 15:50, Rene Struik wrote:
> Hi Jakob:
>
> This confuses different discussions:
>
> a) use of public key in computations.
> Here, Andrey Jivsov's point was that receipt of a full point (x,y) on 
> a curve, rather than a compressed point or simply the x-coordinate, 
> does not artificially impose a performance penalty on all 
> implementations except x-coordinate-only ones (Montgomery).
> b) representation of public key in white list.
> Here, one can use many methods to map a public key Q to a condensed 
> (perhaps, even human-recognizable) format f(Q).
> This condensed format could take the form affine format curve point, 
> compressed format, hash, leftmost n-octets, hash value, etc.
>
> My own take:
>
> Ad a):
> I fully agree with Andrey Jivsov's point and think using x-coordinate 
> only representations imposes a "moat" around ECC implementations, by 
> imposing a levy on all implementations that, for whatever reason, may 
> want to use something else than Montgomery arithmetic. {Please note 
> that this levy is incurred (in the context of ECDH) during *online* 
> computations.} Such fully specified points are particularly useful in 
> settings, including multiple-point multiplication, combined key 
> computations and signature verifications, batch computations, since 
> may allow significant performance advantages in those settings.
>
> Ad b):
> This is a non-issue in representation discussions with CFRG with ECC, 
> since dealing with protocol issues, not user interfaces.
> Nevertheless, here is a comparison that illustrates some condensed 
> representations that are possibly in a completely standardized way, 
> resp. "cooked up" for user interfaces:
>
> Comparison example:
> example P-256 public key, with affine coordinates (x,y),
> x-coord = 6b 17 d1 f2 e1 2c 42 47 f8 bc e6 e5 63 a4 40 f2 77 03 7d 81 
> 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96
> y-coord = 4f e3 42 e2 fe 1a 7f 9b 8e e7 eb 4a 7c 0f 9e 16 2b ce 33 57 
> 6b 31 5e ce cb b6 40 68 37 bf 51 f5
> a) standardized affine format: (0x04 || x-coord || y-coord) {65 octets}
> b) standardized compressed format: (0x03 || x-coordinate) {33 octets}
> c) non-standard, x-coordinate-only: x-coordinate {32 octets}
> d) non-standard, truncated x-coordinate (x-coordinate mod 2^128): 77 
> 03 7d 81 2d eb 33 a0 f4 a1 39 45 d8 98 c2 96 {16 octets}
>
> example Curve25519, Alice's public key (source: 
> draft-irtf-agl-cfrgcurve-00):
> x-coord = 85 20 f0 09 89 30 a7 54 74 8b 7d dc b4 3e f7 5a 0d bf 3a 0d 
> 26 38 1a f4 eb a4 a9 8e aa 9b 4e 6a
> c) non-standard, x-coordinate-only: x-coordinate {32 octets}