Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
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
3  
@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
1  
@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. –  owlstead 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.

share|improve this answer
1  
Thanks for actually explainingthe underlying reasoning, rather than saying "because djb said so". –  nightcracker 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
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.