algorithm - 使用 Strauss-Shamir 方法的 EC 标量乘法

Question

我正在搜索关于椭圆曲线标量乘法的所谓“Strauss-Shamir 方法”的信息。这是一种计算k1 · P + k2 · Q的方法在大约 log₂( k ) 次添加和加倍中，其中 k1, k2 < k .

不幸的是，虽然该算法被左右和居中引用，但实际算法(以及，我敢希望，它的分析)没有在任何地方被引用。有没有人可以向我解释一下，或者至少给我一个关于伪代码/分析的链接？

非常感谢!

Answer 1

要将一个数P乘以一个n位标量k，您可以根据的二进制展开使用加倍和加法强>k。假设 k=9。在二进制中，它是 1001，您可以这样计算 9P:

R=0
R=R*2+P  //the most significant '1' bit
R=R*2    //next bit is 0
R=R*2    //next bit is 0
R=R*2+P  //next bit is 1

Strauss-Shamir 技巧只是通过在链内而不是外部进行加法来计算 aP + bQ。比方说，在二进制中，a=1001 和 b=0011`。然后我们这样做:

R=0
R=R*2+P   //bits from a,b = 1,0
R=R*2     //bits from a,b = 0,0
R=R*2+Q   //bits from a,b = 0,1
R=R*2+P+Q //bits from a,b = 1,1

如果您预先计算 P+Q，那么这不会比一次乘法花费更长的时间。