When using Curve25519, why does the private key always have a fixed bit at 2^254?

Question

When using Curve25519, the private key always seems to have a fixed bit set at position $2^{254}$.

Why is that? Is there any good reason to use a fixed positioned most-significant-bit in the private key?

Answer 1

Did you take a look at DjB's paper?

One of his design criterias in order to improve performance is "Use a fixed position for the leading 1 in the secret key".

The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$.

Answer 2

Curve25519 was designed to take advantage of the Montgomery ladder, which combined with Montgomery curves forgoes the $Y$ coordinates, is side-channel resistant, and enables public keys to be any 255-bit string. The ladder looks something like this (pseudocode):

Q[0] = P; 
Q[1] = 2*P;
for(int i = log2(exponent) - 2; i >= 0; --i)
{
  Q[ bit(exponent, i)] = 2*Q[ bit(exponent, i)];
  Q[!bit(exponent, i)] = Q[0] + Q[1];
}
return Q[0];

You might notice the format of the loop: the counter is initialized with the index of the most significant bit of the exponent (i.e., the private key), and goes down to 0.

In practice, the first step of the ladder will be to find the most significant bit of the exponent. This is not hard, of course, but doing so may leak, through timing, information about the most significant bits of the exponent: exponents with bit 254 set to 0 will run faster than with that bit set to 1. This can lead to real problems.

Curve25519 completely avoids this problem by always setting the most significant bit to 1. This way, the loop always has the same amount of iterations, and no timing information can accidentally be leaked by the variable iteration count.