Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I understand that:

$$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_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.

share|improve this question
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 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
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. – Frank Denis Aug 8 '14 at 3:56
up vote 4 down vote accepted

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_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.

share|improve this answer
Thanks very much! Both solutions were helpful. – user7868 Aug 2 '13 at 12:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.