椭圆曲线密码快速实现方法及其装置

摘要

本发明涉及一种椭圆曲线密码快速实现方法及其装置，该方法包含如下内容：选取Koblitz曲线及其对应的有限域，确定椭圆曲线密码标量k、基点P及设备处理单元个数r；利用Frobenius自同态τ计算标量k的τ‑adic NAF表示，并利用τs将标量k的τ‑adic NAF表示划分为等长r段；通过多项式基表示有限域中的元素及López‑Dahab坐标表示椭圆曲线上的点，对划分后的标量k进行多标量乘kP计算；根据多标量乘kP的计算结果，进行输出。本发明利用多标量乘技巧减少点加运算和自同态τ的计算开销；可以根据设备处理单元个数r来灵活选择并行算法的维数；使得椭圆曲线密码方案具有更高的计算效率，适用于无线通信和资源受限设备的应用需求，有效保证端到端的安全通信。

权利要求

1.一种椭圆曲线密码快速实现方法，其特征在于，包含如下内容：

步骤1、选取Koblitz曲线及其对应的有限域，确定椭圆曲线密码标量k、基点P及设备处理单元个数r；

步骤2、利用Frobenius自同态τ计算标量k的τ-adic NAF表示，并利用τs将标量k的τ-adic NAF表示划分为等长r段；

步骤3、通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，对划分后的标量k进行多标量乘kP计算；

步骤4、对多标量乘kP的计算结果进行输出。

2.根据权利要求1所述的椭圆曲线密码快速实现方法，其特征在于，步骤1包含内容如

2 3 2

下：选取Koblitz曲线Ea:y+xy＝x+ax+1,a∈{0,1}及其对应的有限域 其中，m为素数；

在区间[0,n]随机选取整数k作为标量，其中， 为椭圆曲线Ea的阶，n为大素数且h为辅因子；选择点 作为基点，其中，点P的阶为大素数。

3.根据权利要求2所述的椭圆曲线密码快速实现方法，其特征在于，步骤2包含内容如下：根据Euclid整环Z[τ]＝{a+bτ|a,b∈Z}，及范数N(k)＝k2，N(τ)＝2，标量k的τ-adic NAF表示长度平均为2log2k；设δ＝(τm-1)/(τ-1)，令ρ≡kmodδ，对任意点有kP＝ρP，其中，ρ的约减τ-adic NAF表示长度至多为m+a+3；根据关系式τ2-μτ+2＝0，计算δ＝(τm-1)/(τ-1)；利用环Z[τ]中取整算法Round、环Z[τ]中的除法Division，计算标量k的τ-adic  NAF表示；令 利用τs将τ-adic  NAF表示划分为等长r段，即：其中，若l/r不是整数，需在最高位

补充若干个0。

4.根据权利要求3所述的椭圆曲线密码快速实现方法，其特征在于，步骤3包含内容如下：选择使用多项式基表示有限域中的元素，使用López-Dahab坐标来表示椭圆曲线上的点，标量乘kP表示为：令

φ＝τs,

则kP＝k1P+k2φ(P)+…+krφ(r-1)(P)；预计算i1P+i2φ(P)+…+irφr-1(P)，其中i1,…,in∈{0,±1}，将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特；赋值i＝s-1，通过迭代循环判断i是否大于等于零，如果是，则计算R←τR,R←R+(k1,iP+…+kr,iφr(P)),i←i-1，返回迭代循环，直至i小于零，执行步骤4。

5.根据权利要求3所述的椭圆曲线密码快速实现方法，其特征在于，步骤3中计算标量k的多标量乘kP，还包含内容如下：根据设备处理单元个数r，确定标量乘并行算法的维数，将多标量乘kP计算分为互不相关的r部分，每个设备处理单元并行执行相同标量乘计算。

6.根据权利要求5所述的椭圆曲线密码快速实现方法，其特征在于，步骤3具体内容如下：选择使用多项式基表示有限域中的元素，使用López-Dahab坐标来表示椭圆曲线上的点，标量乘kP表示为：令

φ＝τs,

