1. 引言
自1985年Neal Koblitz和Victor Miller分别独立提出椭圆曲线密码体制(ECC, Elliptic Curve Cryptography)，其安全性和有效实现性就得到了广泛的关注。ECC属于公钥密码体制，它可以提供同RSA密码体制相同的功能。然而它的安全性建立在椭圆曲线离散对数问题(ECDLP)的困难性之上[1] ，目前求解ECDLP最好的算法具有全指数时间复杂度，与RSA相比，ECC具有如下优良性质：
1) ECC安全性高。在同样的攻破时间内，ECC需要的密钥比RSA要短得多，如160 bite的ECC和1024 bite的RSA有相同的安全性；
2) ECC实现性强。密钥短、存储空间占用少、宽带要求低、运算处理时间短等特点均有利于ECC实现；
3) ECC具有多重选择性。在相同基域下，ECC可以通过改变椭圆曲线方程的系数得到不同的加密算法，拥有更多的选择性，而对于给定的素数或只能对应唯一的一个RSA算法。
因此，ECC在信息安全中有广泛的应用。目前，和已经研究得比较充分，而对的研究工作还很少开展。随着Weil对和Tate对理论的不断进展及基于此而设计的各种安全协议的广泛应用，人们对小素数扩域的研究产生了浓厚的兴趣。与传统有限域相比，小素数扩域能提供更多、更灵活的密码方案，且针对其的攻击算法相对较少，因此其安全性也比较高。作为的一种特殊类型，其具有类似于的计算速度快的某些特性，但也有自己的特殊性质，这使得其算术运算效率非常高，极适合作为安全密码算法的载体[2] -[5] 。
在ECC中，核心运算就是椭圆曲线的标量乘的运算，它是ECC快速实现的关键，而求逆运算又是标量乘中最耗时的，因此采用数学技巧减少求逆次数，对提高运算效率具有重要意义[6] 。
本文首先介绍了ECC的基础知识，包括椭圆曲线的定义及分类以及其上点的运算法则；其次，采用递推归纳、乘法代替求逆、立方代替乘法的思想推导出了仿射坐标系下上的递推公式；最后基于滑动窗口标量乘对核心标量乘算法进行改进并分析其性能。
2. ECC基础知识
2.1. 椭圆曲线的定义及分类
定义1. 设为有限域，上的Weierstrass方程为
(2.1)
其中，，称是域上的椭圆曲线。
有限域上椭圆曲线的分类[7] ：
(1)
(2.2)
(2)
(2.3)
(3)
(2.4)
其中是的不变量。
2.2. 椭圆曲线上点的运算法则
定义在域上的椭圆曲线的所有点的集合称为，并上一个无穷远点构成一个交换群，群上的运算法则由“弦切律”定义。设，是上的任意两个非零点，且，下面给出仿射坐标下点加公式和倍点公式：
(1) 点加
(2) 倍点
出于安全性考虑，人们通常选择的椭圆曲线来设计椭圆曲线密码系统，故本文我们将对时，的椭圆曲线进行讨论，其点加和倍点可分别简化为：
(2.5)
(2.6)
令表示域乘法，表示域平方，表示域立方，表示域逆，表示点加，表示计算一次域上运算所需的时间，表示逆乘率。与其他运算时间相比，可以忽略不计，可知所需的计算复杂度为，所需的计算复杂度为。
3. GF(3n)上底层域快速算法综述
标量乘的运算分为两个层次来完成，一个是底层运算，主要是执行有限域中各种点加、倍点运算；另一个是上层运算，即椭圆曲线上的点加和倍点运算构成的有限阿贝尔群上的运算。故研究上底层域快速算法应是寻求实现点加、倍点的快速算法。
上有限域运算[8] 是其底层运算的基础，设是定义在中的次不可约多项式，则可表示为
而对可以唯一地表示为
又因为的特征为3，故对有，从而对有
因而元素立方运算比较快，通常比乘法运算或平方运算快至少十倍[8] ，而域逆运算又是最费时的运算，一般而言有
故本文通过引入多个中间变量，多做乘法运算以减少求逆次数，并尽可能将多项式变换成立方项相加减的形式来提高运算速度。
4. GF(3n)上底层域快速算法介绍
4.1. 3P、9P的直接计算公式
为了寻求的递推公式，我们先来推导、的公式，然后观察、分析，进而推导出直接计算的公式。设椭圆曲线，为E上一点，，先利用式(2.6)得到，再利用式(2.5)得到，即
(将分子上的多项式变换成立方项相加减的形式)
综上所述可得，的直接计算公式为
(4.1)
若令
则(4.1)式可化为
(4.2)
其计算复杂度为，相当于不用计算直接得到，而若先得到再将其代入(2.5)式得到的计算复杂度为，相比之下，该算法虽然增加了1次乘法操作和6次立方操作，但却减少了1次求逆运算，不仅在逆乘率较大的情况下极大地减少了运算量，而且为下面推导的一般算法提供了便利。
再设，将代入(2.6)式得到，再将和代入(2.5)式得到的直接计算公式，结果如下(为书写方便，将记为)：
(4.3)
则(4.3)式可化为
(4.4)
其计算复杂度为，与逐次计算的复杂度相比，该算法牺牲了12次立方操作，但却减少了3次求逆运算，而，可知该算法极大地提高了运算效率。
4.2. 3kP的直接计算公式
根据上一节、的计算，以此类推我们可以得到的递推公式。
设，令
则有
(4.5)
下面给出仿射坐标下直接计算的算法：
算法1：
在此递归过程中，先计算当时的，其计算复杂度为，此后步每次需增加，最后还需计算，需要，故总的计算复杂度为：
与此同时，直接计算需要，虽然增加了，，但却减少了，当很大时，直接计算的运算量将会极大地降低。
4.3. 算法性能比较
根据域中运算量的比较，假设，如表1。
通过表1，可以直观地看出：直接计算较逐次计算效率有显著的提升，并且随着值的增大提升幅度也越来越大，特别是当时，提升幅度均可达到以上。
5. 基于滑动窗口标量乘算法改进
5.1. 算法介绍
利用底域直接计算的优势，对传统滑动窗口算法[9] [10] 改进，得到一个新的标量乘法，新算法在赋值阶段比传统算法效率有较大提高。由于新算法预处理栈中存储的都是非零窗口，所以还能抵抗边际信道攻击。
滑动窗口算法分为三个阶段：①标量编码阶段，计算出的形式，为窗口宽度；②预计算
Table 1. Comparison of different methods in the underlying domain
表1. 不同方法在底层域运算量比较
阶段，计算出的值存储在一个表中，供下一阶段查询使用；③赋值阶段，利用预计算表计算出[11] [12] 。
将标量改写成(5.1)式：
(5.1)
那么计算标量乘可改写成(5.2)式：
(5.2)
算法2：
算法3：
5.2. 算法性能分析与结论
算法2是对进行重新编码，展开数字集，且在其展开式中任意个邻接数字中最多只有1个非零数字[10] ，故任意两个非零数字之间至少有个0，其非零数字密度为，算法平均需要次3倍点和次点加。
算法3与传统滑动窗口算法的区别在于赋值阶段，对于固定基点的标量乘法，预计算表不需要频繁更换，故建立预计算表在整个标量乘中所占比例不大[9] ，而赋值阶段对于提高标量乘的计算复杂度就显得格外重要。赋值阶段的复杂性与非零窗口的个数有关，文献[13] 给出非零窗口的密度是，而在展开式中任意个非零数字之间至少有个0，故Step 4最多执行次，每次执行一次和一次点加，故算法3的计算复杂度为
(5.3)
由于滑动窗口可变，因此可以有效地减少非零窗口的长度，从而减少点加运算量；此外，由于在Step 4中采用直接计算的递归算法，在逆乘率较高时有效地减少了算法中3倍点总的计算量。
6. 结束语
作为的一种特殊类型，具有其他有限域不可比拟的特点，它可提供更多更加灵活的加密方案且具备较高的安全性。本文采用递归思想，研究了椭圆曲线在仿射坐标下直接计算算法，对底层域进行改进，当时，相对于逐次计算而言效率提升到了以上；同时采用滑动窗口标量乘的方法对上层域进行改进，既有效减少了非零窗口的长度又减少了算法中3倍点总的运算量。
基金项目
国家自然科学基金NSFC11271040资助。
NOTES
*通讯作者。
参考文献