0 概述

随着无线通信技术的快速发展，人们对物联网安全的需求与日俱增，而加密技术可在确保用户身份验证和授权、通信数据机密性和完整性等方面发挥重要作用。自1975年RIVEST、SHAMIR和ADLEMAN提出RSA公钥密码体制以来，其得到了广泛的研究和应用，但该系统严重依赖使用1 024 bit和2 048 bit等大密钥位的整数分解难题（Integer Factorization Problem，IFP）^[1]。之后，MILLER^[2]和KOBLITZ^[3]提出的椭圆曲线密码体制（Elliptic Curve Cryptography，ECC）使该情况得到了改善。ECC具有与RSA相同功能的公钥密码体制^[4]，其计算原理是求解椭圆曲线离散对数问题（Ellipse Curve Discrete Logarithm Problem，ECDLP）。相比当前主流的加密系统，ECC以更小的密钥尺寸提供了更高级别的安全性，并且运行速度快，适用于计算资源受限的智能移动终端。

ECC中的标量乘法相比其他运算层是求逆次数最多且最核心的运算，标量乘法的运算速率对实现整个密码体制的性能起到关键作用。标量乘运算又称为点乘运算，即$kP = \underbrace {P + P + \cdots + P}_k$，其中，k是一个整数，P为椭圆曲线上的一个基点。在多数情况下，二元表示、非邻接形式（Non-Adjacent Form，NAF）、滑动窗口法以及双基多基标量乘等^[5-6]方法通过研究标量k来改进标量乘运算，从而找到更有效表示k的方法。ECC中的多标量乘运算在ECDH^[7]等密码协商协议中具有重要作用，可表示为${k_1}{P_1} + {k_2}{P_2} + \cdots + {k_m}{P_m}$，在验证椭圆曲线数字签名时通常需要计算kP+JQ^[8]，其中，P、Q是椭圆曲线上的两个基点，k、J是两个正整数。ECC中的直接算法、Shamir算法^[9]、交错NAF算法^[10]等多标量乘算法都是通过将分解为0和1比特串使其最大限度地出现零列。

文献[11]提出双基数系统（Double-Base Number System，DBNS）。文献[12]改进双基思想，将其扩展为多基数系统（Multi-Base Number System，MBNS），且提出5倍点的计算公式及标量乘法，大幅提高了计算速度。文献[13]主要给出一种${k_1}, {k_2}, \cdots , {k_m}$的带符号二进制表示方法，使其全零列的数量尽可能多，并且在此基础上提出一种新的计算多标量乘的算法，降低了算法时间复杂度。文献[14]提出一种基于互反形式（MOF）的标量乘并行计算方法。文献[15]从计算复杂度的角度研究ECC标准曲线优化问题，提出一种基于w-NAF（其中表示窗口宽度）的标量点乘算法。文献[16]研究基于NAF的ECC标量乘算法优化问题，提出一种将加减标量乘算法与NAF表示相结合的新算法，提高了ECC计算性能。文献[17]将双基数系统用于多点乘运算并提出3种基于双基数系统的多点乘算法。本文在文献[17]算法的基础上，提出一种以2、3、7为基元的多基链整数表示方法和两种多标量乘快速算法。

1 相关概念 1.1 椭圆曲线定义

定义1  有限域上的椭圆曲线方程在域K上定义为^[11]：

${y^2} + {a_1}xy + {a_3}y = {x^3} + {a_2}{x^2} + {a_4}x + {a_6}$

(1)

其中，系数，${a_1}, {a_2}, {a_3}, {a_4}, {a_6} \in K$，Δ ≠0，Δ为椭圆曲线判别式，域K中的每个点(x₁, x₁)都满足式（1）。在素域K=F_p上，式（1）可简化为：

${y^2} = {x^3} + ax + b$

(2)

其中，$a, b \in K, \mathit{\Delta } = 4{a^3} + 27{b^2}$。

在二元域K=F₂上，式（1）可简化为：

${y^2} + xy = {x^3} + a{x^2} + b$

(3)

