2
$\begingroup$

I just migrated CodesInChaos' C# port of Ed25519(ref10) to Java, and everything works fine. (I.e. I get the same results for key generation, signature and verification.)

Now, I would like to do a Diffie-Hellman key exchange directly on Ed25519. Therefore I am examining the functions for point addition, doubling and multiplication.

After several tests it appears that doubling a point

dbl(P)

provides a different result than adding the same point to itself

add(P,P).

Even when I use different points for the addition, the results are still different. For example: dbl(dbl(P)) is also different from add(add(dbl(P),P),P).

Is this normal? (I am not familiar with ECC, and I had expected that these functions would return the same values.)

UPDATE

There was a bug in my code which is now corrected thanks to CodesInChaos.

Here is my test code for C#:

using System; using Chaos.NaCl.Internal.Ed25519Ref10; namespace Chaos.NaCl { public static class RunTest { static void Main () { testAddition (); } public static void testAddition () { Console.WriteLine ("============================= testAddition "); byte[] l_Seed = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; byte[] l_PK = new byte[32]; byte[] l_SK = new byte[64]; Ed25519Operations.crypto_sign_keypair (l_PK, 0, l_SK, 0, l_Seed, 0); byte[] l_A = add (l_PK, l_PK); byte[] l_B = dbl (l_PK); Console.WriteLine (CryptoBytes.ToHexStringUpper (l_A)); Console.WriteLine (CryptoBytes.ToHexStringUpper (l_B)); // Output Java and C#: // 382CE0B6971265E859F317BBCD18F6ADF4517102055DEFA3ED7C4EBFD2C0D655 // 382CE0B6971265E859F317BBCD18F6ADF4517102055DEFA3ED7C4EBFD2C0D655 // which is OK // LETS DO IT AGAIN: byte[] l_C = add (l_B, l_B); byte[] l_D = dbl (l_B); Console.WriteLine (CryptoBytes.ToHexStringUpper (l_C)); Console.WriteLine (CryptoBytes.ToHexStringUpper (l_D)); // Output Java port: // 40838B988FB4A3809EBEAA600604EAB4A39A75BD86509A73C40B5A2820BEB94E // 90A0F26E495C4A73BCE8BE36B361FF84F8CA8E19E15B9F623AC538E5F9646B63 // which is wrong ? // Output C# (Mono): // 0000000000000000000000000000000000000000000000000000000000000040 // 0000000000000000000000000000000000000000000000000000000000000040 // which is also wrong ?? :) } static byte[] dbl (byte[] p_Element) { byte[] l_Result = new byte[32]; GroupElementP3 l_P3; GroupOperations.ge_frombytes_negate_vartime(out l_P3, p_Element, 0); GroupElementP1P1 l_P1P1; GroupOperations.ge_p3_dbl(out l_P1P1,ref l_P3); GroupElementP3 l_P3again; GroupOperations.ge_p1p1_to_p3(out l_P3again,ref l_P1P1); GroupOperations.ge_p3_tobytes(l_Result,0,ref l_P3again); // EVIL MISTAKE: ScalarOperations.sc_clamp(l_Result, 0); return l_Result; } static byte[] add (byte[] p_ElementA, byte[]p_ElementB) { byte[] l_Result = new byte[32]; GroupElementP3 l_A; GroupOperations.ge_frombytes_negate_vartime(out l_A, p_ElementA, 0); GroupElementP3 l_B; GroupOperations.ge_frombytes_negate_vartime(out l_B, p_ElementB, 0); GroupElementCached l_Cached; GroupOperations.ge_p3_to_cached(out l_Cached,ref l_A); GroupElementP1P1 l_P1P1; GroupOperations.ge_add(out l_P1P1, ref l_B, ref l_Cached); GroupElementP3 l_P3again; GroupOperations.ge_p1p1_to_p3(out l_P3again, ref l_P1P1); GroupOperations.ge_p3_tobytes(l_Result, 0, ref l_P3again); // EVIL MISTAKE: ScalarOperations.sc_clamp (l_Result, 0); return l_Result; } } }
Improve this question
$\endgroup$
6
  • $\begingroup$ Why do you want to avoid the conversion to Montgomery for DH? It's a bit slower than using (Y/Z) coordinates in Edwards form due to an additional field inversion, but almost certainly faster than what you're attempting to build. Conversion back to edwards at the end of the scalar multiplication is free, but I didn't do so for compatibility with existing Curve25519 shared secrets. $\endgroup$ Commented May 9, 2014 at 7:48
  • $\begingroup$ @CodesInChaos: Actually what I want is a group G on which the discrete log problem holds, and which allows me to implement various things like Diffie-Hellman key exchange, Pedersen commitments and also custom zero-knowledge proofs. If possible, I'd prefer to use a single fast curve which allows me to perform all the required group operations. Currently I am trying to get there using the Edwards curve, but this is more tricky than expected. Maybe I should try the Montgomery approach instead? $\endgroup$ Commented May 9, 2014 at 11:37
  • $\begingroup$ If you only need one coordinate of the output, you can convert to montgomery form, compute the scalar multiplication and convert back. You only need your approach if you need both coordinates. $\endgroup$ Commented May 9, 2014 at 11:39
  • $\begingroup$ Is your code publicly available? $\endgroup$ Commented May 9, 2014 at 12:06
  • $\begingroup$ sc_clamp makes no sense on encoded points. It operations on scalars. $\endgroup$ Commented May 9, 2014 at 15:39

2 Answers 2

Reset to default
5
$\begingroup$

Edwards curves have unified addition so adding a point to itself returns the correct result. This differs from Weierstrass curves, where adding a point to itself gives the wrong result and you must use doubling. So your expectation that addition and doubling should return the same point is correct.

High performance implementations of ECC use some form of extended or projective coordinates where you add an additional field for the denominator. $(x,y)$ could be represented as $(X, Y,Z)$ with $x=X/Z$ and $y=Y/Z$. Ref10 uses several different of these representations, but the idea remains the same.

So you can't compare points simply by comparing all of $X,Y,Z$ since there are multiple representations of the same point. Similar to how $\frac{1}{3}$ and $\frac{2}{6}$ are the same number despite looking different. Doubling and addition return the same point, but with different representation.

To compare points

  • The easiest method of doing so is ge_tobytes. This converts to affine coordinates, but requires an expensive field inversion.

  • Alternatively if you want to compare $\frac{X_1}{Z_1}$ with $\frac{X_2}{Z_2}$ you check if $X_1 Z_2 = X_2 Z_1$.

    This follows from $\frac{X_1}{Z_1} = \frac{X_1 Z_2}{Z_1 Z_2}$ and $\frac{X_2}{Z_2} = \frac{X_2 Z_1}{Z_1 Z_2}$ where you only need to compare the nominator since the denominator is the same.

    Do the same for the $Y/Z$ or $Y/T$ parts as appropriate for the point representation you're working with.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Currently I convert between the different representations in order to perform the operations, and I do use 'ge_tobytes'. Thank you for explaining the approach with X and Z; I can certainly use this during further testing. $\endgroup$ Commented May 9, 2014 at 11:49
1
$\begingroup$

The results should be the same as you have noted. Although I would think that most people would have a function more akin to ScalarMult(int, point) instead of dbl. Perhaps you could look at dbl and check if it is really a doubling function.

Another check you could perform is to look at the $x$-coordinates of either outputs. Are they the same? If only the $y$-coordinate is different, then one is computing $2[P]$, while they other is computing $-2[P]$.

Lastly, just check against SAGE or Pari or magma.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for confirming that the result should be the same. I'll have a look the tools you mention; so far I knew SAGE but I did not know of Pari and magma before. $\endgroup$ Commented May 9, 2014 at 11:56

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.