论文标题:椭圆曲线密码体系中标量乘的快速算法研究
Research on Fast Algorithm of Scalar Multiplication in Elliptic Curve Cryptography
论文作者
论文导师 王育民,论文学位 博士,论文专业 密码学
论文单位 西安电子科技大学,点击次数 577,论文页数 107页File Size3131K
2005-04-01论文网 http://www.lw23.com/lunwen_10943692/
Elliptic curve cryptosystem;Scalar Multiplication;NAF;Endomorphism;Window Technic;Braid Group
自从公钥密码体制被提出以来,它就被广泛用于许多实用密码系统中,比如密钥协商、身份认证、数据完整性保护、数字签名、电子选举、电子商务、电子政务等等。特别以CA和证书为支撑的PKI更是成为构建大型安全网络所必须的基础设施。目前在实际中使用最为广泛的公钥算法是RSA。 椭圆曲线密码制(ECC)是1985提出的新公钥体制,由于在保证相同安全强度下其所需的密钥长度较RSA的短,而特别适用于无线系统或者存储受限的设备。在许多安全标准中,如IPsec、WAPI、WPKI等等,都已经将其采用。在不远的将来ECC会成为应用标准中的首选算法。 在ECC的快速实现中,最关键的就是标量乘kP的计算,其中k为一个大整数而P为椭圆曲线上的一个点。因此,标量乘的快速算法研究成为了许多密码学家关心的问题,并取得了相当多的不错的成果。在前人成果的基础上,本文主要做了以下的工作: 1.基于NAF分解,我们提出了一种新的方法,以任意的正整数w而不仅仅是2为基来表示整数k。因为它以w为基又近似NAF,我们称这种方法为w-NNAF方法。在所有以w为基的表示中,该方法的汉明重量最轻。使用k的w-NNAF表示,结合现存的一些方法,我们提出了一种计算kP的方法。 2.基于Solinas提出的RTNAF方法,我们提出了一种三比特结合的方法用以快速计算ECC中的标量乘。使用这种方法,可以以两个额外的存储为代价节省m/18个点加法。在有多余的存储的情况下,可将该方法推广到(w+1)比特结合,使得标量乘的计算复杂性可以进一步降低。最后定量分析了该方法所降低的计算复杂性。 3.提出了一种RTSNAF方法,它使用τ~2为基底而不象RTNAF方法那样使用τ来分解标量k。通过数学分析证明了该分解的存在性和唯一性。同时给出了该分解的长度和汉明密度的精确估计。最后,确定了使用该分解来计算kP的计算量为3m/14个点加法,相对RTNAF的m/3次有所改善。 4.为了加速ECC中标量乘法kP的计算,通过使用特征多项式为φ~2+2=0的自同态φ,Ciet将标量k分解为φ-NAF表示。通过对φ-NAF表示使用窗口技术,我们得到了七的φ-NAF_w分解。它能比Ciet的方法更高效的计算kP。最后,我们精确的估计了该分解的长度和汉明密度。 5.基于整数NAF(非相邻形式)表示,Solinas提出了一对整数(a,b)的JSF(联合稀疏形式)表示。由于JSF可以产生更多的双零位置,因此在计算ECC中的
After it"s first proposition, pulic key cryptosystem was widely used to design cryptographical application, such as key agreement, identity authentication, data integrality, digital signature, electronic election, electronic business, electronic government programme, etc. Especially, sustained by CA and certificate, PKI has played a foundational role in the security of a large-scale dynamic network. At this moment, the most popular pulic key cryptosystem in practice is RSA.Elliptic curve cryptosystem (ECC) is a novel public key cryptosystem brought out in 1985. Compared with RSA and, it has a much smaller key length with the same security level. Thus, it is suitable for wireless system and the device with limited storages. It has been adopted by many security standards, such as IPsec, WAPI, WPKI etc, and is going to be the primary standard for application in the not long future.With regard to the implementation of ECC, the key factor is the computation of scalar multiplication kP, where k is a large number and P is a point on the elliptic curve. Scalar multiplication quickly became the research focus of many cryptology experts and many fairly good results had been obtained. Based on the previous work, the production of this paper is listed as below:1. Based on the non-adjacent form (NAF) expression, here we present a new method to express a large positive integer k with the base of any positive integer w other than 2. We call this method the w-NNAF method as the expression is near to the NAF one and with base w. This expression leads to the minimal Hamming weight of all the base w expressions. Based on the proposed expression and some existing methods, an algorithm is developed to compute kP efficiently.2. Based on the RTNAF representation proposed by Solinas[5], we present a triple-bit grouping method for the efficient computation of the scalar multiplication in elliptic curve cryptosystem. By using this method, about m/18 point additions are avoided at the cost of two storage requirements. In the case that extra storage is available, we can further reduced the computational complexity of scalar multiplication by extending the triple-bit grouping method to the general (w+1)-bit grouping one. The reduction in the computational complexity is analyzed in detail.3. A method called RTSNAF, which expresses scalar k with the base τ~2 rather than τ in the RTNAF method. The existence and uniqueness of this expression is proven by mathematical analysis. An estimation of the length and the density of the proposed expression is also given, respectively. Finally, the computation cost of kP using this expression is determined by 2m/14 times of point additions. It is better than m/3 of the RTNAF representation.4. With the use of the endomorphismmethods, Frobenius map is utilized to expand the integer k and each coefficient of the expansion is represented as a binary string. In this paper, with the application of joint sparse form (JSF) to the coefficients, some variations of Lee et a/"s methods are proposed to achieve a better performance at a lower storage requirement.7. Lee et al proposed two methods to speed up the computation of scalar multiplication of elliptic curve defined over GF(2m") with a medium size of m in the range 10 |
