ABSTRACT

In this paper we investigate the fast algorithm of scalar multiplication based on Elliptic Curve Cryptography (ECC) over fields of characteristic three, and make improvements both in underlying operations and upper operations respectively. In the underlying operations, we deduce a formula of calculating 3^kP directly under the affine coordinates based upon the idea of recursion, trading inversion for multiplication and trading multiplication for cube, which reduces the inversion to once; in the upper operations, we adopt the sliding window scalar multiplication method, which reduces the length of the non-zero windows and the total computations of 3P effectively.

Keywords:Elliptic Curve Cryptography (ECC), Scalar Multiplication, Recursion, Sliding Window

GF(3ⁿ)椭圆曲线密码体制中标量乘快速算法研究

申少芳，周梦^*

北京航空航天大学数学与系统科学学院，LMIB，北京

收稿日期：2015年11月9日；录用日期：2015年11月25日；发布日期：2015年11月30日

摘 要

本文研究了特征为3的椭圆曲线密码体制中标量乘的快速算法，并针对底层运算和上层运算分别进行改进。在底层运算中，采用递推归纳、乘法代替求逆、立方代替乘法的思想提出在仿射坐标下直接计算3^kP的算法，将求逆运算降至1次；在上层运算中，采用滑动窗口标量乘的方法，既有效减少了非零窗口的长度又减少了算法中3倍点总的运算量。

关键词 :椭圆曲线密码体制，标量乘，递推归纳，滑动窗口

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) 倍点

出于安全性考虑，人们通常选择的椭圆曲线来设计椭圆曲线密码系统，故本文我们将对时，的椭圆曲线进行讨论，其点加和倍点可分别简化为：

(1) 点加

(2.5)

(2) 倍点

(2.6)

令表示域乘法，表示域平方，表示域立方，表示域逆，表示点加，表示计算一次域上运算所需的时间，表示逆乘率。与其他运算时间相比，可以忽略不计，可知所需的计算复杂度为，所需的计算复杂度为。

3. GF(3ⁿ)上底层域快速算法综述

标量乘的运算分为两个层次来完成，一个是底层运算，主要是执行有限域中各种点加、倍点运算；另一个是上层运算，即椭圆曲线上的点加和倍点运算构成的有限阿贝尔群上的运算。故研究上底层域快速算法应是寻求实现点加、倍点的快速算法。

上有限域运算[8] 是其底层运算的基础，设是定义在中的次不可约多项式，则可表示为

而对可以唯一地表示为

又因为的特征为3，故对有，从而对有

因而元素立方运算比较快，通常比乘法运算或平方运算快至少十倍[8] ，而域逆运算又是最费时的运算，一般而言有

故本文通过引入多个中间变量，多做乘法运算以减少求逆次数，并尽可能将多项式变换成立方项相加减的形式来提高运算速度。

4. GF(3ⁿ)上底层域快速算法介绍

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. 3^kP的直接计算公式

根据上一节、的计算，以此类推我们可以得到的递推公式。

设，令

则有

(4.5)

下面给出仿射坐标下直接计算的算法：

算法1：

在此递归过程中，先计算当时的，其计算复杂度为，此后步每次需增加，最后还需计算，需要，故总的计算复杂度为：

与此同时，直接计算需要，虽然增加了，，但却减少了，当很大时，直接计算的运算量将会极大地降低。

4.3. 算法性能比较

根据域中运算量的比较，假设，如表1。

通过表1，可以直观地看出：直接计算较逐次计算效率有显著的提升，并且随着值的增大提升幅度也越来越大，特别是当时，提升幅度均可达到以上。

5. 基于滑动窗口标量乘算法改进

5.1. 算法介绍

利用底域直接计算的优势，对传统滑动窗口算法[9] [10] 改进，得到一个新的标量乘法，新算法在赋值阶段比传统算法效率有较大提高。由于新算法预处理栈中存储的都是非零窗口，所以还能抵抗边际信道攻击。

滑动窗口算法分为三个阶段：①标量编码阶段，计算出的形式，为窗口宽度；②预计算

表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资助。

文章引用

申少芳,周梦. GF(3ⁿ)椭圆曲线密码体制中标量乘快速算法研究
Research on Fast Algorithms for Scalar Multiplication of Elliptic Curve Cryptography over GF (3ⁿ)[J]. 应用数学进展, 2015, 04(04): 390-399. http://dx.doi.org/10.12677/AAM.2015.44049

参考文献 (References)