Curve25519 base point speed up

Question

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?

Answer 1

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.