其中，$a, b \in K, \mathit{\Delta } = b \ne 0$。

标量乘运算在实现过程中会调用点加和倍点运算，而点加和倍点运算又会再调用底层有限域算术运算，即标量乘算法的运算效率受底层域运算的影响。表 1给出了有限域中相关操作的运算量统计，其中，I表示求逆操作，S和M表示平方和乘法操作。

1.2 整数k的双基表示

双基链是椭圆曲线标量乘算法的一种加速方法，其中每个正整数n都可表示为2^a3^b的和或差形式。

定义2  设集合B={2,3}，则整数k可表示为如下形式^[1]：

$k = \mathop \sum \limits_{i = 1}^n {d_i}{2^{{a_i}}}{3^{{b_i}}}$

(4)

该形式为整数k的双基链表示，其中，{a_i}，{b_i}为单调递减序列，d_i∈{-1, 1}。双基链表示高度稀疏，可减少标量展开的汉明权值。由于三元基表示方法引入了高效的三倍公式，因此其大幅减少了标量乘法的运行时间。例如，使用双基链计算$40\;12\;174 = {2^{11}}{3^7} - {2^9}{3^6} - {2^8}{3^5} - {2^7}{3^5} + {2^5}{3^2} + {2^4}{3^1} - {2^1}{3^0}$。

1.3 w-NAF算法

整数可表示为长度为的二进制序列，考虑到NAF一次只能处理两个连续的相邻位。w-NAF对NAF进行了扩充^[18]，采用整数k的w位表示，这样便可使非零元素的取值范围从[-1, 1]扩展到$\left[ { - {2^{w - 1}}, {2^{w - 1}} - 1} \right]$。令w≥2，则正整数k的w位宽度的NAF表达式为：

$k = \mathop \sum \limits_{i = 0}^{l - 1} {k_i}{2^i}$

(5)

其中，k_i是奇数且$\left| {{k_j}} \right| < {2^{w - 1}}$。

算法1   w-NAF算法

输入  窗口宽度w，正整数k

输出  NAFw（k）

1.i←0

2.While k ≥ 1 do

2.1.If k is odd，then ${{\rm{k}}_{\rm{i}}} \leftarrow {\rm{kmod}}{2^{\rm{w}}}, {\rm{k}} \leftarrow {\rm{}}$ k-k_i

2.2.Else ${\rm{k}} \leftarrow 0$

2.3. ${\rm{k}} \leftarrow {\rm{k}}/2, {\rm{i}} \leftarrow {\rm{i}} + 1$

3.Return $\left( {{{\rm{k}}_{{\rm{i}} - 1}}, {{\rm{k}}_{{\rm{i}} - 2}}, \cdots , {{\rm{k}}_0}} \right){\rm{}}$

2 多基整数表示方法和多标量乘算法 2.1 多基整数表示方法

多基数系统作为双基数系统的一个扩展，其汉明重量变小，标量表示链长也随之变短，进而使标量乘运算效率得到明显提高。对于一组小整数集合$B = \left\{ {{b_1}{\rm{}}, {b_2}{\rm{}}, \cdots , {b_i}{\rm{}}} \right\}$，如果用元素和的形式来表示标量k，则任何一个整数k都可以表示为$k = \mathop \sum \limits_{i = 1}^m {s_i}b_1^{{e_{i1}}}b_1^{{e_{i2}}} \cdots b_l^{{e_{il}}}$，其中s_i表示符号位，$\left\{ {{e_{i1}}} \right\}{\rm{}}, {\rm{}}\left\{ {{e_{i2}}} \right\}{\rm{}}, \cdots , {\rm{}}\left\{ {{e_{il}}} \right\} \ge 0$为单调递减序列。由于多基整数表示系统将{2,3,7}作为多基系统的基元，因此本文提出标量k的多基表示方法。

定义3  设集合B={2, 3, 7}，则整数k可以表示成如下形式：

$k = \mathop \sum \limits_{i = 1}^m {s_i}{2^{{b_i}}}{3^{{t_i}}}{7^{{q_i}}}$

(6)

