【作者】 韩柯；

【导师】 许光午；

【作者基本信息】 山东大学 ， 网络与信息安全（专业学位）， 2025， 硕士

【摘要】 椭圆曲线密码学(Elliptic Curve Cryptography,ECC)的安全性依赖于数学难题椭圆曲线离散对数问题(ECDLP),即已知椭圆曲线上两点P和Q=kP,求解标量k的困难性。这一特性使得攻击者即使拥有强大的计算能力,也难以在多项式时间内破解密钥,从而为现代通信提供了高强度的安全保障。为实现密码技术完全自主可控,国家密码局于2010年发布了《SM2椭圆曲线公钥密码算法标准》。而目前国际上主流的区块链系统(包括比特币、以太坊等)均采用素域上的Koblitz曲线(secp256k1)作为其数字签名算法的核心基础。本文聚焦于这两类曲线的计算优化问题,其分别代表了国内外密码主流应用中的典型实例。本文第一个工作针对SM2曲线提出了一种基于字重组变换与辅助模数技术的快速模约减算法。密码学中一些标准的椭圆曲线所在的基域特征常为广义梅森素数,如NIST曲线P-256和国密SM2。在基本算术运算中,此类具有特殊性质的素数可令模运算十分简洁高效。对于P-256,Brown等利用Solinas方法设计的快速模约减算法可以归结成计算9个字的向量组成的中间变量的代数和。对于SM2也有一些相关研究,目前这方面可能最好的结果由于子钦等提出,需要11个(字的向量组成的)中间变量。本文对此进行优化,采用适当变换进一步降低中间变量的个数,并引入辅助模数。最终得到的结果只需10个中间变量,与NIST P-256的9个中间变量的模约减算法已十分接近。本文方法相较于普通模约减算法减少80%以上的时间开销,对于一些已有的方案,也有17.5%的优势。本文第二个工作针对素域上的Koblitz曲线上的新w-τ窗口法提出了一种高效预计算策略。二元域上的Koblitz曲线自1985年由Neal Koblitz提出以来,就因其独特的数学性质和高效的计算性能而备受关注。其特殊之处在于其具有Frobenius自同态,使得椭圆曲线的点乘运算可以通过Frobenius映射进行优化,从而显著提高计算效率。Solinas引入了一种新型整数表示方法——τ-adic表示(类似特定类型的二进制展开),并结合预计算与存储优化技术进行加速,其运行效率较以往版本效率提升可达50%。而对素域上的Koblitz曲线,并没有找到相应的τ映射。直到最近才由Xu等人找到了一个易于计算的τ映射,进而发展出了素域上Koblitz曲线的新窗口w-τNAF法。利用爱森斯坦整数环的优良代数性质,本文为此w-τNAF法方法设计了一种高效预计算优化方案。该方案将预计算点数缩减至原方法的1/6,显著降低了预计算阶段的复杂度。实验结果表明,改进后的算法在标量乘运算整体性能上实现了超过11%的提升。由于标量乘法为椭圆曲线密码体系的核心运算,其效率优化将直接提升相关密码协议的整体性能表现。更多还原

【Abstract】 Elliptic Curve Cryptography(ECC)security depends on the difficulty of the mathematical problem of elliptic curve discrete logarithm(ECDLP),that is,given two points P and Q=kP on an elliptic curve,the difficulty of solving for the scalar k.This property makes it difficult for attackers to break the key even with powerful computing capabilities,thus providing a high-level security guarantee for modern communication.In order to achieve complete independent control of cryptographic technologies,the State Cryptography Administration released the "SM2 Elliptic Curve Public-Key Cryptography Algorithm Standard" in 2010.Moreover,currently,mainstream blockchain systems in the world(including Bitcoin,Ethereum,etc.)all use the Koblitz curve(secp256k1)as the core basis of their digital signature algorithms.This paper focuses on the computational optimization of these two types of curves,which respectively represent typical examples of national cryptographic standards and international mainstream applications.The improvement of their computational efficiency is of great significance for the practical deployment of cryptography techniques.The first work of this paper proposes a fast modular reduction algorithm based on word-recombination transformation and auxiliary modulus techniques for the SM2 curve.The characteristic of the base field where some standard elliptic curves in cryptography are located is often a generalized Mersenne prime,such as the NIST curve P256 and the national-level SM2.In basic arithmetic operations,primes with such special properties can make modular operations very simple and efficient.For P-256,the fast modular reduction algorithm designed by Brown et al.using the Solinas method can be reduced to calculating the algebraic sum of intermediate variables composed of vectors of 9 words.There are also some related studies on SM2,and the possibly best result so far is proposed by Yu Zi-qin et al.,which requires 11 intermediate variables(composed of vectors of words).This paper optimizes this.By using appropriate transformations,the number of intermediate variables is further reduced,and an auxiliary modulus is introduced.The final result only requires 10 intermediate variables,which is very close to the modular reduction algorithm with 9 intermediate variables of NIST P-256.The method in this paper reduces the time cost by more than 80%compared with the ordinary modular reduction algorithm,and also has a 17.5%advantage over some existing schemes.The second work of this paper proposes an efficient pre-computation strategy for the new w-window method on the Koblitz curve over prime fields.Since the Koblitz curves over binary fields were proposed by Neal Koblitz in 1985,they have attracted much attention due to their unique mathematical properties and high-efficiency computing performance.Their particularity lies in having the Frobenius endomorphism,which enables the point-multiplication operation of elliptic curves to be optimized through the Frobenius map,thereby significantly improving computing eficiency.Solinas introduced a new integer representation method-r-adic representation(similar to a specific type of binary expansion),and combined with pre-computation and storage optimization techniques for acceleration.Its operating efficiency can be increased by up to 50%compared with previous versions.However,for Koblitz curves over prime fields,the corresponding τ-map has not been found until recently.Xu et al.have found an easily-computed τ-map,and then developed a new window w-τNAF method for Koblitz curves over prime fields.Utilizing the excellent algebraic properties of the ring of Eisenstein integers,this paper designs an efficient pre-computation optimization plan for this w-τNAF method.This plan reduces the number of pre-computed points to one-sixth of that of the original method,significantly decreasing the complexity of the pre-computation stage.Experimental results show that the improved algorithm achieves an improvement of over 11%in the overall performance of scalar-multiplication operations.Since scalar multiplication is the core operation of the elliptic-curve cryptosystem,its efficiency optimization will directly improve the overall performance of relevant cryptographic protocols.更多还原