基于双基系统的椭圆曲线标量乘算法研究

Double-base number system is an inherently sparse integer representation system, which has been attracting extensive attentions from both theoretical investigation and engineering implementation for more than ten years. Elliptic curve cryptosystems have many advantages such as strong resistance against attack, short system key, less calculation, less storage space and so on. Scalar multiplication is the most time-consuming part of elliptic curve cryptosystems. As a powerful mathematical tool, double-base number system will hopefully speed up the efficiency of elliptic curve cryptosystems..This project studies scalar multiplications on elliptic curves based on double-base number system, which includes double-base number system, point operations on elliptic curves in diverse forms and software implementation of scalar multiplication..This project emphasizes on both theoretical analysis and practical applications of double-base number system for scalar multiplication. We will use mathematical tools such as Chinese remainder theorem, combinatorial theory, and universal exponent to investigate the properties of double-base number system and find double-base representations which suit for the scalar multiplication on elliptic curves. We will improve the efficiency of point operations on elliptic curves by division polynomials and theta functions. Besides， we will develop software for scalar multiplications on elliptic curves based on double-base number system， and specially optimize scalar multiplications on elliptic curves recommended by NIST and SM2.

双基系统是一种内在稀疏的整数表示系统，无论是其理论研究，还是工程实现，近十年来一直备受关注。椭圆曲线密码系统具有抗攻击能力强、系统密钥短、计算量小、占用存储空间少等优势。标量乘是椭圆曲线密码体制中最耗时的部分。利用双基系统这一强有力的数学工具进行标量乘算法研究，有望大大提高椭圆曲线密码系统的运算效率。.本项目研究基于双基系统的标量乘算法。主要包括：双基系统算法研究；各种形式椭圆曲线上点操作研究；椭圆曲线标量乘算法的软件实现。.本项目注重于理论研究和实践相结合。我们将利用中国剩余定理、组合论、通用指数等数学工具考察整数的双基表示的性质，寻找适合于椭圆曲线标量乘的双基表示，并计划利用除多项式、theta函数等数学工具提高点操作运算的效率。此外，我们将开发基于双基系统的标量乘算法的软件，并对NIST和SM2推荐使用的椭圆曲线上的标量乘算法进行特别优化。

本项目属公钥密码学研究领域，主要研究椭圆曲线密码学中标量乘算法的加速。我们利用双基系统加速标量乘算法的效率。主要结果包括双基系统方面、椭圆曲线点操作研究、基于双基系统的标量乘算法和抗侧信道分析的标量乘算法研究。关键成果包括利用中国剩余定理、组合论等数学工具双基链的平均Hamming重量的准确下界,利用动态规划算法快速生成最优双基链，利用Frobenius的复共轭提高Koblitz曲线的标量乘效率。我们开发了基于双基系统的标量乘算法的软件，并对NIST和SM2推荐使用的椭圆曲线上的标量乘算法进行特别优化。..此外，我们研究了散列进椭圆曲线和椭圆曲线离散对数分析，给出了一些结果。