该形式即为整数的多基数表示，其中，{b_i}、{t_i}、{q_i}变化呈递减形式，s_i∈{-1, 1}，m为多基数表示的长度。多基链相较双基链冗余度不仅更高，而且汉明重量也更小。例如，当s_i=1时，整数100总计有402个双基数表示方法，而多基数表示可达8 425个^[19]。b_i、t_i、q_i的数值大小对2、3、7倍点运算的运算次数有直接影响。使用DBNS表示一个160位的大数，需约23项，然而使用MBNS表示则仅需约15项^[20]。由此可看出，使用多基链能有效提高ECC中的标量乘法运行效率，通常采用贪婪算法编码可获得多基链的整数表示。

算法2   贪婪算法

输入  正整数k，二进制、三进制、七进制的最大指数max 2，max 3，max 7 > 0，序列T={0，…，max 2；0，…，max 3；0，…，max 7}

输出  序列$\left( {{s_i}, {b_i}, {t_i}, {q_i}} \right)$ > 0，其中s_i是符号位且s_i∈{-1, 1}

1.s←1

2.While k > 0 do

2.1.For（b=0 to max 2，t=0 to max 3，q=0 to max 7）

z=T[b，t，q]，找出离k最近的z

2.2.Output（s，b，t，q）

2.3.If k < z，then s←-s

2.4.k←|k-z|

3.Return $ \left( {{{\rm{s}}_{\rm{i}}},{{\rm{b}}_{\rm{i}}},{{\rm{t}}_{\rm{i}}},{{\rm{q}}_{\rm{i}}}} \right)$

2.2 基于MBNS滑动窗口的多标量乘快速算法

计算多标量乘的方法大致可以分为两种：一种是计算m个标量乘的k_ip_i并将其相加，然而该方法运算效率较低；另一种是同时计算多个标量乘，如Shamir算法、Shamir-NAF算法等。本文通过将多基数表示引入滑动窗口算法中提出一种多标量乘快速算法Sliding MBNS，假定已知椭圆曲线上的基点，t bit的标量k^j被划分为窗口宽度为w的d$\left( {d = \left[ {\frac{t}{w}} \right]} \right)$个窗口，k_l^j_i表示标量的第个窗口中的第i位。

$ {k^j} = K_{{d_j} - 1}^j\left\| \cdots \right\|\left. {k_1^j} \right\|k_0^j $

(7)

$K_l^j = k_l^{{j_{\left( {w - 1} \right)}}}, \cdots , k_l^{{j_1}}, k_l^{{j_0}} $

(8)

算法3   基于MBNS滑动窗口的多标量乘快速算法

输入  t bit的标量，窗口宽度w，基点，1≤j≤j_max

输出  $\mathop \sum \limits_{j = 1}^{{j_{{\rm{max}}}}} {k^j}{P_j}$

1.For l from 1 to j_max do

计算iP_l，${\rm{i}} \in \left\{ {1, 2, \cdots , {2^{{{\rm{b}}_{\rm{i}}}}}{3^{{{\rm{t}}_{\rm{i}}}}}{7^{{{\rm{q}}_{\rm{i}}}}}} \right\}$，其中$0 \le {b_i} < w, 0 \le {{\rm{t}}_{\rm{i}}} < \left\lfloor {{\rm{log}}_3^{}{2^w}} \right\rfloor , 0 \le {q_i} < \left\lfloor {{\rm{log}}_7^{}{2^w}} \right\rfloor , {2^{{{\rm{b}}_{\rm{i}}}}}{3^{{{\rm{t}}_{\rm{i}}}}}{7^{{{\rm{q}}_{\rm{i}}}}} < {2^{\rm{w}}}$

2.Q←∞

3.Q_p←∞

4.P←0

5.s←0

6.For P from d-1 downto 0 do

6.1.For q from 1 to j_max do

lookup ${\rm{MBNS}}\left( {{\rm{K}}_{\rm{P}}^{\rm{q}}} \right) = {\rm{d}}_{\rm{P}}^{{\rm{q}}\left( {{\rm{w}} - 1} \right)} + {\rm{d}}_{\rm{P}}^{{\rm{q}}\left( {{\rm{w}} - 2} \right)} + \cdots + {\rm{d}}_{\rm{P}}^{{\rm{v}}0}$

