首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >椭圆曲线点乘的滑动窗法和wNAF法简析

问椭圆曲线点乘的滑动窗法和wNAF法简析
EN

Cryptography用户
提问于 2020-07-21 14:03:33
回答 1查看 1.3K关注 0票数 4

我试图理解椭圆曲线点乘的实现。我可以很容易地理解朴素的双加加算法,但是我很难找到一个很好的窗口方法的解释/例子,或者wNAF方法。

规范引用似乎是这个维基百科页面,其中概述了高级别上的所有各种算法。

有人知道关于点乘的窗口方法/ wNAF方法的任何易懂的解释/例子吗?或者,有人能很容易地解释这些算法是如何工作的吗?

为了给您提供一个示例,说明我是如何被Wikipedia的文章弄糊涂的,窗口的方法列出如下:

代码语言:javascript
复制
Q ← 0
  for i from m to 0 do
      Q ← point_double_repeat(Q, w)
      if di > 0 then
          Q ← point_add(Q, diP) # using pre-computed value of diP
  return Q

但它引用了"point_double_repeat(Q,w)“。方法呼叫。但这种方法是什么呢?这到底是做什么的?

关于"w-ary非邻接形式(wNAF)方法“,算法看起来很简单,但是如果没有一个简单的例子,很难确信我能正确理解它。

我知道这对本论坛上的许多人来说可能是相当初级的,但我还是非常感谢任何帮助。

Update 8月10日:

阅读下面Sam的答案是有意义的,我能够实现wNAF方法,但是我仍然很难理解如何实现window方法。

我就是这么努力去理解的:

让我们从标量2329的一个普通的双添加示例开始。

2329的二进制数是100100011001,所以从右到左:

代码语言:javascript
复制
1   0   0   1   0   0   0   1   1   0   0   1
DBL DBL DBL DBL DBL DBL DBL DBL DBL DBL DBL START
ADD         ADD             ADD ADD         ADD
2048        256             16  8           1

正如你所看到的,有12个双打和5个加法。现在,我将尝试将其转换为一个窗口方法,这样就可以减少添加量。让我们使用4的窗口大小:

代码语言:javascript
复制
1   0   0   1       0   0   0   1       1   0   0   1
DBL DBL DBL DBL     DBL DBL DBL DBL     DBL DBL DBL START
2048   +    256                 16      8     +     1
---------------     ---------------     ---------------
      2304       +        16         +        9     

这意味着只增加了三个,减少了40%,非常好。

现在对于算法本身,按照维基百科中的描述:

一个选择窗口大小w并计算dP的所有d = 0,1,2,...2^w - 1值。该算法现在使用表示d = d_0 + 2^wd_1 + 2^{2w}d_2 + ... + 2^{mw}d_m。

在使用窗口大小为4的标量2329的示例中,这意味着预先计算16点的集合(0 ... 2^4 - 1或0 ... 15)。

对于标量值,该算法随后使用表示(9 \cdot 2^0) + (1 \cdot 2^4) + (9 \cdot 2^8)。简化:(9 + 16 + 2304)。所以在下面的算法中,这意味着d1 = 9, d2 = 16, d3 = 2304和"m“是3。

根据维基百科,这是该算法的窗口方法:

代码语言:javascript
复制
Q ← 0
  for i from m to 0 do
      Q ← point_double_repeat(Q, w)
      if di > 0 then
          Q ← point_add(Q, diP) # using pre-computed value of diP
  return Q

在这种情况下,当添加预先计算的点d_iP时,有三个迭代,其中d_i要么是9P, 16P, or 2304P。但我们的预计算是0,1,2,...2^w-1。按照顺序,在我们的预计算中没有"9P“。只有P,2P,4P,8P,16P,32P,64P....

显然,我误解了算法本身,或者我应该如何计算算法使用的预计算,无论是哪种方式,我都有点不知所措。

EN

回答 1

Cryptography用户

回答已采纳

发布于 2020-07-21 14:53:28

假设为了简单起见,我们有一个4位键k= (k_0,k_1,k_2,k_3),其中每个k_i都有一点。为了计算kP,我们找到了k_0P + k_1(2P)+k_2(4P)+k_3(8P)

但我们可以编写k=(k_{01},k_{23}),将其分为2位窗口。然后我们可以编写kP = (k_0+2k_1)P + (k_2+2k_3)(4P) = k_{01}P + k_{23}(4P),然后一种实际计算的方法是计算k_{23}P,然后加倍才能得到4(k_{23}P)=k_{23}(4P)。然后我们将k_{01}P添加到这里。

