第二十六个知识点：描述NAF标量乘法算法

NAF标量乘法算法是标量乘法算法的一种增强，该算法使用了非邻接形式（Non-Adjacent Form)表达，减少了算法的期望运行时间。下面是具体细节：

让\(k\)是一个正整数，\(P\)是一个在域\(F_q\)上椭圆曲线\(E\)上的点。这个计算乘法操作\(Ｑ = k * P\)就是圆曲线上的标量乘法操作（点乘）。一个最简单计算的方法就是基于双倍-加法的霍纳规则的变体。顾名思义，该方法最突出的两个构建块是点加倍和点添加原语。就像名字那样，算法也十分简单。把\(k\)写成

\[k=k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+ \cdots +k_{1}+k_{0}
\]

，其中\(k \in \{0,1\},i = 0,1,2,…,n-1\)。下面有两种算法来表达。

INPUT: k = (kt−1,…, k1, k0)2, P ∈ E(Fq).

OUTPUT: k ⋅ P.

​ Q←∞.

​ For i from 0 to t−1 do

​ If ki = 1 then Q←Q+P.

​ P←2P.

Return(Q).

INPUT: k = (kt−1,…, k1, k0)2, P ∈ E(Fq).

OUTPUT: k ⋅ P.

​ Q←∞.

​ For i from t−1 down to 0 do

​ Q←2Q.

​ If ki = 1 then Q←Q+P.

Return(Q).

第一个算法计算\(k\)从右到左，第二个算法计算从左到右。在一个二进制表示中，1的数量大概是t/2=m/2。因此期望的运行时间是

\[\frac{m}{2} * A + m * D
\]

。

在1951年，Booth[3]提出了一个新的标量二进制表达被叫做有符号二进制方法。然后Rietweisner[4]证明了每个整数在这种表达下都是独一无二的[5]。尤其，如果\(p=(x,y) \in E(F_q)\)，那么有\(-P=(x,x+y)\)，如果\(F_q\)是二进制域。同时如果\(F_q\) 的阶大于3，就有\(-P = (x,-y)\)。计算减法就会很有效。这让我们想出了另一种有符号整数的表达方式。\(k = \sum^{l-1}_{i=0}k_i * 2^i\)，其中\(k_i \in \{0,+,-\}\)。一个十分有用的有符号整数表达就是不相邻范式(NAF)。NAF的形式就是上面那样，但是规定了 \(k_{l-1} \neq 0\)，同时没有两个相邻的\(k_i\)都是0。NAF的长度是\(l\)。

NAF的性质[1]

• 每个正整数k都有独一无二的NAF表达。记作NAF(k)。
• NAF(k)有所有\(k\)的有符号表达最少的非零数字。
• NAF(k)的长度最多比二进制表达多一个。
• 如果NAF(k)的长度是l,那么有\(\frac{2^l}{3}<k<\frac{2^{l+1}}{3}\)。
• 在所有长度为\(l\)的NAF中，非零系数的概率约为1/3。

NAF(k)能够通过下面的算法有效率的计算。

INPUT: A positive integer k.

OUTPUT: NAF(k).

​ i←0.

​ While k≥1 do

​ If k is odd then: ki ←2−(k mod 4), k←k−ki;

​ Else: ki ←0.

​ k←k/2, i←i+1.

Return(ki−1, ki−2,…, k1, k0).

最后一个算法给出了我们可以用NAF(k)代替k[1]的二进制表示来修改标量乘法从左到右的二进制方法：

INPUT: Positive integer k, P ∈ E(Fq).

OUTPUT: k ⋅ P.

​ Based on previous algorithm compute NAF(k) =∑l−1i=0ki⋅2i.

​ Q←∞.

​ For i from l−1 down to 0 do

​ Q←2Q.

​ If ki = 1 then Q←Q+P.

​ If ki = −1 thenQ←Q−P.

Return(Q).

基于NAF的第三个和第四个属性，我们能计算上述算法的平均时间复杂度。

\[\frac{m}{3} * A + m * D
\]

[1] Hankerson, Darrel, Scott Vanstone, and Alfred J. Menezes. "Guide to elliptic curve cryptography". Springer Science & Business Media, 2004.

[2] Jonathan Taverne, Armando Faz-Hernández, Diego F. Aranha, Francisco Rodríguez-Henríquez, Darrel Hankerson, Julio López. "Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction", Journal of Cryptographic Engineering, Vol. 1, No 3, pp. 187-199, 2011.

[3] A.D.Booth, “A Signed binary multiplication technique”, Journal of Applied Mathematics, Vol. 4. No. 2, pp.236-240, 1951

[4] G.W.Reitwiesner, “Binary Arithmetic”, Advances in computers, Academic Press, Vol. 1, pp.231-308, 1960

[5] Karthikeyan, E. “Survey of elliptic curve scalar multiplication algorithms.” International Journal of Advanced Networking and Applications, Vol. 4, No 2, pp. 1581-1590, 2012