Point addition and doubling in Ed25519 (ref10)?

Question

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;
        }
    }
}

Answer 1

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.

Answer 2

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.