则kP＝k1P+φ(k2P)+…+φ(r-1)(krP)；将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特；每个设备处理单元并行执行如下计算：赋值 i＝s-1，通过迭代循环判断i是否大于等于零，如果是，则计算Rr←τRr,并判断kr,i是否满足kr,i≠0，若是，则Rr←Rr+kr,iP,i←i-1，返回迭代循环，否则，i←i-1，返回迭代循环；直至i小于零，Rr←φr-1(Rr)，R←R1+R2+…+Rr，执行步骤4。

7.根据权利要求4或6任一项所述的椭圆曲线密码快速实现方法，其特征在于，选择使用多项式基表示有限域中的元素，包含如下内容：将 看作F2上m维向量空间，则存在一组基{α0,α1,…,αm-1}，使得任意 可以唯一表示为α＝a0α0+a1α1+…+am-1αm-1；设f(x)∈F2[x]为m次不可约多项式，β为f(x)在 上的根，则{1,β,β2,…,βm-1}为多项式基，为正规基。

8.一种椭圆曲线密码快速实现装置，其特征在于，包含：

参数选取模块，用于选取椭圆曲线及其对应的有限域，确定椭圆曲线密码标量、基点及设备处理单元个数；

标量编码模块，用于根据Frobenius自同态τ计算椭圆曲线密码标量的τ-adic NAF表示，并利用τs将该表示进行等长划分；

标量乘计算模块，用于将等长划分后的标量进行多标量乘计算；

输出模块，用于对多标量乘的计算结果进行输出。

9.根据权利要求8所述的椭圆曲线密码快速实现装置，其特征在于，所述的标量乘计算模块包含：多标量乘转化单元，用于通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，并根据等长划分后的标量进行多标量乘公式表示；

预计算单元，用于根据多标量乘公式表示，预先计算点加运算和τs运算的开销，选取最优的多标量乘维数；

循环计算单元，用于通过迭代循环计算多标量乘。

10.根据权利要求8所述的椭圆曲线密码快速实现装置，其特征在于，所述的标量乘计算模块包含：多标量乘转化单元，用于通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，并根据等长划分后的标量完成并行执行的多标量乘公式表示，将多标量乘计算分为互不相关的各个设备处理单元；

循环计算单元，用于通过迭代循环并行计算每个设备处理单元的多标量乘。

说明书

椭圆曲线密码快速实现方法及其装置

技术领域

[0001] 本发明属于通信技术领域，特别涉及一种椭圆曲线密码快速实现方法及其装置。

背景技术

[0002] 椭圆曲线密码(Elliptic Curve Cryptosystem,ECC)是公钥密码的一大热门研究领域，其安全性建立在椭圆曲线有理点群离散对数问题求解的困难性上。相对于分别基于大整数分解问题困难性和有限域上离散对数问题困难性的RSA公钥密码和ElGamal类公钥密码方案而言，ECC有其独特的优势——安全强度高，目前针对一般椭圆曲线上的离散对数问题还没找到亚指数时间的算法。椭圆曲线密码体制一经提出就倍受关注，已经逐步取代RSA成为最重要的公钥密码体制。由于相对其他密码算法具有更高的安全强度，椭圆曲线密码在密钥长度、占用存储空间、处理速度和占用带宽等方面有很强的优势。在同等安全强度下椭圆曲线密码的密钥长度要远远小于RSA，160比特ECC安全强度等同于1024比特的RSA。这些优点使得椭圆曲线密码特别适合存储资源受限的设备和无线环境中使用。由于其相对于其他密码算法具有更强的安全性、更高的实现效率，椭圆曲线密码已经广泛应用于移动通信、安全电子商务等领域，并得到了商业机构和国际组织标准化的认可。基于它的很多加密方案、签名方案以及协议都被ANSI、IEEE、ISO和NIST等很多权威的标准化组织接受并已经纳入国际标准中。

[0003] 在椭圆曲线密码算法中，最核心的操作是椭圆曲线标量乘法，同时它也是整个密码方案中最占用资源、最耗时的操作。其计算速度决定着椭圆曲线密码方案实现的效率，加速椭圆曲线标量乘运算一直是椭圆曲线密码学的一个研究热点。目前提高椭圆曲线标量乘算法的效率主要有以下几个研究方向：直接改进点加和倍点运算公式、利用标量的稀疏表示、寻找新的曲线形式使点加和倍点运算更快、利用可有效计算自同态进行加速。随着物联网、无线传感器网络的发展与应用，对标量乘算法的效率提出了更高的要求。

