椭圆曲线NAF标量法

Question

我是椭圆曲线方面的新手，我通过阅读获得了很多知识:)但是我把NAF方法作为标量乘法方法，但不明白在这个例子中是如何得到它的：

Let k = 1234567 and its binary representation contains 21- bits:
100101101011010000111. In this 
11 1′s and 10 0′s can be found resulting in 20 doubling operations (D) and 10 point addition operations (A). The width-4 NAF
representation of 1234567 is
9 0 0 0 0 13 0 0 0 0 13 0 0 0 0 0 0 7. In this, an increased number of 0′
s can be
seen. The computational cost = 18D + 4A, assuming that the values 9P, 13P
and 7P are computed before hand and stored.

Answer 1

利用曲线乘法的双加法，在指数中设置单比特.例如，如果我们在1101000G，我们可以加倍(获取11010000G)，然后有条件地添加G (设置lsbit，获取11010001G)。

NAF扩展了这一点，注意到，通过一点预计算，我们可以一次插入几个位。例如，如果我们在11010000G，并且有预先计算的1101G，我们可以将它们相加，得到11011101G。在这个例子中，我们在指数中设置了3位，用一个加法来做同样的事情，用双加法和加3点加法。

因此，对于4位NAT，我们从预先计算的值0G, 1G, 2G, ..., 15G开始.如果我们重复使用相同的G (例如，G是曲线‘生成器点’)，我们可以做一次，并将它们放在一个表中。或者，我们可以计算有7个加法和7个加法。

然后，为了计算100101101011010000111G，我们从前4位1001开始。我们的预计算表中有1001G，所以我们从这里开始。然后，我们继续加倍，直到到达100100000G为止；此时，目标中有4位( 1101模式)没有用当前值表示--我们在预先计算的表中得到1101G值，并将其添加到给定的100101101G中。我们继续前进(当我们在目标中得到4位没有用当前值表示的值时，从我们预先计算的表中添加值)，直到我们到达终点--在这种情况下，还有一个剩余的111G，所以我们把它加进去，就完成了。

如果您注意到加法和加法的模式(加倍而不以0表示加法)，则该模式是在引号中找到的9 0 0 0 0 13 0 0 0 0 13 0 0 0 0 0 0 7。

对于双加加法，我们最终使用一个预期的n/2加法乘以一个n-bit标量；对于4位n/5加法，我们使用了一个预期的D21加法(加法次数大致相同--4位NAT使用的次数减少了3个)--这并不是一种节省的坏结果。

另一方面，如果攻击者能够在我们执行加法和加法时侦听，他可以获得一些关于我们正在乘的标量的信息--这可能是不好的(因此，在某些情况下，如果没有额外的掩蔽，这个算法可能是不合适的)。

对于用椭圆曲线实现点乘，还有更积极的方法；然而，这将有助于理解这条曲线。