For r from 0 to w-1 do

lookup ${{\rm{Q}}_{\rm{P}}} = {\rm{d}}_{\rm{P}}^{{\rm{vr}}}{{\rm{p}}_{\rm{q}}}$

Q←Q+Q_P

6.2.P←P+1

6.3.向右移s位，直至找到下一个非零元素

6.4.Q←2^sQ

6.5.If没有非零元素，then跳出

7.Return Q

算法3采用滑动窗口算法可以有效降低时间复杂度。该算法运行在底层元素集合的大数组上的一个子列表上，在运行整个列表时会进行特定操作，动态寻找窗口以减少存储空间，其中实际窗口计算数小于d。点加的运算次数由多基表示的链长和非零位数决定，也会随着窗口宽度w的变化而变化。基于算法3的有限域中窗口宽度及相应点加平均运算次数如表 2所示，其中，E(F_2^m)表示二元域，E(F_P)表示素域，A_wE(F_2^m)和A_wE(F_P)分别表示二元域和素域上不同窗口宽度下的平均点加次数。

算法3中假设基点已知，即定点标量乘运算，因此无需多次更换预计算表，主要计算赋值阶段的运算消耗。本文在j_max=3下对算法性能进行分析研究，先对MBNS表示的每个窗口进行点加操作，然后分别对i(i=3)个标量求和，算法3在赋值阶段所需总的点加运算次数为${\rm{AD}}{{\rm{D}}_w} = \left( {3 + {A_w}} \right)\left( {1 - \frac{1}{{8w}}} \right)\frac{t}{w}$。

2.3 基于交错MBNS滑动窗口的多标量乘快速算法

基于交错MBNS滑动窗口的多标量乘快速算法I-MBNS采用w-NAF表示，只需计算小于2^w-1的奇数项。例如，对于一个数的7-NAF表示，只需计算介于-63~63的奇数项，因此其点加运算次数会减少。首先计算标量k^j的NAF_w形式，其次进行预处理操作，使用MBNS表示串k_lj并计算出iP₁、mP₂、nP₃$\left( {i, m, n \in \left\{ {0, 1, \cdots , {2^{{b_i}}}{3^{{t_i}}}{7^{{q_i}}}} \right\}} \right)$的数值结果，最后根据预处理值，经点加和倍点的反复运算操作得到$\sum {k_l^j{P_j}} $。

算法4   基于交错MBNS滑动窗口的多标量乘快速算法

输入  t bit的标量k^j，窗口宽度w，基点P_j，1≤j≤j_max

输出  $\mathop \sum \limits_{j = 1}^{{j_{{\rm{max}}}}} {k^j}{P_j}$

1.For l from 1 to j_max do

计算iP_l，${\rm{i}} \in \left\{ {1, 2, \cdots , {2^{{{\rm{b}}_{\rm{i}}}}}{3^{{{\rm{t}}_{\rm{i}}}}}{7^{{{\rm{q}}_{\rm{i}}}}}} \right\}$，其中$0 \le {{\rm{b}}_{\rm{i}}} < {\rm{w}}, 0 \le {{\rm{t}}_{\rm{i}}} < \left\lfloor {{\rm{log}}_3^{}{2^{\rm{w}}}} \right\rfloor , 0 \le {{\rm{q}}_{\rm{i}}} < \left\lfloor {{\rm{log}}_7^{}{2^{\rm{w}}}} \right\rfloor , {2^{{{\rm{b}}_{\rm{i}}}}}{3^{{{\rm{t}}_{\rm{i}}}}}{7^{{{\rm{q}}_{\rm{i}}}}} < {2^{\rm{w}}}$

2.计算${\rm{NA}}{{\rm{F}}_{\rm{w}}}\left( {{{\rm{k}}^{\rm{j}}}} \right)$

3.Q←∞

4.Q_P←∞

5.P←0