发明内容

[0004] 本发明提供一种椭圆曲线密码快速实现方法及其装置，进一步提高椭圆曲线密码算法的效率，高效地实现端到端的安全通信和数据传输。

[0005] 按照本发明所提供的设计方案，一种椭圆曲线密码快速实现方法，包含如下内容：

[0006] 步骤1、选取Koblitz曲线及其对应的有限域，确定椭圆曲线密码标量k、基点P及设备处理单元个数r；

[0007] 步骤2、利用Frobenius自同态τ计算标量k的τ-adic NAF表示，并利用τs将标量k的τ-adic NAF表示划分为等长r段；

[0008] 步骤3、通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，对划分后的标量k进行多标量乘kP计算；

[0009] 步骤4、根据多标量乘kP的计算结果，进行输出。

[0010] 上述的，步骤1包含内容如下：选取Koblitz曲线Ea:y2+xy＝x3+ax2+1,a∈{0,1}及其对应的有限域 其中，m为素数；在区间[0,n]随机选取整数k作为标量，其中，为椭圆曲线Ea的阶， n为大素数且h为辅因子；选择点
作为基点，其中，点P的阶为大素数。

[0011] 优选的，步骤2包含内容如下：根据Euclid整环Z[τ]＝{a+bτ|a,b∈Z}，及范数N(k)＝k2，N(τ)＝2，标量k的τ-adic NAF表示长度平均为2log2k；设δ＝(τm-1)/(τ-1)，令ρ≡k modδ，对任意点 有kP＝ρP，其中，ρ的约减τ-adic NAF表示长度至多为m+a+3；根据关系式τ2-μτ+2＝0，计算δ＝(τm-1)/(τ-1)；利用环Z[τ]中取整算法Round、环Z[τ]中的除法Division，计算标量k的τ-adic NAF表示；令 利用τs将τ-adic NAF表示划分为等长r段，即： 其中，若l/r不是
整数，需在最高位补充若干个0。

[0012] 优选的，步骤3包含内容如下：选择使用多项式基表示有限域中的元素，使用López-Dahab坐标来表示椭圆曲线上的点，标量乘kP表示为：

[0013] 令

[0014]

[0015] 则kP＝k1P+k2φ(P)+…+krφ(r-1)(P)；预计算i1P+i2φ(P)+…+irφr-1(P)，其中i1,…,in∈{0,±1}，将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特；赋值 i＝s-1，通过迭代循环判断i是否大于等于零，如果是，则计算R←τR,R←R+(k1,iP+…+kr,iφr(P)),i←i-1，返回迭代循环，直至i小于零，执行步骤4。

[0016] 上述的，步骤3中计算标量k的多标量乘kP，还包含内容如下：根据设备处理单元个数r，确定标量乘并行算法的维数，将多标量乘kP计算分为互不相关的r部分，每个设备处理单元并行执行相同标量乘计算。

[0017] 优选的，步骤3具体内容如下：选择使用多项式基表示有限域中的元素，使用López-Dahab坐标来表示椭圆曲线上的点，标量乘kP表示为：

[0018] 令

[0019]

[0020] 则kP＝k1P+φ(k2P)+…+φ(r-1)(krP)；将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特；每个设备处理单元并行执行如下计算：赋值 i＝s-1，通过迭代循环判断i是否大于等于零，如果是，则计算Rr←τRr,并判断kr,i是否满足kr,i≠
0，若是，则Rr←Rr+kr,iP,i←i-1，返回迭代循环，否则，i←i-1，返回迭代循环；直至i小于零，Rr←φr-1(Rr)，R←R1+R2+…+Rr，执行步骤4。

[0021] 优选的，选择使用多项式基表示有限域中的元素，包含如下内容：将 看作F2上m维向量空间，则存在一组基{a0,a1,…,αm-1}，使得任意 可以唯一表示为α＝a0α0+a1α12
+…+am-1αm-1；设f(x)∈F2[x]为m次不可约多项式，β为f(x)在 上的根，则{1,β,β,…,βm-1}为多项式基，{β,β2,…,β2m-1}为正规基。

