如何计算椭圆曲线上的标量乘法？

#1 楼

$ \ def \ dbl {\ mathrm {dbl}} $好的，让我们在mikeazo和雨披的答案之间做一个缺失的步骤。

我假设您已经阅读了mikeazo的答案，知道如何加和加倍。

现在，我们如何获得一个点的标量倍数？

一个简单的算法就是“双重加法”，它就是这样做的。 br />
在一个简单的示例中，我们有$ 5 = 4 + 1 = 2·2 + 1 $，因此$ 5·P =（2·2 + 1）·P = 2·2·P + P $。因此我们计算$ P→\ dbl（P）= 2·P→\ dbl（\ dbl（P））= 4·P→4·P + P = 5·P $。

您以$ 200 $为例，我们有$ 200 = 128 + 64 + 8 = 2 ^ 7 + 2 ^ 6 + 2 ^ 3 $，因此$ 200·P = 2 ^ 7·P + 2 ^ 6·P + 2 ^ 3 ·P $，可以计算为$ \ dbl（\ dbl（\ dbl（\ dbl（\ dbl（\ dbl（\ dbl（P））））））））+ \ dbl（\ dbl（\ dbl（\ dbl（\ dbl（\ dbl（P）））））+ \ dbl（\ dbl（\ dbl（P）））$。 （当然，您只计算一次公共子项。）或者，我们可以使用分布定律这样写：$ 200·P = 2·2·（2·2 ·2·（2·P + P）+ P）$。

（请注意，这里我们使用标量因子的二进制形式来决定何时添加和何时不添加。）

当$ d $具有二进制形式$ d_kd_ {k-1} \ dots d_1d_0 $（假设d_k = 1）时，这里有两种通用形式的$ d·P $算法：

从小端开始：

Q := 0
R := P
for i = 0 .. k:
   if(d_i = 1)
      Q = add(Q, R)
   R = double(R)
return Q

从大端开始：

Q := 0
for i = k ... 0:
   Q := double(Q)
   if(d_i = 1)
      Q := add(Q, P)
return Q

请注意，这实际上与用于模（或其他）乘幂运算的算法相同，只是使用平方运算和乘法运算（然后通常称为平方乘运算）。

此外，如果在智能卡上实施，则这种微不足道的实现方式很容易受到功耗分析攻击，因为加倍和加法使用的功率量不尽相同，仅在（通常是机密的）指数中设置了一点时，才执行此操作。有一些措施可以解决这个问题，而且点乘法算法也更有效-任何有关椭圆曲线的书都应提及其中一些。

#2 楼

在图形上，对于两个不同的点（$ P + Q = R $），加法看起来像这样：



为了执行$ P + P = 2P $，您可以绘制与$ P $相切的线。找到它相交的位置，并围绕$ x $轴进行反射。像这样：



从数学上讲，这是通过找到与$ P $相切的线，相交的位置并反射约$ x $来完成的。诀窍是要记住在给定的字段中进行数学运算。

因此，在您的示例中，$ P $处的斜率切线为$ s =（3（16）^ 2 + 9）\ cdot （2 \ cdot 5）^ {-1} \ bmod {23} = 11 $。 $ 2P $的$ x $坐标为$ s ^ 2-2（16）\ bmod {23} = 20 $。

$ y $坐标为$ -5 + s \ cdot（ 16-20）\ bmod {23} = 20 $。

可以在此处找到一个很好的小程序，以查看发生了什么。一旦拥有2P，则添加P以获得3P，依此类推。

#3 楼

您要问的还不清楚。是否做点加法（麦克对此进行了介绍），如何进行标量点乘法（例如，如何计算9G = G + G + G + G + G + G + G + G + G + G）或如何计算离散量对数（例如，给定点G和Q，求k使得kG = Q）。如果您要问后者，我的回答是适用的。

一种简单易懂的方法来计算$ O（\ sqrt {N}）$时间中的离散日志是Big-Step-Little-步。在这种情况下，它的工作方式如下。

我们知道，这条特殊的曲线上有32个点（计算无穷远处的点）。如果我们使用的是逼真的尺寸的曲线（而不是这个玩具示例），则可以通过点计数算法知道这一点。

现在，如果曲线上的点数是平滑的（即，由小因素组成），有相当有效的方法来计算离散日志；我们绝不使用具有平滑组序的椭圆曲线，特别是因为它们在密码学上较弱。因此，我将忽略这些方法，并讨论适用于所有曲线的方法。

因此，我们知道离散对数是介于0到31之间的值。我们选择bigstep $ b \ approx \ sqrt {32} $;我们将选择值6。

因此，我们计算出较大的步长，计算各种整数$ i $的$ 6iG $，直到$ 6i \ ge 31 $：

$ 0G = 0 $

$ 6G =（7,3）$

$ 12G =（18,10）$

$ 18G = （10,16）$

$ 24G =（12，6）$

$ 30G =（20，3）$

然后，我们计算出一些小步骤，即$ Q-iG $ of $ 0 \ le i
$ Q-0G =（4，5）$

$ Q-1G =（12，17）$

$ Q-2G =（8，7）$

$ Q-3G =（7，3）$

$ Q-4G =（13，10）$

$ Q-5G =（19，20）$

然后，我们扫描两个列出要搜索的共同点。在这里我们看到$ 6G $和$ Q-3G $都是点$（7，3）$，因此$ 6G = Q-3G $或$ Q = 9G $

现在，在这个玩具示例中，这实际上比幼稚的方法要完成的工作更多。但是，如果我们扩大组的规模，我们很快就会达到严格限制此方法的地步。

评论

---

$ \ begingroup $
我不明白如何做上面例子中所说的标量乘法，P =（16,5）我知道使用加倍来获得2P值。但是在进行加密时，给定随机值k表示200，如何计算kP =（x，y）。像您的示例一样，您是如何获得全部（7,3）（18,10）（10,16）的……这是我不知道的部分。
$ \ endgroup $
–刘思基（Keith Lau Si Keit）
2012年9月30日上午11:01

---