一种特征为2的椭圆曲线上标量乘的并行处理方法及装置
技术领域
本发明涉及一种计算特征2上的椭圆曲线标量乘的新方法，该方法采用并行运算的思路，并给出了具体处理方法和运算单元，在椭圆曲线密码学中有重要的应用，属于信息安全技术领域。
背景技术
密码学既是一门艺术，也是一门科学，它有着悠久的历史。随着计算机的出现、信息时代的到来，现代密码学与经典密码学相比出现了很多的变化和长足的进步。现代密码学的加密方式主要分为两类：对称加密和公钥加密。而在现代广泛使用和流行的公钥加密方案中，椭圆曲线加密方案无疑有着举足轻重的地位。
1985年，Koblitz和Miller同时独立地提出了椭圆曲线公钥密码体制(ECC：elliptic curve cryptosystem)。椭圆曲线密码体制的安全性基于椭圆曲线离散对数问题的困难性。迄今为止，对普通椭圆曲线上离散对数问题的攻击算法都是指数时间的。因此，ECC与其他公钥密码体制如RSA相比具有抗攻击能力强、系统密钥短、计算量小、占用存储空间少、带宽要求低等诸多优点，因此它具有广泛的应用前景。在椭圆曲线密码体制中定义的点的运算与普通的四则运算有着很大的区别，通过观察一般方程的点加和倍点公式可以看出，标量乘运算是整个密码系统中最耗时的部分。因此，研究和改进椭圆曲线标量乘快速计算方法和相应的运算单元有着非常重要的理论和现实意义。
有关椭圆曲线密码学方面的著述资料非常丰富，包括国外的经典著作、国内的译著、国内的论著等。很多标准化组织还相继提出了椭圆曲线密码算法的相关标准：NIST在标准FIPS186-4中，推荐了美国政府使用的15条不同安全级别的椭圆曲线，包括5条特征为2的有限域上的椭圆曲线、5条特征为2的有限域上的Koblitz曲线和5条大素域上的椭圆曲线；美国国家标准化组织提出了椭圆曲线签名标准ANSI X9.62和规定各种椭圆曲线密钥协商、传送、加密协议的标准ANSI X9.63；电气和电子工程师协会给出了椭圆曲线密码学标准IEEE P1363；中国国家密码管理局也已发布了SM2椭圆曲线公钥密码算法标准和SM9标识密码算法标准等等。2017年，我国自主研发的SM2椭圆曲线标准的数字签名算法成功入选ISO标准，标志着我国在ECC方面的研究处于世界前列。我国学者在椭圆曲线密码的研究方面做出了很多贡献，主要包括标量乘和双线性对的快速计算、椭圆曲线离散对数的攻击和椭圆曲线密码在智能卡、物联网等环境中的应用。
事实上，加速标量乘的计算有很多种方式，已经有很多国内外学者从不同的角度提出了很多比较成熟的方案，如利用自同态加速标量乘的计算，使用新的坐标形式或曲线形式加速标量乘的计算，通过降低标量的汉明重量加速标量乘的计算，利用优化算法加速标量乘的计算等等。
2015年，Negre和Robert在他们的一篇文章中给出了一种新思路，他们通过分裂标量，利用并行算法来给标量乘计算进行加速。这是一个新颖而有效的思路，还能够抵抗简单能量分析攻击，而且根据实验结果，算法的运算速度的确有了很大的提高。由于在计算标量乘的过程中，我们常常会遇到域逆运算，这是一个相对很耗时的运算，因此一般选择使用射影坐标代替仿射坐标以回避域逆运算，这样可以有效地提高标量乘的计算速度。遗憾的是，在Negre和Robert的并行算法中，它们模仿Montgomery倍点算法设计的半点算法只能使用仿射坐标，使得算法中的半点计算部分的效率不够高。
发明内容
针对Negre和Robert提出的并行算法中半点算法无法使用射影坐标的问题，本发明的目的在于提供一种特征为2的椭圆曲线上标量乘的并行处理方法及装置。
本发明的技术方案为：
一种特征为2的椭圆曲线上标量乘的并行处理方法，其步骤包括：
1)将密码学所使用的椭圆曲线参数以及一标量k输入预处理模块；
2)预处理模块根据所在的计算平台运行倍点-加运算和半点-加运算的实际运行速度，选取一放大倍数t，然后对标量k放大t倍并传递给分裂模块；
3)分裂模块将放大后的标量k进行分裂，将得到的以2为基底的展开部分发送给倍点-加模块、将得到的以1/2为基底的展开部分发送给半点-加模块，进行并行计算；
4)倍点-加模块将仿射坐标转换为标准射影坐标进行计算对以2为基底的展开部分采用Montgomery倍点-加算法进行计算，并将计算结果发送给合并加模块，同时半点-加模块使用混合坐标形式对以1/2为基底的展开部分放入规则编码的半点-加算法中进行计算，并将计算结果发送给合并加模块；所述混合坐标形式是指计算半点的寄存器使用λ仿射坐标计算，计算点加的寄存器使用λ射影坐标计算，点加时使用混合点加；
5)合并加模块将输入的两部分计算结果转换成相同的坐标形式后进行相加并转换为设定的坐标形式输出，完成密码学中特征为2的椭圆曲线上标量乘。
输入的椭圆曲线参数包括特征为2的椭圆曲线E、椭圆曲线E的基点P和基点P的阶r。
所述预处理模块对标量k放大得到k’，使得
所述倍点-加模块对输入的基点P以及k1，使用Montgomery倍点-加算法计算P1＝k1P；其中k1的二进制展开形式为k1＝(kn-11,kn-21,…,k01)2，kn-11＝1，具体方法为：11)计算Q0←P，Q1←2P；12)对于i＝n-2到0，如果ki1＝0，则计算Q1←Q0+Q1，Q0←2Q0；否则计算Q0←Q1+Q0，Q1←2Q1；13)输出计算结果Q0即为P1。
所述半点-加模块对输入基点P以及k2使用规则标量编码的半点-加算法计算P2＝2-tk2P；其中k2的二进制展开形式为k2＝(kn-12,kn-22,…,k02)2，kn-12＝1，具体方法为：21)计算R1←P/2，R0←P/2；22)对于i＝n-1到1，计算
所述合并加模块将并行计算的所述倍点-加模块计算结果P1和所述半点-加模块计算结果P2进行一次点加操作，得到结果Q＝P1+P2为椭圆曲线E的基点P与标量k相乘结果Q＝kP。
一种特征为2的椭圆曲线上标量乘的并行处理装置，其特征在于，包括
预处理模块，用于接收输入的密码学所使用的椭圆曲线参数以及一标量k，并根据所在的计算平台运行倍点-加运算和半点-加运算的实际运行速度，选取一放大倍数t，然后对标量k放大t倍并传递给分裂模块；
分裂模块，用于将放大后的标量k进行分裂，将得到的以2为基底的展开部分发送给倍点-加模块、将得到的以1/2为基底的展开部分发送给半点-加模块，进行并行计算；
倍点-加模块，用于将仿射坐标转换为标准射影坐标进行计算，对以2为基底的展开部分采用Montgomery倍点-加算法进行计算，并将计算结果发送给合并加模块，同时半点-加模块使用混合坐标形式，对以1/2为基底的展开部分放入规则编码的半点-加算法中进行计算，并将计算结果发送给合并加模块；所述混合坐标形式是指计算半点的寄存器使用λ仿射坐标计算，计算点加的寄存器使用λ射影坐标计算，点加时使用混合点加；
合并加模块，用于将输入的两部分计算结果转换成相同的坐标形式后进行相加并转换为设定的坐标形式输出，完成密码学中特征为2的椭圆曲线上标量乘。
本发明还涉及一种加密或签名方法，其特征在于，基于上述方法对数据进行加密或者签名时所涉及的标量乘进行计算，然后输出该数据的加密或签名结果。
本发明提出了一种新的半点算法，该算法具有不同于原算法的结构并能够使用射影坐标进行计算，且新算法具有同原算法一样的抵抗简单侧信道攻击的能力。本发明同样使用并行算法结构，主要提出新的半点算法，以改进原算法中Montgomery“半点-加”算法部分不能使用射影坐标的问题。新算法不再使用类似于Montgomery梯子算法的结构，但为了保证新的算法同样能够抵抗简单能量分析攻击和时钟攻击，本发明使用了规则编码标量的技术，并设计了新的半点算法。
与Montgomery“半点-加”算法结构不同，由于本发明使用了规则编码标量的技术，在本发明的算法中，标量都表示为非零有符号的表示形式。-1的引入和0的消失，使得每一轮的计算都包括一次倍点和一次点加，且这些计算都是有意义的。因此它能够保证算法的过程是规则的，每一轮都会根据一样的模式进行倍点和点加的流程，这就保证了它抵抗简单能量分析攻击和时钟攻击的能力。另外，由于算法结构不同，新的算法中没有条件分支，它在两个寄存器中分别进行半点和点加运算，使得新算法在计算点加时可以通过使用混合点加的方式利用λ射影坐标进行计算；而原算法由于存在条件分支，因此存在寄存器中可能要进行点加也要进行半点的操作，这样如果勉强使用射影坐标就会带来额外的频繁进行坐标转换的计算量，因此只能使用仿射坐标。这样，由于具有新的算法结构，新算法能够使用射影坐标，回避了大量的域逆运算，新算法的运算效率得到了一定的提升。本发明方法的并行处理模块结构参见图1(由于本发明计算模块针对的是特征2上的椭圆曲线的标量乘运算，因此下文默认在此前提下进行计算描述，不再赘述)。
图1中，在运算开始前，首先要向运算模块中输入计算所需的参数。其中参数E表示在实际应用中所使用的椭圆曲线，如NIST推荐的曲线B-233。而当所使用的曲线选定后，曲线的方程就确定了，相应的基点P也就确定了，它的阶r也就确定了。在实际使用中，参数k需要被输入计算模块，取值通常在0到r-1之间。比如，在使用加密或者签名方案时，需要计算标量乘kP，这里的k就是需要输入的标量参数。关于实际加解密中，明文处理与标量乘计算的关系可以参见本部分最后面的算法3-5。至于签名，情况类似。将这些基本参数输入并行处理器中预处理模块后，并行处理器准备进入并行计算。
预处理模块：将输入的标量k放大，得到k’，使得
分裂模块：分裂标量k，也就是k＝2-t·k′＝k1+k2·2-t，其中以2为基底的展开部分
倍点-加模块：输入基点P以及分裂后的第一部分标量k1，使用Montgomery倍点-加算法，也就是算法1计算P1＝k1P。
半点-加模块：输入基点P以及分裂后的第二部分标量k2，使用规则标量编码的半点-加算法，也就是算法2计算P2＝2-tk2P。
合并加模块：将并行计算的结果P1和P2进行一次点加操作，得到最终结果Q＝P1+P2。
完成上述五个模块的处理后，就可以输出结果了。根据实际需要，调整坐标形式，输出最终结果标量乘Q＝kP。
算法1Montgomery梯子算法
输入：具有奇数阶r的基点P∈E(F2m)，标量k1＝(kn-11,kn-21,…,k01)2，其中kn-11＝1
计算开始：
输出：根据实际需求，调整坐标形式，输出计算结果Q0。
注：这里算法1是Montgomery梯子算法。算法中P是实际应用的曲线的基点，
算法2非零有符号展开的半点算法
输入：具有奇数阶r的基点P∈E(F2m)，标量k2＝(kn-12,kn-22,…,k02)2，其中kn-12＝1
计算开始：
输出：根据实际需求，调整坐标形式，输出计算结果R0。
注：这里算法2是本发明提出的计算半点-加的算法。算法中P是实际应用的曲线的基点，
如图1所示，本发明中并行处理方法基于输入输出和5个计算模块的装置完成特征2椭圆曲线上的并行标量乘计算，关于输入输出以及这5个基本模块的名称和功能分别是：
1、输入：将实际所用的椭圆曲线的基本参数输入算法，完成算法的初始化，并将相关参数传递到重编码部分。
2、预处理模块：根据实际使用的计算平台和系统等条件，进行实验，比较倍点-加运算和半点-加运算的实际运行速度，并选择适当的放大倍数t，使得运算速度达到最快。将输入系统的标量参数进行预处理，放大t倍，将结果传递给分裂模块。倍数t与使用者在进行计算时具体使用的平台条件和系统条件等有关系，需要根据具体实验进行确定，目的是使得两部分的计算时间尽可能接近，从而实现更快的计算。
3、分裂模块：放大后的标量经过变换，得到新的表示形式，这样，原标量可以被自然地分裂为两部分。将这两部分的相关参数和结果分别传递到Montgomery倍点-加算法和规则编码的半点-加算法部分，准备进行并行计算。
4、倍点-加模块：分裂标量后，将其中的以2为基底的展开部分放入Montgomery倍点-加算法进行计算，计算中的坐标形式应根据算法的要求将仿射坐标转换为射影坐标进行。
5、半点-加模块：将其中以1/2为基底的展开部分放入规则编码的半点-加算法中，计算中应根据算法要求使用混合坐标形式的方法，即计算半点的寄存器使用λ仿射坐标计算，计算点加的寄存器使用λ射影坐标计算，计算半点的寄存器输出结果与计算点加的寄存器输出结果进行点加时能够使用混合点加从而避开域逆运算。保证两部分算法同步进行，且运行时间尽量相同，将最终结果传递到合并部分。
6、合并结果：将并行计算的两部分结果转换成相同的坐标形式，一般可使用标准射影坐标，并将两部分结果相加，这一结果就对应于椭圆曲线上的一个点。将这个点的坐标传递给输出部分。
7、输出：根据实际需要，调整坐标形式，将最终的计算结果输出。
与现有技术相比，本发明的优点：
(1)新的半点-加算法：与Negre和Robert的想法不同，本发明使用的半点-加算法不同于Montgomery梯子算法的结构，它利用了规则标量编码的技术，设计了新的算法结构。该结构同样具有很强的规则性，保证了它能够抵抗简单能量分析攻击。更重要的是，对于半点算法，最为高效的坐标形式就是λ(仿射)坐标，但在这种形式下，由于需要进行大量的域逆操作，点加的计算效率并不是很高。而如果转换为射影坐标再进行计算，根据Montgomery半点-加算法的流程，计算的过程中由于经常需要将寄存器的计算结果进行互相替换，将出现频繁的坐标转换，这就引入了过多的额外的计算量。但在新的半点-加算法中，规则标量编码技术的使用使得算法能够采用新的结构，不必担心像Montgomery半点-加算法那样，一旦使用射影坐标将会出现很多额外的坐标转换的计算量。新的半点-加算法能够使用λ射影坐标，利用混合点加技术，不需要进行坐标转换就可以完成运算，使得算法不需要进行大量的域逆运算，有效地提高了算法的效率。
(2)新的并行处理方法：新的并行算法与原并行算法的大体思路是一致的，都是利用现代处理器的并行计算能力，通过将标量分裂，将一般的标量乘运算分裂乘两个标量乘，并在两个线路中同时进行计算。在提出新的半点-加算法后，我们又设置了新的倍点-加算法，但运行效率均不如Montgomery梯子算法。因此，将最快的倍点-加算法即Montgomery梯子算法和新的半点-加算法结合，得到新的并行算法。使用新的并行处理的方式和模块设计，本发明能够抵抗简单能量分析攻击和时钟攻击，且运行速度较原来有很大的提升，因此本发明可以大大提升处理器的性能。
附图说明
图1为并行处理器模块示意图。
具体实施方式
1、底层运算程序和系统基础参数
在实现标量乘运算之前，需要根据椭圆曲线的参数，实现特征2有限域上的加法、乘法、平方、求逆、开平方、求二次方程的根运算等等。实现上述运算时，需要用到特征2有限域的性质和模运算。本专利中所述的乘法、平方、开平方、求二次方程的根和求逆运算分别是模乘、模平方、模开方、和模二次方程的根和模逆运算。这就需要有限域的不可约多项式选择的足够好，才能够提高计算效率。
在标准FIPS 186-4中，NIST推荐了10条特征为2的有限域上的椭圆曲线：K-163，K-233，K-283，K-409，K-571，B-163，B-233，B-283，B-409，B-571。由于Koblitz曲线具有特殊的性质，因此本专利选择两条伪随机曲线进行举例：B-233和B-409。
下面给出具体的曲线参数。
曲线方程：E:y2+xy＝x3+x2+b。
m为有限域
f(t)是定义在有限域
h是伴随因子。
n为基点P的阶，下面为十进制表示。
P点是基点。
x,y是P点的坐标，下面为十六进制表示。
b是曲线方程参数，下面为十六进制表示。
(1)B-233
B-233：m＝233，f(t)＝t233+t74+1，h＝2
n＝69017 46346 79056 37874 34755 86227 70255 55839 81273 73450 1355537938 36344 85463
b＝0x00000066 647EDE6C 332C7F8C 0923BB58 213B333B 20E9CE42 81FE115F7D8F90AD
x＝0x000000FA C9DFCBAC 8313BB21 39F1BB75 5FEF65BC 391F8B36 F8F8EB7371FD558B
y＝0x00000100 6A08A419 03350678E58528BE BF8A0BEF F867A7CA 36716F7E01F81052
(2)B-409
B-409：m＝409，f(t)＝t409+t87+1，h＝2
n＝661 05596 87902 48598 95191 53080 32771 03982 84046 82964 2812192846 48798 30415 7774827374 80520 81437 23762 17911 09659 79867 28836 6567526771
b＝0x0021A5C2 C8EE9FEB 5C4B9A75 3B7B476B 7FD6422E F1F3DD67 4761FA99D6AC27C8 A9A197B2 72822F6C D57A55AA 4F50AE31 7B13545F
x＝0x015D4860 D088DDB3 496B0C60 64756260 441CDE4A F1771D4D B01FFE5B34E59703 DC255A86 8A118051 5603AEAB 60794E54 BB7996A7
y＝0x0061B1CF AB6BE5F3 2BBFA783 24ED106A 7636B9C5 A7BD198D 0158AA4F5488D08F 38514F1F DF4B4F40 D2181B36 81C364BA 0273C706
以上就是本发明举例使用的两条曲线，实际上，本发明中所使用的方法可以应用到一般特征2的椭圆曲线上，在一些特殊的曲线上甚至可以结合其特殊性质进行进一步加速，本发明中，我们使用一般曲线进行举例。需要注意的是，我们计算域中的运算，如乘法、平方和求逆等时，都需要模f(z)。为了能够快速的计算特征2椭圆曲线上的标量乘，本发明中使用了并行计算的方式，在Montgomery倍点-加算法下，结合Lopez and Dahab的优化方法，倍点部分采用的是标准射影坐标是更优的；而在本发明中新提出的半点-加算法，采用了λ射影坐标，在计算点加的过程中采用λ仿射和λ射影坐标混合点加的计算方式，从而达到了更快的计算速度。这样本发明使用的基础参数和基础的域运算就实现了。
2、点操作运算的实现
在椭圆曲线标量乘的计算中，一般主要涉及点加和倍点的操作，这是两种最基本的点操作形式。对于这两种点操作，最直接的计算方式就是使用常见的仿射坐标用点加和倍点的计算公式进行计算。但是不同于一般的四则运算，每一个基本的点操作所需要的基本域运算量就很大，因而这样朴素的计算方式的效率是非常低的。在实际使用中，人们一般会对标量进行重编码、使用更加高效的计算公式、不同的坐标形式等一些计算技术，本发明中主要包括使用不同的坐标形式和对标量的规则编码技术。下面先介绍本发明中涉及的几种不同的坐标形式。
(1)仿射坐标
仿射坐标是人们最为常见和熟知的一种坐标形式，在这种坐标下，特征2的椭圆曲线的Weierstrass方程如下y2+xy＝x3+ax2+b。其中a,b∈F2m＝F2[t]/f(t)，f(t)∈F2[t]是m次不可约多项式。由此，椭圆曲线上的所有有理点P(x,y)与无穷远点∞以及其上的由弦切法则定义的加法运算构成阿贝尔群。在该坐标下，对于椭圆曲线上的两个不同的点
P1＝(x1,y1),P2＝(x2,y2)，设这两点的和Q＝(x3,y3)＝P1+P2，则相应的点加运算公式为
其中，λ＝(y1+y2)/(x1+x2)。对于二倍点，即P1＝(x1,y1)＝P2＝(x2,y2)时的加法，计算的公式类似，如下：
其中，λ＝x1+y1/x1。
从以上的计算公式可以看出，在基本的有限域运算中，我们无法回避逆运算，而逆运算又非常耗时。因此，一般地，我们采用射影坐标形式来表示椭圆曲线上的点并对它们进行运算，这样能够有效避开逆运算。
(2)标准射影坐标
标准射影坐标是最简单也是很有效的一种射影坐标形式，在此基础上进行发展后，还有很多种不同的射影坐标形式，它们各有优缺点。在标准射影坐标下，特征2上的椭圆曲线的方程就变为Y2Z+XYZ＝X3+a·X2Z+bZ。可以看到，从仿射坐标到标准射影坐标，坐标参数由两个变为三个。一般说来，设K是一个域，仿射点集A(K)＝{(x,y):x,y∈K}与标准射影点集P(K)＝{(X,Y,Z):X,Y,Z∈K,Z≠0}中的点存在一个一一对应的关系，即x＝X/Z，y＝Y/Z。只需要将这个一一对应的变换关系带入到仿射坐标下的点加和倍点的计算公式，我们就很容易得到新的公式。在本发明中，由于计算倍点-加部分，Montgomery梯子算法的效率很高，我们直接使用该算法中的策略，利用标准射影坐标即可。
此外，在该算法中，除了将仿射坐标改为射影坐标外，它还使用了一项技术大大降低了运算量，这就是中间计算过程不计算Y坐标的技术，该技术不影响最后输出结果时恢复仿射坐标(x,y)。由于在Montgomery梯子算法中，每轮运算总能保证两个寄存器Q1-Q0＝P，因而可以推导出计算过程中不需要计算Y坐标的公式。
设特征2上的椭圆曲线上点P1＝(x1,y1)，P2＝(x2,y2)，P＝(x,y)，且满足P2-P1＝P，设P1+P2的横坐标为x3，纵坐标为y3，则可以导出不需要y坐标的计算公式如下：
在最后需要恢复y坐标时，可用下面的公式：
y1＝(x1+x){(x1+x)(x2+x)+x2+y}/x+y
这样，就可以在中间计算的过程中完全不计算y坐标，从而节省大量的运算量。
在实际使用中，我们使用的是标准射影坐标，上面给出的都是仿射坐标下的公式。如果要使用标准射影坐标形式，只需要根据两种坐标形式的一一对应关系进行变换，得到标准射影坐标下的计算公式如下：
恢复y3可用如下公式：
y3＝(x+x1)[(x2+y)Z1Z2+(xZ2+X2)(xZ1+X1)](xZ1Z2)-1+y
这样，通过使用标准射影坐标和中间结果不计算y坐标的技术，就可以快速计算倍点-加部分。
(3)λ坐标及射影形式
λ坐标系统是在研究二进制椭圆曲线上的半点运算时提出的。若给定点P＝(x,y)∈E(F2m)，且x≠0，则点P的λ坐标被定义为(x,λ)，这里λ＝x+y/x。因此，我们能够很容易推导出仿射形式下λ坐标的点加和二倍点公式。令P＝(xP,λP),Q＝(xQ,λQ)是椭圆曲线E(F2m)上的两个点，且P≠±Q，则这两点的和P+Q＝(xP+Q,λP+Q)可以由以下公式计算出来
类似地，倍点公式如下：
以上是在仿射形式下的λ坐标及其点加、二倍点公式。下面讨论射影情形。在λ坐标中，与仿射点(x,y)对应的射影点可表示为(X,L,Z)，其中x＝X/Z,λ＝L/Z,λ＝x+y/x，点(X,L,Z)对应的负点为(X,L+Z,Z)。令P(XP,LP,ZP),Q＝(XQ,LQ,ZQ)是椭圆曲线上的两个用λ射影坐标表示的两个点，与仿射情形相似，加法运算P+Q＝(XP+Q,LP+Q,ZP+Q)可由公式表示如下
至于2P＝(X2P,L2P,Z2P)，其计算公式如下
为了减少计算量，在实际应用中可以使用2Q+P＝(X2Q+P,L2Q+P,Z2Q+P)的计算公式：
3、对标量进行处理
(1)分裂标量
从计算标量乘的算法的角度来看，半点操作给标量k的表示增加了新的方式，k可以以
受到半点处理方式的启发，如果我们选择一个合适的小于l的数，那么标量k就可以很自然地被分成两部分。这样，通过利用现在处理器多核并行运算的特点，我们能够并行利用“倍点-加”和“半点-加”算法，使得标量乘能够更加快速地被计算出来。具体说来，如果r的二进制长度是l，并选择一个合适的t，则标量k就可以分成两部分，每部分的长度为t和l-t，其中一个部分使用“倍点-加”算法，另一个部分使用“半点-加”算法。而t可根据两种算法的实际运行速度进行选择，以使得整体运算速度达到最大。最后将两部分结果相加就得到最终的计算结果。这一过程可以用表示如下，设k′＝2t·k modr，且假设我们已经得到二进制展开
k＝k′·2-t modr＝(k′t-1·2-1+…+k′0·2-t)+(k′l-1·2l-t-1+…+k′t)modr。于是，标量乘k·P就能够被直接分为两部分：
k·P＝(k′t-1·2-1+…+k′0·2-t)·P+(k′l-1·2l-t-1+…+k′t)·P
从这个公式可以看出，它的第一部分可以由“半点-加”操作算出，而第二部分可以由“倍点-加”操作算出，于是就提供了并行计算的可能。
(2)对标量进行规则编码
一般说来，椭圆曲线上的点加和倍点运算与一般的域运算很不相同，它们包含很多不同的域运算，因而相对非常复杂耗时。众所周知，负点运算几乎不耗时，它能够将点的减法变成点加运算。这就能启发我们将普通二进制表示的方法修改成带符号的二进制表示法。也就是说，标量k通常用集合{-1,0,1}中的元素来表示，而不是只用集合{0,1}中的元素表示。
非零有符号展开是一种非常规则的标量编码算法。它将奇整数k用数字{-1,1}来表示。在这里，-1一般用1来表示。由于在这种编码序列中，0没有出现，因而在计算标量乘的每轮运算种都需要一个二倍点运算和一个点加运算，这就使得该算法结构能够天然抵抗简单能量分析攻击和时钟攻击。
设(kn-1,kn-2,…,k0)是k的二进制展开，注意到，对任意连续ω比特00…01，这一展开又可以写为
从安全的角度来说，标量的展开中每一个比特都应该是非零的。因而当k是偶数时，我们应该对它进行特殊处理。这时，标量k的最后一个比特k0＝0，将它从0改为1，计算k·P，最后再减去P或
在本发明中，我们将规则编码标量的方法融入算法中，设计了算法2，来计算半点-加模块的运算，它体现在For循环的t赋值部分。在算法2中，For循环部分t的取值与k的二进制表示的每一位数字有关，为1或-1，这个步骤其实就是用上述公式完成了规则编码标量的过程。这样将标量改写后，在后边进行点加运算时，就不存在零还是非零的区别，从而使得本发明能够抵抗简单能量分析攻击和时钟攻击。在实际应用中，如算法2展现的那样，规则编码的过程与计算的过程是同时进行的，不会先将标量进行规则编码，再用这个结果进行计算。因此，使用时，直接将参数输入算法2即可。
在了解了非零有符号展开形式后，我们就能够将通常使用的一般二进制展开方法改进为非零有符号展开形式，这样就能更加有效地计算标量乘。
4、计算标量乘
由于NIST推荐的曲线得到广泛的应用，本发明将主要关注NIST推荐的伪随机曲线，它的方程均为y2+xy＝x3+x2+b，其中b是F2(t)中的元素。为了更容易进行算法间的比较，我们具体选择NIST-B233和NIST-B409这两条曲线，它们的方程分别为f(t)＝t233+t74+1和f(t)＝t409+t87+1。下表给出了不同算法的运算量比较。
表1原半点算法与新半点算法运算量比较
表1中mH+mA代表需要m个半点运算和m个点加运算，且所用坐标形式为仿射坐标；mHλ+mAλ代表需要m个半点运算和m个点加运算，且所用的坐标形式是λ坐标，并采用混合点加等技巧。
表2原并行算法与新并行算法运算量比较
表2中分裂值t由实际中半点和倍点算法的计算速度决定，分裂值t要保证两种算法计算时间尽量接近；m是标量的比特长度。两个表格中M是域中乘法运算。为了便于比较算法的速度，本发明中，设定域逆运算I＝10M，半点运算在射影坐标下需要2M，由于域中加(减)法和平方运算速度非常快，因此不计入运算量比较，最终得到的计算量数值都表示为M的倍数。
由表1可以看出，算法2由于克服了Montgomery“半点-加”算法的缺陷，因而能够使用射影坐标进行运算，这就使得新的半点算法比Montgomery“半点-加”算法减少了约33％的运算量。这样，将最快速的“倍点-加”算法和“半点-加”算法结合，我们就得到了新的并行算法。如表2，新的算法节省了约12％的计算量。这就是本发明提出的计算特征2上的椭圆曲线标量乘的新的处理方法，该方法采用并行运算的思路。本发明给出了具体处理方法和运算单元，给出了计算量分析和简单实例。可以看出，本发明的并行处理方式和运算模块设计能够有效加速标量乘的运算，同时具备抗简单侧信道攻击的能力。
本发明还提供了一种加密或签名方法，基于上述方法对数据进行加密或者签名时所涉及的标量乘进行计算，然后输出该数据的加密或签名结果，具体实例如算法3～5。
算法3椭圆曲线密钥生成算法
输入：椭圆曲线域参数(E，P，
计算开始：
1.随机选取一个整数d[1,r-1]
2.利用本发明中的处理标量乘的方法，计算公钥Q＝dP
3.返回公钥Q，私钥d
输出：公钥Q，私钥d；然后进行算法4。
算法4椭圆曲线ElGamal加密算法
输入：椭圆曲线域参数(E，P，
计算开始：
1.将明文m嵌入椭圆曲线E上的一个点
2.随机选择一个整数k[1，r-1]
3.利用本发明中的处理标量乘的方法，计算C0＝kP
4.利用本发明中的处理标量乘的方法，计算C1＝M+kQ
5.返回密文(C0,C1)
输出：密文(C0,C1)
对密文进行解密时采用算法5进行处理。
算法5椭圆曲线ElGamal解密算法
输入：椭圆曲线域参数(E，P，
计算开始：
1.利用本发明中的处理标量乘的方法，计算M＝C1-dC0
2.将明文m从M中提取出来
3.返回明文m
输出：明文m。
