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?

dusk
  • 1,799
  • 18
  • 25
Zeta
  • 913
  • 10
  • 24

1 Answers1

1

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.

dusk
  • 1,799
  • 18
  • 25
  • One thing to note.. Nettle curve25519 is not little endian. In the manual and web site, it says so, but it is big endian in practice.. It confused me a lot. They should correct the manual as soon as possible. – Zeta Apr 24 '20 at 07:33