[0022] 一种椭圆曲线密码快速实现装置，包含：

[0023] 参数选取模块，用于选取椭圆曲线及其对应的有限域，确定椭圆曲线密码标量、基点及设备处理单元个数；

[0024] 标量编码模块，用于根据Frobenius自同态τ计算椭圆曲线密码标量的τ-adic NAF表示，并利用τs将该表示进行等长划分；

[0025] 标量乘计算模块，用于将等长划分后的标量进行多标量乘计算；

[0026] 输出模块，用于根据多标量乘的计算结果，进行输出。

[0027] 上述的装置，所述的标量乘计算模块包含：

[0028] 多标量乘转化单元，用于通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，并根据等长划分后的标量进行多标量乘公式表示；

[0029] 预计算单元，用于根据多标量乘公式表示，预先计算点加运算和τs运算的开销，选取最优的多标量乘维数；

[0030] 循环计算单元，用于通过迭代循环计算多标量乘。

[0031] 上述的装置，所述的标量乘计算模块包含：

[0032] 多标量乘转化单元，用于通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，并根据等长划分后的标量完成并行执行的多标量乘公式表示，将多标量乘计算分为互不相关的各个设备处理单元；

[0033] 循环计算单元，用于通过迭代循环并行计算每个设备处理单元的多标量乘。

[0034] 本发明的有益效果：

[0035] 本发明通过选择具有特殊自同态结构的Koblitz曲线，利用Frobenius自同态τ替代二倍点运算，并结合了GLV方法的将单标量乘转化为多标量乘的思想，设计快速标量乘算法，利用多标量乘技巧减少点加运算和自同态τ的计算开销；进一步给出并行标量乘算法，可以根据设备处理单元个数r来灵活选择并行算法的维数；使得椭圆曲线密码方案具有更高的计算效率，适用于无线通信和资源受限设备的应用需求。通过本发明可以高效地实现椭圆曲线密码方案，有效保证端到端的安全通信。经过试验验证，相较于标准的τ-and-add方法，本发明中快速标量乘算法的2维实现效率提高16％以上，3维实现效率提高22％以上；相对于τ-and-add算法实现，本发明中并行标量乘算法可以提速将近r倍，其中，r为设备处理单元的个数。
附图说明：

[0036] 图1为本发明的装置示意图；

[0037] 图2为本发明的方法流程图；

[0038] 图3为本发明中标量乘快速实现算法示意图；

[0039] 图4为本发明中标量乘并行实现算法示意图。具体实施方式：

[0040] 下面结合附图和技术方案对本发明作进一步详细的说明，并通过优选的实施例详细说明本发明的实施方式，但本发明的实施方式并不限于此。

[0041] 实施例一，参见图1所示，一种椭圆曲线密码快速实现装置，包含：

[0042] 参数选取模块，用于选取椭圆曲线及其对应的有限域，确定椭圆曲线密码标量、基点及设备处理单元个数；

[0043] 标量编码模块，用于根据Frobenius自同态τ计算椭圆曲线密码标量的τ-adic NAF表示，并利用τs将该表示进行等长划分；

[0044] 标量乘计算模块，用于将等长划分后的标量进行多标量乘计算；

[0045] 输出模块，用于根据多标量乘的计算结果，进行输出。

[0046] 本发明利用Frobenius自同态τ替代二倍点运算，并结合了GLV方法的将单标量乘转化为多标量乘的思想，有效提高标量乘计算效率。

[0047] 实施例二，与实施例一基本相同，不同之处在于：所述的标量乘计算模块包含：

[0048] 多标量乘转化单元，用于通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，并根据等长划分后的标量进行多标量乘公式表示；

[0049] 预计算单元，用于根据多标量乘公式表示，预先计算点加运算和τs运算的开销，选取最优的多标量乘维数；

[0050] 循环计算单元，用于通过迭代循环计算多标量乘。

[0051] 通过多标量乘，减少点加运算和自同态τ的计算开销，大大提高标量乘的计算效率，保证椭圆曲线密码算法效率得到有效提升。

[0052] 实施例三，与实施例一基本相同，不同之处在于：所述的标量乘计算模块包含：

