0
$\begingroup$

In the paper regarding Curve25519 DJB defines the base point to be $P_{base} = (9,y)$. The main reason for choosing it this way is, that $P_{base}$ has a big prime order which gives security advantages. But there are a lot of other points with the same properties. $x=9$ was choosen, because it is the smallest point with such a big order.

My question: Does a small x-value although give an advantage regarding the speed of the scalar point multiplication?

$\endgroup$
  • $\begingroup$ The reason is the 'nothing up my sleeve numbers'. They simply choose it as the first $x$ coordinate. rfc7748#appendix-A.3 The base point for a curve is the point with minimal, positive u value that is in the correct subgroup. The findBasepoint function in the following Sage script returns this value given p and A: Once a few scalar multipication the smalles will be gone. $\endgroup$ – kelalaka Jul 3 at 11:11
  • $\begingroup$ I understand why he chose this value. My question is, wether it has another advantage, too. $\endgroup$ – Titanlord Jul 3 at 11:22
  • $\begingroup$ Pick a random secret $x$ and see that the small $[x]9$ has no much effect on the complexity of the calculations. If they did not choose the first, then the first question will be why this number? $\endgroup$ – kelalaka Jul 3 at 11:25
  • $\begingroup$ AFAIK modulo calculations on bit level are tricky. I think, that bigger numbers need more cpu cycles to compute the modulo value. With a smaller x, you get smaller numbers and therefore you need less cpu cycles. $\endgroup$ – Titanlord Jul 3 at 11:32
  • $\begingroup$ Half of the $x$ candidates have $2^{251}$-bit size, half is less than it, half of it has $2^{250}$-bit size half of it less... $\endgroup$ – kelalaka Jul 3 at 11:36
1
$\begingroup$

Yes it could be exploited to have a small performance advantage.

In pseudocode, the montgomery ladder is defined as:

 x2,z2,x3,z3 = 1,0,x1,1    
 for i in reversed(range(255)):
     bit = 1 & (n >> i)
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)
     x3,z3 = ((x2*x3-z2*z3)^2,x1*(x2*z3-z2*x3)^2)
     x2,z2 = ((x2^2-z2^2)^2,4*x2*z2*(x2^2+A*x2*z2+z2^2))
     x2,x3 = cswap(x2,x3,bit)
     z2,z3 = cswap(z2,z3,bit)    
  return x2*z2^(p-2)

There is a line which uses $x1$ in the multiplication $x1*(x2*z3-z2*x3)^2$.

$x1$ is the x-coordinate of the input. It is possible to write an optimized implementation of that multiplication by hardcoding that value to 9 which will be faster than the generic multiplication by $x1$, where $x1$ could be any element of the field.

However I never seen an optimizations like that, mainly because the generic code is usable for all inputs and the speed-up could be around 5%. You could try to put an conditional decision for that multiplication to have the best of both worlds (if the input is "9" then call the optimized multiplication otherwise the generic one) but putting branches in a constant-time code for a minimum speedup is not probably worth it. (even though I don't see security issue in doing that).

There are also better way to do optimized implementations if you know the input point in advance and don't have preconditions on the value of the x-coordinate. This achieves up to 44% speed up.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I see what you mean and that's a pretty good point. But you are right, it is not used, because the advantage would be to small, for to much effort. But on a much lower level, cpu cycles, can there be a speed up in contrast to a bigger x-value, without changing the code? $\endgroup$ – Titanlord Jul 3 at 13:34
  • 1
    $\begingroup$ @Titanlord: yes, someone could use a nonconstant-time multiplier that would be faster if one of the inputs is small (as in '9'); however that would open up a potential timing-based side channel attack. $\endgroup$ – poncho Jul 4 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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