Curve25519基点加速

Question

在关于曲线25519的文件中，DJB将基点定义为P_{base} = (9,y)。选择这种方式的主要原因是，P_{base}具有很大的质数顺序，这给安全性带来了优势。但是还有很多其他的点具有相同的性质。x=9之所以被选中，是因为它是排序如此之大的最小点。

我的问题是:一个小的x值虽然在标量点乘法的速度上有优势吗？

Answer 1

是的，它可以被利用来获得较小的性能优势。

在伪码中，montgomery梯子是已定义，如下所示：

 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)

在乘法x1 x1*(x2*z3-z2*x3)^2中有一行使用D3。

x1是输入的x坐标.可以通过将该值硬编码为9来编写该乘法的优化实现，这将比x1的泛型乘法更快，其中x1可以是字段的任何元素。

然而，我从未见过这样的优化，主要是因为泛型代码对于所有输入都是可用的，而且速度可能在5%左右。您可以尝试对乘法进行一个有条件的决策，使其兼具两个世界的优点(如果输入为"9“，则调用优化的乘法，否则调用泛型乘法)，但将分支放入固定时间代码中，以获得最小加速比可能不值得。(尽管我认为这样做没有安全问题)。

如果事先知道输入点，并且没有x坐标值的先决条件，那么还有更好的方法来进行优化实现。这的速度提高了44%。