[0053] 多标量乘转化单元，用于通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，并根据等长划分后的标量完成并行执行的多标量乘公式表示，将多标量乘计算分为互不相关的各个设备处理单元；

[0054] 循环计算单元，用于通过迭代循环并行计算每个设备处理单元的多标量乘。

[0055] 根据设备处理单元个数灵活选择并行计算的多标量乘维数，每个处理单元都执行相同的命令，算法计算速度得到有效提升。

[0056] 实施例三，参见图1～2所示，一种椭圆曲线密码快速实现方法，包含如下内容：

[0057] 步骤1、选取Koblitz曲线及其对应的有限域，确定椭圆曲线密码标量k、基点P及设备处理单元个数r；

[0058] 步骤2、利用Frobenius自同态τ计算标量k的τ-adic NAF表示，并利用τs将标量k的τ-adic NAF表示划分为等长r段；

[0059] 步骤3、通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，对划分后的标量k进行多标量乘kP计算；

[0060] 步骤4、根据多标量乘kP的计算结果，进行输出。

[0061] 利用多标量乘技巧减少点加运算和自同态τ的计算开销，使得椭圆曲线密码方案具有更高的计算效率，适用于无线通信和资源受限设备的应用需求，有效保证端到端的安全通信。

[0062] 实施例四，参见图1～4所示，一种椭圆曲线密码快速实现方法，包含如下内容：

[0063] 一)、选取Koblitz曲线及其对应的有限域，确定椭圆曲线密码标量k、基点P及设备处理单元个数r。

[0064] 选取Koblitz曲线Ea:y2+xy＝x3+ax2+1,a∈{0,1}及其对应的有限域 其中，m为素数，(可设定m＝163,233,283,409,571)；在区间[0,n]随机选取整数k作为标量，其中，为椭圆曲线Ea的阶， n为大素数且h为辅因子；选择点作为基点，其中，点P的阶为大素数，其中，大素数为长度大于160比特
的素数。

[0065] 二)、利用Frobenius自同态τ计算标量k的τ-adic NAF表示，并利用τs将标量k的τ-adic NAF表示划分为等长r段。

[0066] 根据Euclid整环Z[τ]＝{a+bτ|a,b∈Z}，及范数N(k)＝k2，N(τ)＝2，标量k的τ-adic NAF表示长度平均为2log2k；设δ＝(τm-1)/(τ-1)，令ρ≡k modδ，对任意点有kP＝ρP，其中，ρ的约减τ-adic NAF表示长度至多为m+a+3；根据关系式τ2-μτ+2＝0，计算δ＝(τm-1)/(τ-1)；利用环Z[τ]中取整算法Round、环Z[τ]中的除法Division，计算标量k的τ-adic NAF表示；令 利用τs将τ-adic NAF表示划分为等长r段，即： 其中，若l/r不是整数，需在
最高位补充若干个0。

[0067] 三)、通过多项式基表示有限域中的元素及López-Dahab坐标表示椭圆曲线上的点，对划分后的标量k进行多标量乘kP计算。

[0068] 选择使用多项式基表示有限域中的元素，使用López-Dahab坐标来表示椭圆曲线上的点，标量乘kP表示为：

[0069] 令

[0070]

[0071] 则kP＝k1P+k2φ(P)+…+krφ(r-1)(P)；预计算i1P+i2φ(P)+…+irφr-1(P)，其中i1,…,in∈{0,±1}，将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特；赋值 i＝s-1，通过迭代循环判断i是否大于等于零，如果是，则计算R←τR,R←R+(k1,iP+…+kr,iφr(P)),i←i-1，返回迭代循环，直至i小于零，根据多标量乘kP的计算结果，进行输出。

[0072] 进一步地，本实施例还提供一种标量乘并行实现方法，根据设备处理单元个数r，确定标量乘并行算法的维数，将多标量乘kP计算分为互不相关的r部分，每个设备处理单元并行执行相同标量乘计算，具体内容如下：选择使用多项式基表示有限域中的元素，使用López-Dahab坐标来表示椭圆曲线上的点，标量乘kP表示为：

[0073] 令

[0074]

