gmpelliptic-curvenettle

nettle curve 25519 result of base point * 1


I am using GNU nettle library. I have the following code:

#include <nettle/curve25519.h>

uint8_t result[32], one[32];
for(auto &i : one) i = 0;
one[31] = 1;
curve25519_mul_g(result, one);

In the code, I multiplied 1 with the base point. The base point's x-coordinate is 9, so I would expect the result to be 9.

But instead, it gives me this number: 0xfd3384e132ad02a56c78f45547ee40038dc79002b90d29ed90e08eee762ae715.

Why does this code not generate 9?


Solution

  • Curve25519 clamps some bits of the scalar to 1 or 0. Specifically in Curve25519 scalar multiplication:

    1. the lowest 3 bits are set to 0, to ensure the output point is only in the large subgroup, and
    2. the highest bit (2^254) is set to one, to make sure the implementer does not skip any Montgomery-ladder steps.

    After this clamping operation, the scalar multiplication algorithm will be executed. So in Curve25519, a point cannot be multiplied with 1.


    In your case, however, there is even more going on. nettle uses a little-endian convention in their code. That is, when you execute

    one[31] = 1;
    

    you are actually setting the 2^248 bit to one, not the 2^0 bit. Then the clamped value will become k = 2^254 + 2^248.

    The computation [2^254 + 2^248] * (9 : 1) results in 0x15e72a76ee8ee090ed290db90290c78d0340ee4755f4786ca502ad32e18433fd (big endian), which corresponds with your observation.