椭圆曲线算法及方程形式研究

 研究方向：椭圆曲线密码学   指导教师：李宝 教授

摘   要

 椭圆曲线密码体制(ECC)是一种重要的公钥密码体制，其密钥短，计算效率高。与另一种公钥密码体制RSA相比，同等安全性下ECC比RSA的密钥更短，且随着安全性的提高，ECC的密钥长度增长幅度远小于RSA。椭圆曲线密码的快速计算是椭圆曲线密码应用的关键，主要有点的标量乘（点乘）和双线性对的计算，其中双线性对目前被广泛的用于基于身份的协议。本文的研究内容主要围绕这两个方面，并包含了对椭圆曲线方程形式的研究。具体内容如下：

 1.我们总结了目前主要的点乘算法，研究了Montgomery算法，给出了特征3有限域上Weierstrass曲线的Montgomery算法的具体优化公式。该算法在计算速度上不如利用NAF计算点乘的算法高效，但由于Montgomery算法抵抗能量攻击的特性，可用于安全性要求较高的环境。我们还研究了数的双基表示，双基表示可用于加速点乘的计算，我们提出了一种窗口化的双基表示方法，在窗口大小小于6时，该算法生成的双基表示比相同窗口大小的窗口NAF表示计算点乘效率更高。

 2.我们研究了椭圆曲线双线对算法，主要是Tate对的计算。双线性对的计算包含了点乘中的基本运算，如点加和倍点的计算，也与椭圆曲线方程形式有关。因此，我们总结了大部分已知的椭圆曲线方程形式，其上群律公式（包括点加统一公式）和双线性对的公式。我们对Weierstrass形式的椭圆曲线给出了一种Tate对的新的计算方式，将加法和倍乘阶段混合，在一般的参数下提高了效率。我们首次给出了四次椭圆曲线Jacobi quartic曲线上的群律解释和Tate对计算具体公式，其上Tate对的倍乘阶段效率较高，而加法阶段与其他曲线相比效率较低。我们研究了一种新型椭圆曲线Selmer曲线，给出了其上的Tate对计算公式，Selmer曲线的Tate对计算非常高效，大部分情况下均比其他椭圆曲线的Tate对计算效率要高。