[0075] 则kP＝k1P+φ(k2P)+…+φ(r-1)(krP)；将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特；每个设备处理单元并行执行如下计算：赋值 i＝s-1，通过迭代循环判断i是否大于等于零，如果是，则计算Rr←τRr,并判断kr,i是否满足kr,i≠
0，若是，则Rr←Rr+kr,iP,i←i-1，返回迭代循环，否则，i←i-1，返回迭代循环；直至i小于零，Rr←φr-1(Rr)，R←R1+R2+…+Rr，则根据多标量乘kP的计算结果，进行输出。

[0076] 下面结合本发明实施例中的附图3和4，对本发明实施例中的技术方案涉及到的算法进行清楚、完整地描述。为了描述方便，首先对所涉及的一些参数进行说明：

[0077] k表示标量，P表示基点，n表示点P的阶；τ表示椭圆曲线Ea上的Frobenius自同态，φ表示椭圆曲线Ea上的自同态τs； 表示椭圆曲线Ea上的无穷远点；r表示多标量乘的维数。

[0078] 一)图3中标量乘快速算法的流程示意图，具体步骤如下：

[0079] 101、针对λ0+λ1τ在环Z[τ]寻找与其“最近”的整数q0+q1τ，其中λ0和λ1为有理数，q0,q1为整数。取整算法见算法1。

[0080]

[0081]

[0082] 102、环Z[τ]中除法运算，a＝a0+a1τ∈Z[τ],β＝b0+b1τ∈Z[τ]且β≠0，利用算法1计算a除以β的商k＝q0+q1τ∈Z[τ]和余数ρ＝r0+r1τ∈Z[τ]满足a＝kβ+ρ。除法算法见算法2。

[0083]

[0084] 103、计算δ＝(τm-1)/(τ-1)，再利用算法2标量k的τ-adic  NAF表示其中l≤m+a+3。τ-adic NAF表示算法见算法3。

[0085]

[0086] 104、令 则可以利用τs将上述τ-adic NAF表示划分为等长r段(若l/r不是整数，只需在最高位补充若干个0即可)：

[0087]

[0088] 105、选择使用多项式基来表示有限域中的元素，有效实现有限域上的乘法和平方运算； 可以看作F2上m维向量空间，则存在一组基{a0,a1,…,am-1}，使得任意 可以唯一表示为a＝a0a0+a1a1+…+am-1am-1。 在F2上的基表示有多种选择，从有效实现的角度通常考虑多项式基和正规基。设f(x)∈F2[x]为m次不可约多项式，β为f(x)在 上的根，则{1,β,β2,…,βm-1}为多项式基， 为正规基。在正规基表示下， 上的平方运算可以通过循环右移位实现：

[0089] 设 则

[0090]

[0091] 但利用正规基做域上乘法比较慢。在多项式基下，F2m上的平方运算是一个线性操作，比域上乘法要快的多。正规基比较合适硬件实现，多项式基适合软件实现。

[0092] 106、使用López-Dahab坐标来表示椭圆曲线上的点，避免在点基本运算中使用求逆运算；在这种坐标表示下，射影点(X:Y:Z)对应于仿射点(X/Z,Y/Z2)，点加(ADD)的计算开销为13M+4S，混合加法(mADD)的计算开销为8M+5S，二倍点(DBL)和τ映射的计算开销分别为：3M+5S和3S，其中M和S分别为有限域上 的乘法和平方。

[0093] 107、利用 表示方法将标量乘kP表示为

[0094]

[0095] 令 则上式可以写作

[0096] kP＝k1P+k2τs(P)+…+krτ(r-1)s(P)。

[0097] 令φ＝τs，则kP＝k1P+k2φ(P)+…+krφ(r-1)(P)。上述表示将单标量乘转化为多标量乘；

[0098] 108、预计算i1P+i2φ(P)+…+irφr-1(P)，其中i1,…,in∈{0,±1}，利用[0099] 表示将k写作k1||k2||…||kr，其中每个ki的比特长度为s，ki,j表示ki的第j比特。

[0100] 109、赋值 i＝s-1。

[0101] 110、判断i是否大于等于零，如果是，则计算R←τR,

[0102] R←R+(k1,iP+…+kr,iφr(P)),i←i-1，并重复本步骤；否则输出R。

