Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

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 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
add comment

1 Answer 1

up vote 2 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_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.

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

Your Answer

 
discard

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