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

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?

-

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\}\}$.

-
That this answer is tautological. I read the paper including those paragraphs and still Why does having a fixed position for the leading 1 improve performance? I didn't notice an algorithm in the code that relies on this bit being set. Does the code produce incorrect results if this bit is wrong? –  CodesInChaos Nov 20 '13 at 13:12
@CodesInChaos I just cited the paper to answer "why it is set to one" as it is listed as a design choice. I did not take a closer look at the arithmetic to find a justification. –  DrLecter Nov 20 '13 at 13:16
@CodesInChaos I guess the answer is sufficient. The sentence "When using Curve25519, the private key always seems to have a fixed bit set at position 2^254." hints at a question about an implementation. The fact that this is hinted at in a paper is sufficient; why the paper specifies it as such is an interesting but different question. –  Maarten Bodewes Nov 20 '13 at 14:22
The algorithm is intended to be used with mostly floating point operations, the fixed bit is probably there to prevent overflows or something... –  Richie Frame Nov 20 '13 at 19:26

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.

-
Thanks for actually explainingthe underlying reasoning, rather than saying "because djb said so". –  orlp Nov 21 '13 at 8:39
Sorry but I still don't get it. 1) The actual code starts with $P$ and $\infty = (x=1,z=0)$ 2) Why does the code not work if it always starts the ladder at bit 254, but that bit happens to be 0? 3) Your Montgomery ladder link is dead –  CodesInChaos Nov 21 '13 at 8:55
@CodesInChaos Link fixed. –  e-sushi Nov 21 '13 at 10:57
@nightcracker "because djb said so" answers the first point of the question of the OP (it's a design issue). I did not claim that my answer also provides an argument for the second part... ;) Thx to Samuel Neves for providing the answer! –  DrLecter Nov 21 '13 at 11:09
It is true that the reference code protects against this by starting with $(P, \infty)$; however, every textbook displays the version I described, so there's a good chance that an independent implementer could make that mistake. Setting that bit to 1 is a preventive measure that costs almost nothing. –  Samuel Neves Nov 21 '13 at 14:55