[0103] 利用同时多标量乘的技巧来计算kP，减少了点加运算和自同态τ的计算开销，椭圆曲线快速标量乘见算法4。

[0104]

[0105] 下面针对具体的曲线来评估算法4的效率。考虑NIST推荐的两类曲线：分别定义在和 上的Koblitz曲线K-163和K-233。利用多项式基表示可以有效实现域 上的乘法(M)和平方运算(S)。忽略域上加法运算的开销，设I表示域上的求逆运算。当m＝163时，I≈8M；当m＝233时， I≈10M。另外，计算元素的2s次方的开销大约为连
续计算s次平方开销的1/6。

[0106] 在实现二进制域上椭圆曲线点运算时，本文选择使用López-Dahab坐标，在这种坐标下，射影点(X:Y:Z)对应于仿射点(X/Z,Y/Z2)，可以避免使用求逆运算。此时，点加(ADD)的计算开销为13M+4S，混合加法(mADD)的计算开销为8M+5S，二倍点(DBL)和τ映射的计算开销分别为：3M+5S和3S。

[0107] 由于标量k的τ-adic NAF表示大约为m+a+3，则τ-and-add算法的计算开销为算法2中需要预计算：若r＝2，预计算P±φ(P)需要2个点加运算和τs运算。若r＝3，预计算P±φ(P),P±φ2(P),P±φ(P)±φ2(P)需要6个点加运算和
2个τs运算。若 联合表示的密度为 τs的计算开销大约为 算法2的
计算开销为 (预计算需要2ADD+τs)。随着r的增大，算法2主
循环中点加运算的个数会减少，但预计算的量成指数级增长，对于随机点标量乘来说，r＝3为最优的选择。最终还要将射影坐标转化为仿射坐标，计算开销为1I+2M+S。下表中给出了r不同取值下，算法3的效率的理论评估。针对m＝163的情况，取r＝2时，算法2比原始的τ-and-add算法效率提高16.2％；取r＝3时，算法2比τ-and-add算法效率提高22.8％。针对m＝
233的情况，分别比τ-and-add算法效率提高16.7％和25.1％。

[0108] 表1.算法3效率理论评估

[0109]m a τ-and-add算法 算法2(r＝2) 加速 算法2(r＝3) 加速
163 1 556.1M 465.8M 16.2％ 429.1M 22.8％
233 0 760.6M 633.4M 16.7％ 569.9M 25.1％

[0110] 二)图4为本发明实施例中标量乘并行实现算法的流程示意图，具体流程如下：

[0111] 201、类似101至107的步骤，得到kP＝k1P+k2φ(P)+…+krφ(r-1)(P)。

[0112] 202、将公式kP＝k1P+k2φ(P)+…+krφ(r-1)(P)重写为

[0113] kP＝k1P+k2φ(P)+…+krφ(r-1)(P)

[0114]   ＝k1P+φ(k2P)+…+φ(r-1)(krP)，

[0115] 其中，r可以根据处理器的个数来灵活选择。

[0116] 203、将标量乘kP计算分为互不相关的r部分，不需要任何预计算。并行标量乘算法见算法5。如果设备中有r个不同的处理单元，则算法3比算法1加速将近r倍。

[0117]

[0118] 本发明中选择使用多项式基来表示有限域中的元素，有效实现有限域上的乘法和平方运算；使用López-Dahab坐标来表示椭圆曲线上的点，避免在点基本运算中使用求逆运算；利用上述表示将单标量乘转化为多标量乘，利用同时多标量乘的技巧来计算kP，从而减少了点加运算和自同态τ的计算开销，相较于τ-and-add方法，该算法2维实现效率提高16％以上，3维实现效率提高22％以上。标量乘并行实现算法可以根据设备处理单元个数r来灵活选择并行算法的维数，每个处理单元都执行相同的命令，相对于标准的τ-and-add算法实现，该算法可以提速将近r倍，提高了标量乘的计算效率，从而使椭圆曲线密码算法的效率得到提高。

[0119] 本说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其它实施例的不同之处，各个实施例之间相同或相似部分互相参见即可。对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本发明。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本发明的精神或范围的情况下，在其它实施例中实现。因此，本发明将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。