6.s←0

7.For P from d-1 downto 0 do

7.1.For q from 1 to j_max do

lookup ${\rm{MBNS}}\left( {{\rm{K}}_{\rm{P}}^{\rm{q}}} \right) = {\rm{d}}_{\rm{P}}^{{\rm{q}}\left( {{\rm{w}} - 1} \right)} + {\rm{d}}_{\rm{P}}^{{\rm{q}}\left( {{\rm{w}} - 2} \right)} + \cdots + {\rm{d}}_{\rm{P}}^{{\rm{v}}0}$

For r from 0 to w-1 do

lookup ${{\rm{Q}}_{\rm{P}}} = {\rm{d}}_{\rm{P}}^{{\rm{vr}}}{{\rm{P}}_{\rm{q}}}$

Q←Q +Q_P

7.2.P←P+1

7.3.向右移s位，直至找到下一个非零元素

7.4.Q←2^sQ

7.5.If没有非零元素，then跳出

8.Return Q

基于算法4的有限域中窗口宽度及相应点加平均运算次数如表 3所示。w-NAF算法的平均非零元素的密度近似为$\frac{l}{{w + 1}}$，算法4在赋值阶段所需总的点加运算次数为${\rm{AD}}{{\rm{D}}_w} = \left( {3 + {A_w}} \right)\frac{t}{{w + 1}}$。

3 运算效率分析

本文对Sliding MBNS和I-MBNS算法在j_max下进行实验并用Python实现上述算法。为便于算法性能对比，Shamir算法^[21]和交错NAF算法^[22]的窗口大小分别为2 bit和4 bit~8 bit，Sliding MBNS和I-MBNS算法的窗口大小为10 bit~16 bit。表 4将Shamir算法、交错NAF算法、Sliding MBNS和I-MBNS算法在二元域（E(F2^m)）和素域（E(F_p)）上的底层域平均运算量进行比较，设置$\frac{S}{M} = 0.8$、$\frac{I}{M} = 8$，标量长度分别取160 bit、192 bit和230 bit。

根据实验数据分析可知：在二元域上t=160 bit时，Sliding MBNS算法相比Shamir算法和交错NAF算法运算量分别减少了10.00%和1.69%；I-MBNS算法相比Shamir算法和交错NAF算法运算量分别减少了13.00%和4.97%。在素域上t=160 bit时，Sliding MBNS算法相比Shamir算法运算量减少了11.50%，I-MBNS算法相比Shamir算法和交错NAF算法运算量分别减少了15.02%和3.11%。Shamir、交错NAF、Sliding MBNS和I-MBNS算法在二元域和素域上的运算量对比结果如图 1和图 2所示。由图 1和图 2可以看出，无论二元域还是素数域，Sliding MBNS和I-MBNS算法的运算量明显低于Shamir和交错NAF算法，运算效率更高。本文还分析了算法运算量与窗口宽度的关系。以二元域I-MBNS为例，t=160 bit时不同窗口对应的平均运算量如表 5所示。

由表 5可知，不同窗口宽度对应的平均运算量不同，并且随着窗口宽度的不断增大，平均运算量逐渐减少。为能更清晰地显示两者之间的变化情况，绘制二元域窗口宽度与平均运算量的曲线图，如图 3所示。可以看出，当t=160 bit时，随着I-MBNS算法窗口宽度的不断增大，平均运算量呈下降趋势。

4 结束语

本文结合多基数系统和滑动窗口算法，提出一种以2、3、7为基元的多基整数表示形式及Sliding MBNS和I-MBNS两种多标量乘算法，分析并比较了Sliding MBNS和I-MBNS算法在二元域和素域及不同窗口宽度下的平均运算量。实验结果表明，Sliding MBNS和I-MBNS算法大幅提升了运算效率，且随着窗口宽度的不断增加，平均运算量呈现下降趋势，进而加速多标量乘运算及ECC整体实现。下一步将融合目前主流椭圆曲线密码体制的硬件实现，将标量乘算法应用于网络信息安全传输中，保证信息传输的高效性和安全性。