扩展该模式,这与双重加和加一样,除了(1)我们在每个添加之间加倍;(2)在添加步骤中,我们不只是添加P或0,而是在\{0,P,2P,3P\}中添加一个值。

对于w的窗口大小,我们将密钥拆分为(k_0,\dots, k_{n/w}),其中每个k_i都有w位。我们从Q=0开始,然后将i=0重复到i=n/w:

  1. Q \leftarrow 2^w Q
  2. Q\leftarrow Q + 2^{k_i}P

在n-bit键的常规双加加中,我们需要n加法和n加法.使用这个加窗的方法,我们仍然需要n加法,但只需要n/w加法,再加上计算2^{k_i}P的每个值所需的任何费用。

如果您只使用常规的双加加计算2^{k_i}P,那么这个窗口化的方法就没有意义了--它将花费更多!但是,如果您预先计算了\{0,P,\dots, (2^w - 1)P\}所有值的表,那么您可以在表中查找值,这个值(取决于您的成本模型)可能要便宜得多。但是这个表的大小在w中是指数的,所以您以牺牲一个指数的预计算量为代价来保存一个w添加因子。

我以前没听说过滑动窗口,但是看起来完全一样,除非你在2^{w-1}P上启动你的预计算表,然后如果前导位k_i是0,你就不用再添加P的倍数了--你只需要加倍Q,直到引导位是1,这就会把所有的窗口都按双倍的次数移动。

维基百科说,“实际上,没有什么理由在这种方法上使用加窗的方法,除了前者可以在固定的时间内实现”--在我看来,这似乎是在说“没有理由用电梯到达建筑物的底层,而不是跳出窗户,除了前者可以在不打断你的腿的情况下完成”。

编辑:对于wNAF,主要思想是如果预先计算\{0,P,\dots, (2^w-1)P\},那么\{-(2^w-1)P,\dots,-P,0,P,\dots,(2^w-1)P\}几乎是免费的,因为您只需翻转y-coordinate的符号(至少以Weierstrass形式)。

如果您注意如何表示一个数字,那么您应该能够做一些与加窗乘法几乎相同的事情,除非您使用P的负倍数,从而使用同样数量的预计算量的加法。

我很确定(但不确定!)您可以用(k_0,0,k_1,0,\dots, 0, k_{n/w})表示一个数字D46,其中每个k_i都在\{-2^{w-1},\dots,2^{w-1} -1 \}中。也就是说,通过使用负值,您可以在每个单词(因此是“非相邻形式”)之间设置一个0。

维基百科上的wNAF算法所做的类似于滑动窗口:与其在每次添加之间翻倍,不如检查剩余值是否为偶数,如果是的话,则在添加之前再加倍。这确保了它只增加了P的奇数倍数,节省了一半的预计算成本。

其中一个重要段落是:

NAF的一个属性是保证每个非零元素{\displaystyle \scriptstyle d_{i}}后面至少有{\displaystyle \scriptstyle w\,-\,1}附加零。这是因为该算法通过每次减去mods函数的输出来清除\scriptstyle d 的较低的D55比特。

编辑:看起来问题是0,1,2,\dots, 2^w-1是模棱两可的符号。预先计算出来的值实际上是0,1,2,3,4,\dots, 2^w-1。也就是说,它们只是增加了1,而不是每次增加一倍。

在您的示例中,这意味着预先计算的值是\{P,2P,3P,4P,5P,6P,7P,8P,9P,10P,11P,12P,13P,14P,15P\} (自w=4)。然后d_i实际上是d_1=9、d2=1和d_3=9 (即不包括2的幂),因此d_iP在所有i的表中。

启动算法时,m=3和Q=0,然后将d_3P=9P添加到Q以获得Q=9P。9P应该在你的桌子上。然后转到循环的下一次迭代,双Q用于w迭代。从w=4开始,这意味着我们

(2^4)Q = (9\cdot 2^4)P

然后是m=2,然后添加d_2P = 1P,得到Q=(9\cdot 2^4 + 1)P。然后,在循环的下一次迭代中,再加倍Q四次,得到:

(2^4)Q = (2^4)(9\cdot 2^4 + 1)P=(9\cdot 2^8 + 1\cdot 2^4)P

最后是m=1,因此我们将d_1P=9P添加到Q中以获取(9\cdot 2^8 + 1\cdot 2^4 + 9)P = 2329P。

票数 6
EN
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://crypto.stackexchange.com/questions/82013

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档