Re: [Cfrg] 25519 naming

[Dan Brown <[e-mail]>]

> -----Original Message-----
> From: D. J. Bernstein
> Sent: Monday, August 25, 2014 7:43 PM
> 
> use short Weierstrass x and y coordinates for everything (as required by,
> e.g., the ANSI and NIST ECDSA standards), 

With an ANSI hat on: 

Just a small clarification, because I think saying "for everything"
overstates the ANSI ECDSA requirements. The quoted statement "for
everything" to me suggests that ANSI requires these formats for
transmission, but that's not strictly true.

While ANSI X9.62 ECDSA and ANSI X9.63 do specify recommended formats such
octet string conversions and some ASN.1 types, using these formats for
transmitting public keys is *not* a requirement to claim compliance to the
algorithms in ANSI X9.62 or ANSI X9.63. (Unless I'm missed something today
in my quick review of these documents, or have forgotten some requirement
text.)   

Of course, it is correct that some conversions *are required* in the
internal algorithm calculations, in order to obtain interoperability:

- Both the ECDSA and ECMQV algorithms specify a required operation that
takes a short Weierstrass x-coordinate of an ephemeral public key and
convert to an integer. 

- Both ECDH and ECMQV algorithms specify a required operation that takes a
short Weierstrass x-coordinate of a shared secret and converts it to a bit
string.

Both ends of the communication must use the same internal conversions to
achieve interoperability.  I think that the choice of short Weierstrass was
mainly motivated by being able to work for any curve.  Recall, that ANSI
optionally users to specify their own curves, even providing an ASN.1 format
to help them out.  (Aside: some IETF specs forbade this general curve
specifying format, so, in a weak sense, it is really IETF disallowing the
curve part of Curve25519, not ANSI ;-)

With ANSI hat off now:

I'm not sure at the moment at the costs or benefits of changing the
algorithm internal conversions with new curves, but here are some tentative
thoughts:

- I think one might be able to separate/tie the curve choice from/to the
internal representations used in the algorithms above, but one would need to
expand the algorithms slightly, and if things are more separated, then add
some mechanisms to negotiate the relevant internals.

- Most of the hard work, i.e. scalar multiplication, can be done in whatever
format is convenient, with wire-format and final algorithm conversions being
done just when needed.

- From a security perspective, these internal conversion functions require
some very mild security properties (e.g. they must not cluster at one output
value) that I think most reasonable alternatives would easily meet, perhaps
with proof.

Regarding NIST requirements: I'm not sure because there are more layers
documents involved, and in particular, there's FIPS 140-3 with the CAVP and
CMVP program and so on, which I think get rather more specific by mandating
formats, which is indeed almost "everything".  Maybe people have been, or
still are, more interested in NIST than in ANSI, anyway. So, another reason
this is a just small clarification.

Best regards,

Dan