Converting Ed25519 public key to a Curve25519 public key

$$x_{montgomery} = \frac{1 + y_{edwards}}{1 - y_{edwards}}$$

Using the libsodium ed25519 implementation, I have tried to write the following:

void keypair_2(unsigned char *pk, unsigned char *sk)
{
ge_p3 A;
int i;

sk[0] &= 248;
sk[31] &= 63;
sk[31] |= 64;

ge_scalarmult_base(&A,sk); // generate ed25519 public from sk.

fe one;
fe u, v, vinv;
fe montx;
fe_1(one);
fe_sub(v, one, A.Y); //v = 1-y
fe_add(u, A.Y, one); //u = y+1
fe_invert(vinv, v); //vinv = v^(-1) = (1-y)^(-1)
fe_mul(montx, u, vinv); //montx = u/v = (y+1)/(1-y)
fe_tobytes(pk, montx);
}

And I have compared this against the curve25519 implementation, but I am getting differing results.

I am unsure as to my error.

-
In my own application I chose to use Ed25519 public keys in the public API, even for key-exchange. Then convert the public key to montgomery during key-exchange. That's slightly more expensive, but makes the API nicer since there is only one kind of public key visible to the consumer. I also think that it's possible to convert the key-exchange to use Ed25519 natively, removing the performance penalty, but didn't get around to investigating that yet. –  CodesInChaos Aug 2 '13 at 12:10
@CodesInChaos - I am doing the same (using Ed25519 as the public key). It is probably possible to implement DH in Ed25519 natively, but I am not sufficiently confident in my ability to do so without messing up. I understand ImperialViolet has such an implementation? –  user7868 Aug 2 '13 at 12:18
You can add github.com/nightcracker/ed25519/blob/master/src/key_exchange.c to your project. It should be compatible with the rest of your implementation. It takes an Ed25519 public key, converts it to montgomery, and then computes a scalar multiplication. Don't forget to add a hashing step in the end, preferably one that's compatible with NaCl. That's what I do in my C# port. –  CodesInChaos Aug 2 '13 at 12:22

ge_scalarmult_base returns GroupElementP3 which doesn't have (x, y) as members. It has X, Y, Z from which you can compute x = X / Z and y = Y / Z.

So you have two choices:

1. Compress the point with ge_tobytes:

byte[32] Abytes;
fe y;

ge_scalarmult_base(&A,sk);

ge_tobytes(Abytes, &A);
fe_frombytes(&y, Abytes);

// your code here using y instead of A.Y

The downside of this technique is that it costs two field inversions. So I'd only use it if the input is a compressed point.

2. Modify the formula to work with X, Y, Z coordinates:

$$x_{mont} = \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y}{Z}}{1-\frac{Y}{Z}} = \frac{Z+Y}{Z-Y}$$

fe_sub(v, A.Z, A.Y); //v = Z - Y
fe_add(u, A.Y, A.Z); //u = Z + Y

This solution is preferable if you just computed the point without having reduced yet. Typically directly after a scalar multiplication.

-
Thanks very much! Both solutions were helpful. –  user7868 Aug 2 '13 at 12:03

Support for this has now (2014-08-05) been added to Sodium.

Implement ed25519 -> curve25519 keys conversion

Look at test/default/ed25519_convert.c for some example code.

-