基于高效自同态的椭圆曲线标量乘算法研究

An endomorphism is a morphism from a mathematical object to itself, which has been attracting extensive attentions from theoretical investigation and engineering implementation with a long history. Elliptic curve cryptosystems have many advantages such as strong attack resistant, short system key, small amount of calculation, less storage space, low bandwidth requirements and so on. Scalar multiplication is the most time-consuming part of elliptic curve cryptosystems. As a powerful mathematical tool, endomorphism will hopefully speed up the efficiency of elliptic curve cryptosystems..This project studies scalar multiplications on elliptic curves based on efficient endomorphism, which includes constructing efficient endomorphism, scalar multiplications on elliptic curves with efficient endomorphism, and secure software implementation of scalar multiplication..This project emphasizes on both theoretical analysis and the real applications of endomorphism for scalar multiplication. We will use mathematical tools such as Chinese remainder theorem, Frobenius endomorphism，and isogeny to investigate the properties of endomorphism and find efficient endomorphisms which suit for the scalar multiplication on elliptic curves. We will develop secure software for scalar multiplications on elliptic curves， and specially improve scalar multiplications on elliptic curves recommended by NIST, SM2, and TLS.

自同态是从一个数学对象到它自身的态射，无论是其理论研究，还是工程实现，一直备受关注。椭圆曲线密码系统具有抗攻击能力强、系统密钥短、计算量小、占用存储空间少、带宽要求低等优势。标量乘是椭圆曲线密码体制中最耗时的部分。利用自同态这一强有力的数学工具进行标量乘算法研究，有望大大提高椭圆曲线密码系统的运算效率。.本课题研究基于高效自同态的标量乘算法。主要包括：构造高效的自同态，基于高效自同态的标量乘算法研究及其安全软件实现。.本项目注重于理论研究和实践相结合。我们将利用中国剩余定理、Frobenius映射、同源等数学工具考察椭圆曲线自同态的性质，寻找适合于椭圆曲线标量乘的自同态，利用高效的自同态映射，进而提高标量乘的效率。我们将开发标量乘算法的安全软件，并对NIST、SM2、TLS推荐使用的椭圆曲线上的标量乘算法进行特别优化。

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