ECDH using Curve25519

[NIIBE Yutaka]

Hello,

I'm considering another experiment, that is, ECDH using Curve25519.

This week, I wrote Curve25519 routines for Gnuk:

    Gnuk: Add Curve25519 computation:
    https://gitorious.org/gnuk/gnuk/commit/85b2698bb3d741dd32517533ec9086343d1df1bb

I had thought that its were the name of the curve, but it's actually
the name of ECDH function.  I read two papers ([curve25519],
[curvezero]) at:

    http://cr.yp.to/ecdh.html

Curve25519 uses x-coordinate only representation for its public key.

If we apply Andrey Jivsov's draft-jivsov-ecc-compact-05 to RFC 6637
(Elliptic Curve Cryptography (ECC) in OpenPGP, also written by him)
for public key representation, I think that we can naturally extend
RFC 6637 for Curve25519.

The differences are that (1) it's defined on Montgomery curve, and (2)
its cofactor is 8.  (1) is no problem for ECDH, and (2) is no problem
(against the small-subgroup attack) as Curve25519's private key is
multiple of 8.

>From the viewpoint of Curve25519, MPI representation is a bit
different culture, though.

In this case (extending RFC 6637 with Curve25519), all we need is the
OID of the Montgomery curve.

Werner once suggested that using Ed25519 curve (as we already have
it's routine in libgcrypt).  However, with the experience of writing
an implementation (for Gnuk), I think that implementing Montgomery
curve in libgcrypt would be straight-forward and better in long term.

We need two things: (a) implement Montgomery's double-and-add function
and (b) extend the gcry_mpi_ec_mul_point function for Montgomery
curve.  Then, we can implement Curve25519 function by a specific
Montgomery curve over prime field 2^255-19 calling the
gcry_mpi_ec_mul_point function.  (Note that we will not implement
gcry_mpi_ec_add_points for Montgomery curve, as it's not
used for ECDH, and Montgomery curve is only for ECDH.)

I think that (a) is not that hard and (b) will become naturally
constant-time implementation.

Shall I go ahead to experiment with libgcrypt (and then, GnuPG,
hopefully) for Curve25519 function?

Any comments are appreciated.
--